Overlap–add method

This article is about a method of performing convolution, not to be confused with WOLA (Weight, OverLap, Add), which is a method of performing channelization. See Sampling the DTFT

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)

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

A sequence of 5 plots depicts one cycle of the Overlap-add convolution algorithm. The first plot is a long sequence of data to be processed with a lowpass FIR filter. The 2nd plot is one segment of the data to be processed in piecewise fashion. The 3rd plot is the filtered segment, including the filter rise and fall transients. The 4th plot indicates where the new data will be added with the result of previous segments. The 5th plot is the updated output stream. The FIR filter is a boxcar lowpass with M=16 samples, the length of the segments is L=100 samples and the overlap is 15 samples.

$y[n]=x[n]*h[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot x[n-m]=\sum _{m=1}^{M}h[m]\cdot x[n-m],$

where h[m] = 0 for m outside the region [1, M].

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

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

where L is an arbitrary segment length. Then:

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

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

${\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 $y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]\,$ is zero outside the region [1, L + M − 1]. And for any parameter $N\geq L+M-1,\,$ it is equivalent to the $N\,$-point circular convolution of $x_{k}[n]\,$ with $h[n]\,$ in the region [1, N].

The advantage is that the circular convolution can be computed very efficiently as follows, according to the circular convolution theorem:

$y_{k}[n]=\scriptstyle {\text{IFFT}}\displaystyle (\ \scriptstyle {\text{FFT}}\displaystyle (x_{k}[n])\cdot \scriptstyle {\text{FFT}}\displaystyle (h[n])\ ),$ Eq.1

where FFT and IFFT refer to the fast Fourier transform and inverse fast Fourier transform, respectively, evaluated over $N$ discrete points.

Pseudocode

A pseudocode of the algorithm is the following:

   Algorithm 1 (OA for linear convolution)
   Evaluate the best value of N and L (L > 0, N = M + L - 1 nearest to power of 2).
   Nx = length(x);
   H = FFT(h, N)       (zero-padded FFT)
   i = 1
   y = zeros(1, M + Nx - 1)
   while i <= Nx  (Nx: the last index of x[n])
       il = min(i + L - 1, Nx)
       yt = IFFT( FFT(x(i:il), N) * H, N)
       k  = min(i + N - 1, M + Nx - 1)
       y(i:k) = y(i:k) + yt(1:k - i + 1)    (add the overlapped output blocks)
       i = i + L
   end

Cost of the overlap-add method

The cost of the convolution can be associated to the number of complex multiplications involved in the operation. The major computational effort is due to the FFT operation, which for a radix-2 algorithm applied to a signal of length $N$ roughly calls for $C={\frac {N}{2}}\log _{2}N$ complex multiplications. It turns out that the number of complex multiplications of the overlap-add method are:

$C_{OA}=\left\lceil {\frac {N_{x}}{N-M+1}}\right\rceil N\left(\log _{2}N+1\right)\,$

$C_{OA}$ accounts for the FFT + filter multiplication + IFFT operation.

The additional cost of the $M_{L}$ sections involved in the circular version of the overlap–add method is usually very small and can be neglected for the sake of simplicity. The best value of $N$ can be found by numerical search of the minimum of $C_{OA}\left(N\right)=C_{OA}\left(2^{m}\right)$ by spanning the integer $m$ in the range $\log _{2}\left(M\right)\leq m\leq \log _{2}\left(N_{x}\right)$. Being $N$ a power of two, the FFTs of the overlap–add method are computed efficiently. Once evaluated the value of $N$ it turns out that the optimal partitioning of $x[n]$ has $L=N-M+1$. For comparison, the cost of the standard circular convolution of $x[n]$ and $h[n]$ is:

$C_{S}=N_{x}\left(\log _{2}N_{x}+1\right)\,$

Hence the cost of the overlap–add method scales almost as $O\left(N_{x}\log _{2}N\right)$ while the cost of the standard circular convolution method is almost $O\left(N_{x}\log _{2}N_{x}\right)$. However such functions accounts only for the cost of the complex multiplications, regardless of the other operations involved in the algorithm. A direct measure of the computational time required by the algorithms is of much interest. Fig. 2 shows the ratio of the measured time to evaluate a standard circular convolution using Eq.1 with the time elapsed by the same convolution using the overlap–add method in the form of Alg. 2, vs. the sequence and the filter length. Both algorithms have been implemented under Matlab. The bold line represents the boundary of the region where the overlap–add method is faster than the standard circular convolution. Note that the overlap–add method in the tested cases can be three times faster than the standard method.

Figure 2: Ratio between the time required by Eq.1 and the time required by the overlap–add Alg. 2 to evaluate a complex circular convolution, vs the sequence length $N_{x}$ and the filter length $M$.

See also

• Overlap–save method

Further reading

• Oppenheim, Alan V.; Schafer, Ronald W. (1975). Digital signal processing. Englewood Cliffs, N.J.: Prentice-Hall. ISBN 0-13-214635-5.
• Hayes, M. Horace (1999). Digital Signal Processing. Schaum's Outline Series. New York: McGraw Hill. ISBN 0-07-027389-8.