1 Overview of overlap-add (OLA)

1.1 Core idea: blockwise convolution and recombination

Overlap-add (OLA) is a method for computing the linear convolution of a long input signal with a filter by splitting the input into shorter segments. Each segment is processed separately (often using fast Fourier transforms), producing a partial convolution result. These partial results overlap in time, and the final output is formed by summing the overlapping samples.

This strategy is advantageous when the overall convolution length is large, because it replaces one large convolution with multiple smaller ones whose computational cost is reduced.

1.2 Relationship to convolution and linear time-invariant systems

In a linear time-invariant (LTI) system, the output is the convolution of the input signal with the system’s impulse response. OLA provides a practical way to realize this convolution for long signals without directly computing all pairwise multiplications in the time domain. Conceptually, it preserves the defining behavior of convolution: each output sample reflects contributions from the appropriate portions of the input weighted by the filter.

1.3 When OLA is preferred over direct convolution

OLA is typically favored when:

  • The input signal is long or arrives in a stream, making a single batch convolution inefficient.
  • The filter is fixed (e.g., an FIR filter), allowing precomputation of frequency-domain representations.
  • FFTs offer favorable scaling relative to direct time-domain convolution.

Direct convolution can still be appropriate for very short signals, small filters, or when computational simplicity outweighs performance gains.

2 Mathematical foundation

2.1 Convolution basics and block partitioning

2.1.1 Defining input blocks and time indices

Let the input be \(x[n]\) and the filter (impulse response) be \(h[n]\). The linear convolution is \[ y[n] = (x * h)[n] = \sum_{k=-\infty}^{\infty} x[k]\, h[n-k]. \] In OLA, the input is partitioned into blocks of length \(L\). A common block index \(m\) selects samples \[ x_m[n] = x[mL + n], \quad 0 \le n \le L-1. \] Each block is treated as a finite-length sequence for processing.

2.1.2 Handling filter length and output delay

Suppose the filter has length \(M\) (e.g., \(h[0],\dots,h[M-1]\) are nonzero). Linear convolution between a block of length \(L\) and an \(M\)-tap FIR produces \(L+M-1\) nonzero samples. Therefore, each block generates a partial output segment of length \(L+M-1\), which must be placed at the correct absolute time position relative to the original input indexing.

2.2 Overlap region interpretation

Because each input block starts \(L\) samples apart, the partial results extend beyond their “own” block duration by \(M-1\) samples. Those tail portions overlap with the head portions produced by subsequent blocks. The overlap length determines how many samples from neighboring partial convolutions must be summed.

2.3 Output stitching via summation

Let \(y_m[n]\) denote the convolution result of block \(x_m\) with \(h\), producing samples indexed over \(0\le n\le L+M-2\). The full output is assembled by adding shifted partial results: \[ y[n] = \sum_m y_m[n - mL], \] where terms outside each partial segment are treated as zero. This “add overlapping samples” rule is the defining reconstruction step in OLA.

3 FFT-based implementation

3.1 Choosing between time-domain and FFT-domain processing

OLA can be performed with direct time-domain convolution per block, but the typical motivation is FFT efficiency for larger \(M\) and \(L\). When the filter length or block size grows, the FFT-based approach often reduces computation by turning convolution into multiplication in the frequency domain.

3.2 Frequency-domain block convolution

3.2.1 Zero-padding requirements

FFT-based convolution performed on finite-length sequences is inherently circular unless padding is used. To emulate linear convolution for each block, both the block and the filter must be padded to at least the linear-convolution length \(N \ge L+M-1\). With this padding, the circular convolution computed by the FFT corresponds to the desired linear convolution over the relevant range.

A typical construction is:

  • form a zero-padded block \(\tilde{x}_m\) of length \(N\),
  • zero-pad the filter to the same length \(\tilde{h}\) (often precomputed once),
  • compute FFTs, multiply spectra, and inverse FFT.

3.2.2 Managing FFT sizes and efficiency

The FFT length \(N\) is a key design knob. Choosing \(N\) equal to the smallest value that satisfies \(N \ge L+M-1\) can reduce arithmetic work. In practice, many systems also prefer \(N\) values with efficient factorization (e.g., powers of two), even if slightly larger than the minimum, because FFT libraries can be faster for certain sizes.

Since each block uses the same filter, \( \text{FFT}(\tilde{h}) \) can be reused, reducing per-block overhead.

3.3 Complexity and performance considerations

