Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 38 ยท Filters: FIR

Fast Convolution: Overlap-Add and Overlap-Save

Filter long signals efficiently with FFT-based fast convolution. Implement overlap-add and overlap-save from scratch, count the cost, and compare with scipy.signal.oaconvolve.

Direct convolution of a signal with an M-tap filter costs M multiplications per output sample. For a 2000-tap reverb or a long matched filter, that is a lot of work. The convolution theorem says there is a shortcut: multiply in the frequency domain. With the FFT the cost per sample grows only like log2(N) instead of linearly with the filter length.

There are two catches. The signal may be too long to transform in one go (or may arrive in a stream), and the DFT gives circular convolution (see DFT properties). Two classic block methods solve both: overlap-add and overlap-save.

FFT convolution for one block

For a signal of length L and a filter of length M, the linear convolution has length L + M - 1. Zero-pad both to an FFT size N >= L + M - 1, multiply the spectra, and invert.

Python One-shot FFT convolution

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Overlap-add

  1. Cut the input into blocks of length B.
  2. Convolve each block with h using the FFT with size N >= B + M - 1. Each result has length B + M - 1: it is longer than its block by M - 1 samples.
  3. Place each result at the start of its block in the output buffer and add the overlapping tails together.
flowchart LR
    A["block 1<br/>B samples"] --> C["FFT conv.<br/>B+M-1 outputs"]
    B["block 2<br/>B samples"] --> D["FFT conv.<br/>B+M-1 outputs"]
    C --> E["add overlapping tails<br/>(M-1 samples)"]
    D --> E
    E --> F["output stream"]

Each block's output spills M-1 samples into the next block's region; adding gives the exact linear convolution.

Python Overlap-add from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Overlap-save

Overlap-save does the opposite: it avoids the add step by throwing away the wrapped part.

  1. Take blocks of length N (the FFT size) that overlap by M - 1 samples with the previous block.
  2. Multiply the block's FFT by the filter's FFT (circular convolution of length N).
  3. The first M - 1 output samples are corrupted by wrap-around: discard them. The remaining N - M + 1 samples are exact and are saved to the output.

It needs no additions between blocks and is the favourite in real-time software.

Python Overlap-save from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

How much does it save?

Direct convolution costs about L * M multiplications for L output samples. FFT-based block convolution with FFT size N costs about three transforms per block (one forward for the data, one inverse; the filter's FFT is reused), each (N/2) log2 N, and yields N - M + 1 outputs. Let's count.

Python Multiplication counts: direct versus FFT blocks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The FFT cost grows only logarithmically with the filter length, while the direct cost grows linearly: at 4096 taps the FFT needs about 18 multiplications per sample against 4096. This simple count ignores overhead (memory traffic, padding, complex arithmetic), so in practice direct convolution is still faster for very short filters, and libraries switch to the FFT at a few dozen taps.

Real-time and streaming use

In a real-time application, the block size sets the latency: you must collect a whole block before you can process it. Small blocks mean low latency but lower efficiency. An audio plug-in may run blocks of 64 to 512 samples. Hybrid schemes (partitioned convolution) split a long impulse response into pieces: a short direct part for zero latency and FFT blocks for the rest. Convolution reverb uses this.

When you filter in blocks with lfilter (an FIR or IIR filter) rather than FFTs, you must carry the filter state between calls to avoid start-up glitches in every block.

Python Block processing with filter state (lfilter zi)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Library tools

scipy.signal.fftconvolve does a single large FFT convolution. scipy.signal.oaconvolve implements overlap-add and is the best choice when one input is much longer than the other. scipy.signal.convolve(x, h, method="auto") picks direct or FFT for you.

Python oaconvolve and the automatic method choice

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can't you just multiply the DFTs of x and h without padding?

    DFT multiplication implements circular convolution of length N.
  2. 2. In overlap-add, what happens to the extra M - 1 output samples of each block?

    Each block's output is longer than its input block; the tails overlap and are summed.
  3. 3. In overlap-save, which samples of each block's output are discarded?

    Only the first M - 1 outputs of a circular convolution are affected by wrap-around.
  4. 4. A longer block size in FFT convolution mostly increases:

    You must wait for the whole block before processing it.

Summary

  • FFT convolution multiplies spectra, which is far cheaper than direct convolution for long filters.
  • Zero-pad to at least L + M - 1 to avoid circular wrap-around.
  • Overlap-add: convolve blocks, add the overlapping tails. Overlap-save: overlap the input blocks and discard the first M - 1 outputs.
  • Block size trades efficiency against latency.
  • For block-wise time-domain filtering with lfilter, carry the state zi from block to block; use oaconvolve for long inputs.

Next: FIR Design in Practice