Defining equation for the N point DFT of the signal x(n) , so we have
$ X(k) = \sum_{n=0}^{N-1} x(n)e^{-j{\frac{2{\pi}kn}{N}}} $
We denote
X(k) = DFTN[X(n)] * Here we assume that N is even
In the preceding steps, we will show how Radix-2 FFT Alorithm for computation o the DFT based on the divide-and-conquer approach.
Step 1: Deine two new N/2 points from th original N point sequency x(n)
x0(n) = x(2n) even subset of x(n)
x1(n) = x(2n + 1) odd subset of x(n)
* where n = 0,1,2 .... N/2-1
Step 2: Perform an N/2 point DFT on each subset
$ X_0 (k)=DFT_\frac{N}{2}[x_0 (n)] $
$ X_1 (k)=DFT_\frac{N}{2}[x_1 (n)] $
Then we have
X(k) = X0(k) + X1(k)
Let n = 2m (even) and n = 2m+1 (odd)
$ {X(k) = \sum_{m=0}^{\frac{N}{2}-1} x(2m)e^{-j{\frac{2{\pi}k}{N}}(2m)}}+ { \sum_{m=0}^{\frac{N}{2}-1} x(2m+1)e^{-j{\frac{2{\pi}k}{N}}(2m+1)}} $ $ {X(k) = \sum_{m=0}^{\frac{N}{2}-1} x(2m)e^{-j{\frac{2{\pi}k}{N}}(2m)}}+ { {e^{-j{\frac{2{\pi}k}{N}}}}{\sum_{m=0}^{\frac{N}{2}-1} x(2m+1)e^{-j{\frac{2{\pi}k}{N}}(2m+1)}}} $
$ X(k)= X_0(k) + e^{-j{\frac{2{\pi}k}{N}}}X_1(k) $
Step 3: Define twiddle factor and find periodic version of X(k)
Notice: each N/2 point DFT is periodic with period N/2
So we have
$ X(k+ \frac{N}{2})= X_0(k+\frac{N}{2}) + e^{-j{\frac{2{\pi}}{N}}{(k+\frac{N}{2})}}X_1(k+\frac{N}{2}) $
$ X(k+ \frac{N}{2})= X_0(k+\frac{N}{2}) + e^{-j{\frac{2{\pi}k}{N}}}(-1)X_1(k+\frac{N}{2}) $
Let's define twiddle factors
$ W_N^k = e^{-j{\frac{2{\pi}k}{N}}} $
Then we can get the following expression
$ X(k+{\frac{N}{2}})= X_0(k) - e^{-j{\frac{2{\pi}k}{N}}}X_1(k) $
So we derive the a simple expression for the N point DFT
$ X(k)= X_0(k) + W_N^k X_1(K) $
$ X(k+{\frac{N}{2}})= X_0(k)- W_N^k X_1(K) $
- For k = 0,1,2 ... N/2-1
These two expressions interpretate the N point DFT by using the "divide -and - conquer DFT"
