Chapter 8
The Fast Fourier Transform
8.1 Theory
THE fast Fourier transform (FFT) is just what the name says it is: a fast way for computers to calculate the Fourier transform, specifically the discrete Fourier transform (DFT). The introduction of the FFT algorithm by Cooley and Tukey in 1965 revolutionized signal processing and has had an enormous effect on engineering and applied science in general [1]. This chapter is by no means a treatise on the FFT. Despite the fact that we will only cover a few of the major points, this is still a long chapter, but we encourage you to read it completely. For more details about the FFT, see [2,4,72].
Having a fast way to calculate the DFT has many advantages. We will see in Chapter 9 how ...
