You can edit almost every page by Creating an account. Otherwise, see the FAQ.

Winograd Fast Fourier Transform Algorithm

From EverybodyWiki Bios & Wiki





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.