Winograd Fast Fourier Transform Algorithm

Winograd Fast Fourier Transform Algorithm (Winograd FFT) is proposed by Shmuel Winograd in 1978. Winograd FFT algorithm uses about the same number of additions as the Cooley–Tukey FFT algorithm, while using significantly fewer multiplications.

For example, using the matrix representation to express the Discrete Fourier transform(DFT) formula:

$[\begin{matrix} y_{0} \\ y_{1} \\ ⋮ \\ y_{n - 1} \end{matrix}] = [\begin{matrix} 1 & 1 & 1 & \dots & 1 & 1 \\ 1 & w & w^{2} & \dots & w^{n - 2} & w^{n - 1} \\ ⋮ & ⋮ & ⋮ & \dots & ⋮ & ⋮ \\ 1 & w^{n - 1} & w^{2 (n - 1)} & \dots & w^{(n - 2) (n - 1)} & w^{(n - 1) (n - 1)} \end{matrix}] [\begin{matrix} x_{0} \\ x_{1} \\ ⋮ \\ x_{n - 1} \end{matrix}], w = e^{- j \begin{matrix} \frac{2 π}{n} \end{matrix}}$

If n is a prime, then we can remove the first row and the first column and use the algorithm for n-1 point cyclic convolution instead of the algorithm for n point DFT.

n is prime

For example, n=5:

$[\begin{matrix} y_{0} \\ y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \end{matrix}] = [\begin{matrix} 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{matrix}] [\begin{matrix} x_{0} \\ x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{matrix}], w = e^{\frac{- j 2 π}{5}}$

We can rewrite the transform as

