威諾格拉德快速傅立葉變換演算法

威諾格拉德快速傅立葉演算法（）是由美國電腦科學家在1978年提出。此演算法可以找出最少的乘法運算量。

當把DFT的公式： 

用矩陣方式來表示：

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

使用方法

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

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

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

a)找出一個原根 a，使得.

b)用p[n]表示列與行的順序：

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

故要將此矩陣  的第三列與第四列交換，第三行與第四行交換，把矩陣變成如下：

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

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

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

缺點

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

其他運用

任意長度的DFT都可以用長度為點的DFT來簡化，舉例來說：

7點的DFT：先將7點DFT用Winograd簡化成6點DFT，再利用6=2x3，故6點DFT可用2點DFT與3點的DFT來表示，再把3點的DFT用Winograd簡化成2點的DFT，即可把7點的DFT用點的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.

W