0
4.7kviews
Compute the DFT of the sequence x(n) = {1, 2, 2, 2, 1, 0, 0, 0} using DIF-FFT algorithm. Compare the computational complexity of above algorithm with DFT.
0
244views

Output of stage-1:

$S_1 (0)=x(0)+x(4)=1+1=2$

$S_1 (1)=x(1)+x(5)=2+0=2$

$S_1 (2)=x(2)+x(6)=2+0=2$

$S_1 (3)=x(3)+x(7)=2+0=2$

$S_1 (4)=[x(0)-x(4) ] W_8^0=(1-1) W_8^0=0$

$S_1 (5)=[x(1)-x(5) ] W_8^1=(2-0)(0.707-0.707j)=1.414-1.414j$

$S_1 (6)=[x(2)-x(6) ] W_8^2=(2-0)(-j)=-2j$

$S_1 (7)=[x(3)-x(7) ]=(2-0)(-0.707-j0.707)=-1.414-1.414j$

Output of stage- 2

$S_2 (0)=S_1 (0)+S_1 (2)=2+2=4$

$S_2 (1)=S_1 (1)+S_1 (3)=2+2=4$

$S_2 (2)=[S_1 (0)-S_1 (2) ] W_8^0=(2-2)(1)=0$

$S_2 (3)=[S_1 (1)-S_1 (3) ] W_8^2=(2-2)(-j)=0$

$S_2 (4)=[S_1 (4)+S_1 (6) ]=(0-2j)=-2j$

$S_2 (5)=[S_1 (5)+S_1 (7) ]=(1.414-1.414j-1.414-1.414j)(=2.818j$

$S_2 (6)=[S_1 (4)-S_1 (6) ] W_8^0=(0+2j)(1)=2j$

$S_2 (7)=[S_1 (5)-S_1 (7) ] W_8^2=(1.414-1.414j+1.414+1.414j)(-j)=-2.828j$

Final Output

$X(0)=S_2 (0)+S_2 (1)=4+4=8$

$X(4)=S_2 (0)-S_2 (1)=4-4=0$

$X(2)=S_2 (2)+S_2 (3)=0+0=0$

$X(6)=S_2 (2)-S_2 (3)=0-0=0$

$X(1)=S_2 (4)+S_2 (5)=-2j-2.828j=-4.828j$

$X(5)=S_2 (4)-S_2 (5)=-2j+2.828j=0.828j$

$X(3)=S_2 (6)+S_2 (7)=2j-2.828j=-0.828j$

$X(7)=S_2 (6)-S_2 (7)=2j+2.828j=4.828j$

$X(K)={8,-4.828j,0,-0.828j,0,0.0828j,0,4.828j}$

Computational Complexity [N=8]

For DFT

$No.of complex multiplication =N^2=64$

$No.of complex addition =N(N-1)=56$

For FFT

$No.of complex multiplication = \frac{N}{2} log_2⁡N$

$=4log_2⁡(8)=12$

$No.of complex addition=N log_2⁡N$

$=8log_2⁡8=24$