# Cross Correlation in Java (Android) Using FFT (Frequency Domain Convolution / Correlation)

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?

• 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). – dsp_user Jan 30 '18 at 13:43
• 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. – 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.