Power-of-two-length FFTs are usually best for general use when the DFT length is somewhat at the user's discretion. The best power-of-two algorithm may depend on the type of computer to be used.
FFTs of prime length can be computed efficiently via Rader's conversion, via the chirp z-transform, or by use of Winograd methods.
This book uses an index map, a polynomial decomposition, an operator factorization, and a conversion to a filter to develop a very general and efficient description of fast algorithms to calculate the discrete Fourier transform (DFT). The work of Winograd is outlined, chapters by Selesnick, Pueschel, and Johnson are included, and computer programs are provided.
This book uses an index map, a polynomial decomposition, an operator factorization, and a conversion to a filter to develop a very general and efficient description of fast algorithms to calculate the discrete Fourier transform (DFT). The work of Winograd is outlined, chapters by Selesnick, Pueschel, and Johnson are included, and computer programs are provided. This version is to printed in a 6"x9" size.
This is a slightly revised version of: "Large DFT Modules: 11, 13, 16, 17, 19, and 25" which was an ECE Technical Report 8105 at Rice University, Dec. 13, 1981. The original authors were H. W. Johnson and C. S. Burrus
Fast Fourier transform (FFT) algorithms efficiently compute the discrete Fourier transform (DFT). There are different types of FFT algorithms for different DFT lengths; lengths equal to a power of two are the simplest and by far the most commonly used. The prime-factor algorithm yields fast algorithms for some other lengths, and along with the chirp z-transform and Rader's conversion allow fast algorithms for DFTs of any length.
Prime Factor FFT Algorithm
Prime Factor FFT Algorithm without unscrambler
