跳转到内容

威诺格拉德快速傅里叶变换算法

本页使用了标题或全文手工转换
维基百科,自由的百科全书

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