Forums

Fast cross correlation!

Started by Atmapuri October 7, 2004
Hi!

I would like to speed up a cross correlation
application  which looks like this:

x has to be cross-correlated with "n" different
length y's.

I would like to precompute the FFT of the x
before making the convolution with all the y's.
Thats why I dont want to use the classic
convolution and cross correlation functions
available in Matlab. (nor the filtering functions).

Any suggestions?

Thanks!
Atmapuri


"Atmapuri" <janez.makovsek@usa.net> wrote in message news:<KTb9d.3912$F6.1073538@news.siol.net>...
> Hi! > > I would like to speed up a cross correlation > application which looks like this: > > x has to be cross-correlated with "n" different > length y's. > > I would like to precompute the FFT of the x > before making the convolution with all the y's. > Thats why I dont want to use the classic > convolution and cross correlation functions > available in Matlab. (nor the filtering functions). > > Any suggestions?
You are using matlab, right? Try this (I haven't tested it, so no guarantees about the details): Y= [y1,y2,y3,...,yn]; % All the ys are stored as colomns in a matrix. % If the ys are of different length, append zeros. M=length(Y(:,1)); % Length of columns in matrix Y N= length(x); % Length of data, which is stored as column vector L= max(M,N); % MAke data matrix from x vector X=x*ones(1,length(Y(1,:))); % Compute DFT of columns of X and Y. Zero-pad the shorter sequence % to match the length of the longer one, and correct for wrap-around % effects. The details can be a bit more elegant... XX=fft(X,1,2*L); YY=fft(Y,1,2*L); SXY= XX.*conj(YY); rsy=fftshift(real(ifft(SXY,1))); The one thing that remains is to find the correct time axes. Rune
Hi!

Thanks. Would you have any references to why
you have to XX=fft(X,1,2*L);
double length of FFT with zero padding?

Thanks!
Atmapuri

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message
news:f56893ae.0410080132.71d4362d@posting.google.com...
> "Atmapuri" <janez.makovsek@usa.net> wrote in message
news:<KTb9d.3912$F6.1073538@news.siol.net>...
> > Hi! > > > > I would like to speed up a cross correlation > > application which looks like this: > > > > x has to be cross-correlated with "n" different > > length y's. > > > > I would like to precompute the FFT of the x > > before making the convolution with all the y's. > > Thats why I dont want to use the classic > > convolution and cross correlation functions > > available in Matlab. (nor the filtering functions). > > > > Any suggestions? > > You are using matlab, right? Try this (I haven't tested it, so no > guarantees about the details): > > Y= [y1,y2,y3,...,yn]; % All the ys are stored as colomns in a matrix. > % If the ys are of different length, append zeros. > > M=length(Y(:,1)); % Length of columns in matrix Y > > N= length(x); % Length of data, which is stored as column vector > > L= max(M,N); > > % MAke data matrix from x vector > X=x*ones(1,length(Y(1,:))); > > % Compute DFT of columns of X and Y. Zero-pad the shorter sequence > % to match the length of the longer one, and correct for wrap-around > % effects. The details can be a bit more elegant... > > XX=fft(X,1,2*L); > YY=fft(Y,1,2*L); > > SXY= XX.*conj(YY); > rsy=fftshift(real(ifft(SXY,1))); > > The one thing that remains is to find the correct time axes. > > Rune
"Atmapuri" <janez.makovsek@usa.net> wrote in message news:<PET9d.4029$F6.1102482@news.siol.net>...
> Hi! > > Thanks. Would you have any references to why > you have to XX=fft(X,1,2*L); > double length of FFT with zero padding?
The key word is "circular convolution". Rune