|
In [[signal processing]], the '''overlap–add method''' ('''OA''', '''OLA''') is an efficient way to evaluate the discrete [[convolution]] of a very long signal <math>x[n]</math> with a [[finite impulse response]] (FIR) filter <math>h[n]</math>''':'''
[[Image:Overlap-add algorithm.svg|thumb|500px|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.]]
:<math>
The advantage is that the [[circular convolution]] can be computed very efficiently as follows, according to the [[Discrete Fourier transform#Circular convolution theorem and cross-correlation theorem|circular convolution theorem]]:
{{NumBlk|:|<math>y_k[n] = \textrmscriptstyle \text{IFFT} \leftdisplaystyle (\textrm \scriptstyle \text{FFT} \leftdisplaystyle (x_k[n]\right) \cdot \textrmscriptstyle \text{FFT} \leftdisplaystyle (h[n]\right)\right ),</math>
|{{EquationRef|Eq.1}}
}}
where FFT and IFFT refer to the [[fast Fourier transform]] and inverse fast Fourier transform, respectively, evaluated over <math>N</math> discrete points.
== The algorithm Pseudocode==
A [[pseudocode]] of the algorithm is the following:
[[Image:Depiction of overlap-add algorithm.png|frame|none|Figure 1: The overlap–add method{{efn-ua
|<math>y_k(t)</math> in the diagram actually corresponds to <math>y_k[n - kL]</math> in the text.}}]]
Fig. 1 sketches the idea of the overlap–add method. The signal <math>x[n]</math> is first partitioned into non-overlapping sequences, then the [[discrete Fourier transform]]s of the sequences <math>y_k[n]</math> are evaluated by multiplying the FFT of <math>x_k[n]</math> with the FFT of <math>h[n]</math>. After recovering of <math>y_k[n]</math> by inverse FFT, the resulting output signal is reconstructed by overlapping and adding the <math>y_k[n]</math> as shown in the figure. The overlap arises from the fact that a linear convolution is always longer than the original sequences. In the early days of development of the fast Fourier transform, <math>L</math> was often chosen to be a power of 2 for efficiency, but further development has revealed efficient transforms for larger prime factorizations of L, reducing computational sensitivity to this parameter. A [[pseudocode]] of the algorithm is the following:
'''Algorithm 1''' (''OA for linear convolution'')
y(i:k) = y(i:k) + yt(1:k - i + 1) <span style="color:green;">(''add the overlapped output blocks'')</span>
i = i + L
'''end'''
This algorithm is based on the linearity of the DFT.
== Circular convolution with the overlap–add method ==
When sequence ''x''[''n''] is periodic, and ''N''<sub>''x''</sub> is the period, then ''y''[''n''] is also periodic, with the same period. To compute one period of y[n], Algorithm 1 can first be used to convolve ''h''[''n''] with just one period of ''x''[''n'']. In the region {{nowrap|''M'' ≤ ''n'' ≤ ''N''<sub>''x''</sub>}}, the resultant ''y''[''n''] sequence is correct. And if the next {{nowrap|''M'' − 1}} values are added to the first {{nowrap|''M'' − 1}} values, then the region {{nowrap|1 ≤ ''n'' ≤ ''N''<sub>''x''</sub>}} will represent the desired convolution. The modified pseudocode is''':'''
'''Algorithm 2''' (''OA for circular convolution'')
Evaluate Algorithm 1
y(1:M - 1) = y(1:M - 1) + y(Nx + 1:Nx + M - 1)
y = y(1:Nx)
'''end'''
| 