# Fast linear correlation

Started by June 12, 2006
```Hi all,

I am trying to implement the fast linear correlation in C as follows. x
and y are the input arrays.
C = IFFT(conjucate( X) * Y)

It works correctly for circular correlation. when we try with zero
padding to get the linear correlation it will give the incorrect
result.

Could you pls anbody explain me, how can we get the linear correlation
from fast correlation.

```
```Thaya wrote:
> Hi all,
>
> I am trying to implement the fast linear correlation in C as follows. x
> and y are the input arrays.
> C = IFFT(conjucate( X) * Y)
>
> It works correctly for circular correlation. when we try with zero
> padding to get the linear correlation it will give the incorrect
> result.
>
> Could you pls anbody explain me, how can we get the linear correlation
> from fast correlation.
>

Zero padding to double width in the time domain, i.e., of x(t) and
y(t), is all that is necessary.  You must have an error somewhere else.

```
```"Thaya" <kthayapararajh@yahoo.com> wrote in message
> Hi all,
>
> I am trying to implement the fast linear correlation in C as follows. x
> and y are the input arrays.
> C = IFFT(conjucate( X) * Y)
>
> It works correctly for circular correlation. when we try with zero
> padding to get the linear correlation it will give the incorrect
> result.
>
> Could you pls anbody explain me, how can we get the linear correlation
> from fast correlation.
>

You didn't start out in the time domain above - so it's hard to tell what's
going on.
If done right, there should be no difference between circular and what you
call "linear".  You just make sure that the circle in the circular case is
big enough in the time domain.
"Big enough" is M+N-1.
(Well, I'm assuming that both X and Y represent time-limited functions).

In addition, if you want to zero-pad in the time domain in then I suppose
that adds samples to that number.  Call the zero padded sample counts M'>M
and N'>N.  Then there may need to be M'+N'-1 samples or more to get the full
results from zero-padded arrays.  Although, that may be overkill depending
on what you're trying to do.

X and Y above have to both be of length M+N-1.  That's for circular
convolution without overlap and the result should be the same as for
"linear" convolution.  However, the result in time won't be zero padded.  If
zero-padded time domain result is what you want then you have to
*interpolate* in frequency so there are M'+N'-1 samples in frequency (at
least).  Normally it's done in the other direction:  you zero pad in one
domain with the result that you get an interpolated transform.  I'm not sure
I know how to do interpolation such that zero padding is guaranteed for the
transform.

I hope this helps.

Fred

```