Overlap–add method: Difference between revisions

Revision as of 16:15, 17 July 2013

Revision as of 00:13, 21 October 2013

Line 1:

TheIn [[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>''':'''

:<math>

Line 33:

where &nbsp;<math>y_k[n] \ \stackrel{\mathrm{def}}{=} \ x_k[n]*h[n]\,</math>&nbsp; is zero outside the region [1,&nbsp;''L''&nbsp;+&nbsp;''M''&nbsp;&minus;&nbsp;1]. &nbsp;And for any parameter &nbsp;<math>N\ge L+M-1,\,</math>&nbsp; it is equivalent to the <math>N\,</math>-point [[circular convolution]] of <math>x_k[n]\,</math> with <math>h[n]\,</math>&nbsp; in the region&nbsp;[1,&nbsp;''N''].

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] = \textrm{IFFT}\left(\textrm{FFT}\left(x_k[n]\right)\cdot\textrm{FFT}\left(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.