威諾格拉德快速傅立葉演算法 （英語：Winograd FFT ）是由美國電腦科學家Shmuel Winograd
當把DFT 的公式：
y
j
=
∑
k
=
0
n
−
1
x
k
e
−
j
2
π
n
i
k
j
=
0
,
1
,
⋯
,
n
−
1.
{\displaystyle 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.}
用矩陣方式來表示：
[
y
0
y
1
⋮
y
n
−
1
]
=
[
1
1
1
⋯
1
1
1
w
w
2
⋯
w
n
−
2
w
n
−
1
⋮
⋮
⋮
⋯
⋮
⋮
1
w
n
−
1
w
2
(
n
−
1
)
⋯
w
(
n
−
2
)
(
n
−
1
)
w
(
n
−
1
)
(
n
−
1
)
]
[
x
0
x
1
⋮
x
n
−
1
]
,
w
=
e
−
j
2
π
n
{\displaystyle {\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為例：
[
y
0
y
1
y
2
y
3
y
4
]
=
[
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
]
[
x
0
x
1
x
2
x
3
x
4
]
,
w
=
e
−
j
∠
72
∘
{\displaystyle {\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 }}}
[
y
1
−
x
0
y
2
−
x
0
y
3
−
x
0
y
4
−
x
0
]
=
[
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
]
[
x
1
x
2
x
3
x
4
]
,
w
=
e
−
j
∠
72
∘
{\displaystyle {\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
mod
N
≠
1
w
h
e
n
k
=
1
,
2
,
⋯
,
N
−
2
,
a
N
−
1
mod
N
=
1
{\displaystyle 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
mod
N
,
n
=
0
,
1
,
⋯
,
N
−
2
{\displaystyle p[n]=a^{n}{\bmod {N}},\quad n=0,1,\cdots ,N-2}
在這例子中，N=5有兩個原根：2與3。取2作為其原根，可得其順序為：1,2,4,3。
[
y
1
−
x
0
y
2
−
x
0
y
3
−
x
0
y
4
−
x
0
]
=
[
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
]
[
x
1
x
2
x
3
x
4
]
{\displaystyle {\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 }
[
y
1
−
x
0
y
2
−
x
0
y
4
−
x
0
y
3
−
x
0
]
=
[
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
]
[
x
1
x
2
x
4
x
3
]
{\displaystyle {\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：為了要符合迴旋摺積 的定義(矩陣的對角線的項數相同)，故必須再將第二列與第四列交換，第二行與第四行交換，矩陣如下：
[
y
1
−
x
0
y
3
−
x
0
y
4
−
x
0
y
2
−
x
0
]
=
[
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
]
[
x
1
x
3
x
4
x
2
]
{\displaystyle {\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來簡化，表示如下：
[
y
1
−
x
0
y
3
−
x
0
y
4
−
x
0
y
2
−
x
0
]
=
I
F
F
T
[
F
F
T
4
{
[
x
1
x
3
x
4
x
2
]
}
.
F
F
T
4
{
[
w
1
w
3
w
4
w
2
]
}
]
{\displaystyle {\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
{\displaystyle 2^{k}}
7點的DFT：先將7點DFT用Winograd簡化成6點DFT，再利用6=2x3，故6點DFT可用2點DFT與3點的DFT來表示，再把3點的DFT用Winograd簡化成2點的DFT，即可把7點的DFT用
2
k
{\displaystyle 2^{k}}
參考資料
编辑
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. 
![{\displaystyle p[n]=a^{n}{\bmod {N}},\quad n=0,1,\cdots ,N-2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4d50ce09c44cac7dda65c1b28c40000c8d14bb2)
![{\displaystyle {\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d845b66701172418f965709d54c4a19ccaa83d6c)
