Solution:

This algorithm is obtained by using the divide \& conquer approach.

To derive this algorithm we begin with $^2$ splitting the DFT formula into hoo summation g of which one involves the sum over the first $\mathrm{N} / 2$ data points and the second sum over the last N/2 data points.

First Stage Decimation:-

By the definition of DFT.

$\begin{aligned}\\ &x[k]=\sum_{n=0}^{N-1} x[n] W_N^{k n} \\\\ &x[k]=\sum_{n=0}^{N / 2-1} x[n] w_N^{k n}+\sum_{n=N / 2}^{N-1} x[n] w_N^{k n} \\. \end{aligned}\\ $

$\begin{aligned}\\ &\text { Consider Second Sum: }\\\\ &\sum_{n=N / 2}^{N-1} x[n] W_N^{k n}\\\\ &\text { substitute } n=m+N / 2\\\\ &\therefore n=\frac{N}{2} ; \quad m=\frac{N}{2}-\frac{N}{2}=0 \text {. }\\\\ &n=N-1 ; \quad m=N-1-\frac{N}{2}=\frac{N}{2}-1\\ \end{aligned}\\ $

$\begin{aligned} &\text { By change of variable }\\ &\therefore \sum_{n=0}^N x\left[n+\frac{N}{2}\right] W_k^{k(n+\pi / 2)}\\ &x[k]=\sum_{n=0}^{\frac{N}{-1}} x[n] w_H^{k n}+\sum_{n=0}^{\frac{N}{-1}} x\left[n+\frac{N}{2}\right] w_H^{k(n+N / 2}\\ &\left.=\sum_{n=0}^{\frac{n}{2}-1} x[n] w_s^{k n}+v_N^{k+k_{n=0}^{N / l_2-1}}\right][n+N / 2] w_N^{k n}\\ &V_H^{K N / 2}=e^{-j \frac{2 \pi}{M} \cdot \frac{N}{2} \cdot k} \end{aligned}$

$\begin{gathered} =\left[e^{-j 1 \pi}\right]^k=(-1)^k \\ x[k]=\sum_{n=0}^{\frac{N}{2}-1} x[n] w_n^{k n}+(-1)^k \sum_{n=0}^{\frac{N}{2}-1} x[n+N / 2] w_N^{k n} \end{gathered}$

Now let us split (decimate) $x[k]$ into the even 2 odd-numbered samples.

$\begin{gathered} x[2 k]=\sum_{n=0}^{\frac{N}{2}-1}\left[x[n]+(-1)^{2 k} x\left[n+\frac{N}{2}\right]\right] w_N^{2 k n} \\ (-1)^{2 k}=1 \text { \& } W_H^{2 k n}=W_{N / 2}^{k n} \end{gathered}$

$\begin{aligned} x[2 k+1] &=\sum_{n=0}^{\frac{N}{2}-1}\left[x[n]+(-1)^{2 k+1} x\left[n+\frac{N}{2}\right]\right] W_N^{(2 k+1) n} \\ (-1)^{2 k+1} &=-1, W_N^{(2 k+1) n}=w_N^{2 k n} W_N^n=W_{N / 2}^{k n} W_N^n \\ x[2 k+1] &=\sum_{n=0}^N\left[[x[n]-x[n+N / 2]] W_N^n\right] W_{N / 2} \\ \quad k=0,1 \ldots \frac{N}{2}-1 \end{aligned}$

Let us define $\frac{N}{2}$ point sequences $g_1[n] \& g_2[n]$ as

$\begin{aligned} &g_1[n]=x[n]+x\left[n+\frac{N}{2}\right] \\ &g_2[n]=\left[x[n]-x\left[n+\frac{N}{2}\right]\right] W_N^N \\ &n=0,1 \ldots \frac{N}{2}-1 \end{aligned}$

then

$\begin{aligned} &G_1[k]=x[2 k]=\sum_{n=0}^{\frac{N}{2}-1} g_1[n] w_{N / 2}^{k n} \\ &G_2[k]=x[2 k+1]=\sum_{n=0}^{\frac{N}{2}-1} g_2[n] w_{N / 2}^{k n} \end{aligned}$

At this stage, we have decimated the sequence of N point DFT into two $\frac{N}{2}$ points BETs. given by $e q^n(7) \& 8$

Let us consider $N=8 &\ N=4$

Here we get even and odd $0 / p$ of x[k].

Thus decimation of sequence in frequency. Therefore it is called Decimation in Frequency Radix - 2 FFT algorithm.

Second Stage Decimation:-

$\begin{aligned} &G_1[k]=x[2 k]=\sum_{n=0_{N / 2}}^{N / 1} g_1[n] w_{N / 2}^{k n} \\ &=\sum_{n=0}^{N / 4} g_1[n] w_{N / 2}^{k n}+\sum_{n=N / 4}^k g_1[n] w_{N / 2}^{k n} \\ &g_{11}[n]=g_1[n]+g_1[n+N / 4] \\ &g_{12}[n]=\left[g_1[n]-g_1[n+N / 4]\right] w_N^{2 n}- \\ &G_{11}[k]=G_1[2 k]=\sum_{n=0}^{N / 4} g_{11}[n] w_{N / 4}^{k n} \\ &G_{12}[k]=G_1[2 k+1]=\sum_{N=1}^{N / 2-1} g_{12}[n] w_{N / 4}^{k n} \\ &G_2[k]=x[2 k+1]=\sum_{n=0}^{N / 2-1} g_2[n] w_{N / 2}^{k n} \end{aligned}$

$\begin{gathered} g_{21}[n]=g_2[n]+g_2[n+N / 4] \\ g_{22}[n]=\left[g_2[n]-g_2[n+N / 4]\right] W_N^{2 n}- \\ G_{21}[k]=G_2[2 k]=\sum_{n=0}^{N / 4} g_{21}[n] w_{N / 4}^{k n} \\ G_{22}[k]=G_2[2 k+1]=\sum_{n=1}^{N / 4} g_{22}^{-1}[n] w_{N / 4}^{k n} \end{gathered}$

Third Stage Decimation:

$G_{11}[k]=\sum_{n=0}^{N_k^{-1}} g_{11}[n] w_{N / h}^{k n}$

$\begin{aligned} &G_{11}[k]=\sum_{n=0}^1 g_{11}[0] w_2^{k n} \\ &G_{11}[k]=g_{11}[0]+w_2^k g_{11}[1] \\ &G_{11}[0]=g_{11}[0]+w_2^0 g_{11}[1] \\ &G_{1 f}[1]=g_{11}[0]+w_2^{\prime} g_{q_1}[1] \\ &G_{11}[1]=g_{11}[0]-g_{11}[1] \end{aligned}$