Convolution - book

Digital Imaging and Deconvolution: The ABCs of Seismic Exploration and Processing

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

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} B\left(Z\right)=b_0+b_{1}Z+b_2Z^2+b_3Z^3+\ldots+b_NZ^N \end{align}

(6)

is the Z-transform of the finite-length causal impulse-response function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): b_0,b_{1}, b_2,b_{N} . Similarly, the Z-transform of an infinite-length causal impulse-response function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): b\; = \;\{ b_0 ,\;b_1 ,\;b_2 ,\; \ldots \} is the power series in Z given by

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} B\left(Z\right)=b_0+b_{1}Z+b_2Z^2+ . .. . \end{align}

(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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): x_0,x_{1}, x_2, . . . , x_M . The numbers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): x_n are going into the filter; that is, the input is as follows: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): x_{-1} enters at time Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): n=-1, x_0 enters at time Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): n=0,x_{1} enters at time Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): n=1, x_2 enters at time n = 2, and so forth.

Coming out of the filter are the numbers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): y_n , that is, the output is as follows: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): y-1 emerges at time n = –1, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): y_0 emerges at time Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): n=0,y_{1} emerges at time Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): n=1, y_2 emerges at time n = 2, and so forth.

The output is seen to be

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} y_n=b_0x_n+b_{1}x_{n-1}\ +b_2x_{n-2}+\\dots +b_Nx_{n-N}. \end{align}

(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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): x_0,x_{1},x_2,\ldots, x_{{\rm M}} , with the filter’s impulse-response coefficients Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): b_0,b_{1}, b_2,\ldots, b_{N} . A more compact notation for convolution is

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} y_n=\sum^N_{i=0}{b_j}x_{n-i}, \end{align}

(9)

where it is understood that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): y_n=0 when n falls outside the range Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): 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, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): a=\left\{a_0,\ a_{1},\ a_2{,\ .\ .\ .}\right\} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): 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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} \left\{a_0,\ a_{1},\ a_2,\ \cdots \right\} \\ b=\left\{,\ \ b_2,\ b_{1},\ b_0\right\}. \\ a_0b_0 \end{align}

(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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align}\{ a_0 ,\;a_1 ,\;a_2 ,\;...\} \\ b=\left\{,\ \ b_2,\ \ b_{1},\ \ b_0\right\}. \\ a_0b_{1}+a_{1}b_0\end{align}

(11)

We obtain the third value

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align}\left\{a_0,\ a_{1},\ a_2,\ \cdots \right\} \\ \left\{\dots,\ \ b_2,\ b_{1},\ b_0\right\}. \\ a_0b_2+a_{1}b_{1}+a_2b_0\end{align}

(12)

The complete convolution is then

$ {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): -\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): a=\left\{a_0,\ a_{1}\right\}=\{2, 1\} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): 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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} c=a*b=\left\{c_0,\ \ c_{1},\ \ c_2\right\} , \end{align}

(14)

where

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} c_0=a_0b_0=2\left({3}\right)=6, \end{align}

(15)

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} c_{1}=a_0b_{1}+a_{1}b_0=2\left({4}\right)+1\left({3}\right)=11, \end{align}

(16)

and

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} c_2=a_{1}b_{1}=l\left({4}\right)=4. \end{align}

(17)

Hence,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} c=a*b=\{{6,} 11 , 4\}. \end{align}

(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):

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} \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{align}

(19)

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} \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{align}

(20)

The element in the upper left corner, that is, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): a_0b_0 , or 6, is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): c_0 . Now fold this entry over, thus obtaining

$ {\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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} a_{1}b_0+a_0b_{1}\ or\ {3}+8={11}, \end{align}

(22)

which is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): c_{1} . Now fold again, thus obtaining the lower right entry Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): c_{1}=a_{1}b_{1}=4 . The final result is the convolution given by

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} \left\{c_0,\ \ c_{1},\ \ c_2\right\}=\left\{a_0b_0,\ \ a_0b_{1}+a_{1}b_0,\ \ a_{1}b_{1}\right\}=\left\{{6,11,4}\right\}. \end{align}

(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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} h=\left\{h_0,\ h_{1},\ h_2,\ \cdots \right\} \end{align}

(24)

and let the arbitrary time series be

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} x=\left\{\dots,\ \ x_{-2},\ x_{-1},x_0,\ x_{1},\ x_2,\ \cdots \right\} , \end{align}

(25)

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

$ {\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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} y_n=\sum^{\infty }_{k=0}{h_k}x_{n-k}. \end{align}

(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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} A\left(Z\right)=a_0+a_{1}Z,\ B\left(Z\right)=b_0+b_{1}Z \end{align}

(28)

or

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} A\left(Z\right)=2+Z, B\left(Z\right)=3+4 Z. \end{align}

(29)

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} A\left(Z\right)B\left(Z\right)=B\left(Z\right)A\left(Z\right) . \end{align}

(31)

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} \left(a*b\right)*c=a*\left(b*c\right) , \end{align}

(32)

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align} a*\left(b+c\right)=\left(a*b\right)+\left(a*c\right) . \end{align}

(33)

Continue reading

Previous section	Next section
Digital filtering	Feedback filters
Previous chapter	Next chapter
Sampling	Frequency
Table of Contents (book)

Also in this chapter

• Digital filtering
• Feedback filters
• Inverse filters
• Minimum delay
• Appendix E: Exercises

External links

find literature about Convolution - book/en