6
$\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$
7
  • $\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$ Commented Sep 26, 2016 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
    Commented Sep 26, 2016 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$ Commented Sep 26, 2016 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
    Commented Sep 26, 2016 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
    Commented Sep 26, 2016 at 2:38

1 Answer 1

9
$\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 and acknowledge you have read our privacy policy.

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