If each block uses an FFT of length \(N\), the per-block cost is dominated by FFT and inverse FFT operations and a complex pointwise multiplication. The total cost scales with the number of blocks, approximately the input length divided by the block hop (often \(L\) in canonical OLA). Compared to direct convolution, OLA’s advantage becomes clearer for long signals, where the FFT overhead is amortized across many samples.

4 Practical design parameters

4.1 Selecting block length and hop size

4.1.1 Impact on latency and throughput

Block length \(L\) (and the implied hop size in classic OLA) influences:

  • Latency: OLA typically requires processing an entire block before its convolution contribution becomes available.
  • Throughput: larger blocks reduce the number of FFT calls but may increase per-block compute and memory.
  • Overlap behavior: the relationship between \(L\) and filter length \(M\) affects how much summation overlap occurs.

Systems targeting real-time operation often tune \(L\) to balance prompt output availability against CPU efficiency.

4.2 Selecting zero-padding length

The zero-padding length \(N\) must prevent circular-convolution artifacts. A standard requirement is \(N \ge L+M-1\). If \(N\) is too small, energy from one block’s circular wrap-around contaminates the overlap region, producing incorrect outputs.

Choosing a larger \(N\) than necessary can improve FFT efficiency if it matches fast transform lengths in the implementation, but it increases memory and compute per block.

4.3 Windowing considerations (when applicable)

For linear convolution via OLA, OLA does not inherently require a window on the input blocks, because the method aims to preserve the exact time-domain segments that compose the original signal. However, in variants used for spectral processing or for certain overlap strategies, windowing may be applied to reduce artifacts or to satisfy constraints for specific reconstruction objectives. Whether windowing is appropriate depends on the overall processing goals, not on OLA alone.

5 Step-by-step algorithm

5.1 Preprocessing: partitioning and padding

  1. Choose:
  • block length \(L\),
  • filter length \(M\),
  • FFT length \(N \ge L+M-1\).
  1. Partition input \(x[n]\) into blocks of length \(L\): \(x_m[n]=x[mL+n]\).
  2. Zero-pad each block \(x_m\) and the filter \(h\) to length \(N\).
  3. Precompute \(H = \text{FFT}(\tilde{h})\) if the filter is fixed.

5.2 Per-block processing flow

5.2.1 Compute block convolution

For each block \(m\):

  1. Compute \(X_m = \text{FFT}(\tilde{x}_m)\).
  2. Multiply spectra: \(Y_m = X_m \cdot H\).
  3. Inverse FFT to obtain time-domain result: \(y_m = \text{IFFT}(Y_m)\).
  4. Keep the first \(L+M-1\) samples of \(y_m\) as the valid partial convolution output for that block.

5.3 Accumulation and overlap-add reconstruction

  1. Initialize the output buffer \(y[n]\) to zeros with enough length to hold the full convolution duration.
  2. For each block \(m\), add the partial result into the output at the offset \(mL\):

\[ y[mL + n] \mathrel{+}= y_m[n],\quad 0 \le n \le L+M-2. \]

  1. After processing all blocks, the buffer contains the linear convolution result (within the expected finite-length extent determined by how the input is handled at the ends).

6 Examples and verification

6.1 Simple toy example with small signals

Consider a short input \(x = [x_0,x_1,x_2,x_3]\) and a filter \(h=[h_0,h_1,h_2]\) (so \(M=3\)). Choose \(L=2\), giving two blocks:

  • Block 0: \([x_0,x_1]\)
  • Block 1: \([x_2,x_3]\)

Each block produces \(L+M-1=4\) samples. The first partial convolution covers output indices \(0\) to \(3\). The second covers indices \(2\) to \(5\). The overlap at indices \(2\) and \(3\) is where partial results must be added. Summing those overlapping samples yields the same output as direct linear convolution.

6.2 Using OLA for FIR filtering

If \(h\) is a finite impulse response (FIR) filter, OLA naturally applies because the system memory is finite (length \(M\)). In a streaming scenario, as each new block arrives, the method produces the corresponding new output segment while previous contributions have already been placed into the accumulation buffer.

A common verification approach is to feed an impulse input \(x[n]=\delta[n]\). The output should match the filter coefficients \(h[n]\) in the expected indexing.

6.3 Using OLA for long streaming audio

6.3.1 Checking boundary conditions and continuity

For audio streams, the main practical concerns are:

  • Initial conditions: the first blocks assume prior input samples are zero unless the system state is explicitly carried.
  • End handling: if the stream ends, the final blocks may require zero-padding to compute the tail response.
  • Continuity: overlap-add must be implemented so that sample boundaries align correctly in the output buffer; otherwise, audible glitches or discontinuities can occur.

