Adaptive Filter | ADPCM | ADSP | ADSP-2181 | Aliasing | AMR | Anti-Aliasing | ARMA | Autocorrelation | AutoCovariance | Beamforming | Bessel | Blackfin | Butterworth | C6713 | CCS | Chebyshev | CIC Filter | Circular Convolution | Code Composer Studio | Comb Filter | Compression | Convolution | Cross Correlation | DCT | Decimation | Deconvolution | Demodulation | DM642 | DSP Boards | DSP/BIOS | DTMF | Echo Cancellation | Equalization | Equalizer | ETSI | EZLITE (Ez-kit Lite) | FFT | FFTW | FIR Filter | Fixed Point | FSK | G.711 | G.723 | G.729 | Gaussian Noise | Goertzel | GPIO | Hilbert Transform | IFFT | IIR Filter | Interpolation | Invariance | JTAG | Kalman | Laplace Transform | Levinson | LPC | McBSP | MIPS | Modulation | MPEG | Multirate | Notch Filter | Nyquist | OFDM | Oversampling | Pink Noise | Pitch | PLL | Polyphase | QAM | QDMA | Quantization | Quantizer | Radar | Random Noise | Reed Solomon | Remez | Resampling | RTDX | Sampling | Sharc | TI C6711 | Undersampling | Viterbi | Wavelets | White Noise | Wiener Filter | Windowing | XDS510PP | Z Transform

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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

"Atmapuri" <j...@usa.net> wrote in message
news:<KTb9d.3912$F...@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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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" <a...@tele.ntnu.no> wrote in message
news:f...@posting.google.com...
> "Atmapuri" <j...@usa.net> wrote in message
news:<KTb9d.3912$F...@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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

"Atmapuri" <j...@usa.net> wrote in message
news:<PET9d.4029$F...@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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.