[科普中国]-威诺格拉德快速傅里叶变换

威诺格拉德快速傅里叶算法（英语：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来简化。1

本词条内容贡献者为:

何星 - 副教授 - 上海交通大学