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

# Fast linear correlation

Started by ●June 12, 2006

Reply by ●June 12, 20062006-06-12

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 advanceZero 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.

Reply by ●June 13, 20062006-06-13

"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 advanceYou 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