**1. Concept**

Convolution is used in signal processing and analysis.

We can use convolution to construct the output of system for any arbitrary input signal, if we know the impulse response of system.

**2. Definition**

The mathematical form of convolution in discrete time domain;

$y[n]=x[n]*h[n]=\sum_{k=-\infty }^{+\infty }x[k].h[n-k]$

where:

$x[n]$ is input signal

$h[n]$ is impulse response, $h[n-k]$ time shifted

$y[n]$ is output

* denotes convolution

In order to understand the meaning of convolution, we have to take a look on impulse response and impulse decomposition.

**3. Impulse decomposition**.

The input signal is decomposed into simple additive components (in general, weighted sum of basis signals). And the system response of the input signal is the additive output of these components passed through the system.

We often use impulse (delta) functions for the basis signals.

Example how a signal is decomposed into a set of impulse (delta) functions:

**Figure: input signal decomposition**

1, & n=0\\

0, & n\neq 0

\end{matrix}\right.$

So

$x[0] = x[0].\delta [n] = 2\delta [n]$

$x[1] = x[1].\delta [n-1] = 3\delta [n-1]$

$x[2] = x[2].\delta [n-2] = 1\delta [n-2]$

because

$\delta [n-1]$ is 1 at n=1 and zeros at others.

Then

$x[n]$ can be represented by adding 3 shifted and scaled impulse functions.

$x[n] = x[0].\delta [n] +x[1].\delta [n-1]+x[2].\delta [n-2]=\sum_{k=-\infty }^{+\infty }x[k].h[n-k]$

**4. Impulse Response**

It is the output of a system resulting from an impulse input.

**Figure: h[n] is impulse response**

**Figure: the response of a time-shifted impulse function is also a time-shifted response, shifted by K**

**Figure: a scaled in input signal causes a scaled in the output (linear), c is constant**

**Figure: 3 additive components input, 3 additive components output**

**Figure: convolution equation**

$x[n]=\sum x[k].\delta [n-k]\\

y[n]=\sum x[k].h [n-k]$

It means a signal is decomposed into a set of impulses and the output signal can be computed by adding the scaled and shifted impulse responses.

Convolution works on the linear and time invariant system.

**5. Convolution in 1D**

Consider example:

$x[n] = \{3, 4, 5\}$

$h[n] = \{2, 1\}$

**Figure: x[n]**

**Figure: h[n]**

$y[n]=x[n]*h[n]=\sum_{k=-\infty }^{+\infty }x[k].h[n-k]$

We have:

$y[0]=x[0].h[0-0]=3x2=6$

$y[1]=x[0].h[1-0]+x[1].h[1-1]=3x2+4x2=14$

$y[2]=x[0].h[2-0]+x[1].h[2-1]+x[2].h[2-2]=3x0+4x1+5x2=14$

$y[3]=x[0].h[3-0]+x[1].h[3-1]+x[2].h[3-2]+x[3].h[3-3]=4x0+5x1=5$

$y[4]=x[0].h[4-0]+x[1].h[4-1]+x[2].h[4-2]+x[3].h[4-3]+x[4].h[4-4]=0$

**Figure: y[n]**

$y[i]=x[i]h[0]+x[i-1]h[1]+...+x[i-k]h[k]$

If you face the boundary such as x[-1],x[-2] you can skip the convolution at the boundary or pad 0 to them.

**6. Convolution in 2D**

2D convolution is extension of 1D convolution. It convolves both horizontal and vertical directions. It is used in image processing.

**Figure: impulse function in 2D**

$\delta [m,n]=\left\{\begin{matrix}

1, & m,n=0\\

0, & m,n\neq 0

\end{matrix}\right.$

Here, the matrix uses [column, row] form.

A signal can be decomposed into a sum of scaled and shifted impulse functions.

$x[m,n]=\sum_{j=-\infty }^{+\infty}\sum_{i=-\infty }^{+\infty}x[i,j].\delta [m-i,n-j]$

and the output is:

$y[m,n]=x[m,n]*h[m,n]=\sum_{j=-\infty }^{+\infty}\sum_{i=-\infty }^{+\infty}x[i,j].h [m-i,n-j]$

The index of kernel matrix can be negative:

**Figure: a 3x3 matrix with indices -1,0,1, with origin is at middle of kernel.**

$

y[1,1]=\sum_{j=-\infty }^{+\infty}\sum_{i=-\infty }^{+\infty}x[i,j].h [1-i,1-j]=\\

x[0,0].h[1-0,1-0]+x[1,0].h[1-1,1-0]+x[2,0].h[1-2,1-0]\\

+ x[0,1].h[1-0,1-1]+x[1,1].h[1-1,1-1]+x[2,1].h[1-2,1-1]\\

+ x[0,2].h[1-0,1-2]+x[1,2].h[1-1,1-2]+x[2,2].h[1-2,1-2]

$