# "definition" of CONVOLUTION

Started by November 18, 2004
I think I'm missing something basic.

http://mathworld.wolfram.com/Convolution.html defines convolution as
"A convolution is an integral that expresses the amount of overlap of
one function g as it is shifted over another function f. ..."

So what is difference between convolution and correlation?


Richard Owlett <rowlett@atlascomm.net> writes:

> I think I'm missing something basic.
>
> http://mathworld.wolfram.com/Convolution.html defines convolution as
> "A convolution is an integral that expresses the amount of overlap of
> one function g as it is shifted over another function f. ..."
>
>
> So what is difference between convolution and correlation?

Hey Richard,

They're VERY closely related - almost the same thing. The only
difference is that, with convolution, you time-reverse one of
the functions before overlapping it:

x(t) * y(t) = \int_{-\infty}^{+\infty} x(tau)y(t - tau) d tau

Here y is time-reversed relative to the variable of integration "tau."
It's also shifted by "t".

These notions are closely related to a concept with the fancy name
"matched filter." If you're searching for a signal of a specific
shape, the best way to do it is by filtering with a filter that has an
impulse response that is the time-reversed version of the signal
you're looking for. Then when the filter is applied, the impulse
response gets "re" reversed and you're essentially correlating the
received signal against the desired signal.

I find much of DSP is this way: fancy terminology, simple concepts...
--
Randy Yates
Sony Ericsson Mobile Communications
Research Triangle Park, NC, USA
randy.yates@sonyericsson.com, 919-472-1124

Randy Yates wrote:

> Richard Owlett <rowlett@atlascomm.net> writes:
>
>
>>I think I'm missing something basic.
>>
>>http://mathworld.wolfram.com/Convolution.html defines convolution as
>>"A convolution is an integral that expresses the amount of overlap of
>>one function g as it is shifted over another function f. ..."
>>
>>
>>So what is difference between convolution and correlation?
>
>
> Hey Richard,
>
> They're VERY closely related - almost the same thing. The only
> difference is that, with convolution, you time-reverse one of
> the functions before overlapping it:
>
>   x(t) * y(t) = \int_{-\infty}^{+\infty} x(tau)y(t - tau) d tau
>
> Here y is time-reversed relative to the variable of integration "tau."
> It's also shifted by "t".
>
> These notions are closely related to a concept with the fancy name
> "matched filter." If you're searching for a signal of a specific
> shape, the best way to do it is by filtering with a filter that has an
> impulse response that is the time-reversed version of the signal
> you're looking for. Then when the filter is applied, the impulse
> response gets "re" reversed and you're essentially correlating the
> received signal against the desired signal.
>
> I find much of DSP is this way: fancy terminology, simple concepts...

Yes. (A good thing, too. Otherwise, I'd be completely lost!) One of the
nicest examples of a matched filter is a SAW chirp generator, something
I knew before I'd heard of matched filters. Basically an impulsive wave
is launched down a piezo-electric substrate -- the Surface Acoustic Wave
device -- that has a series of output electrodes on it at steadily
decreasing spacing. The impulse excites each in turn as it passes them,
causing a combined output that rises in frequency as time advances;
i.e., a chirp. If the signal. or something very much like it, is fed
into the "output" electrodes, then after a short delay, an impulse
emerges from the "launcher" electrode. It's not too hard to see why, or
to see how arranging the output electrodes in different patterns
produces chips that generate, and are sensitive to, different signals.

Jerry
--
Engineering is the art of making what you want from things you can get.
&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;


Richard Owlett wrote:

> I think I'm missing something basic.

> http://mathworld.wolfram.com/Convolution.html defines convolution as
> "A convolution is an integral that expresses the amount of overlap of
> one function g as it is shifted over another function f. ..."

> So what is difference between convolution and correlation?

I would have said that correlation should be normalized, but
according to mathworld for correlation one function should
have a complex conjugate operation applied to it.

Mathworld doesn't seem to normalize the correlation.

-- glen


Randy Yates wrote:

>Richard Owlett <rowlett@atlascomm.net> writes:
>
>
>
>>I think I'm missing something basic.
>>
>>http://mathworld.wolfram.com/Convolution.html defines convolution as
>>"A convolution is an integral that expresses the amount of overlap of
>>one function g as it is shifted over another function f. ..."
>>
>>
>>So what is difference between convolution and correlation?
>>
>>
>
>Hey Richard,
>
>They're VERY closely related - almost the same thing. The only
>difference is that, with convolution, you time-reverse one of
>the functions before overlapping it:
>
>  x(t) * y(t) = \int_{-\infty}^{+\infty} x(tau)y(t - tau) d tau
>
>Here y is time-reversed relative to the variable of integration "tau."
>It's also shifted by "t".
>
>These notions are closely related to a concept with the fancy name
>"matched filter." If you're searching for a signal of a specific
>shape, the best way to do it is by filtering with a filter that has an
>impulse response that is the time-reversed version of the signal
>you're looking for. Then when the filter is applied, the impulse
>response gets "re" reversed and you're essentially correlating the
>received signal against the desired signal.
>
>I find much of DSP is this way: fancy terminology, simple concepts...
>
>
People like examples they can see and feel. DSP doesn't offer too many
of those. :-) A surface acoustic wave convolver illustrates the nature
and simplicity of convolution in as easy to see physical form.

