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

威诺格拉德快速傅里叶算法（英语：Winograd FFT）是由美国计算机科学家Shmuel Winograd在1978年提出。此算法可以找出最少的乘法运算量。

当把DFT的公式：$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.$

用矩阵方式来表示：${\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}}}$

如果n是质数，则可以无视第一行与第一列，把n点的DFT用n-1点的回旋折积来取代。

使用方法

使用此算法，可分为以下几个步骤，此处以n=5的DFT为例：

${\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\angle 72^{\circ }}$

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

${\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\angle 72^{\circ }}$

Step 2：找出列与行的顺序：

a)找出一个原根 a，使得$a^{k}{\bmod {N}}\neq 1\quad when\quad k=1,2,\cdots ,N-2,\quad a^{N-1}{\bmod {N}}=1$.

b)用p[n]表示列与行的顺序：$p[n]=a^{n}{\bmod {N}},\quad n=0,1,\cdots ,N-2$

在这例子中，N=5有两个原根：2与3。取2作为其原根，可得其顺序为：1,2,4,3。

故要将此矩阵${\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$ 的第三列与第四列交换，第三行与第四行交换，把矩阵变成如下：

${\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$

如此第一行与第一列都跟所求得的顺序：1,2,4,3一样，此为circular correlation的形式。

Step 3：为了要符合回旋折积的定义(矩阵的对角线的项数相同)，故必须再将第二列与第四列交换，第二行与第四行交换，矩阵如下：

${\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$

如此就可把N点DFT用N-1点的DFT来简化，表示如下：

${\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]$

缺点

虽然此算法有着可以大幅减少乘法量的优点，但相对于此，也有一些缺点：

• N不同，那硬件的架构也会跟着改变。
• Time Cycle较多（因为要做两次N-1点的DFT）。
• 加法量会增加很多。

其他运用

任意长度的DFT都可以用长度为$2^{k}$点的DFT来简化，举例来说：

7点的DFT：先将7点DFT用Winograd简化成6点DFT，再利用6=2x3，故6点DFT可用2点DFT与3点的DFT来表示，再把3点的DFT用Winograd简化成2点的DFT，即可把7点的DFT用$2^{k}$点的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.