3
$\begingroup$

Suppose that the impulse response of a discrete time filter is $h[i]$ where $i=0,1,2,...,N-1$ and the input sequence to the filter is $x[i]$ for $i=0,1,2,.., M-1,$ what would be the length of output vector length?

I have concluded it is $N$ because according to discrete time convolution

\begin{align} y[0] &= x[0]h[0]\\ y[1] &= x[0]h[1]+x[1]h[0]\\ y[2] &= x[0]h[2]+x[1]h[1]+x[2]h[0]\\ \vdots &=\vdots\\ y[N] &= x[1]h[N-1]+x[2]h[N-2]+...+x[N]h[0] \end{align}

Is this correct?

$\endgroup$
  • $\begingroup$ assuming $h[i]=0$ and $x[i]=0$ outside of those two intervals you state, the length of the resulting linear convolution is the sum of the lengths of the two linear sequences going in minus 1. so the length of the output is $N+M-1$. $\endgroup$ – robert bristow-johnson Sep 26 '16 at 0:45
  • $\begingroup$ @robertbristow-johnson Thank you but could you elaborate your answer, I don't get it. What did I do wrong in calculating the output sequence? $\endgroup$ – Jack Sep 26 '16 at 0:49
  • $\begingroup$ well, you got $y[0]$ to $y[N]$ (after a correction from me). now ask yourself: $$ $$ what is $y[-1]$? and what is $y[N+1]$? $\endgroup$ – robert bristow-johnson Sep 26 '16 at 1:14
  • $\begingroup$ @robertbristow-johnson $$y[N+1] = x[0]h[N]+x[1]h[N-1]+...+x[N+1]h[0]$$ and y[-1] is zero..I still do not get why M appears in the length of vector. We have to some how get to y[N+M-1] $\endgroup$ – Jack Sep 26 '16 at 2:05
  • $\begingroup$ Continuing on that line of reasoning, in your expression for $y[N+1]$, if $h[i]=0$ outside $i=0,1,2,\dots,N-1$, what happens to $x[0]h[N]$? Then if you keep going with $y[N+2]$, $y[N+3]$, ... do you observe a pattern? What do you think will eventually happen (and when)? $\endgroup$ – SleuthEye Sep 26 '16 at 2:38
3
$\begingroup$

The output $y$ is convolution of $x[n]$ and $h[n]$:

$$y[n]=\sum_{l=-\infty}^{l=+\infty} x[l]h[n-l]$$ As you said, let's assume only $h[0],\cdots,h[N-1]$ and $x[0],\cdots,x[M-1]$ are non-zero.

  • When $0\le l\le N-1$, then we have a non-zero $x[l]$.
  • Now consider $h[n-l]$. As long as $0 \le n-l \le M-1$, then we have a non-zero $h[n-l]$.

add up the sides of the two inequalities to get

$$0\le n\le N+M-2$$

as the set of indices where $y[n]$ is nonzero. There are $N+M-2+1=N+M-1$ terms.

$\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.