Verification typically uses a known test signal (e.g., sine sweeps) and compares the OLA output against a reference convolution computed offline.

7 Comparison with overlap-save

7.1 Conceptual differences

Overlap-save (OLS) is another FFT-based block convolution method. Whereas OLA keeps the entire convolution result for each block and sums overlaps, OLS discards a portion of each block’s output that is corrupted by circular convolution, and concatenates the remaining valid samples.

In OLA, the overlap region is retained and combined through addition. In OLS, invalid wrap-around regions are removed, so recombination differs.

7.2 Throughput and boundary handling trade-offs

Key trade-offs include:

  • Output efficiency: OLS can produce valid output with less overlap summation complexity, but it may discard some samples per block.
  • Boundary behavior: OLA may be simpler to reason about when reconstructing full-length convolution, while OLS can be advantageous for continuous streaming because it more directly yields “valid” samples each block after an initial transient.
  • Implementation convenience: depending on how an application buffers data, one method may require fewer bookkeeping steps.

7.3 Choosing between OLA and overlap-save

OLA is commonly chosen when:

  • The straightforward “add overlapping tails” approach aligns well with the desired output buffering.
  • Simplicity of reconstruction is prioritized.

OLS is often chosen when:

  • The system is designed around producing only “valid” convolution samples per block.
  • Discarding a predictable initial segment each block is acceptable and simplifies streaming logic.

In many practical DSP systems, both methods are available, and selection depends on performance benchmarks and integration details.

8 Applications in signal processing

8.1 Real-time audio and streaming systems

OLA enables efficient convolution over long durations, which is useful in room impulse response (RIR) simulation, headphone/earphone filtering, and other audio effects requiring convolution-like processing. By processing data in blocks, the system can maintain a steady computational load rather than attempting a prohibitively large batch operation.

8.2 Efficient convolution in DSP libraries

Many DSP libraries implement block convolution for performance. OLA is a common option when the filter is fixed and the library can reuse FFTs of the filter, reducing overhead. Users may select block sizes and overlap strategy via library parameters.

8.3 Hybrid approaches and multi-rate systems

In hybrid processing chains, one may use OLA for certain stages (e.g., long-range filtering) while other stages use time-domain filtering or decimation/interpolation. In multi-rate systems, the convolution method must respect sample-rate changes so that block boundaries and filter lengths correspond to the effective time scale at each rate.

9 Common pitfalls and troubleshooting

9.1 Off-by-one indexing and alignment errors

A frequent source of incorrect results is misalignment between:

  • where a block’s partial convolution is inserted in the output buffer,
  • how input indices map to block indices,
  • and the assumed lengths of filter and block.

Off-by-one mistakes can shift the entire response, producing a consistent delay error or phase-like artifacts.

9.2 Incorrect padding leading to circular convolution artifacts

If \(N\) is less than \(L+M-1\), the FFT-based method computes circular convolution for each block, causing wrap-around interference. Symptoms include energy appearing earlier than expected, distorted overlap sums, or persistent discrepancies compared to a reference linear convolution.

9.3 Scaling/normalization and gain mismatches

FFT implementations differ in normalization conventions (e.g., whether the forward or inverse transform includes scaling). If not handled consistently, the reconstructed output may have incorrect amplitude. Verification using impulse or step tests helps detect scaling errors quickly.

10 Implementation notes and resources

10.1 Reference pseudocode and data structures

A minimal OLA implementation typically maintains:

  • an FFT length \(N\),
  • block length \(L\),
  • a precomputed filter spectrum \(H\),
  • an output buffer \(y\) initialized to zeros,
  • and per-block temporary arrays for \(X_m\) and the inverse FFT result.

Pseudo-logic follows the steps in Section 5: partition, zero-pad, FFT multiply, inverse FFT, then add into the shifted output buffer.

10.2 Testing methodology (impulse/step responses)

Robust testing includes:

  • Impulse input: output should match \(h\).
  • Step input: output should match the cumulative response implied by convolution.
  • Random input compared to a direct convolution reference for moderate lengths (where direct computation is feasible).

Tests should cover short signals, long signals, and cases where the stream ends mid-block.

Related techniques include overlap-save, fast convolution variants, partitioned convolution (splitting filters into frequency-domain and time-domain parts), and adaptive block sizing strategies. Reading typically focuses on DSP implementation details such as FFT efficiency, buffering schemes, and numerical precision.