How can I obtain the convolution output for an input function and operator?

[AlecYates]

Hey,

I've begun going through a book called "An introduction to geophysical exploration" by Phillip Kearey and Michael Brooks and I've come across a problem I can't for the life of me see how they got their answer.

Essentially, given an input function g_i (i = 1,2... m), and a convolution operator f_j (j = 1,2 ...n) the convolution output is given by:

y_k = $\Sigma$g_if_{k - i} (k = 1,2 ... m + n - 1)

with (Sigma sum starting at i = 1 and going up to m).

Their example is with an input of g(2,0,1) and operator of f(4,3,2,1) the output is y(8,6,8,5,2,1).

Not only can I not see how this is obtained, but based on the function if I'm trying to find y₁ I end up with negative index of f_j as I perform f_{k - i} as i increases from 1 to 3 with the largest index being f₀ (from f_{1 - 1} where k = 1 and i = 1). How can this be correct?

Any help would be appreciated.

 

[AlecYates]

Just realized this should be in the homework/CW area (by the rules listed in the pinned thread). Reposting.

 

[olivermsun]

Their example is with an input of g(2,0,1) and operator of f(4,3,2,1) the output is y(8,6,8,5,2,1).

Not only can I not see how this is obtained, but based on the function if I'm trying to find y₁ I end up with negative index of f_j as I perform f_{k - i} as i increases from 1 to 3 with the largest index being f₀ (from f_{1 - 1} where k = 1 and i = 1). How can this be correct?

The convolution g*f basically applies a "sliding filter" to g, where the filter is just a reversed f (or f by a reversed g; it's symmetric). In this case f(-n) = (1,2,3,4), so the terms in g*f are just

$$
\begin{matrix}
g & & & & 2 & 0 & 1 \\
f(-n) & 1 & 2 & 3 & 4 \\
g*f & & & & 8
\end{matrix}
\qquad \ldots \qquad
\begin{matrix}
& 2 & 0 & 1 \\
1 & 2 & 3 & 4 \\
& 4 & 0 & & = 4
\end{matrix}
\qquad \ldots \qquad
\begin{matrix}
& 2 & 0 & 1 \\
& & & 1 & 2 & 3 & 4 \\
& & & 1
\end{matrix}
$$

At the endpoints you see that f(-n) is allowed to "fall off the ends," so you get as many outputs as both inputs combined, less 1. This is just because f and g have to overlap by at least one term to make an output.

There are some nice visual demonstrations at the Wikipedia page for Convolution.

 

[AlecYates]

Yeah they have a demonstration of this on the next page of the textbook, which is easy enough to follow (although it didn't mention anything about the reversed filter which is helpful, I had wondered if it was a mistake originally).

It's just frustrating I can't get the same result using the Sigma Summation given.

Using the sigma summation I get y(0,8,6,8,5,2) as if I regard any impossible index's i.e. f(n) where n < 1 as 0, y1 can only ever be 0 as opposed to 8. So my solution is shifted to the right by one place from the actual solution.

 

[olivermsun]

Well, following your notation it seems to me that the summation should read

$$
y_k = \sum_{i} g_i \, f_{k-i+1} .
$$
That gives
$$
\begin{align}
y_1 &= g_1 \, f_1 + 0 = (2)(4) = 8 \\
& \vdots \\
y_{m+n-1} &= y_6 = 0 + g_3 \, f_{6-3+1} = (1)(1) = 1,
\end{align}
$$
which looks correct.

 

[AlecYates]

Yup seems to be. Guess I'll assume it an error within the text and move on. Cheers