I would like to calculate a long correlation function of length say, 1e6 points. I have a prior knowledge that the correlation peak will be in point k*1000. Is there an efficient way to apply this prior knowledge and perform a shorter calculation.

I don't want to calculate correlation by definition and implement a 1000 correlators. This solution is not sufficient. Batch algorithm (FFT) is always possible but it does not make use of the mentioned structure.

  • 3
    $\begingroup$ I don't have time to write up a full answer, but you could implement the correlation using FFTs. If you know a set of equally-spaced points that you care about, what you really want to do is decimate the correlator output. This can be implemented efficiently in the frequency domain by folding and adding the frequency-domain result, allowing you to use a much smaller inverse FFT. This might help reduce your workload. $\endgroup$ – Jason R Apr 24 '15 at 12:12
  • $\begingroup$ You could probably use a variant of Goertzel algorithm ? $\endgroup$ – Ben Jul 8 '18 at 15:03

If you have a signal of length $N$ you can calculate auto correlation function of length $K=2N-1$.You'll need perform $N$ multiplications for each value of correlation function $r_{xx}$ or in other words you need one correlator. So you need as many correlators as your $r_{xx}$ function length is. If you want to find correlation in the lag $0$ use one correlator. You can can calculate correlation of any lag $i \in (-N+1...N-1)$ via one correlator with signal properly shifted by $i$ times. From the other side $FFT$ method allows you to find $N$ taps of cyclic auto correlation function via only one $FFT$ operation. So it is not optimal if you need only a few correlation values.

  • $\begingroup$ Thanks for the response. Thats is the quistion. I am trying to use some kind of a hybrid algorithm that will use FFT but it will also exploit the structure mentioned in the question. $\endgroup$ – Vlad Sokolik Feb 23 '15 at 9:34

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.