Understanding Digital Signal Processing, Second Edition

Chapter Four. The Fast Fourier Transform

Although the DFT is the most straightforward mathematical procedure for determining the frequency content of a time-domain sequence, it's terribly inefficient. As the number of points in the DFT is increased to hundreds, or thousands, the amount of necessary number crunching becomes excessive. In 1965 a paper was published by Cooley and Tukey describing a very efficient algorithm to implement the DFT[1]. That algorithm is now known as the fast Fourier transform (FFT).^[†] Before the advent of the FFT, thousand-point DFTs took so long to perform that their use was restricted to the larger research and university ...