Field Guide · algorithm

Also known as: overlap-add, overlap-save, overlap-discard, fast convolution

Overlap-add and overlap-save are two block-processing methods that carry out FIR filtering — the convolution of a long input stream with a filter’s impulse response — efficiently by doing the work in the frequency domain with an FFT.12 Multiplying two spectra is equivalent to convolving in time, so for a long filter it is far cheaper to FFT a block, multiply by the filter’s stored frequency response, and inverse-FFT than to compute the direct sample-by-sample sum. Both methods exist to solve the same problem: an FFT gives circular convolution, but filtering needs linear convolution, and the two differ at the block edges.

overlap-add tails summed ↓ add overlapping tails ↓ overlap-save dashed = discarded solid = kept output
Overlap-add zero-pads blocks and sums the wrap-around tails; overlap-save overlaps input blocks and discards the wrap-corrupted leading samples of each result.

How it works

A length-M FIR filter convolving with a length-N block produces N+M-1 output samples, but an L-point FFT (with L ≥ N+M-1) only holds L. Circular convolution wraps the extra M-1 samples back onto the start of the block, corrupting it. The two methods handle that wrap differently:

  • Overlap-add. Cut the input into non-overlapping blocks of length N, zero-pad each to length L = N+M-1, filter it (FFT, multiply, inverse-FFT). Each filtered block is N+M-1 long, so its last M-1 samples spill into the next block’s time span. Lay the blocks end to end and add the overlapping tails. The sum reconstructs exact linear convolution.
  • Overlap-save (overlap-discard). Let the input blocks overlap by M-1 samples. Filter each L-point block with the FFT; the first M-1 output samples are the corrupted circular-wrap region, so simply discard them and keep the rest. No addition is needed — the overlap supplies the history each block needs.

Both give bit-for-bit the same result as a direct FIR; they only differ in bookkeeping. Overlap-add sums tails and zero-pads; overlap-save discards a prefix and overlaps input.

In practice

The speed win is large when the filter is long: direct convolution costs O(N·M) per block while the FFT route costs O(L log L), so once M is more than a few dozen taps the FFT method dominates. The block/FFT size L is tuned to balance FFT efficiency against latency — bigger blocks amortise the FFT better but delay the output more. Overlap-save is often marginally leaner because it avoids the add step, while overlap-add composes naturally when outputs are accumulated from several sources.

The same machinery generalises to channelization: an FFT-based channelizer or fast-convolution filter bank splits a wideband capture into many narrow channels at once by filtering blocks in the frequency domain and selecting sub-bands, reusing exactly the overlap bookkeeping described here.

Relevance to SDR

Fast convolution is a core efficiency tool in SDR. Filtering a wideband I/Q stream with a sharp, long FIR — for channel selection, pulse-shaping, or matched filtering — is often cheapest via overlap-save block convolution, and wideband channelizers that peel dozens of trunking channels out of one capture are built on the same block-FFT structure. Efficient digital filtering of this kind is what lets a general-purpose CPU keep up with megahertz-wide SDR front ends in real time.

GopherTrunk’s decode chain leans on direct/polyphase time-domain filtering and per-channel down-conversion for its trunking work, but the overlap methods are the standard way to make long-FIR and channelizing operations fast, and any FFT-based wideband filtering follows this block-and-stitch pattern.

Sources

  1. Overlap–add method — Wikipedia, on zero-padded block convolution with tail summation. ↩

  2. Overlap–save method — Wikipedia, on overlapping input blocks with discard of the wrap-corrupted output. ↩

See also