Overlap–save method: Difference between revisions

Revision as of 14:43, 8 March 2024

Revision as of 13:13, 31 May 2024

Line 1:

In [[signal processing]], '''''overlap–save''''' is the traditional name for an efficient way to evaluate the [[Convolution#Discrete convolution|discrete convolution]] between a very long signal <math>x[n]</math> and a [[finite impulse response]] (FIR) filter <math>h[n]</math>''':'''

{{NumBlk|:|<math>

{{Equation box 1

|indent= |cellpadding= 0 |border= 0 |background colour=white

|equation={{NumBlk|:|<math>

y[n] = x[n] * h[n]

\ \triangleq\ \sum_{m=-\infty}^{\infty} h[m] \cdot x[n - m]

= \sum_{m=1}^{M} h[m] \cdot x[n - m],

</math> &nbsp; &nbsp;
|{{EquationRef|Eq.1}}}}}}

where {{nowrap|''h''[''m''] {{=}} 0}} for ''m'' outside the region {{nowrap|[1, ''M'']}}.

This article uses common abstract notations, such as <math display="inline">y(t) = x(t) * h(t),</math> or <math display="inline">y(t) = \mathcal{H}\{x(t)\},</math> in which it is understood that the functions should be thought of in their totality, rather than at specific instants <math display="inline">t</math> (see [[Convolution#Notation]]).

Line 35 ⟶ 40:

the convolutions &nbsp;<math>(x_{k,N})*h\,</math>&nbsp; and &nbsp;<math>x_k*h\,</math>&nbsp; are equivalent in the region <math> M+1 \le n \le L+M </math>. It is therefore sufficient to compute the '''N'''-point [[circular convolution|circular (or cyclic) convolution]] of <math>x_k[n]\,</math> with <math>h[n]\,</math>&nbsp; in the region [1,&nbsp;''N'']. &nbsp;The subregion [''M''&nbsp;+&nbsp;1,&nbsp;''L''&nbsp;+&nbsp;''M''] is appended to the output stream, and the other values are <u>discarded</u>.&nbsp; The advantage is that the circular convolution can be computed more efficiently than linear convolution, according to the [[Discrete Fourier transform#Circular convolution theorem and cross-correlation theorem|circular convolution theorem]]''':'''

{{Equation box 1

{{NumBlk|:|<math>y_k[n]\ =\ \scriptstyle \text{IDFT}_N \displaystyle (\ \scriptstyle \text{DFT}_N \displaystyle (x_k[n])\cdot\ \scriptstyle \text{DFT}_N \displaystyle (h[n])\ ),</math>|{{EquationRef|Eq.2}}}}

|indent= |cellpadding= 0 |border= 0 |background colour=white

|equation={{NumBlk|:|<math>y_k[n]\ =\ \scriptstyle \text{IDFT}_N \displaystyle (\ \scriptstyle \text{DFT}_N \displaystyle (x_k[n])\cdot\ \scriptstyle \text{DFT}_N \displaystyle (h[n])\ ),</math>|{{EquationRef|Eq.2}}}} &nbsp; &nbsp;

|{{EquationRef|Eq.2}}}}}}

where''':'''

Line 68 ⟶ 76:

}} Each iteration produces {{nowrap|'''N-M+1'''}} output samples, so the number of complex multiplications per output sample is about''':'''

{{Equation box 1

{{NumBlk|:|<math>\frac{N (\log_2(N) + 1)}{N-M+1}.\,</math>|{{EquationRef|Eq.3}}}}

|indent= |cellpadding= 0 |border= 0 |background colour=white

|equation={{NumBlk|:|<math>\frac{N (\log_2(N) + 1)}{N-M+1}.\,</math>|{{EquationRef|Eq.3}}}} &nbsp; &nbsp;

|{{EquationRef|Eq.3}}}}}}

For example, when '''<math>M'''=201</math> and '''<math>N'''=1024,</math> {{EquationNote|Eq.3}} equals <math>13.67,</math> whereas direct evaluation of {{EquationNote|Eq.1}} would require up to <math>201</math> complex multiplications per output sample, the worst case being when both '''<math>x'''</math> and '''<math>h'''</math> are complex-valued. Also note that for any given '''<math>M''',</math> {{EquationNote|Eq.3}} has a minimum with respect to '''<math>N'''.</math> Figure 2 is a graph of the values of <math>N</math> that minimize {{EquationNote|Eq.3}} for a range of filter lengths (<math>M</math>).

Instead of {{EquationNote|Eq.1}}, we can also consider applying {{EquationNote|Eq.2}} to a long sequence of length <math>N_x</math> samples. The total number of complex multiplications would be: