Overlap–add method

In signal processing, the overlap–add method is an efficient way to evaluate the discrete convolution of a very long signal ${\displaystyle x[n]}$ with a finite impulse response (FIR) filter ${\displaystyle h[n]}$:

where ${\displaystyle h[m]=0}$ for ${\displaystyle m}$ outside the region ${\displaystyle [1,M].}$  This article uses common abstract notations, such as ${\textstyle y(t)=x(t)*h(t),}$ or ${\textstyle y(t)={\mathcal {H}}\{x(t)\},}$ in which it is understood that the functions should be thought of in their totality, rather than at specific instants ${\textstyle t}$ (see Convolution#Notation).

The concept is to divide the problem into multiple convolutions of ${\displaystyle h[n]}$ with short segments of ${\displaystyle x[n]}$:

${\displaystyle x_{k}[n]\ \triangleq \ {\begin{cases}x[n+kL],&n=1,2,\ldots ,L\\0,&{\text{otherwise}},\end{cases}}}$

where ${\displaystyle L}$ is an arbitrary segment length. Then:

${\displaystyle x[n]=\sum _{k}x_{k}[n-kL],\,}$

and ${\displaystyle y[n]}$ can be written as a sum of short convolutions:

${\displaystyle {\begin{aligned}y[n]=\left(\sum _{k}x_{k}[n-kL]\right)*h[n]&=\sum _{k}\left(x_{k}[n-kL]*h[n]\right)\\&=\sum _{k}y_{k}[n-kL],\end{aligned}}}$

where the linear convolution ${\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]\,}$ is zero outside the region ${\displaystyle [1,L+M-1].}$ And for any parameter ${\displaystyle N\geq L+M-1,\,}$ it is equivalent to the ${\displaystyle N}$-point circular convolution of ${\displaystyle x_{k}[n]\,}$ with ${\displaystyle h[n]\,}$ in the region ${\displaystyle [1,N].}$  The advantage is that the circular convolution can be computed more efficiently than linear convolution, according to the circular convolution theorem:

where:

• DFT_N and IDFT_N refer to the Discrete Fourier transform and its inverse, evaluated over ${\displaystyle N}$ discrete points, and
• ${\displaystyle L}$ is customarily chosen such that ${\displaystyle N=L+M-1}$ is an integer power-of-2, and the transforms are implemented with the FFT algorithm, for efficiency.