1. Take a slab of piezo-electric material.

2. Cover the central area with a big rectangle of  metalisation.

3. Put a bar shaped transducer at each end of the rectangle. This can be
as simple as a U of metalisation with a isolated line of metalisation in
the middle of the U - its called an inter-digital transducer.

Now, when signals are injected at the two transducers they flow, as
surface acoustic waves,  in opposite directions under the slab. Being a
piezo-electric slab, this excits a voltage at each point under the
metalisation, in sympathy with the amplitude of the combined signals at
that point. Since the metalisation covers most of the slab between the
transducers, it integrates those potentials. If you look at the overall
varying potential of the metalisation, you will find it is the
convolution of the two signals. Just like a DSP convolution, it is
limited in length, so it is inexact.

SAW filters have seen widescale use, and a lot of DSP people understand
the close relationship they have to a DSP FIR filter. Not so many seem
to have seen , or considered, the "generic" acoustic convolver (compared
to the specific convolution a SAW filter performs). SAW filters have
somewhat limited dynamic range, mostly due to the inevitable bulk waves
that accompany the surface waves, and reflections from edges. SAW
convolvers are worse than SAW filters in this regard, so they never saw
widescale use. They are a neat device, though.

Regards,
Steve

Richard Owlett <rowlett@atlascomm.net> wrote in message
news:<10pq50gofenkk2a@corp.supernews.com>...
> I think I'm missing something basic.
>
> http://mathworld.wolfram.com/Convolution.html defines convolution as
> "A convolution is an integral that expresses the amount of overlap of
> one function g as it is shifted over another function f. ..."
>
> So what is difference between convolution and correlation?

Basically nothing. Both are "inner products" in the sense that
they can be expressed as

b
z(t) = integral x(tau)y(tau) dtau                          [1]
a

over some integration interval [a,b] and both reach their maximal
value iff x(t) == y(t).

In practice, there is a difference. While the correlation is just a
mathematical tool to compare two functions that is directly based
on [1] above, the convolution integral with the impulse response
requires a somewhat more elaborate derivation.

Given a linear filter with impulse response h(t) and a function x(t)
to be filtered. As we know, the impulse response of a LTI system is
formally defined as the response of the system to an impulse input:

inf
y(t)|_{x(t) = D(t)} = integral D(tau)h(tau) dtau = h(t)      [2]
-inf

where D(t) is the Dirac Delta function. We also know that any function
x(t) can be represented as

inf
x(t) = integral D(tau-t)x(tau) dtau                          [3]
-inf

i.e. a set of scaled and "merged" Dirac impulses. This argument is way
easier to see if you consider the discrete-time sequence.

The contribution to the output signal from an "impulse" at time t0
then becomes

t0 + eps
y(t)|_{x(t0)} = lim     integral  x(tau) Delta (tau - t0) dtau [4a]
eps -> 0   t0 - eps

= x(t0)h(t-t0)                                   [4b]

