# Convolution - book

Other languages:
Series Geophysical References Series Digital Imaging and Deconvolution: The ABCs of Seismic Exploration and Processing Enders A. Robinson and Sven Treitel 5 http://dx.doi.org/10.1190/1.9781560801610 ISBN 9781560801481 SEG Online Store

What is the Z-transform? The Nth-order polynomial in Z given by

 {\displaystyle {\begin{aligned}B\left(Z\right)=b_{0}+b_{1}Z+b_{2}Z^{2}+b_{3}Z^{3}+\ldots +b_{N}Z^{N}\end{aligned}}} (6)

is the Z-transform of the finite-length causal impulse-response function ${\displaystyle b_{0},b_{1},b_{2},b_{N}}$. Similarly, the Z-transform of an infinite-length causal impulse-response function ${\displaystyle b\;=\;\{b_{0},\;b_{1},\;b_{2},\;\ldots \}}$ is the power series in Z given by

 {\displaystyle {\begin{aligned}B\left(Z\right)=b_{0}+b_{1}Z+b_{2}Z^{2}+....\end{aligned}}} (7)

What is convolution? Let us consider the action of the Nth-order causal FIR filter on an input given by the equally spaced sampled values ${\displaystyle x_{0},x_{1},x_{2},...,x_{M}}$. The numbers ${\displaystyle x_{n}}$ are going into the filter; that is, the input is as follows: ${\displaystyle x_{-1}}$ enters at time ${\displaystyle n=-1,x_{0}}$ enters at time ${\displaystyle n=0,x_{1}}$ enters at time ${\displaystyle n=1,x_{2}}$ enters at time n = 2, and so forth.

Coming out of the filter are the numbers ${\displaystyle y_{n}}$, that is, the output is as follows: ${\displaystyle y-1}$ emerges at time n = –1, ${\displaystyle y_{0}}$ emerges at time ${\displaystyle n=0,y_{1}}$ emerges at time ${\displaystyle n=1,y_{2}}$ emerges at time n = 2, and so forth.

The output is seen to be

 {\displaystyle {\begin{aligned}y_{n}=b_{0}x_{n}+b_{1}x_{n-1}\ +b_{2}x_{n-2}+\\dots+b_{N}x_{n-N}.\end{aligned}}} (8)

This expression is the discrete representation of the linear operation commonly known as convolution. In the literature, one often sees this operation represented by an integral rather than by a discrete summation. That is because analog filters operate in continuous time, which calls for an integral representation of the convolution operation. Because we are dealing here with discrete-time data, we must represent the convolution process by a summation. Thus, the output of the Nth-order causal FIR filter is obtainable by the discrete convolution of the input ${\displaystyle x_{0},x_{1},x_{2},\ldots ,x_{\rm {M}}}$, with the filter’s impulse-response coefficients ${\displaystyle b_{0},b_{1},b_{2},\ldots ,b_{N}}$. A more compact notation for convolution is

 {\displaystyle {\begin{aligned}y_{n}=\sum _{i=0}^{N}{b_{j}}x_{n-i},\end{aligned}}} (9)

where it is understood that ${\displaystyle y_{n}=0}$ when n falls outside the range ${\displaystyle n=0,1,2,\ldots ,M+N}$. Schematically, we have the block diagram shown in Figure 11a. Whenever we illustrate such an input-output relationship, we mean the following: The output y is equal to the convolution of the input x with the impulse-response function b.

What is the impulse-response function of two cascaded filters? When two filters are cascaded, or connected in tandem, we have the situation shown in Figure 11b. The output of the first filter is a * x, which is the input to the second filter. Hence, the output of the second filter is ${\displaystyle y=b*\left(a*x\right)}$. Thus, the two filters can be replaced with one filter, the impulse-response function h of which is the convolution of the impulse-response functions a and b of the two filters; that is, ${\displaystyle h=b*a}$. Therefore, the block diagram is equivalent to that shown in Figure 11c.

How is convolution carried out? Let us now describe the process of convolution. The convolution of the two signals ${\displaystyle a=\left\{a_{0},\ a_{1},\ a_{2}{,\ .\ .\ .}\right\}}$ and ${\displaystyle b=\left\{b_{0},\ b_{1},\ b_{2}{,\ .\ .\ .}\right\}}$ is obtained by holding one signal fixed and sliding the reverse of the other signal alongside it. At each position, the sum of the products is taken. The entirety of these sums gives a third signal that is the convolution of the two given signals. For example, hold a fixed and slide b. We obtain the first value

 {\displaystyle {\begin{aligned}\left\{a_{0},\ a_{1},\ a_{2},\ \cdots \right\}\\b=\left\{,\ \ b_{2},\ b_{1},\ b_{0}\right\}.\\a_{0}b_{0}\end{aligned}}} (10)
