Overlap–save method: Difference between revisions

Revision as of 06:34, 23 January 2020

Revision as of 16:16, 23 January 2020

Line 29:

:<math>y[n] = \sum_{m=1}^{M} h[m] \cdot x_k[n-kL-m] \ \ \triangleq \ \ y_k[n-kL].</math>

With the substitution &nbsp;{{math|j ≜ n-kL}},&nbsp; the task is reduced to computing {{math|y{{sub|k}}(j)}}, for '''''M''''' &nbsp;≤&nbsp; {{mvar|j}} &nbsp;≤&nbsp; '''''L''&nbsp;+''&nbsp;M''&nbsp;−&nbsp;1'''. These steps are illustrated in the first 3 traces of Figure 1, except that the desired portion of the output (third trace) corresponds to '''''1''''' &nbsp;≤&nbsp; {{mvar|j}} &nbsp;≤&nbsp; '''''L''.{{efn-ua

**The|1=Shifting overlapthe regionundesirable canedge also be shiftedeffects to the last M-1 outputs, which is a potential run-time convenience, because the IDFT can be computed in the <math>y[n]</math> buffer, instead of being computed and copied. Then the overlapedge effects can be overwritten by the next IDFT. The shift is accomplished by replacing <math>\scriptstyle \text{DFT}_N \displaystyle (h[n])</math> with <math>\scriptstyle \text{DFT}_N \displaystyle (h[n+M-1]) =\ \scriptstyle \text{DFT}_N \displaystyle (h[n+M-1-N]),</math> meaning that the N-length buffer is ''circularly-shifted'' (rotated) by M-1 samples.{{efn Thus the h(M) element is at n=1. The h(M-ua1) element is at n=N. h(M-2) is at n=N-1. Etc.}}

If we periodically extend ''x''_''k''[''n''] with period ''N'' &nbsp;≥&nbsp; ''L''&nbsp;+&nbsp;''M''&nbsp;−&nbsp;1, according to''':'''

Line 42 ⟶ 43:

*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.

*As shown in Figure 1 (3rd trace), theThe leading and trailing edge-effects of circular convolution are overlapped and added,{{efn-ua

|Not to be confused with the [[Overlap-add method]], which preserves separate leading and trailing edge-effects.

}} and subsequently discarded.

}} (and subsequently discarded). In other words, the first output value is a weighted average of the <u>last</u> M-1 samples of the input segment (and the first sample of the segment). The next M-2 outputs are weighted averages of both the beginning and the end of the segment. The M^th output value is the first one that combines only samples from the beginning of the segment.

**The overlap region can also be shifted to the last M-1 outputs, which is a potential run-time convenience, because the IDFT can be computed in the <math>y[n]</math> buffer, instead of being computed and copied. Then the overlap can be overwritten by the next IDFT. The shift is accomplished by replacing <math>\scriptstyle \text{DFT}_N \displaystyle (h[n])</math> with <math>\scriptstyle \text{DFT}_N \displaystyle (h[n+M-1]) =\ \scriptstyle \text{DFT}_N \displaystyle (h[n+M-1-N]),</math> meaning that the N-length buffer is ''circularly-shifted'' (rotated) by M-1 samples.{{efn-ua

|1=The h(M) element is at n=1. The h(M-1) element is at n=N. h(M-2) is at n=N-1. Etc.}}

==Pseudocode==