Fast linear correlation

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.

Thanks in advance

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.
>
> Thanks in advance

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 
news:1150100127.500271.251270@y43g2000cwc.googlegroups.com...
> 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.
>
> Thanks in advance

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