Winograd Fast Fourier Transform Algorithm (Winograd FFT) is proposed by Shmuel Winograd in 1978. Winograd FFT algorithm uses about the same number of additions to Cooley–Tukey FFT algorithm, while using significantly fewer multiplications.
For example, using the matrix representation to express the Discrete Fourier transform(DFT) formula:
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[edit]
For example, n=5:
We can rewrite the transform as
Arrange the row in the order 1, 2, 4, 3 and the column in the order 1, 3, 4, 2.
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[edit]
In the case , we can permute the rows and columns of the matrix by the following order:
- can be divided by
- can be divided by
- ...
- can be divided by
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:
Arrange the row and the column to be
We can apply cyclic convolution to the 6 by 6 cyclic matrix located in the lower right corner of the matrix.
Other n[edit]
In this case we can take , where are mutually prime.
For a coefficient in n point FFT , we can define the order of k such that
By Chinese remainder theorem, there exist a coefficient in n point FFT is of order for all order .
Then we arrange the matrix by lexicographic order of its order than we can derive a matrix combined by .( is the by DFT matrix)
For example, n = 6 = 23:
The order is
- 0 - (0, 0)
- 1 - (1, 1)
- 2 - (2, 0)
- 3 - (0, 1)
- 4 - (1, 0)
- 5 - (2, 1)
Arrange the row and the column to be:
Number of operations[edit]
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[edit]
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[edit]
- 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.