# How many non-zeros samples in convolution

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?

• 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 ? – Gilles Mar 27 '16 at 0:58
• Yeah I want to know the non-zero samples in a[n]. – 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$.
• 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. – Tendero Mar 27 '16 at 1:20 • Yeah but now let's consider the case I mention, don't we get 50 non-zero samples? – Ali Ammar Mar 27 '16 at 1:23 • 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$. – Tendero Mar 27 '16 at 1:25 • 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. – 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\$.