Efficient Synthesis and Implementation of Large Discrete Fourier Transformations
S.D. Morgera · SIAM Journal on Computing · 1980
A systematic technique is presented for synthesizing and efficiently performing large discrete Fourier transformations (DFT’s) in the range from 60 to 5000 points. The technique is termed the mutual prime factor cyclic algorithm (MPFCA). The mutual prime factor portion of the algorithm is attributed originally to L. H. Thomas, with generalization supplied by I. J. Good; the cyclic aspect of the algorithm has recently been formalized by S. Winograd. Three methods are described for implementing the MPFCA; computational complexity (multiplications and additions) is estimated for each method and compared with the fast Fourier transform (FFT). For special purpose hardware, the MPFCA is at least twice as efficient as the FFT. A major result of importance is the realization that the three considerably different implementation methods presented lead to rather similar multiplication complexities for large size DFT’s; furthermore, the resulting multiplication complexity is considerably higher than that achieved for small size DFT’s. It is felt that further substantial improvements for large size DFT’s built up using mutually prime factors will require more general theoretical results in addition to long, tedious hours spent with computer based formula manipulation systems.