查看“︁快速演算法”︁的源代码

算法优化，最主要的目的是用來減少運算時間，像是加法、乘法的數目，以及所花的運算週期。此外還能降低硬體實現所花費的成本，像是減少緩衝器的數量、重複利用相同的硬體架構。

==概覽 ==
一般來說，快速演算法的設計可以透過將運算展開，並進行歸納、分析，利用运算次数更少的乘法、除法（如乘以二、除以二等左移、右移）來完成運算，達到降低運算時間的目的。

而在設計的過程中，因為乘法的運算時間會遠大於加法，因此通常會以使用多少個乘法來衡量整體的運算時間。此外，因為是從硬體的角度來看，所以對於乘上<math>2^{\pm k}</math>、0，都可以視為不需要任何的運算時間(trivial multiplications)，因為對於乘上<math>2^k</math>，或者除上<math>2^k</math>，分別只要進行左移<math>k</math>位元或右移<math>k</math>位元的運算即可達成。

==簡單矩陣有关的算法优化設計 ==
以下举几个例子，用以说明如何优化算法，使得矩阵演算能够最优化。
'''<big>1.<math>y[1]=ax[1]+2ax[2]=\begin{bmatrix} a & 2a\end{bmatrix}\begin{bmatrix} x[1] \\ x[2] \end{bmatrix}=a(x[1]+2x[2])</math></big>'''

從上面這個式子來看，在左邊的部分需要用到兩個乘法、一個加法，然而經過一些化簡、合併，在右邊的地方就只需要一個乘法(乘2不需要運算時間)、一個加法。

'''<big>2.<math>\begin{bmatrix} y(1) \\ y(2) \end{bmatrix}=\begin{bmatrix} a & a \\ a & a \end{bmatrix}\begin{bmatrix} x(1) \\ x(2) \end{bmatrix}</math></big>'''

<math>y(2)=y(1)=a(x(1)+x(2))</math>，因此從原本需要四個乘法、兩個加法，變成只要一個乘法、一個加法。

'''<big>3.<math>\begin{bmatrix} y(1) \\ y(2) \end{bmatrix}=\begin{bmatrix} a & -a \\ -a & a \end{bmatrix}\begin{bmatrix} x(1) \\ x(2) \end{bmatrix}</math></big>'''

<math>y(2)=-y(1),\ y(1)=a(x(1)-x(2))</math>，因此從原本的四個乘法、兩個加法，變成只需要一個乘法、二個加法。

'''<big>4.<math>\begin{bmatrix} y(1) \\ y(2) \end{bmatrix}=\begin{bmatrix} a & b \\ b & a \end{bmatrix}\begin{bmatrix} x(1) \\ x(2) \end{bmatrix}</math></big>'''

<math>\begin{bmatrix} a & b \\ b & a \end{bmatrix}=\tfrac{1}{2}\begin{bmatrix} a+b & a+b \\ a+b & a+b \end{bmatrix}+\tfrac{1}{2}\begin{bmatrix} a-b & b-a \\ b-a & a-b \end{bmatrix}</math>, 左邊的部分可以參考例子2，右邊則是例子3，因此從原本的四個乘法、兩個加法，變成兩個乘法、四個加法。

'''<big>5.<math>\begin{bmatrix} y(1) \\ y(2) \end{bmatrix}=\begin{bmatrix} a & b \\ c & a \end{bmatrix}\begin{bmatrix} x(1) \\ x(2) \end{bmatrix}</math></big>'''

<math>\begin{bmatrix} a & b \\ c & a \end{bmatrix}\begin{bmatrix} x(1) \\ x(2) \end{bmatrix}=\begin{bmatrix} a & a \\ a & a \end{bmatrix}\begin{bmatrix} x(1) \\ x(2) \end{bmatrix}+\begin{bmatrix} 0 & b-a \\ c-a & 0 \end{bmatrix}\begin{bmatrix} x(1) \\ x(2) \end{bmatrix}</math>

左邊的部分一樣可以參考例子2，所以需要一個乘法、一個加法，右邊的部分則需要兩個乘法，最後要將左右兩式相加，因此還需要兩個加法才能得到<math>\begin{bmatrix} y(1) \\ y(2) \end{bmatrix}</math>，所以一共需要三個乘法、三個加法。

==實際應用 ==
一般來說，做傅立葉轉換會用到複數的乘法，會比一般實數的乘法多上四倍，若是利用快速演算法，則可以化簡如下：

<math>(a+bj)(c+dj)=ac-bd+j(ad+bd)=e+jf</math>

<math>\begin{bmatrix} e \\ f \end{bmatrix}=\begin{bmatrix} c & -d \\ d & c \end{bmatrix}\begin{bmatrix} a \\ b \end{bmatrix}=\begin{bmatrix} c & c \\ c & c \end{bmatrix}\begin{bmatrix} a \\ b \end{bmatrix}+\begin{bmatrix} 0 & -c-d \\ d-c & 0 \end{bmatrix}\begin{bmatrix} a \\ b \end{bmatrix}</math>

因此左邊的部分可以參考例子2，所以需要一個乘法，右邊的部分則需要兩個乘法，因此可以由四個乘法變為三個乘法。

另外舉一個DFT的例子，一般來說DFT會需要<math>4N^2</math>個實數乘法：

<math>X[m]=\textstyle \sum_{n=0}^{N-1}x[n]e^{-j{2\pi mn \over N}}, N=3</math>

<math>\begin{bmatrix} 1 & 1 & 1 \\ 1 & -1/2 & -1/2 \\ 1 & -1/2 & -1/2 \end{bmatrix}+j\begin{bmatrix} 0 & 0 & 0 \\ 0 & -\sqrt{3}/2 & \sqrt{3}/2 \\ 0 & \sqrt{3}/2 & -\sqrt{3}/2 \end{bmatrix}</math>，左邊都是一些trivial multiplication，所以不需要乘法運算，右邊則可以參考例子3，所以需要一個乘法。整個DFT的運算可以由下式表示：

<math>X=Fx=(F_R+jF_I)(x_R+jx_I)=F_Rx_R+jF_Rx_I+jF_Ix_R-F_Ix_I</math>

所以最後一供需要<math>2*(0+1)=2</math>個乘法。

==參考資料==
<ref>{{Cite web|url=http://djj.ee.ntu.edu.tw/ADSP10.pdf|title=高等數位訊號處理|accessdate=2017-06-20|author=丁建均|date=|publisher=}}</ref>http://djj.ee.ntu.edu.tw/ADSP10.pdf
[[Category:信号处理]]
<references />