Figure 11.  (a) Block diagram for the action of a filter. (b) Two filters in tandem. (c) Two filters in tandem shown as one box.

We obtain the second value

 {\displaystyle {\begin{aligned}\{a_{0},\;a_{1},\;a_{2},\;...\}\\b=\left\{,\ \ b_{2},\ \ b_{1},\ \ b_{0}\right\}.\\a_{0}b_{1}+a_{1}b_{0}\end{aligned}}} (11)

We obtain the third value

 {\displaystyle {\begin{aligned}\left\{a_{0},\ a_{1},\ a_{2},\ \cdots \right\}\\\left\{\dots ,\ \ b_{2},\ b_{1},\ b_{0}\right\}.\\a_{0}b_{2}+a_{1}b_{1}+a_{2}b_{0}\end{aligned}}} (12)

The complete convolution is then

 {\displaystyle {\begin{aligned}c=a*b=\left\{c_{0},\ \ c_{1},\ \ c_{2},\ \ \cdots \right\}\mathrm {where} c_{n}=\sum _{k=0}^{\infty }{a_{k}}b_{n-k}.\end{aligned}}} (13)

(Note: The asterisk * used in this way - that is, as a binary operation between two time functions - denotes convolution.)

The above summation equation for convolution (but with the lower limit on the summation now being ${\displaystyle -\infty )}$ holds for the case in which the signals are noncausal. It also holds for complex valued signals. (Note that when two complex signals are convolved, the complex-conjugate of one or the other signal never is taken. In contrast, when two complex signals are crosscorrelated, the complex-conjugate of one or the other signal must be taken.)

To illustrate the use of this convolution formula, suppose that ${\displaystyle a=\left\{a_{0},\ a_{1}\right\}=\{2,1\}}$ and ${\displaystyle b=\left\{b_{0},\ b_{1}\right\}=\{{3},4\}}$. Each of these wavelets has two coefficients (i.e., it has length 2).

We see that the convolution is

 {\displaystyle {\begin{aligned}c=a*b=\left\{c_{0},\ \ c_{1},\ \ c_{2}\right\},\end{aligned}}} (14)

where

 {\displaystyle {\begin{aligned}c_{0}=a_{0}b_{0}=2\left({3}\right)=6,\end{aligned}}} (15)

 {\displaystyle {\begin{aligned}c_{1}=a_{0}b_{1}+a_{1}b_{0}=2\left({4}\right)+1\left({3}\right)=11,\end{aligned}}} (16)

and

 {\displaystyle {\begin{aligned}c_{2}=a_{1}b_{1}=l\left({4}\right)=4.\end{aligned}}} (17)

Hence,

 {\displaystyle {\begin{aligned}c=a*b=\{{6,}11,4\}.\end{aligned}}} (18)

We can show that convolution] is a folding operation. In fact, the German word for convolution is faltung, which means folding. To see how convolution can be performed by folding, let us construct the equation below (equation 19), whose entries are the products of the wavelets a and b (which are on the margins):

 {\displaystyle {\begin{aligned}{\begin{array}{*{20}c}{\begin{array}{l}\\\left.{\begin{array}{l}a_{0}\\a_{1}\\\end{array}}\right|\\\end{array}}&{\begin{array}{l}{\underline {b_{0}\;\;\;\;\;\;\;\;b_{1\;\;\;\;\;\;\;}}}\\a_{0}\;b_{0}\;\;\;\;a_{0}\;b_{1}\\a_{1}\;b_{0}\;\;\;\;\;a_{1}\;b_{1}\;\\\end{array}}\\\end{array}}\;{\rm {or}}\;\;{\begin{array}{*{20}c}{\begin{array}{l}\\\left.{\begin{array}{l}2\\1\\\end{array}}\right|\\\end{array}}&{\begin{array}{l}{\underline {3\;\;\;\;\;\;\;\;\;4\;}}\\6\;\;\;\;\;\;\;\;\;8\\3\;\;\;\;\;\;\;\;\;4\\\end{array}}\\\end{array}}.\end{aligned}}} (19)