The output from a continuous input x(t) becomes the integral of
contributions from all impulses at previous inputs:

t
y(t) = integral x(tau)h(t-tau) dtau                            [5]
-inf

where the "t-tau" in the argument of h is caused by the causality
of the system. For general systems, is not required to use "t-tau"
as opposed to "tau-t". It is used that way as a matter of *coise*
because we usually consider causal systems, and the "t-tau" naturally
relates to a Dirac pulse that is shifted an amount tau to the right
from the current time t, on the time axis.

Before you start flaming me for doing all sorts of mistakes here,
this line of arguments works really well in the case of discrete
time series. This is the first time I've attempted to write it out
in the context of continuous functions. Not that I think it would
matter what the amount flaming is concerned...

Rune

In correlation, neither function is inverted with respect to time.

"Richard Owlett" <rowlett@atlascomm.net> wrote in message
news:10pq50gofenkk2a@corp.supernews.com...
> I think I'm missing something basic.
> http://mathworld.wolfram.com/Convolution.html defines convolution as
> "A convolution is an integral that expresses the amount of overlap of
> one function g as it is shifted over another function f. ..."
> So what is difference between convolution and correlation?


Hi,

I guess (I apologize if I guess wrong) Richard's question is not
really about "the difference between convolution and correlation", but
about why Mathworld did not talk about time flipping the function in
its description of convolution.

If you look at Mathworld's Web page, you can see that it does list the
standard time-reverse equation, as given in Bracewell's book, although
its words and animation are misleading......So there is no conflict in
this aspect.

My thought about the conjugate operation:

Correlation should have a conjugate operation so that it gives you the
phase difference between 2 functions, instead of a 90-degree
phased-shifted version.

Example:
f: y = x(1+i)
g: y = x(1-i)

A conjugate operation will make the correlation positive-imaginary,
telling us that the lines are perpendicular to each other. Without a
conjugate operation, the correlation will be positive-real, suggesting
that the lines are parallel.

I am not sure whether it is ever meaningful, application-wise, to
perform a conjugate operation in convolution. (It will destroy its
commutative property.) So far, I can't think of any example, so I
guess conjugate operation is another difference between correlation
and convolution.

Best Regards.

KD

kd20128@yahoo.com (Kedi) wrote in message
> Hi,
>
> I guess (I apologize if I guess wrong) Richard's question is not
> really about "the difference between convolution and correlation", but
> about why Mathworld did not talk about time flipping the function in
> its description of convolution.

Yep, once I actually read the mathworld page, you are right.

> If you look at Mathworld's Web page, you can see that it does list the
> standard time-reverse equation, as given in Bracewell's book, although
> its words and animation are misleading......So there is no conflict in
> this aspect.

For some reason, the functions that are showed in the animation
on the mathworld page are symmetric in time. In that case, flipping the
time doesn't make much difference.

> My thought about the conjugate operation:
>
> Correlation should have a conjugate operation so that it gives you the
> phase difference between 2 functions, instead of a 90-degree
> phased-shifted version.
>
> Example:
> f: y = x(1+i)
> g: y = x(1-i)
>
> A conjugate operation will make the correlation positive-imaginary,
> telling us that the lines are perpendicular to each other. Without a
> conjugate operation, the correlation will be positive-real, suggesting
> that the lines are parallel.

The correlation is a comparision of two functions and pops out a
"measure of similarity". That's why you need the conjugate when
dealing with complex-valued functions. The filter is just a "blending"
of two arbitrary functions.

> I am not sure whether it is ever meaningful, application-wise, to
> perform a conjugate operation in convolution. (It will destroy its
> commutative property.) So far, I can't think of any example, so I
> guess conjugate operation is another difference between correlation
> and convolution.

Makes sense to me.

Rune

the difference betwwen convolution and correlation is that convolution
is a filtering operation and correlation is a measure of relatedness of
two signals.
in filtering operaion we pass a signal through a filter whose frequency
response is equal to to of our interest. so we multiply the filter
frequency response with the signal frequency response to get the
desired frequency response. but mathematically it is manifested such
that in time-domain that opeartion is called convolution. similar
argument can be given to correlation of two signals.