2.9d Fast Fourier Transform

Fast Fourier Transform (FFT)

The Fast Fourier Transform (FFT) is an efficient recursive algorithm for computing the Discrete Fourier Transform (DFT) of a sequence. The DFT itself converts a finite sequence of equally spaced samples (usually from a time-domain signal) into a sequence of complex numbers representing the amplitudes and phases of sinusoidal frequency components. For the DFT equations

Intuition

The FFT algorithm drops the inverse period multiplication in the standard discrete Fourier calculations, such that
$X[k]=\cancel{\frac{1}{N}}{\sum }_{n=0}^{N-1}x[n]e^{-jk\frac{2\pi }{N}n}.$
The FFT optimizes computational time by only taking periods in the scope of $N=2^{\ell }$, where $\ell \in \mathbb{N}.$ This step ensures that the finite signal will always have an even number of elements, and is useful for performing linear algebra on the above equations.
For simplification, we will take $W_N=e^{-j\frac{2\pi }{N}}$. The FFT also performs decimation in time, dividing $x[n]$ into two sets of even and odd multiples of $n$, such that two calculations are performed where
$X[k]={\sum }_{n=0}^{\frac{N}{2}-1}x[2n]W_N^{2kn}+{\sum }_{n=0}^{\frac{N}{2}-1}x[2n+1]W_N^{(2n+1)k}.$
This can equivalently be represented using $W_{N/2}=e^{-j\frac{4\pi }{N}}$, such that
$X[k]={\sum }_{n=0}^{\frac{N}{2}-1}x[2n]W_{N/2}^{kn}+W_N^k{\sum }_{n=0}^{\frac{N}{2}-1}x[2n+1]W_{N/2}^{kn}.$
We see that the right hand side of the equation above closely resembles two Fourier coefficients, one for $e[n]=x[2n]$ and another for $o[n]=x[2n+1]$. Therefore, we can represent the above as
$X[k]=E[k]+W_N^{k}O[k].$
However, this only represents the signal for the first half of the period $N$ ($0\text{ through }\frac{N}{2}-1$). By shifting $k$ by $\frac{N}{2}$, we can obtain the decomposition for the second half of the signal, such that we get $X\left[k+\frac{N}{2}\right].$ This is very straightforward, since the DFT kernel $W_{\frac{N}{2}}$ is periodic on $\frac{N}{2}$, and therefore both $E[k]$ and $O[k]$ are periodic on $\frac{N}{2}$. The equation becomes
$X\left[k+\frac{N}{2}\right]=E[k]+W_N^k{W}_N^{\frac{N}{2}}O[k]=E[k]+W_N^k{e}^{-j\frac{2\pi }{N}\frac{N}{2}}O[k]=E[k]-W_N^{k}O[k].$
Therefore, we get the piecewise equation

\begin{cases} E[k]+e^{-j\omega_0k}O[k] & \text{for } k \in [0,\frac{N}{2}) \\ E[k]-e^{-j\omega_0k}O[k] & \text{for } k \in [\frac{N}{2}, N) \end{cases}$$ where $\omega_0 = \frac{2\pi}{N}$.