Overlap–add method: Difference between revisions

Revision as of 16:11, 14 January 2021

Revision as of 15:31, 6 February 2021

Line 3:

In [[signal processing]], the '''overlap–add method''' 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|Fig 1: A sequence of 5five plots depicts one cycle of the Overlapoverlap-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.]]

{{NumBlk|:|<math>

Line 40:

where''':'''

* DFT_N and IDFT_N refer to the [[Discrete Fourier transform]] and its inverse, evaluated over ''N'' discrete points, and

* {{math|L}} is customarily chosen such that {{math|N {{=}} L+M-1}} is an integer power-of-2, and the transforms are implemented with the [[Fast Fourier transform|FFT]] algorithm, for efficiency.

==Pseudocode==

The following is a [[pseudocode]] of the algorithm:

Line 62 ⟶ 61:

'''end'''

== Efficiency considerations ==

[[Image:FFT_size_vs_filter_length_for_Overlap-add_convolution.svg|thumb|400px|Fig 2: A graph of the values of N (an integer power of 2) that minimize the cost function <math>\tfrac{N\left(\log_2 N + 1\right)}{N - M + 1}</math>]]

Line 85 ⟶ 84:

[[Image:gain oa method.png|frame|none|Fig 3: Gain of the overlap-add method compared to a single, large circular convolution. The axes show values of signal length N_x and filter length N_h.]]

== See also ==

* [[Overlap–save method]]

==Notes==

Line 109 ⟶ 108:

}}

== Further reading==

*{{Cite book

|author1=Oppenheim, Alan V. |author2=Schafer, Ronald W. | title=Digital signal processing