# Response of a system using DFT

Let's say that we have two sequences, input sequence $$x(n) = $$ and impulse response of a given system $$h(n) = [0, 1, -1, 1]$$. I need to find response of this system to given input sequence. After that, i need to calculate linear convolution of given sequences.

If we denote the response as $$y(n)$$ we have $$y(n)=h(n)*x(n)$$, which means that, due to convolution theorem, in frequency domain we have $$Y(k)=H(k)X(k)$$. From this, we can find $$y(n) = IDFT(Y(k))$$.

Considering the fact that i need to find convolution of given sequences, meaning $$y(n)=h(n)*x(n)$$, that would mean that it should yield same result as when i was doing this by using DFT. However, my final results don't match at all.

$$x(n) =  \Rightarrow X(k) = [4, -2, 0, -2] \\ h(n) = [0, 1, -1, 1] \Rightarrow H(k) = [1, 1, -3, 1] \\ Y(k)=X(k)H(k) = [4, -2, 0, -2] \Rightarrow y(n)=[0, 1, 2, 1]$$

On the other hand, convolution of given sequences gives the following result:

$$y(n) = h(n)*x(n) = [0, 0, 1, 1, 0, 1, 1]$$

Not only that result is completely wrong, but also dimensions of vectors i got as a result are not the same. What am i doing wrong? Any help appreciated!

• You need to do zero-padding before computing the DFTs in order to use the DFTs to calculate the linear convolution. – Dilip Sarwate Jun 4 at 20:28

It will match for circular convolution modulo $$N$$, where $$N$$ is 4 here. For finite length sequences product of DFT of 2 sequences is equivalent to DFT of circular-convolution of the 2 sequences.

>> cconv([0,1,2,1], [0,1,-1,1], 4)

ans =

0     1     2     1


>>ifft(fft([0,1,2,1]).*fft([0,1,-1,1]))

ans =

0     1     2     1