0
1.8kviews
By using FFT - 2FFT find linear convolution,

$x (n) = {2, 1, 2, 1}, h (n) = {1, 2, 3, 4} \ x (n) = {2, 1, 2, 1} h (n) = {1, 2, 3, 4} $

1 Answer
0
9views

L = number of samples of x (n) = 4

M = number of samples of h (n) = 4

$L + M - 1 = 4 + 4 -1 = 7$

Now, first we calculate DFT of x (n) by DIT – FFT,

enter image description here

$S_0 = x (0) + x (1) = 2 + 2 = 4 \\ S_1 = x (0) – x (2) = 2 – 2 = 0 \\ S_2 = [x (1) + x (3)]w^0_4 = 1 + 1 = 2 \\ S_3 = [x (1) – x (3)]w^1_4 = (1 - 1)(-j) = 0 $

Final output will be,

$X (0) = S_0 + S_2 = 4 + 2 = 6 \\ X (1) = S_1 + S_3 = 0 + 0 = 0 \\ X (2) = S_0 - S_2 = 4 - 2 = 2 \\ X (3) = S_1 – S_3 =0 - 0 = 0 \\ X (k) = \{6, 0, 2, 0\}$

Now , we will obtain DFT of h (n), similarly, by using same flow graph

$S_0 = h (0) + h (2) = 3 + 1 = 4 \\ S_1 = h (0) – h (2) = 1 – 3 = -2 \\ S_2 = [h (1) + h (3)]w^0_4 = 2 + 4 = 6 \\ S_3 = [h (1) – h (3)]w_4^1 = [2 - 4] (-j)= 2j$

The final output is,

$H (0) = S_0 + S_2 = 4 + 6 = 10 \\ H (1) = S_1 + S_3 = -2 + 2j \\ H (2) = S_0 – S_2 = 4 – 6 = -2 \\ H (4) = S_1 – S_3 = -2 – 2j \\ H (k) = \{10, -2 + 2j, -2, -2 -2j\}$

Now, multiply H (k) and X (k)

Let y (k) = H (k) . X (K)

$Y (k) = \{80, 0, -4, 0\}$

Now, by performing 2FFT

enter image description here

$S_0=\dfrac 14y(0)+\dfrac 14y(2)=15+(-1)=14 \\ S_1=\dfrac 14y(0)-\dfrac 14y(2)=15-(-1)=16\\ S_2=[\dfrac 14y(1)+\dfrac 14y(3)]\times 1=0 \\ S_3=[\dfrac 14y(1)+\dfrac 14y(3)]j=0$

Now, Final output is given as,

$y (0) = S_1 + S_2 = 14 + 0 = 14 \\ y (1) = S_1 + S_3 = 16 + 0 = 16 \\ y (2) = S_0 – S_2 = 14 \\ y (3) = S_1 – S_3 = 16 – 0 = 16 \\ y (n) = \{14, 16, 14, 16\} $

Please log in to add an answer.