Convolution output function

by AlecYates
Tags: convolution, function, output
 P: 12 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 gi (i = 1,2.... m), and a convolution operator fj (j = 1,2 ......n) the convolution output is given by: yk = $\Sigma$gifk - 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 y1 I end up with negative index of fj as I perform fk - i as i increases from 1 to 3 with the largest index being f0 (from f1 - 1 where k = 1 and i = 1). How can this be correct? Any help would be appreciated.
 P: 12 Just realised this should be in the homework/CW area (by the rules listed in the pinned thread). Reposting.
P: 866
 Quote by AlecYates 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 y1 I end up with negative index of fj as I perform fk - i as i increases from 1 to 3 with the largest index being f0 (from f1 - 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.

 P: 12 Convolution output function 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.
 P: 866 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.
 P: 12 Yup seems to be. Guess I'll assume it an error within the text and move on. Cheers

 Related Discussions Advanced Physics Homework 1 Calculus & Beyond Homework 3 Calculus & Beyond Homework 27 Linear & Abstract Algebra 3 Calculus 1