Appendix: Summary of the theory and algorithmic development of the fast Fourier transform
Patrick A. Gaydecki · Institution of Engineering and Technology eBooks · 2004
The theoretical framework and algorithmic realisation of the fast Fourier transform (FFT) was first established in workable form by Cooley and Tukey in 1965, although, as was stated in Chapter 6, several early pioneers in this area had made partial contributions to the technique. The development of the FFT was arguably the single most important contribution to DSP, enabling practical realisation of a vast number of algorithms that we now take for granted. Bearing in mind that there are many ways in which the FFT can be implemented, in this appendix we will examine briefly the radix-2 decimation-in-time fast Fourier transform (DIT FFT). The FFT is far more efficient than a directly implemented DFT, the number of calculations being propor tional to log2 N for the former, in comparison to iV2 for the latter, for an N-point data record. The mathematical treatment below has been compiled from a number of sources, including Ifeachor and Jervis (1993), Oppenheim and Shafer (1999), Lynn and Feurst (1998), Burrus and Parks (1985), Sohie and Chen (1993) and Ingle and Proakis (1991). With regard to the indexing problem, which appears later in the Appendix, I have extended the explanation provided by Ifeachor and Jervis to clarify the operation of my implementation of the radix-2 DIT FFT algorithm, which is available on the CD accompanying this book.