# Understanding Convolution

Take:

$$(u*v)(k) = \sum_{i=-\infty}^\infty u(i)v(k-i).$$

The $k$ is there, it's because you want to define $$\ldots\ldots, (u*v)(-3), (u*v)(-2), (u*v)(-1), (u*v)(0), (u*v)(1), (u*v)(2), (u*v)(3), \ldots\ldots >$$ etc. The number in the parentheses is $k$. Thus, for example, when $k=4$, we have \begin{align} (u*v)(4) = \sum_{i=-\infty}^\infty u(i)v(4-i) \end{align} $$= \cdots\cdots+u(-3)v(7)+u(-2)v(6)+u(-1)v(5)+u(0)v(4)+u(1)v(3)+u(2)v(2) >$$ $$\phantom{={}} {}+u(3)v(1)+ u(4)v(0) + u(5) v(-1) + u(6)v(-2)+u(7)v(-3)+u(8)v(-4)+\cdots>\cdots. >$$

Could you give examples of what the 'k' value could stand for? Can it only be time offset?

Could you give an intuitive explaination why you need to multiply u(-3) [a point left from the y-axes] with v(7) [a point right from the y-axes]! And not u(-3) with v(-3) for example? With a diagram for example.

I think the reason you are getting confused is that you are only considering the convolution of two signals, whereas convolution is not usually between signals but between a signal and an impulse response.

The best way to visualise it is probably with a filter. For example, in we can see that the input comes in, and is multiplied by $b_0$ to give its contribution to the output $y$. Then in the next time step, that input value is multiplied by $b_1$ to give its contribution to the output, and so forth. In this case your $k$ variable specifies which time in the output sequence you want. The output signal is given by $y[n] = (x * b)[n]$.

For example, consider the case of $n=4$ (that's the same as $k=4$ in your example). That means we're looking at the 4th time step (since time = 0). So the value at the input is $x$, the fourth input value; the value to the right of the first $z^{-1}$ block is the previous input value $x$; the value to the right of the next $z^{-1}$ block is $x$; and so forth. The output $y$ will be given by $$y = xb_0 + xb_1 + xb_2 + xb_3 + \cdots + x[-3]b_7 + \cdots$$ which you should be able to see is the discrete convolution sum, and includes the product of $x[-3]$ with $b$.

Any linear filter or transfer function can be implemented as a convolution, where the output is given by the convolution of the input with the system impulse response. Try reading up on convolution in a text book, and look particularly at the sliding-strip method of calculating it, which might help with your visualisation.

• So, b0 stands for k (or in this case n) = 0 and b1 stands for n/k=1, etc? And what does $z^-1$ stand for in the diagram? – user1095340 Apr 1 '13 at 13:13
• @user1095340 $z^{-1}$ means one time step delay. Consider $b_0$ as $b$, etc, so no, $b_0$ doesn't stand for $k=0$. I'll update the answer a bit. – lxop Apr 1 '13 at 20:11

It is the definition of convolution operation, i.e :

$$(u*v)(k) \stackrel{\mathrm{def}}{=} \sum_{i=-\infty}^\infty u(i)v(k-i)$$

and this definition is not arbitrary. $k$ simply stands for the independent variable ; in some extents represents time and sometimes other quantities.

for example when multiplying two polynomials, the coefficients of the product are given by the convolution of the original coefficient sequences ( extended with zeros) . (Cauchy product) . (here $k$ does not represent time!)

In the theory of linear time-invariant systems ,you can derive the response of the system as the convolution of input function with impulse response of the system. So you can arrive at the above definition for convolution in this way too.(here , k stands for time,)

also , convolution doesn't add any new frequencies to the fourier spectrum of the convolved signals and the resulting signal spectrum is the product of the two spectrums. If you start from this , you can arrive at the definition of convolution.(convolution theorem)

• "for example when multiplying two polynomials, the coefficients of the product are given by the convolution of the original coefficient sequences ( extended with zeros) . (Cauchy product) . " I don't understand the Cauchy product. – user1095340 Apr 1 '13 at 2:01

I guess one misunderstanding that you had is the only reason we need to multiply $u(-3)$ and $v(7)$ is because $(u*v)(4)$ requires all $x,y$ that $x+y=4$ in $u(x)v(y)$. If you take $x=i$ and $y=4-i$, you will see the same formulation as you described. We actually also need $u(-3)v(-3)$, but this term is for $(u*v)(0)$ rather than $(u*v)(4)$. If you want to see examples of convolutions, go to the convolution wiki page.

To some extend, I agree that the convolution operation is defined in a weird way that many students may ask why define convolution in this way but not something different. If this is also your problem, then you get the point: if you define convolution in other ways, then it is not convolution again. Of course, you may define an operation as $$(u\star v)(k)=\sum_{i=-\infty}^{\infty}u(i)v(k+i)$$, and this is so called cross-correlation. The only difference between the cross correlation and the convolution is that the convolution requires to first flip the signal then to compute the sum, while the cross-correlation computes the sum directly.

I think in most cases understanding the function of convolution or cross-correlation from a high level is good enough. Both convolution and cross-correlation do a similar thing, that is to compute some quality dependent on two signals. Because they can be easily computed (via FFT) and their computed qualities are meaningful to some extend.

• The problem is that I can't imagine how you would multiply a point -3 with 7.... Can't make a graph of the 2 functions... Can't visualize it... – user1095340 Apr 1 '13 at 2:02
• "to first flip the signal then to compute the sum, while the cross-correlation computes the sum directly." Can't visualize this either. Could you make a graph? – user1095340 Apr 1 '13 at 2:21
• @user1095340 Sheesh! Over on math.SE where you posted the identical question, I had pointed out two questions on this site (dsp.SE) which addressed precisely the questions you are asking such as "why is it important to flip the signal..." – Dilip Sarwate Apr 1 '13 at 2:41
• @DilipSarwate: But those answers say that there's no flipping. – user1095340 Apr 1 '13 at 13:18