查看“︁威諾格拉德快速傅立葉變換演算法”︁的源代码

{{NoteTA|1=zh:傅里叶; zh-hans:傅里叶; zh-hant:傅立葉;}}
'''威諾格拉德快速傅立葉演算法'''（{{lang-en|Winograd FFT}}）是由美國電腦科學家{{le|Shmuel Winograd}}在1978年提出。此演算法可以找出最少的乘法運算量。

當把[[离散傅里叶变换|DFT]]的公式：<math>y_j=\sum_{k=0}^{n-1} x_k e^{-j\begin{matrix} \frac{2\pi}{n} \end{matrix} ik} \qquad  j=0,1,\cdots,n-1. </math> 

用矩陣方式來表示：<math>\begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_{n-1}  \end{bmatrix}= \begin{bmatrix} 1 &  1 & 1 & \cdots & 1 & 1 \\ 1 & w & w^2 & \cdots & w^{n-2} & w^{n-1}\\ \vdots & \vdots  & \vdots  & \cdots  & \vdots  & \vdots \\ 1 & w^{n-1} & w^{2(n-1)} & \cdots & w^{(n-2)(n-1)} & w^{(n-1)(n-1)}\end{bmatrix}\begin{bmatrix} x_0 \\ x_1 \\ \vdots \\ x_{n-1}  \end{bmatrix}, \quad w=e^{-j\begin{matrix} \frac{2\pi}{n} \end{matrix}}</math>

如果n是質數，則可以無視第一行與第一列，把n點的DFT用n-1點的迴旋摺積來取代。

==使用方法==

使用此演算法，可分為以下幾個步驟，此處以n=5的DFT為例：

<math>\begin{bmatrix} y_0 \\ y_1 \\ y_2 \\ y_3 \\ y_4 \end{bmatrix}= \begin{bmatrix} 1 &  1 & 1  & 1 & 1 \\ 1 & w & w^2 & w^3 & w^4 \\ 1 & w^2  & w^4  & w  & w^3  \\ 1 & w^3 & w & w^4 & w^2 \\ 1 & w^4 & w^3 & w^2 & w\end{bmatrix}\begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix}, \qquad w=e^{-j\angle72^\circ }</math>


Step 1：消去第一行與第一列，式子可以改寫如下：

<math>\begin{bmatrix}  y_1-x_0 \\ y_2-x_0 \\ y_3-x_0 \\ y_4-x_0 \end{bmatrix}= \begin{bmatrix} w & w^2 & w^3 & w^4 \\ w^2  & w^4  & w  & w^3  \\ w^3 & w & w^4 & w^2 \\ w^4 & w^3 & w^2 & w\end{bmatrix}\begin{bmatrix}  x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix}, \qquad w=e^{-j\angle72^\circ }</math>

Step 2：找出列與行的順序：

a)找出一個[[原根]] a，使得<math>a^k\bmod N \ne 1 \quad when \quad k=1,2,\cdots,N-2,\quad a^{N-1}\bmod N=1</math>.

b)用p[n]表示列與行的順序：<math>p[n]=a^n \bmod N,\quad n=0,1,\cdots,N-2</math>

在這例子中，N=5有兩個原根：2與3。取2作為其原根，可得其順序為：1,2,4,3。


故要將此矩陣<math>\begin{bmatrix}  y_1-x_0 \\ y_2-x_0 \\ y_3-x_0 \\ y_4-x_0 \end{bmatrix}= \begin{bmatrix} w & w^2 & w^3 & w^4 \\ w^2  & w^4  & w  & w^3  \\ w^3 & w & w^4 & w^2 \\ w^4 & w^3 & w^2 & w\end{bmatrix}\begin{bmatrix}  x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix}\quad </math>  的第三列與第四列交換，第三行與第四行交換，把矩陣變成如下：


<math>\begin{bmatrix}  y_1-x_0 \\ y_2-x_0 \\ y_4-x_0 \\ y_3-x_0 \end{bmatrix}= \begin{bmatrix} w & w^2 & w^4 & w^3 \\ w^2  & w^4  & w^3  & w  \\ w^4 & w^3 & w & w^2 \\ w^3 & w & w^2 & w^4\end{bmatrix}\begin{bmatrix}  x_1 \\ x_2 \\ x_4 \\ x_3 \end{bmatrix}\quad </math>

如此第一行與第一列都跟所求得的順序：1,2,4,3一樣，此為[[circular correlation]]的形式。

Step 3：為了要符合[[迴旋摺積]]的定義(矩陣的對角線的項數相同)，故必須再將第二列與第四列交換，第二行與第四行交換，矩陣如下：

<math>\begin{bmatrix}  y_1-x_0 \\ y_3-x_0 \\ y_4-x_0 \\ y_2-x_0 \end{bmatrix} = \begin{bmatrix} w & w^3 & w^4 & w^2 \\ w^2  & w  & w^3  & w^4  \\ w^4 & w^2 & w & w^3 \\ w^3 & w^4 & w^2 & w\end{bmatrix}\begin{bmatrix}  x_1 \\ x_3 \\ x_4 \\ x_2 \end{bmatrix}\quad </math>

如此就可把N點DFT用N-1點的DFT來簡化，表示如下：


<math>\begin{bmatrix}  y_1-x_0 \\ y_3-x_0 \\ y_4-x_0 \\ y_2-x_0 \end{bmatrix} = IFFT \left[FFT_4 \left\{\begin{bmatrix}  x_1 \\ x_3 \\ x_4 \\ x_2 \end{bmatrix}\right\}.FFT_4\left\{\begin{bmatrix}  w^1 \\ w^3 \\ w^4 \\ w^2 \end{bmatrix}\right\}\right]</math>

==缺點==

雖然此演算法有著可以大幅減少乘法量的優點，但相對於此，也有一些缺點：
*N不同，那硬體的架構也會跟著改變。
*Time Cycle較多（因為要做兩次N-1點的DFT）。
*加法量會增加很多。

==其他運用==

任意長度的DFT都可以用長度為<math>2^k</math>點的DFT來簡化，舉例來說：

7點的DFT：先將7點DFT用Winograd簡化成6點DFT，再利用6=2x3，故6點DFT可用2點DFT與3點的DFT來表示，再把3點的DFT用Winograd簡化成2點的DFT，即可把7點的DFT用<math>2^k</math>點的DFT來簡化。

== 參考資料 ==
*Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2007.
*S.Winograd, "On computing the discrete Fourier transform," Mathematics of Computation, vol.32,no.141,pp.179-199,Jan.1978.

[[Category:傅里叶分析|W]]