1
$\begingroup$

Let's say that we have two sequences, input sequence $x(n) = [0121]$ 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) = [0121] \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!

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

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
| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.