Overlap–add Method

In signal processing, the overlap–add method is an efficient way to evaluate the discrete convolution of a very long signal x /math> with a finite impulse response (FIR) filter h /math>:

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

The concept is to divide the problem into multiple convolutions of ''h'' 'n''with short segments of x /math>:

:x_k \triangleq\ \begin
x + kL & n = 1, 2, \ldots, L\\
0, & \text,
\end

where ''L'' is an arbitrary segment length. Then:

:x = \sum_ x_k - kL\,

and ''y'' 'n''can be written as a sum of short convolutions:

:\begin
y = \left(\sum_ x_k - kLright) * h &= \sum_ \left(x_k - kL* h right)\\
&= \sum_ y_k - kL
\end

where the linear convolution y_k \triangleq\ x_k * h , is zero outside the r