In this lesson you will learn the principles at the core of the decimation-in-time fast Fourier transform algorithm. The (re)discovery of the fast Fourier transform algorithm by Cooley and Tukey in 1965 was perhaps the most significant event in the history of signal processing. There is evidence that Gauss first developed a fast Fourier transform-type algorithm in 1805.
Fourier analysis and the discrete Fourier transform (DFT) are central players in signal processing. The fast Fourier transform algorithm (FFT) reduces the computation of a length DFT from order
to order
operations when
is a power of 2. The FFT achieves a very large reduction in the cost of computation as
becomes large. There are FFT algorithms for many different factorizations of
.
Understanding the principles behind the fast Fourier transform algorithm will position you to effectively apply the FFT and appreciate its significance in signal processing. Furthermore, the general approach for reducing computation in the FFT – breaking a large problem up into a combination of smaller problems – also applies in many other algorithms.