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)$$

where we have defined

$$w_N \stackrel{\triangle}{=} e^{-j2\pi/N}$$

It is easy to show that $w_N$ has the following properties:

1. 
   
   $$w_N^{kN}=\left( e^{-j2\pi /N} \right)^{kn}=e^{-j2\pi kN/N} =e^{-j2k\pi} \equiv 1$$
   
   

2. 
   
   $$w_{2N}^{2k}=\left( e^{-j2\pi /2N} \right)^{2k}=e^{-j2\pi k2/2N} =e^{-jk2\pi/N} \equiv w_N^k$$
   
   

3. 
   
   $$w_{2N}^{N}=\left( e^{-j2\pi /2N} \right)^N=e^{-j2\pi N/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 $M=N/2$ even terms and the second all $M=N/2$ 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[2m+1... ...n}[n]+X_{odd}[n] w_{2M}^n,\;\;\;\;\;\;\;\;\;\;(n=0,\cdots,M-1)$$ (1)

where

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

are two M-point DFTs, where

$$w_M^{mn}=e^{-j2\pi mn/M}=\cos(2\pi mn/M)-j\sin(2\pi mn/M)$$

Note that the index $n=0,\cdots, M-1$ for these two M-point DFTs only covers the first half of the range $n=0,\cdots,N-1$ for the original N-point DFT. However, the second half can be easily obtained by replacing $n$ in Eq. (1) with $n+M$:

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

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

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

The last equation is due to the 3rd property of $w_M$. Also, 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

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

Now the second half of the N-point DFT can be obtained as

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

The N-point DFT can now be obtained from Eqs. (1), (2), once $X_{ever}[n]$ and $X_{odd}[n]$ are available. However, as $X_{ever}[n]$ and $X_{odd}[n]$ are two N/2-point DFTs, they each can also be obtained by two N/4-point DFTs. This process can be carried out 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)$.