15 September, 2013

The basics of convolution

  • What is convolution and where it is used?
  • Can I see an explained example of convolution?
  • How can I do convolution in MATLAB?

Convolution is a mathematical operation on two functions, or in our case on two vectors. In this tutorial the simplest 1D convolution is to be explained, but of course this operation works for higher dimensions as well. It can be used for several tasks, for example signal or image processing. First we need to understand what the convolution does. Have a look at the definition:

$$
y_{k} = \sum_{n = 0}^{N - 1}h_{n}\,\cdot\,x_{k-n}
$$

There are two input signals, x and h, while N is the number of elements in h. The output vector is y. The subscripts denote the nth element of the vector.

Here is an example, how the output shall be calculated, when h has three elements:

$$
\begin{aligned}
y_{0} & = h_{0} \cdot x_{0} \\
y_{1} & = h_{1} \cdot x_{0} + h_{0} \cdot x_{1} \\
y_{2} & = h_{2} \cdot x_{0} + h_{1} \cdot x_{1} + h_{0} \cdot x_{2} \\
y_{3} & = h_{2} \cdot x_{1} + h_{1} \cdot x_{2} + h_{0} \cdot x_{3} \\
\vdots
\end{aligned}
$$

There is an interesting pattern. We got the same results if we wrote down the elements of h in reversed order as [h2 h1 h0], and slid that window along x. During this sliding in each step we multiply the coherent elements and summarize them: the result will be the appropriate element of the output y vector.

Here is an explained real-life example:

$$
\begin{aligned}
x & = \left[
\begin{array}{c} 1 \, 2 \, 1 \, 3
\end{array}
\right]
\\
h & = \left[
\begin{array}{c}
2 \, 0 \, 1
\end{array}
\right]
\end{aligned}
\\
\begin{array}{c|cccccccc|r}
k & \it{0} & \it{0} & 1 & 2 & 1 & 3 & \it{0} & \it{0} & \it{y_{k}}\\
\hline
0 & 1 & 0 & 2 & & & & & & 2 \cdot 1 = 2\\
1 & & 1 & 0 & 2 & & & & & 2 \cdot 2 = 4\\
2 & & & 1 & 0 & 2 & & & & 2 \cdot 1 + 1 \cdot 1 = 3\\
3 & & & & 1 & 0 & 2 & & & 2 \cdot 3 + 1 \cdot 2 = 8\\
4 & & & & & 1 & 0 & 2 & & 1 \cdot 1 = 1\\
5 & & & & & & 1 & 0 & 2 & 1 \cdot 3 = 3\\
\end{array}
$$

Zeros are supposed where x is not defined – in case of negative indices or overindexing. The reversed h vector is slid along, the multiplications and additions are visualized in the yk column.

Convolution can be used efficiently for several different tasks, it is a fast and well implemented operation.

Convolution in MATLAB

In MATLAB we use the conv function to do the convolution. To apply this to our example above, use the following code:

>> x = [1, 2, 1, 3];
>> h = [2, 0, 1];
>> y = conv(x, h)
y = 2 4 3 8 1 3

Convolution is commutative, the order of the operands makes no difference:

>> y = conv(h, x)
y =
2 4 3 8 1 3

The third parameter of the conv function defines which region to get back from the resulting signal. There are three different modes:

  • Option same outputs a vector of the same length as the input.
  • Option full gives back the whole result set.
  • Option valid returns those elements only which were fully covered, so there was no sliding off during the windowing.

Play with the different options and compare the following results with the explained example above:

>> x = [1, 2, 1, 3];
>> h = [2, 0, 1];
>> y = conv(x, h, 'same')
y =
4 3 8 1

>> y = conv(x, h, 'full')
y =
2 4 3 8 1 3

>> y = conv(x, h, 'valid')
y =
3 8

That was all for now. In the next posts there will be some practical usages of the convolution.

         

New comment

comments powered by Disqus