Overlap–add method
918 VIEWS
Everipedia is now IQ.wiki - Join the IQ Brainlist and our Discord for early access to editing on the new platform and to participate in the beta testing.
Overlap–add method
Overlap–add method
Insignal processing, the overlap–add method (OA, OLA) is an efficient way to evaluate the discreteconvolutionof a very long signalwith afinite impulse response(FIR) filter:
![x[n]](https://wikimedia.org/api/rest_v1/media/math/render/svg/864cbbefbdcb55af4d9390911de1bf70167c4a3d)
![h[n]](https://wikimedia.org/api/rest_v1/media/math/render/svg/89981bbbb05ffd469eeadb828c18359965985e46)
![{\begin{aligned}y[n]=x[n]*h[n]\ {\stackrel {{\mathrm {def}}}{=}}\ \sum _{{m=-\infty }}^{{\infty }}h[m]\cdot x[n-m]=\sum _{{m=1}}^{{M}}h[m]\cdot x[n-m],\end{aligned}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1c4b745668c257e4bfd759286a3bcbc1b09fe35)
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_{k}[n]\ {\stackrel {{\mathrm {def}}}{=}}{\begin{cases}x[n+kL]&n=1,2,\ldots ,L\\0&{\textrm {otherwise}},\end{cases}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31f52e643302e5fc43da6801b422fcf23edec21c)
where L is an arbitrary segment length. Then**:**
![x[n]=\sum _{{k}}x_{k}[n-kL],\,](https://wikimedia.org/api/rest_v1/media/math/render/svg/f33a5b92185ef8df40abcfd64c8de367434e2d46)
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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37b306ce8098217c0f1f7d2ac444aad8cdca697d)
where is zero outside the region [1, L + M − 1]. And for any parameter it is equivalent to the-pointcircular convolutionofwith in the region [1, N].
![y_{k}[n]\ {\stackrel {{\mathrm {def}}}{=}}\ x_{k}[n]*h[n]\,](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6fd9f8d3d30edb73c9aea90fc043ecc7b0323a8)
![x_{k}[n]\,](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc9d9200977fc896075d42002a94bfb133d0dd0a)
![h[n]\,](https://wikimedia.org/api/rest_v1/media/math/render/svg/657f337326ef0221b43c4ae709e54fe608a6a527)
The advantage is that the circular convolution can be computed very efficiently as follows, according to the circular convolution theorem**:**
| **(Eq.1)** |
![y_{k}[n]={\textrm {IFFT}}\left({\textrm {FFT}}\left(x_{k}[n]\right)\cdot {\textrm {FFT}}\left(h[n]\right)\right)](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe69512eb4721236f283419737c5c7218b0d5b9e)
where FFT and IFFT refer to thefast Fourier transformand inverse
fast Fourier transform, respectively, evaluated overdiscrete
points.
The algorithm
Fig. 1 sketches the idea of the overlap–add method. The
signalis first partitioned into non-overlapping sequences,
then thediscrete Fourier transformsof the sequencesare evaluated by multiplying the FFT ofwith the FFT of. After recovering ofby inverse FFT, the resulting
output signal is reconstructed by overlapping and adding theas 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,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. Apseudocodeof the algorithm is the
following:
![y_{k}[n]](https://wikimedia.org/api/rest_v1/media/math/render/svg/510488c42185dcb9ae020abf4162b1a53fcb8d0c)
![x_{k}[n]](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c026d7248e9d22c83e7a7e3ae7e913244090146)
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**x 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 M ≤ n ≤ N**x, the resultant y[n] sequence is correct. And if the next M − 1 values are added to the first M − 1 values, then the region 1 ≤ n ≤ N**x will represent the desired convolution. The modified pseudocode is**:**
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 lengthroughly calls forcomplex multiplications. It turns out that the number of complex multiplications
of the overlap-add method are:
accounts for the FFT+filter multiplication+IFFT operation.
The additional cost of thesections 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 ofcan be found by numerical search of the minimum ofby spanning the integerin the range.
Beinga power of two, the FFTs of the overlap–add method
are computed efficiently. Once evaluated the value ofit
turns out that the optimal partitioning ofhas.
For comparison, the cost of the standard circular convolution ofandis:
Hence the cost of the overlap–add method scales almost aswhile the cost of the standard circular convolution method is almost. 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 underMatlab. 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.
See also
References
[3]
Citation Linken.wikipedia.orgThe original version of this page is from Wikipedia, you can edit the page right here on Everipedia.Text is available under the Creative Commons Attribution-ShareAlike License.Additional terms may apply.See everipedia.org/everipedia-termsfor further details.Images/media credited individually (click the icon for details).
Sep 25, 2019, 12:02 AM