The Fast Fourier Transform (FFT)

The fast Fourier transform (FFT) is an efficient implementation of the discrete Fourier transform (DFT) for highly composite^A.1 transform lengths $N$. When $N$ is a power of 2, the computational complexity drops from ${\cal O}(N^2)$ (for the DFT) down to ${\cal O}(N\lg N)$ for the FFT, where $\lg N$ denotes the logarithm-base-2 of $N$. The FFT was evidently first described by Gauss in 1805 [25] and rediscovered in the 1960s by Cooley and Tukey [13].

Pointers to FFT software are given in §A.4.^A.2

The first stage of a radix 2 FFT algorithm is derived below; the remaining stages are obtained by applying the same decomposition recursively. The DFT is defined by

$$X(k) = \sum_{n=0}^{N-1} x(n) W_N^{kn}, \quad k=0,1,2,\ldots,N-1,$$

where $x(n)$ is the input signal amplitude at time $n$, and

$$W_N \isdef e^{-j\frac{2\pi}{N}}.\quad \hbox{(primitive $N$th root of unity)}$$

Note that $W_N^N=1$.

There are two basic varieties of FFT, one based on decimation in time (DIT), and the other on decimation in frequency (DIF). Here we will derive decimation in time.