# Fast cross correlation with limited range

I am measuring the phase shift between two pseudorandom signals using correlation ifft(A.conjugate()*B) and picking out the maximum). That works very well, but takes a lot of time. I roughly know where the peaks are, and don't need the correlation for other shifts.

Is there an adaptive cross-correllation algorithm that would speed up the process if I am only interested in the positions of maxima, and already roughly know their positions? Analog to the sliding DFT?

Maybe running the cross-correlation on a decimated version of data, finding the peaks, interpolating, and then doing a manual correlation around the max?

I already know within 200 samples where the maxima are. The record length is about 200k samples.

• I was wondering something similar: Is it possible to manipulate the template signal such that the cross-correlation is positive for positive lags and negative for negative lags? So that it can do a "synchronous cross-correlation", only computing the value for a single lag, but that lag is constantly adjusted with a feedback loop to track the match? Are you tracking multiple maxima, though? – endolith Apr 21 '14 at 20:56
• Interesting idea. In principle I can choose any binary sequence. I am measuring the phase between two copies of the sequence in my signal. That gives me two peaks. I need to measure that phase as precisely as possible, so I need a sharp central peak, but otherwise the sequence is more or less arbitrary. – Dan Apr 21 '14 at 21:05
• Can the two peaks occur at any time? At the same time? – endolith Apr 29 '14 at 17:43

## 1 Answer

If the limited range is significantly more than log(N) shorter than the total signal of length N, then ordinary cross correlation over that limited range may be faster than FFT-based fast correlation. You could just iterate away from the estimated/predicted lag until you find you have gone past a correlation peak (by a sufficient amount to account for expected noise). But if you go more than log(N)/2 points away from your initial estimate, then perhaps switch back to fast convolution cross correlation.

• "more than log(N) shorter" could be more clearly worded? – endolith Apr 29 '14 at 15:26