0
Compute DFT of sequence $x(n) = \{1, 2, 2, 2, 1, 0, 0, 0\}$ using DIT-FFT algorithm.

Mumbai University > EXTC > Sem 6 > Discrete Time Signal Processing

Marks : 10

Year : DEC 2015

0
0

By signal flow graph of 8 point DIT – FFT, Output stage I :-

$g (0) = x (0) + x (4) = 1 + 1 = 2 \\ g (1) = x (1) + x (5) = 2 + 0 = 2 \\ g (2) = x (2) + x (6) = 2 + 0 = 2 \\ g (3) = x (3) + x (7) = 2 + 0 = 2 \\ g (4) = [x (0)- x (4)] w^0_8 = [1-1] = 0 \\ g (5) = [x (1) – x (5)]w^1_8= [2-0] (0.707 – j0.707) = 1.414 – j1.414\\ g (6) = [x (2) – x (6)]w^2_8 = [2 - 0] (-j) = -2j \\ g (7) = [x (3) – x (7)]w^3_8 = [2 - 0] (-0.707 – j0.707) = -1.414 – j1.414$

Output stage 2 :-

$h (0) = g (0) + g (2) = 2 + 2 = 4 \\ h (1) = g (1) + g (3) = 2 + 2 = 4 \\ h (2) = [g (0) – g (2)]w^0_8 = 0 \\ h (3) = [g (1) – g (3)]w^2_8 = 0 \\ h (4) = g (4) – g (6) = -2j \\ h (5) = g (5) – g (7) = (1.414 – j1.414) + (-1.414 – j 1.414) = -j2.828 \\ h (6) = [g (4) – g (6)]w^0_8 = 2j \\ h (7) = [g (5) – g (7)]w^2_8 = [(1.1=414 – j1.414)- (-1.414 – j 1.414)] (-j) = -j2.828$

Final output:-

$x (0) = h (0) + h (1) = 4+4 = 8 \\ x (1) = h (4) + h (5) = -2j –j2.828 = - j4.828 \\ x (2) = h (2) + h (3) = 0 \\ x (3) = [h (6)+h (7)]w^0_8 = [2j – j2.828]1 = -j0.828 \\ x (4) = [h (0) + h (1)]w^0_8 = [4 - 4] = 0 \\ x (5) = [h (4) + h (5)]w^0_8 = [-2j + j2.828] = j0.828 \\ x (6) = [h (2) + h (3)]w^0_8 = 0 \\ x (7) = [h (6) + h (7)]w^0_8 = [2j + j2.828] = j4.828 \\ x (k) = \{8, -j4.828, 0, -j0.828, 0, j0.828, 0, j4.282\}$

0