Overlap–save method: Difference between revisions

Revision as of 16:16, 23 January 2020

Revision as of 20:07, 23 January 2020

Line 30:

With the substitution  {{math|j ≜ n-kL}},  the task is reduced to computing {{math|y{{sub|k}}(j)}}, for '''''M'''''  ≤  {{mvar|j}}  ≤  '''''L'' +'' M'' − 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'''''  ≤  {{mvar|j}}  ≤  '''''L''.{{efn-ua

|1=Shifting the undesirable edge effects to the last M-1 outputs 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 edge effects can be overwritten by the next IDFT. TheA shiftsubsequent isfootnote accomplishedexplains 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 thathow the N-length buffershift is ''circularly-shifted'' (rotated)done, by Ma time-1shift samples. Thusof 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.impulse Etcresponse.}}

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

Line 45:

*The 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.{{efn-ua

|1=The edge effects can be moved from the front to the back of the IDFT output 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. Thus 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==