If I have $b[n]$ of length 30 (30 non-zero samples) and $c[n]$ of length 40 (40 non-zero samples).

How many non-zero samples will $a[n]=b[n] * c[n]$ have? (Note '$*$' is a convolution).

I think there will be 30 non-zero samples. Am I correct?

  • $\begingroup$ So, you want to know not just the number of samples from the convolution sum, but how many of them are non-zero. Is it ? $\endgroup$ – Gilles Mar 27 '16 at 0:58
  • $\begingroup$ Yeah I want to know the non-zero samples in a[n]. $\endgroup$ – Ali Ammar Mar 27 '16 at 1:11

Actually, you can't say how many non-zero values $a[n]$ is going to have because, depending on the values that $b[n]$ and $c[n]$ take, $a[n]$ may equal 0 for some values of $n$ or not.

Nevertheless, I think that you want to know the length of the sequence $a[n]$. As a general rule, for two sequences of length $P$ and $L$, the linear convolution between them returns a sequence of length $N=P+L-1$. In this case, the maximum length of $a[n]$ would be $N=30+40-1=69$ (it can be less than 69 if $b[n]$ and $c[n]$ are such that the convolution between them returns null values for the first or the last values of $a[n]$).

The reason why the resulting sequence has a length of $N=P+L-1$ can be easily seen by doing the convolution graphically. Let's assume for simplicity (although the reasoning without these assumptions would be exactly the same) that the first non-zero value of $b[n]$ appears at $n=0$ and that the same thing happens with $c[n]$. Let's remember what the definition of convolution is:

$$a[n]=b[n]*c[n]=\sum\limits_{m=-\infty}^\infty b[m]c[n-m]$$

This means that we should have in mind $b[m]$ and $c[-m]$, and then start moving $c[-m]$ from $-\infty$ until we get our first non-zero value for $a[n]$. This happens for $n=0$. Then the two sequences always return some information until the last value of $b[m]$ is in the same spot as the first value of $c[n-m]$. This happens for $n=L+P-2=68$. So that leaves us with the length I wrote before: $N=69$.

  • $\begingroup$ My case is: a[n]= b[n] * c[n], length of b is 740 and it have 73 non-zero samples and length of c is 50 with 50 non-zero-samples. How many non-zero samples does a[n] have? $\endgroup$ – Ali Ammar Mar 27 '16 at 1:17
  • $\begingroup$ I don't get it. You said in your question that $b[n]$ had 30 non-zero values and that $c[n]$ had 40. Also, please use the '$' symbol to write mathematical expressions in the future. $\endgroup$ – Tendero Mar 27 '16 at 1:20
  • $\begingroup$ Yeah but now let's consider the case I mention, don't we get 50 non-zero samples? $\endgroup$ – Ali Ammar Mar 27 '16 at 1:23
  • $\begingroup$ No. As I wrote in the answer, the convolution between a sequence of length $P=740$ and $L=50$ would return a sequence of length $N=P+L-1=789$. $\endgroup$ – Tendero Mar 27 '16 at 1:25
  • 1
    $\begingroup$ There is no way to know how many zero-valued samples you get between $n=0$ and $n=P+L-2$ unless you specify which sequences are being convoluted. The only thing that can be known for certain is that $a[n]$ is zero for $n<0$ and for $n>N+P-2$, but what happens in the middle completely depends on the values $b[n]$ and $c[n]$ take. Nothing else can be said without knowing each single value of these two sequences. $\endgroup$ – Tendero Mar 27 '16 at 1:30

No, you aren't correct. Convolution is equivalent to multiplying polynomials, with a sequence of length $n$ corresponding to the coefficients of a polynomial (let's say for a variable called $x$) of degree $n-1$. So convolving sequences with length $n$ and $m$ is equivalent to getting a polynomial of degree $n-1+m-1$ corresponding to a sequence of length $n+m-1$.


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.