Re: Correlation using FFT

From: rg (rg1117_at_hotmail.com)
Date: 08/28/04 

Date: Sat, 28 Aug 2004 18:25:29 +0100

Hi Mark,

Thank you for your reply. It is certainly more complicated then I thought it
would be, but I will figure it out. Thanks also for the link to your
document, I will read through it.
As for the cross correlation function, I would be more then happy to provide
the code for it when I have it working. Mind you, I write my code in C++,
STL-compliant style but it should be easy to make that C compliant.

Many Thanks,

RG

"Mark Borgerding" <mark@borgerding.net> wrote in message
news:5I2Yc.242341$fv.83510@fe2.columbus.rr.com...
> rg wrote:
> > Dear All,
> >
> > Can someone describe the algorithm for performing correlation analysis
> > between two signals using fft. I tried using the simple correlation
> > algorithm but as my signals are quite long (upto 45 seconds of audio),
as
> > you can imagine, the calculation takes for ever.
> >
> > I know there is a quicker technique to do this by transforming the
signals
> > into frequency spectrum using fft, but I am not sure of the exact
algorithm.
> > I do have the advantage that both of the signals are the exact same
length.
> >
> > BTW, I am using kissfft as the fft library for my work.
> >
> > If anyone can help me with this, or point to me a suitable link, I would
be
> > very greatful.
> >
> > Many Thanks,
> >
> > RG
> >
> >
>
> If you are not already, you should get familiar with the concepts of
> circular convoultion and overlap-add filtering.
> Many DSP texts cover this. Also, pages 6 & 7 of
> http://www.borgerding.net/comp.dsp/borgerding_fastconvfilt.pdf
> cover overlap-add.
>
> The algorithm is probably more involved than I can describe quickly, but
> I'll try nonetheless.
>
> You need to do two ffts per buffer. The buffer length is nfft minus
> twice the number of lags. So if nlags = 128, you can use nfft = 1024
> and consume 768 samples each buffer. One of the signals must have
> overlapping input, the other should be zero padded. I think half the
> zero padding needs to be in front, half at back; but I can't recall
exactly.
>
> Summation across buffers can be done in the frequency domain, postponing
> the inverse fft until an answer is required (i.e. only once).
>
> A great book on the technique (as well as many others) is Richard
> Blahut's "Fast Algorithms for Digital Signal Processing". It is out of
> print, but you can probably find it used. Amazon.com shows 3 in the
> $65-$75 range.
>
> -- Mark
>
> P.S. Glad to hear you are using kissfft. If you are willing to "give
> back", we can put your cross-correlation code into the ./tools/ section.

Relevant Pages

  • Re: Correlation using FFT
    ... > between two signals using fft. ... > into frequency spectrum using fft, but I am not sure of the exact algorithm. ... You need to do two ffts per buffer. ...
    (sci.math.num-analysis)
  • Re: Analyzing fundamental frequencies from musical signals
    ... This is about analyzing fine detail in pitch and pitch changes ... As you found, zero-padding and using a long fft, although a very ... Plot that phase difference. ... accurate and reliable on real audio signals. ...
    (comp.dsp)
  • Re: Secure passwords?
    ... >> noise using FFT integration. ... An FFT is an FFT is an FFT is an FFT! ... As an index of how commonplace an EE problem extracting signals from ... metallic-deposition-layer glass used for emsec shielding where visibility ...
    (alt.computer.security)
  • Re: Oversampling and the FFT
    ... I suggested we sample just above Nyquist and perform our 1024 point FFT. ... regardless of the window function or sample rate. ... Also the phase of a sharp filter may change ... signals near the Nyquist frequency of a given sampling rate than ...
    (comp.dsp)
  • Re: Discrete Deconvolution
    ... I'm analyzing some time signals for periodicities, ... a window function, and s is the actual source signal. ... I know the FFT ... The FFT can be used as an approximation of the Fourier transform of a signal in sampled time with an infinite number of points, which is in turn an approximation of a signal in continuous time that extends into infinity. ...
    (comp.dsp)