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.

3.2kviews

written 7.2 years ago by

teamques10 ★ 70k

• modified 7.1 years ago

enter image description here

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 …

Create a free account to keep reading this post.

and 5 others joined a min ago.

ADD COMMENT EDIT