I am trying to find out if an algorithm similar to the Overlap-And-Add method that enables frame-based computation of convolution and cross-correlation exists.

When I say frame-based computation I am referring to having a very large input signal vector, subdividing it into smaller frames, processing the autocorrelation of those frames, and then concatenating all of the frame results plus any extra magic to form the overall auto-correlation result as if I had computed the whole thing at once.

Working through toy examples by hand for auto-correlation I quickly realized the normal Overlap-And-Add method doesn't work due to the correlation "template" changing every frame vs generally being fixed in the cross-correlation and convolution cases.

  • $\begingroup$ There is already a thread on this subject dsp.stackexchange.com/questions/1919/… $\endgroup$
    – Ben
    Mar 8, 2019 at 12:27
  • $\begingroup$ @Ben It looks like that thread is just addressing the computation of auto-correlation via FFTs and not frame-based computation. The point of being frame-based is allowing the FFT sizes to be much smaller and being able to process in a real-time type manner where you stream your long input signal in a frame at a time. $\endgroup$ Mar 8, 2019 at 13:11
  • $\begingroup$ You're right my bad. I think your could adapt the FFT-based algorithm though. You could compute the initial FFT with an overlap-and-add method for starters. $\endgroup$
    – Ben
    Mar 8, 2019 at 13:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.