0.6 Winograd's short dft algorithms  (Page 8/11)

This result is not practically useful because the number of additions necessary to realize this minimum of multiplicationsbecomes very large for lengths greater than 16. Nevertheless, it proves the minimum number of multiplications required of an optimalalgorithm is a linear function of $N$ rather than of $NlogN$ which is that required of practical algorithms. The best practical power-of-two algorithm seems to the Split-Radix [link] FFT discussed in The Cooley-Tukey Fast Fourier Transform Algorithm: The Split-Radix FFT Algorithm .

All of these theorems use ideas based on residue reduction, multiplication of the residues, and then combination by the CRT. Itis remarkable that this approach finds the minimum number of required multiplications by a constructive proof which generates analgorithm that achieves this minimum; and the structure of the optimal algorithm is, within certain variations, unique. For shorterlengths, the optimal algorithms give practical programs. For longer lengths the uncounted operations involved with the multiplication ofthe higher degree residue polynomials become very large and impractical. In those cases, efficient suboptimal algorithms can begenerated by using the same residue reduction as for the optimal case, but by using methods other than the Toom-Cook algorithm of Theorem 1 to multiply the residue polynomials.

Practical long DFT algorithms are produced by combining short prime length optimal DFT's with the Type 1 index map from Multidimensional Index Mapping to give the Prime Factor Algorithm (PFA) and the Winograd Fourier Transform Algorithm (WFTA) discussed in The Prime Factor and Winograd Fourier Transform Algorithms . It is interesting to note that the index mapping technique is useful inside the short DFT algorithms to replace the Toom-Cookalgorithm and outside to combine the short DFT's to calculate long DFT's.

The automatic generation of winograd's short dfts

by Ivan Selesnick, Polytechnic Institute of New York University

Introduction

Efficient prime length DFTs are important for two reasons. A particular application may require a prime length DFT and secondly, the maximum lengthand the variety of lengths of a PFA or WFTA algorithm depend upon the availability of prime length modules.

This [link] , [link] , [link] , [link] discusses automation of the process Winograd used for constructing prime length FFTs [link] , [link] for $N<7$ and that Johnson and Burrus [link] extended to $N<19$ . It also describes a program that will design any prime length FFT in principle,and will also automatically generate the algorithm as a C program and draw the corresponding flow graph.

Winograd's approach uses Rader's method to convert a prime length DFT into a $P-1$ length cyclic convolution, polynomial residue reduction to decompose the problem into smaller convolutions [link] , [link] , and the Toom-Cook algorithm [link] , [link] . The Chinese Remainder Theorem (CRT) for polynomials is then used to recombine theshorter convolutions. Unfortunately, the design procedure derived directly from Winograd's theory becomes cumbersome for longer length DFTs, and this has oftenprevented the design of DFT programs for lengths greater than 19.