0
4.2kviews
Find DFT of $x(n)=2^n$ using the 8-point DIT-FFT algorithm.
0
332views

Solution:

\begin{aligned} x[n] &=2^n \\\\ &=\{1,2,4,8,16,32,64,128\} .\\ \end{aligned}\\

\begin{aligned}\\ &x[k]=\sum_{n=0}^{N / 1} x[n] W_N^{k n} \\\\ &W_8^0=e^{-j 2 \pi / 8 \cdot 0}=0,1 . \cdot N-1 \\\\ &W_8^1=e^{-j 2 \pi / 8 \cdot 1}=0.707-j 0.707 \\\\ &W_8^2=e^{-j 2 \pi / g^2 \cdot 2}=-j \\\\ &W_8^3=e^{-j 2 \pi / 8 \cdot 3}=-0.707-j 0.707\\ \end{aligned}\\

Stage I $O / P$.

\begin{aligned} &V_{11}[0]=x[0]+x[4]=17 \\\\ &V_{11}[1]=x[0]-x[4]=-15 \\\\ &V_{12}[0]=x[2]+x[6]=68 \\\\ &V_{12}[1]=x[2]-x[6]=-60 \\\\ &V_{21}[0]=x[1]+x[5]=34 \\\\ &V_{21}[1]=x[1]-x[5]=-30 \\\\ &V_{22}[0]=x[3]+x[7]=186 \\\\ &V_{22}[1]=x[3]-x[7]=-120\\ \end{aligned}\\

\begin{aligned} &\text { Stage II o/P:- } \\ \\ &F_1[k]=V_{11}[k]+W_N^{2 k} V_{12}[k] \ \\\ &F_1[k+N / 4]=V_{11}[k]-W_N^{2 k} V_{12}[k] \\ \\ &F_1[0]=V_{11}[0]+W_8^0 V_{12}[0]=85 \\ \\ &F_R[k]=V_{11}[1]+W_8^2 V_{12}[1]=-15+j 60 \ \\\ &F_2[k]=V_{27}[k]+W_N^{2 k} V_{22}[k] \ \\\ &F_2[k+N / 4]=V_{21}[k]-W_N^{2 k} V_{22}[k] \\ \end{aligned} \\

\begin{aligned}\\ &\text { Stage III opP:- }\\\\ &x[k]=F_1[k]+W_N^k F_2[k]\\\\ &x[k+k / 2]=F_1[k]-w_N^k F_2[k]\\\\ &x[0]=F_1[0]+W_8^0 F_2[0]\\\\ &=85+170\\\\ &=255\\ \end{aligned}\\

\begin{aligned}\\ x[1] &=F_1[1]+W_8 F_2[1] \\\\ &=(-15+j 60)+(0.707-j 0.707) \\\\ &=-(-30+j 120) \\\\ &=45+j 60-21.21+j 84.84+j 21.21 \\\\ &=84.84\\ \end{aligned}\\

\begin{aligned} \times[2] &=F_1[2]+w_8^2 F_2[2] \\\\ &=-51-j(-102) \\\\ &=-51+j 102 \\\\ \times[3] &=F_1[3]+w_8^3 F_2[3] \\\\ &=-15-j 60+(-0.707-j 0.707)(-30-j 120) \\\\ &=-15-j 60+21.21+j 84.84+j 21.21-84.84\\ \\ &=-78.63+j 46.05\\ \end{aligned}\\

\begin{aligned} &x[4]=F_1[0]-W_8^0 F_2[0]\\ &=85-170\\ &=-85\\ &x[5]=F_1[1]-W_8^{\prime} F_2[1]\\ &=-15+j 60-(0.707-j 0 \cdot 707)(-30+j 120)\\ &=-15+j 60+21.21-j 84.84-j 21.21-84.84\\ &=-78.63-j 46.05\\ &x[6]=F_1[2]-W_2^2 F_2[2]\\ &=-51+j(-102)\\ &=-51-j 102 \end{aligned}

\begin{aligned}\\ x[7]=& F_1[3]-W_8^3 F_2[3] \\\\ &=-15-j 60-(-0.707-j 0.707)(-30-j 120) \\\\ &=-15-j 60-21.21-j 84.84-j 21.21+84.84 \\\\ &=48.63-j 166.05 \\\\ x[k]=&\{255,48.63+j 166.05,-51+j 102,-78.63+j 4.05\\\\ &-85,-78.63-j 46.05,-51-j 102,+48.63-j 166.05\}\\ \end{aligned}\\