Fast Fourier Transform (FFT) Algorithm

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 $N$ DFT from order $N^2$ to order $N log_2 N$ operations when $N$ is a power of 2. The FFT  achieves a very large reduction in the cost of computation as $N$ becomes large. There are FFT algorithms for many different factorizations of $N$.

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.