0
26kviews
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.
1 Answer
written 6.5 years ago by | • modified 6.5 years ago |
Output of stage – 1
S1(0)=x(0)+x(4)=1+5=6
S1(1)=x(0)-x(4)=1-5=-4
S1(2)=x(2)+x(6)=3+7=10
S1(3)=x(2)-x(6)=3-7=-4
S1(4)=x(1)+x(5)=2+6=8
S1(5)=x(1)-x(5)=2-6=-4
S1(6)=x(3)+x(7)=4+8=12
S1(7)=x(3)-x(7)=4-8=-4
*Output of stage 2 *
S2(0)=S1(0)+W08S1(2)=6+(1)(10)=16
S2(1)=S1(1)+W28S1(3)=−4+(−j)(−4)=−4+4j
S2(2)=S1(0)−W08S1(2)=6−(1)(10)=−4
S2(3)=S1(1)−W28S1(3)=−4−(−j)(−4)=−4−4j
S2(4)=S1(4)+W08S1(6)=8+(1)(12)=20
S2(5)=S1(5)+W28S1(7)=−4+(−j)(−4)=−4+4j
$S_2 (6)=S_1 (4)-W_8^0 S_1 …