0
23kviews
If x(n) = {1, 2, 3, 4, 5, 6, 7, 8}, Find X(k) using DIT-FFT algorithm. Compare the computational complexity of above algorithm with DFT.
6
2.9kviews

Output of stage – 1

$S_1$(0)=x(0)+x(4)=1+5=6

$S_1$(1)=x(0)-x(4)=1-5=-4

$S_1$(2)=x(2)+x(6)=3+7=10

$S_1$(3)=x(2)-x(6)=3-7=-4

$S_1$(4)=x(1)+x(5)=2+6=8

$S_1$(5)=x(1)-x(5)=2-6=-4

$S_1$(6)=x(3)+x(7)=4+8=12

$S_1$(7)=x(3)-x(7)=4-8=-4

*Output of stage 2 *

$S_2(0)=S_1 (0)+ W_8^0S_1 (2)=6+(1)(10)=16$

$S_2(1)=S_1 (1)+W_8^2 S_1 (3)=-4+(-j)(-4)=-4+4j$

$S_2 (2)=S_1 (0)-W_8^0 S_1 (2)=6-(1)(10)=-4$

$S_2 (3)=S_1 (1)-W_8^2 S_1 (3)=-4-(-j)(-4)=-4-4j$

$S_2 (4)=S_1 (4)+W_8^0 S_1 (6)=8+(1)(12)=20$

$S_2 (5)=S_1 (5)+W_8^2 S_1 (7)=-4+(-j)(-4)=-4+4j$

$S_2 (6)=S_1 (4)-W_8^0 S_1 (6)=8-(1)(12)=-4$

$S_2 (7)=S_1 (5)-W_8^2 S_1 (7)=-4-(-j)(-4)=-4-4j$

Final output

$X(0)=S_2 (0)+W_8^0 S_2 (4)=16+(1)(20)$

$X(1)=S_2 (1)+W_8^1 S_2 (5)=-4+4j+(0.707-j0.707)(-4+4j)$

$X(2)=S_2 (2)+W_8^2 S_2 (6)=-4+(-j)(-4)$

$X(3)=S_2 (3)+W_8^3 S_2 (7)=-4-4j+(-0.707-j0.707)(-4-4j)$

$X(4)=S_2 (0)-W_8^6 S_2 (4)=16-(1)(20)$

$X(5)=S_2 (1)-W_8^1 S_2 (5)=-4+4j-(0.707-j0.707)(-4+4j)$

$X(6)=S_2 (2)-W_8^2 S_2 (6)=-4(-j)(-4)$

$X(7)=S_2 (3)-W_8^3 S_2 (7)=-4-4j-(-0.707-j0.707)(-44j)$

$X(K)={36,-4+9.65j,-4+4j,-4+1.65j,-4,-4-1.65j,-4-4j,-4-9.65j}$