I want to implement cross-correlation with the start-symbol and the signal using FFT.

I zero-pad both signals to length N = x.len + y.len -1 Using the convolution theorem:

        corr(x, y) = IFFT( FFT(x_padded) .* conj(FFT(y_padded)))

Do you have any good library recommendations I could use to compute both the FFT and IFFT? I am running this on an Android app and efficiency is important.

Moreover, the best correlation is the highest peak in the array of the result. How does the index k of the array corr(x,y) relate to x? Does that mean the best alignment is when y lags k samples behind x?

  • $\begingroup$ Kiss is a pretty good and easy to use library written in c or c++(can't remember). I'm not aware of any Java FFT libraries and performance might be an issue if you choose a Java library (sourceforge.net/projects/kissfft/reviews?source=navbar). $\endgroup$
    – dsp_user
    Jan 30 '18 at 13:43
  • $\begingroup$ There appears to be a Java implementation of the FFT here. Doug L. Jones seems to have originated it, which means it's probably kosher. $\endgroup$
    – Peter K.
    Jan 30 '18 at 13:51

If index k refer to the highest correlation coeffitient and let n be the length of each x and y, so would n-k be the lag for y at maxima of the correlation function.

For some applications I prefer the cosine similarity instead of plain correlation, but which is less efficient in calculation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.