Overlap–add method

The Overlap-add Method

The overlap-add method (OA) is an efficient way to evaluate the discrete convolution between a very long signal $x(n)$ with a FIR filter $h(n)$ .

The basic idea is to use block convolution between short segments of $x(n)$ and the FIR filter through the FFT algorithm. Strictly speaking, let $x(n)$ , $n=1,2,\ldots ,N_{x}$ a $N_{x}$ -point signal that has to be convolved with a short filter $h(n)$ , $n=1,\ldots ,N_{h}$ , with $N_{h}\ll N_{x}$ . The result of the convolution turns out to be:

y(n)=x(n)*h(n)\,\quad \quad (1)

Such linear convolution coincide with the $N$ -point circular convolution of $x(n)$ and $h(n)$ provided that $N\geq N_{x}+N_{h}-1$ . The circular convolution can be evaluated in an efficient way through the FFT algorithm (standard approach):

y(n)={\textrm {IFFT}}\left({\textrm {FFT}}\left(x(n)\right)\cdot {\textrm {FFT}}\left(h(n)\right)\right)\quad \quad (2)

where FFT and IFFT refer to the fast Fourier transform and inverse fast Fourier transform, respectively, evaluated over $N$ discrete points. Instead of computing the global FFT of $x(n)$ , the overlap-add method makes use of the following identity:

x(n)=\sum _{k=0}^{M-1}x_{k}(n-kL)

where:

x_{k}(n)={\begin{cases}x(n+kL)&n=1,2,\ldots ,L\\0&{\textrm {else}}\end{cases}}

and $M=\left\lceil {\frac {N_{x}}{L}}\right\rceil$ is the number of block into which $x(n)$ is subdivided. $\left\lceil z\right\rceil$ indicates the smallest integer larger than $z$ . One can therefore write the linear convolution (1) as the following block convolution:

y(n)=\sum _{k=0}^{M-1}x_{k}(n-kL)*h(n)=\sum _{k=0}^{M-1}y_{k}(n-kL)

where $y_{k}(n)=x_{k}(n)*h(n)$ is a sequence of length $N_{FFT}=N_{h}+L-1$ . The sequence $y_{k}(n)$ , $n=1,2,\ldots ,N_{FFT}$ can be evaluated with the same approach of (2), but with shorter FFTs of length $N_{FFT}$ . Due to the nonlinear relation between the cost of the FFT and the sequence length, the overlap-add method can be faster than performing the circular convolution directly with only one block, i.e. with (2).

The Algorithm

Fig. 1 sketches the idea of the overlap-add method. The signal $x(n)$ is first partitioned into non-overlapping sequences, then the discrete Fourier transforms of the sequences $y_{k}(n)$ are evaluated by multiplying the FFT of $x_{k}(n)$ with the FFT of $h(n)$ . After recovering of $y_{k}(n)$ by inverse FFT, the resulting output signal is reconstructed by overlapping and adding the $y_{k}(n)$ as shown in the figure. The overlap arises form the fact that a linear convolution is always longer than the original sequences. Note that $L$ should be chosen to have $N_{FFT}$ a power of 2 which makes the FFT computation efficient. A pseudocode of the algorithm is the following:

   Algorithm 1 (OA for linear convolution)
    $\,$ 
   Evaluate the best value of NFFT and L
   H = FFT(h,NFFT)
   i = 1
   while i <= Nx
       il = min(i+L-1,Nx)
       yt = IFFT( FFT(x(i:il,NFFT)) * H )
       k  = min(i+NFFT-1,Nx)
       y(i:k) = y(i:k) + yt
       i = i+L
   end

Circular convolution with the Overlap-add method

The overlap-add method can be used as well to evaluate circular convolutions, i.e. convolutions of periodic signals. In this case $x(n)$ and $y(n)$ are vectors of $N_{x}$ points containing one period of the corresponding periodic sequences, ${\tilde {x}}(n)$ and ${\tilde {y}}(n)$ respectively. The method is the same as the one sketched in Fig. 1 except that now the first $M_{L}=\left\lfloor {\frac {N_{FFT}-1}{L}}\right\rfloor$ sections of $y(n)$ receive overlapping samples from the convolution of $h(n)$ with the period of ${\tilde {x}}(n)$ placed before the period having $x(n)$ as samples. $\left\lfloor z\right\rfloor$ indicates the largest integer smaller than $z$ . Note that, in the general case with $N_{x}/L$ non-integer, the $M_{L}$ sections ending the last period before $x(n)$ differ from the last $M_{L}$ sections of the vector $x(n)$ . The algorithm Alg. 1 can be extended in the following way:

   Algorithm 2 (OA for circular convolution)
    $\,$ 
   Evaluate Algorithm 1
   ML =  $\left\lfloor \right.$ (NFFT-1)/L $\left.\right\rfloor$ 
   i = Nx-L+1
   k = NFFT - L
   while k >= 1
       il = i+L-1
       yt = IFFT( FFT(x(i:il,NFFT)) * H )
       y(1:k) = y(1:k) + yt(NFFT-k+1:NFFT)
       k  = k-L
       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_{FFT}-N_{h}+1}}\right\rceil N_{FFT}\left(\log _{2}N_{FFT}+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_{FFT}$ can be found by numerical search of the minimum of $C_{OA}\left(N_{FFT}\right)=C_{OA}\left(2^{m}\right)$ by spanning the integer $m$ in the range $\log _{2}\left(N_{h}\right)\leq m\leq \log _{2}\left(N_{x}\right)$ . Being $N_{FFT}$ a power of two, the FFTs of the overlap-add method are computed efficiently. Once evaluated the value of $N_{FFT}$ it turns out that the optimal partitioning of $x(n)$ has $L=N_{FFT}-N_{h}+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_{FFT}\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 (2) 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 algortihms have been implemented under Matlab. The bold line represent the boundary of the region where the overlap-add method is faster (ratio>1) 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 (2) 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 $N_{h}$ .

References

Hayes, M.H. (1999). Digital Signal Processing. Schaum's Outline Series. McGraw-Hill.

Oppenheim, A.V. (1975). Digital Signal Processing. Prentice-Hall, Englewood Cliffs, NJ. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

External Links

Matlab for the implementation of the overlap-add method through the function fftfilt.m.