$[\begin{matrix} y_{1} - x_{0} \\ y_{2} - x_{0} \\ y_{3} - x_{0} \\ y_{4} - x_{0} \end{matrix}] = [\begin{matrix} 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{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{matrix}]$

Arrange the rows in the order 1, 2, 4, 3 and the columns in the order 1, 3, 4, 2.

$[\begin{matrix} y_{1} - x_{0} \\ y_{2} - x_{0} \\ y_{4} - x_{0} \\ y_{3} - x_{0} \end{matrix}] = [\begin{matrix} 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{matrix}] [\begin{matrix} x_{1} \\ x_{3} \\ x_{4} \\ x_{2} \end{matrix}]$

This is the standard form of cyclic convolution and we can use the algorithm for 4 point cyclic convolution to compute the transform.

n is the power of a prime

In the case $n = p^{r}$ , we can permute the rows and columns of the matrix by the following order:

can be divided by $p^{r}$
can be divided by $p^{r - 1}$

...
can be divided by $p^{0}$

Then we can find a block that is a cyclic matrix in the transform matrix so that we can apply cyclic convolution.

For example, n=9:

$[\begin{matrix} y_{0} \\ y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ y_{5} \\ y_{6} \\ y_{7} \\ y_{8} \end{matrix}] = [\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & w & w^{2} & w^{3} & w^{4} & w^{5} & w^{6} & w^{7} & w^{8} \\ 1 & w^{2} & w^{4} & w^{6} & w^{8} & w & w^{3} & w^{5} & w^{7} \\ 1 & w^{3} & w^{6} & 1 & w^{3} & w^{6} & 1 & w^{3} & w^{6} \\ 1 & w^{4} & w^{8} & w^{3} & w^{7} & w^{2} & w^{6} & w & w^{5} \\ 1 & w^{5} & w & w^{6} & w^{2} & w^{7} & w^{3} & w^{8} & w^{4} \\ 1 & w^{6} & w^{3} & 1 & w^{6} & w^{3} & 1 & w^{6} & w^{3} \\ 1 & w^{7} & w^{5} & w^{3} & w & w^{8} & w^{6} & w^{4} & w^{2} \\ 1 & w^{8} & w^{7} & w^{6} & w^{5} & w^{4} & w^{3} & w^{2} & w \end{matrix}] [\begin{matrix} x_{0} \\ x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \\ x_{6} \\ x_{7} \\ x_{8} \end{matrix}], w = e^{\frac{- j 2 π}{9}}$

Arrange the rows and the columns to be

$[\begin{matrix} y_{0} \\ y_{3} \\ y_{6} \\ y_{1} \\ y_{2} \\ y_{4} \\ y_{8} \\ y_{7} \\ y_{5} \end{matrix}] = [\begin{array}{cccccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & w^{3} & w^{6} & w^{3} & w^{6} & w^{3} & w^{6} \\ 1 & 1 & 1 & w^{6} & w^{3} & w^{6} & w^{3} & w^{6} & w^{3} \\ 1 & w^{3} & w^{6} & w & w^{5} & w^{7} & w^{8} & w^{4} & w^{2} \\ 1 & w^{6} & w^{3} & w^{2} & w & w^{5} & w^{7} & w^{8} & w^{4} \\ 1 & w^{3} & w^{6} & w^{4} & w^{2} & w & w^{5} & w^{7} & w^{8} \\ 1 & w^{6} & w^{3} & w^{8} & w^{4} & w^{2} & w & w^{5} & w^{7} \\ 1 & w^{3} & w^{6} & w^{7} & w^{8} & w^{4} & w^{2} & w & w^{5} \\ 1 & w^{6} & w^{3} & w^{5} & w^{7} & w^{8} & w^{4} & w^{2} & w \end{array}] [\begin{matrix} x_{0} \\ x_{3} \\ x_{6} \\ x_{1} \\ x_{5} \\ x_{7} \\ x_{8} \\ x_{4} \\ x_{2} \end{matrix}]$

We can apply cyclic convolution to the 6 by 6 cyclic matrix located in the lower right corner of the matrix.

Other n

In this case we can take $n = n_{1} \cdot n_{2} \cdot \dots n_{r}$ , where $n_{1}, n_{2}, \dots, n_{r}$ are mutually prime.

For a coefficient $w^{k}$ in n point FFT , we can define the order $(i_{1}, \dots, i_{r})$ of k such that

$k = i_{1} (mod n_{1})$
$\dots$
$k = i_{r} (mod n_{r})$

By Chinese remainder theorem, there exists a coefficient in n point FFT is of order $(i_{1}, \dots, i_{r})$ for all order $i_{1}, \dots, i_{r}$ .

Then we arrange the matrix by lexicographic order of its order than we can derive a matrix combined by $D_{n_{1}}$ .( $D_{n_{1}}$ is the $n_{1}$ by $n_{1}$ DFT matrix)

For example, n = 6 = 2 $\cdot$ 3:

$[\begin{matrix} y_{0} \\ y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ y_{5} \end{matrix}] = [\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & w & w^{2} & w^{3} & w^{4} & w^{5} \\ 1 & w^{2} & w^{4} & 1 & w^{2} & w^{4} \\ 1 & w^{3} & 1 & w^{3} & 1 & w^{3} \\ 1 & w^{4} & w^{2} & 1 & w^{4} & w^{2} \\ 1 & w^{5} & w^{4} & w^{3} & w^{2} & w^{1} \end{matrix}] [\begin{matrix} x_{0} \\ x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{matrix}], w = e^{\frac{- j π}{3}}$

The order is

0 - (0, 0)
1 - (1, 1)
2 - (2, 0)
3 - (0, 1)
4 - (1, 0)
5 - (2, 1)

Arrange the rows and the columns to be:

$[\begin{matrix} y_{0} \\ y_{3} \\ y_{2} \\ y_{5} \\ y_{4} \\ y_{1} \end{matrix}] = [\begin{array}{cccccc} 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & w^{3} & 1 & w^{3} & 1 & w^{3} \\ 1 & 1 & w^{2} & w^{2} & w^{4} & w^{4} \\ 1 & w^{3} & w^{2} & w^{5} & w^{4} & w \\ 1 & 1 & w^{4} & w^{4} & w^{2} & w^{2} \\ 1 & w^{3} & w^{4} & w^{1} & w^{2} & w^{5} \end{array}] [\begin{matrix} x_{0} \\ x_{3} \\ x_{4} \\ x_{1} \\ x_{2} \\ x_{5} \end{matrix}] = [\begin{matrix} D_{2} & D_{2} & D_{2} \\ D_{2} & w^{2} D_{2} & w^{4} D_{2} \\ D_{2} & w^{4} D_{2} & w^{2} D_{2} \end{matrix}] [\begin{matrix} x_{0} \\ x_{3} \\ x_{4} \\ x_{1} \\ x_{2} \\ x_{5} \end{matrix}] = D 3 \otimes D 2 [\begin{matrix} x_{0} \\ x_{3} \\ x_{4} \\ x_{1} \\ x_{2} \\ x_{5} \end{matrix}]$

Number of operations

The number of additions and multiplications required for both n-point Winograd FFT and n-point FFT algorithms for various values of n are as follows (the input is complex):


FFT			Winograd FFT
n	Mul	Add	n	M	A
32	192	416	30	72	384
48	352	784	48	108	636
64	384	960	60	144	888
128	1152	2368	120	288	2076
160	1792	4032	168	432	3492
256	2304	5248	240	648	5016
400	6240	14000	420	1296	11352
512	6144	12288	504	1872	14796
800	14080	30400	840	2592	24804
1024	12288	26624	1008	4212	35244
2520	44032	92672	2520	11232	102348

Disadvantage

Although Winograd FFT benefits in reducing the multiplications in FFT algorithms, it still has some disadvantages.

The design of Winograd FFT is much more complex, involving rearrangement using remainders and transforming multidimensional matrix multiplication.
The number of additions may increase significantly, and at current computing speeds, the benefits of reducing the number of multiplications may outweigh the loss of increased additions.

References

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.
Silverman, H. “An introduction to programming the Winograd Fourier transform algorithm (WFTA)” Acoustics, Speech and Signal Processing, IEEE Trans , Apr 1977

This article "Winograd Fast Fourier Transform Algorithm" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Winograd Fast Fourier Transform Algorithm. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.