Overlap–save method: Difference between revisions

Revision as of 03:16, 3 January 2023

Revision as of 16:12, 2 March 2024

Line 10:

[[Image:Overlap-save algorithm.svg|thumb|right|500px|Fig 1: A sequence of four plots depicts one cycle of the overlap–save convolution algorithm. The 1st 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, with the usable portion colored red. The 4th plot shows the filtered segment appended to the output stream.{{efn-ua|[[#refRabiner|Rabiner and Gold]], Fig 2.35, fourth trace.}} 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.]]

The concept is to compute short segments of ''y''[''n''] of an arbitrary length ''L'', and concatenate the segments together. ConsiderThat arequires segmentlonger input seqments that beginsoverlap atthe ''n''next input segment. The overlapped data gets "saved" and used a second time.<ref name=OLA/> ''kL''&nbsp;+&nbsp;''M'', First we describe that process with just conventional convolution for anyeach integeroutput ''k'',segment. and define''':'''Then we describe how to replace that convolution with a more efficient method.

Consider a segment that begins at ''n'' = ''kL''&nbsp;+&nbsp;''M'', for any integer ''k'', and define''':'''

:<math>x_k[n] \ \triangleq

Line 25 ⟶ 27:

With the substitution <math>j = n-kL</math>, the task is reduced to computing <math>y_k[j]</math> for <math>M+1 \le j \le L+M</math>. 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

|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.&nbsp; A subsequent footnote explains how the shift is done, by a time-shift of the impulse response.}}'''

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

Line 102 ⟶ 104:

<ref name=f.harris>

{{cite book |author=Harris, F.J. |year=1987 |title=Handbook of Digital Signal Processing |editor=D.F.Elliot |___location=San Diego |publisher=Academic Press |pages=633–699 |isbn=0122370759

}}</ref>

<ref name=OLA>

{{cite web|url=https://www.dsprelated.com/freebooks/sasp/Overlap_Add_OLA_STFT_Processing.html|title=Overlap-Add (OLA) STFT Processing {{!}} Spectral Audio Signal Processing |website=www.dsprelated.com |access-date=2024-03-02 |quote=The name overlap-save comes from the fact that L-1 samples of the previous frame [here: M-1 samples of the current frame] are saved for computing the next frame.

}}</ref>