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?