Thus, we have the following table of entries (without the margins), which we are going to fold successively on the southwest-northeast diagonals:

 {\displaystyle {\begin{aligned}{\begin{array}{l}a_{0}\;b_{0}\;\;\;a_{0}\;b_{1}\;\;{\rm {or}}\;\;\;6\;\;\;3\\a_{1}\;b_{0}\;\;\;a_{1}\;b_{1}\;\;\;\;\;\;\;\;3\;\;\;4.\\\end{array}}\end{aligned}}} (20)

The element in the upper left corner, that is, ${\displaystyle a_{0}b_{0}}$, or 6, is ${\displaystyle c_{0}}$. Now fold this entry over, thus obtaining

 {\displaystyle {\begin{aligned}{\begin{array}{l}\;\;\;\;\;\;\;\;\;a_{0}\;b_{1}\;\;\;\;{\rm {or}}\;\;\;\;\;\;\;\;\;8\\a_{1}\;b_{0}\;\;\;a_{1}\;b_{1}\;\;\;\;\;\;\;\;\;\;3\;\;\;4.\\\end{array}}\end{aligned}}} (21)

The sum of the two entries of the next fold is

 {\displaystyle {\begin{aligned}a_{1}b_{0}+a_{0}b_{1}\ or\ {3}+8={11},\end{aligned}}} (22)

which is ${\displaystyle c_{1}}$. Now fold again, thus obtaining the lower right entry ${\displaystyle c_{1}=a_{1}b_{1}=4}$. The final result is the convolution given by

 {\displaystyle {\begin{aligned}\left\{c_{0},\ \ c_{1},\ \ c_{2}\right\}=\left\{a_{0}b_{0},\ \ a_{0}b_{1}+a_{1}b_{0},\ \ a_{1}b_{1}\right\}=\left\{{6,11,4}\right\}.\end{aligned}}} (23)

We have defined the convolution of two finite-length signals. There is no reason, however, why this definition cannot be extended to the convolution of an arbitrary time series with a wavelet. Let the wavelet be

 {\displaystyle {\begin{aligned}h=\left\{h_{0},\ h_{1},\ h_{2},\ \cdots \right\}\end{aligned}}} (24)

and let the arbitrary time series be

 {\displaystyle {\begin{aligned}x=\left\{\dots ,\ \ x_{-2},\ x_{-1},x_{0},\ x_{1},\ x_{2},\ \cdots \right\},\end{aligned}}} (25)

which we can think of as being infinitely long in both the positive and negative directions. Their convolution is the time series

 {\displaystyle {\begin{aligned}y=\left\{,\ \ y_{-2},\ y_{-1},y_{0},\ y_{1},\ y_{2},\ \cdots \right\},\end{aligned}}} (26)

where y is given by the formula

 {\displaystyle {\begin{aligned}y_{n}=\sum _{k=0}^{\infty }{h_{k}}x_{n-k}.\end{aligned}}} (27)

As is the case with the x time series, the y time series also is infinitely long in both directions.

Let us show that convolution is polynomial multiplication. Convolution also can be performed by multiplication of polynomials. Thus, we write the Z-transforms

 {\displaystyle {\begin{aligned}A\left(Z\right)=a_{0}+a_{1}Z,\ B\left(Z\right)=b_{0}+b_{1}Z\end{aligned}}} (28)

or

 {\displaystyle {\begin{aligned}A\left(Z\right)=2+Z,B\left(Z\right)=3+4Z.\end{aligned}}} (29)

These polynomials are written in terms of the variable Z. Multiplying the polynomial A(Z) by the polynomial B(Z), we obtain

 ${\displaystyle {\begin{array}{l}3+4\;Z\\{\frac {2+Z}{6+8Z}}\;\;\;\;\;\;\;\;\;\;\ .\\{\frac {3Z+4Z^{2}}{6+11Z+4Z^{2}}}\\\end{array}}}$ (30)

The resulting polynomial has coefficients that are equal to the desired convolution. Thus, multiplication of polynomials corresponds to the convolution of their coefficients.

Next we will show that convolution is commutative, associative, and distributive. Convolution is commutative (i.e., convolutions can be taken in any order) because polynomial products can be taken in any order. For example, a * b = b * a because

 {\displaystyle {\begin{aligned}A\left(Z\right)B\left(Z\right)=B\left(Z\right)A\left(Z\right).\end{aligned}}} (31)

By the same reasoning, we see that convolution is associative; that is,

 {\displaystyle {\begin{aligned}\left(a*b\right)*c=a*\left(b*c\right),\end{aligned}}} (32)

and convolution is distributive with respect to addition; that is,

 {\displaystyle {\begin{aligned}a*\left(b+c\right)=\left(a*b\right)+\left(a*c\right).\end{aligned}}} (33)