DSPRelated.com
Forums

Fast linear correlation

Started by Thaya 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.

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