AI Glossary / Mathematics and optimization / Intermediate

Overlap - add method

Definition

The overlap - add method computes a long signal's convolution by processing shorter input blocks and adding the portions of their outputs that occupy the same sample positions. It is commonly paired with fast Fourier transforms, or FFTs, to implement long finite impulse response filters efficiently. Correctly assembled, the blocks produce the same linear convolution as processing the complete signal at once, apart from numerical rounding.

What it means

A filter with M coefficients spreads each input block's contribution over more output positions. If a block contains L samples, its full convolution has L + M − 1 samples. Consecutive input blocks can be separate, yet their filtered outputs overlap by M − 1 positions. Those overlapping values represent different contributions to the same final samples and must be added. The method changes how the calculation is organized, not what filter is applied. It is useful for long recordings and continuous streams that cannot conveniently be processed as one enormous transform.

How it works

Divide the input into consecutive, nonoverlapping blocks of L samples. For FFT processing, choose a transform length N at least L + M − 1 and pad both the block and filter with zeros to length N. Multiply their Fourier transforms and apply the inverse transform. Place the resulting block at its original starting position in the output and add contributions wherever positions overlap. The filter's transform can be reused while its coefficients remain fixed. Preserve the unfinished output tail between blocks, and handle the last partial block and final tail explicitly. Adequate padding prevents circular wraparound from corrupting the intended linear convolution.

Three practical examples

An audio processor can apply a long room impulse response to a recording without transforming the whole recording at once.
A monitoring pipeline can filter a lengthy sensor stream in bounded blocks while preserving the filter's response across block boundaries.
An image-processing application can extend block convolution to multiple dimensions, carefully combining contributions around tile boundaries. These uses still require a suitable filter and correct boundary conventions; overlap - add itself does not identify useful signal content or remove noise automatically.

Think of it this way

Think of laying transparent strips on a numbered timeline. Each strip contains the contribution produced by one input block. Where two strips cover the same number, their values are added. The analogy captures alignment and accumulation, but it does not mean that arbitrary overlapping pieces of recorded sound should be mixed; the strips must be the correctly computed convolution contributions.

Worked example

Let the input be [1, 2, 3, 4] and the causal filter be [1, 1, 1]. Use two input blocks of length L = 2: [1, 2] and [3, 4]. With M = 3, choose N = 4 because L + M − 1 = 4. Convolving the first block with the filter gives [1, 3, 3, 2], occupying output positions 0 through 3. The second gives [3, 7, 7, 4], occupying positions 2 through 5 because that input block starts at position 2. Add the overlapping positions: position 2 is 3 + 3 = 6, and position 3 is 2 + 7 = 9. The full output is [1, 3, 6, 9, 7, 4], exactly the direct convolution. Simply joining the two four-sample outputs would produce eight samples and the wrong alignment. The correct full output length is 4 + 3 − 1 = 6. This small example demonstrates assembly; a direct calculation would be simpler than FFTs at this tiny size.

Illustrative case study

In a fictional project, Cedar Audio processes spoken recordings through a fixed acoustic response. Its first block implementation introduces artifacts at regular boundaries because it replaces, rather than adds, the previous block's output tail. The team verifies a short numerical example, corrects the accumulation, and compares the full result with a direct convolution reference. It then benchmarks realistic recordings at several block sizes. The case illustrates boundary verification and measurement without inventing a processing-speed improvement or claiming that the filter improves every recording.

Common misconceptions and mistakes

Overlap - add does not mean that the input blocks must overlap in this basic convolution construction; it is their outputs that overlap. Padding an input to length L alone is insufficient when the filter needs additional output positions. A finite record's final tail must not disappear unless an output-cropping convention deliberately removes it. FFT convolution is not automatically faster for short filters or small inputs. Related windowed short-time Fourier transform methods also use overlap and addition, but their reconstruction conditions involve analysis and synthesis windows and should not be substituted blindly for this block-filtering recipe.

Business use

Choose block size by measuring processing cost, memory and acceptable delay on the actual platform. A larger block can improve computational efficiency while requiring more samples to arrive before processing, which may be unsuitable for interactive audio. Keep filter alignment, sample rate and output length in the interface specification. Test impulses placed immediately before and after block boundaries, along with incomplete final blocks. For an AI pipeline using filtered signals, verify that offline preparation and live processing use equivalent boundary behavior; otherwise the model may receive different inputs despite nominally identical filter coefficients.

Check your understanding

A block has 100 samples and a filter has 21 coefficients. What is the minimum transform length for its full linear convolution?

Answer: 120 samples. A larger efficient FFT length is also valid if the implementation preserves the correct alignment and output handling.

Related terms

Circular convolution
linear convolution
FFT
finite impulse response filter
overlap–save
partitioned convolution

Learn next

reproduce the six-sample output by direct convolution and by block accumulation. Move a single nonzero input across the block boundary and verify that the resulting shifted filter remains continuous in its sample alignment. Then compare runtime and delay for several larger block lengths.

Sources

Sources: Steven W. Smith, The Scientist and Engineer's Guide to Digital Signal Processing, chapter 18, https://www.dspguide.com/CH18.PDF ; SciPy, scipy.signal.oaconvolve documentation, https://docs.scipy.org/doc/scipy/reference/generated/scipy.signal.oaconvolve.html . The short convolution and fictional audio project are original examples. The source-list label contains a damaged dash; the standard spelling is used in this explanation.

Previous: Overfitting Next: Overlap coefficient