# Vector length output of discrete time convolution

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?

• 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$. Commented Sep 26, 2016 at 0:45
• @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?
– Jack
Commented Sep 26, 2016 at 0:49
• 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]$? Commented Sep 26, 2016 at 1:14
• @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]
– Jack
Commented Sep 26, 2016 at 2:05
• 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)? Commented Sep 26, 2016 at 2:38

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