Fast Fourier Transform (FFT) Algorithm

The N-point DFT of time samples $x[0], x[1], \cdots, x[N-1]$ is defined as (ignoring the coefficient $1/\sqrt{N}$ for now):

$$X[n]=\sum_{m=0}^{N-1} x[m]e^{-j2\pi mn/N}=\sum_{m=0}^{N-1}x[m]w_N^{mn} \;\;\;\;\;\;\;\;\;\;(n=0, 1, \cdots, N-1)$$

$w_N$ is defined as $w_N \stackrel{\triangle}{=} e^{-j2\pi/N}$ and it is easy to show that $w_N$ has the following properties:

1. 
   
   $$w_N^{kN}=e^{-j2kN\pi/N}=e^{-j2k\pi} \equiv 1$$
   
   

2. 
   
   $$w_{2N}^{2k}=e^{-j2k2\pi/2N}=e^{-jk2\pi/N} \equiv w_N^k$$
   
   

3. 
   
   $$w_{2N}^{N} =e^{-j2N\pi/2N}=e^{-j\pi} \equiv -1$$
   
   

Let $N=2M$, the above DFT can be written as

$$X[n]=\sum_{m=0}^{N-1} x[m]w_{N}^{mn} =\sum_{m=0}^{M-1} x[2m]w_{2M}^{2mn}+\sum_{m=0}^{M-1} x[2m+1]w_{2M}^{(2m+1)n}$$

The first summation has all the even terms and the second all the odd ones. Due to the 2nd property of $w_M$, the above can be rewritten as

$$X[n]= \sum_{m=0}^{M-1} x[2m]w_{M}^{mn}+ \sum_{m=0}^{M-1} x[... ...X_{even}[n]+X_{odd}[n] w_{2M}^n,\;\;\;\;\;\;\;(n=0,\cdots,M-1)$$ (1)

where

$$X_{even}[n]\stackrel{\triangle}{=}\sum_{m=0}^{N-1} x[2m]w_{M}... ...d}[n]\stackrel{\triangle}{=}\sum_{m=0}^{N-1} x[2m+1]w_{M}^{mn}$$

are two $N/2$-point DFTs.

Here we let the index $n$ cover only the first half of the original range of the DFT, $n=0, 1, \cdots, N/2-1=M-1$. The second half can be obtained by replacing $n$ in Eq. (1) by $n+N$:

$$X[n+M]=X_{even}[n+M]+X_{odd}[n+M] w_{2M}^{n+M}$$

Due to the first property of $w_M$, we have

$$X_{even}[n+M]=\sum_{m=0}^{M-1} x[2m]w_{M}^{m(n+M)} =\sum_{m=0}^{M-1} x[2m]w_{M}^{mn}=X_{even}[n]$$

and similarly

$$X_{odd}[n+M]=X_{odd}[n]$$

Also, due to the 3rd property of $w_M$, we have

$$w_{2M}^{n+M}=w_{2M}^n w_{2M}^M=-w_{2M}^{n}$$

Now the second half of the DFT becomes

$$X[n+M]=X_{even}[n]-X_{odd}[n] w_{2M}^n$$ (2)

The N-point DFT can now be obtained from Eqs. (1), (2), once $X_{ever}[n]$ and $X_{odd}[n]$ are available. However, since $X_{even}[n]$ and $X_{odd}[n]$ are N/2-point DFTs, they can be obtained the same way. This process goes on recursively until finally only 1-point DFTs are needed, which are just the time samples themselves. Therefore, the operations of an N-point DFT can be symbolically represented by the following diagram. The complexity is therefore reduced from $O(N^2)$ to $O(N\; log_2 N)$.