Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
How to convert between convolution and corrleation? And more on FFT. Thanks a lot.

Subject: How to convert between convolution and corrleation? And more on FFT. Thanks a lot.

From: Antony

Date: 22 Jul, 2010 13:24:04

Message: 1 of 5

Dear all,

   What's the relationship between correlation and convolution? For example, if \otimes denoting convolution operator and * denoting correlation operator, "A * B" can be written into what form of correlation? "B^T \otimes A" is incorrect, I think. But how to convert? Furthermore, how to convert a convolution operation into a correlation operation? What is the transfer rule? Thanks a lot.

   In addition, I often see some articles saying convolution can be accelerated by FFT, but I have no idea of such a transformation. Would you mind give me some advice or links on how such a transformation takes?

Subject: How to convert between convolution and corrleation? And more on FFT. Thanks a lot.

From: Wayne King

Date: 22 Jul, 2010 14:29:21

Message: 2 of 5

"Antony " <mutang.bing@gmail.com> wrote in message <i29gpk$1ve$1@fred.mathworks.com>...
> Dear all,
>
> What's the relationship between correlation and convolution? For example, if \otimes denoting convolution operator and * denoting correlation operator, "A * B" can be written into what form of correlation? "B^T \otimes A" is incorrect, I think. But how to convert? Furthermore, how to convert a convolution operation into a correlation operation? What is the transfer rule? Thanks a lot.
>
> In addition, I often see some articles saying convolution can be accelerated by FFT, but I have no idea of such a transformation. Would you mind give me some advice or links on how such a transformation takes?

Hi Anthony, Look at the "Definition" of convolution at

http://en.wikipedia.org/wiki/Convolution

Now imagine that you have g(t-\tau)=h*(\tau-t) where the asterisk denotes complex conjugation.

Substituting h*(\tau-t) gives the cross correlation of f with h.
So convolving f with g is the same as cross correlating f with a function that is the time-reverse and complex conjugate of g.

As far as computing convolution through the FFT algorithm, you should read about circular convolution and under what conditions the circular convolution of two sequences is equal to the linear convolution.

For example:

A = 1:5;
B = 2:7;
A1 =[A zeros(1,5)];
B1 = [B zeros(1,4)];
% compare
ifft(fft(A1).*fft(B1))
% with
conv(A,B)

Hope that helps,
Wayne

Subject: How to convert between convolution and corrleation? And more on

From: TideMan

Date: 22 Jul, 2010 20:19:45

Message: 3 of 5

On Jul 23, 1:24 am, "Antony " <mutang.b...@gmail.com> wrote:
> Dear all,
>
>    What's the relationship between correlation and convolution? For example, if \otimes denoting convolution operator and * denoting correlation operator, "A * B" can be written into what form of correlation? "B^T \otimes A" is incorrect, I think. But how to convert? Furthermore, how to convert a convolution operation into a correlation operation? What is the transfer rule? Thanks a lot.
>
>    In addition, I often see some articles saying convolution can be accelerated by FFT, but I have no idea of such a transformation. Would you mind give me some advice or links on how such a transformation takes?  

This is explained very well in an old textbook of mine:
Brigham, E. O. 1974: The Fast Fourier transform. Prentice-Hall.
Most libraries will have it.

Subject: How to convert between convolution and corrleation? And more on FFT. Thanks a lot.

From: Antony

Date: 23 Jul, 2010 02:30:14

Message: 4 of 5

"Antony " <mutang.bing@gmail.com> wrote in message <i29gpk$1ve$1@fred.mathworks.com>...
> Dear all,
>
> What's the relationship between correlation and convolution? For example, if \otimes denoting convolution operator and * denoting correlation operator, "A * B" can be written into what form of correlation? "B^T \otimes A" is incorrect, I think. But how to convert? Furthermore, how to convert a convolution operation into a correlation operation? What is the transfer rule? Thanks a lot.
>
> In addition, I often see some articles saying convolution can be accelerated by FFT, but I have no idea of such a transformation. Would you mind give me some advice or links on how such a transformation takes?

Thank you very much, Wayne and TideMan. I understand the relationship between covolution and correlation a little now, *-*. I will follow the links and other advice you provide for more details, and wish that I can completely know the principle finally. Thanks again!

Antony

Subject: How to convert between convolution and corrleation? And more on FFT. Thanks a lot.

From: Javier Montoya

Date: 19 Jan, 2011 16:25:20

Message: 5 of 5

"Antony" wrote in message <i2aurm$247$1@fred.mathworks.com>...
> "Antony " <mutang.bing@gmail.com> wrote in message <i29gpk$1ve$1@fred.mathworks.com>...
> > Dear all,
> >
> > What's the relationship between correlation and convolution? For example, if \otimes denoting convolution operator and * denoting correlation operator, "A * B" can be written into what form of correlation? "B^T \otimes A" is incorrect, I think. But how to convert? Furthermore, how to convert a convolution operation into a correlation operation? What is the transfer rule? Thanks a lot.
> >
> > In addition, I often see some articles saying convolution can be accelerated by FFT, but I have no idea of such a transformation. Would you mind give me some advice or links on how such a transformation takes?
>
> Thank you very much, Wayne and TideMan. I understand the relationship between covolution and correlation a little now, *-*. I will follow the links and other advice you provide for more details, and wish that I can completely know the principle finally. Thanks again!
>
> Antony

Although, it seems to be an old topic, I'll reply since it might be useful for somebody in the future.
Basically, the relationship between convolution and correlation is that in convolution you rotate your filter h by 180 degrees before passing it by your image f.
In 1D:
h=[1 2 3 4 5] for correlation.
h=[5 4 3 2 1] for convolution.

Hope that helps!

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us