Overlap–save method: Difference between revisions

Revision as of 13:13, 31 May 2024

Revision as of 15:54, 6 January 2025

Line 15:

[[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. That requires longer input seqmentssegments that overlap the next input segment. The overlapped data gets "saved" and used a second time.<ref name=OLA/> First we describe that process with just conventional convolution for each output segment. 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''':'''