24
$\begingroup$

What differences or other criteria can be used to help decide between using overlap-add and overlap-save for filtering? Both overlap-add and overlap-save are described as algorithms for doing FFT based fast convolution of data streams with FIR filter kernels. What are the latency, computational efficiency or caching locality (etc.) differences, if any? Or are they the same?

$\endgroup$
27
$\begingroup$

Essentially, OS is slightly more efficient since it does not require the addition of the overlapping transients. However, you may want to use OA if you need to reuse the FFTs with zero-padding rather than repeated samples.

Here is a quick overview from an article I wrote a while ago

Fast convolution refers to the blockwise use of circular convolution to accomplish linear convolution. Fast convolution can be accomplished by OA or OS methods. OS is also known as “overlap- scrap” . In OA filtering, each signal data block contains only as many samples as allows circular convolution to be equivalent to linear convolution. The signal data block is zero-padded prior to the FFT to prevent the filter impulse response from “wrapping around” the end of the sequence. OA filtering adds the input-on transient from one block with the input-off transient from the previous block. In OS filtering, shown in Figure 1, no zero-padding is performed on the input data, thus the circular convolution is not equivalent to linear convolution. The portions that “wrap around” are useless and discarded. To compensate for this, the last part of the previous input block is used as the beginning of the next block. OS requires no addition of transients, making it faster than OA.

$\endgroup$
  • $\begingroup$ Great article! = ) $\endgroup$ – Phonon Jun 29 '12 at 0:52
  • $\begingroup$ There may be some optimizations in the way the DFT over the zero-padded portion of the OA buffer is computed, that give an edge to the OA method. This would depend on your processor and FFT package. Also, you could feasibly write your own FFT algorithm specifically for the OA that takes into account the zero-pad. $\endgroup$ – orodbhen Oct 10 '16 at 17:35
  • $\begingroup$ @orodbhen, do you know of any such FFT package? $\endgroup$ – Mark Borgerding Oct 10 '16 at 18:14
  • $\begingroup$ @MarkBorgerding In OpenCV you can specify the number of zero rows, but that's specific to 2D. As far as what implicit optimizations are present in that or other FFT packages, I don't know. I can think of a lot of cases where a custom FFT to exploit sparseness would be helpful but I haven't gone down that road myself. Not yet. $\endgroup$ – orodbhen Oct 11 '16 at 18:59
  • $\begingroup$ Good thing you quoted because the link is broken :( $\endgroup$ – Mehrdad May 10 at 21:08

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.