威诺格拉德快速傅里叶算法(英语:Winograd FFT)是由美国计算机科学家Shmuel Winograd在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.