[[Image:Overlap-save algorithm.png|thumb|500px|A sequence of 4 plots depicts one cycle of the Overlap-saveoverlap–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. 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. Consider a segment that begins at ''n'' = ''kL'' + ''M'', for any integer ''k'', and define''':'''
Line 57:
==Efficiency==
When the DFT and its inverse is implemented by the FFT algorithm, the pseudocode above requires about '''N log<sub>2</sub>(N) + N''' complex multiplications for the FFT, product of arrays, and IFFT.<ref group=note>Cooley-TukeyCooley–Tukey FFT algorithm for N=2<sup>k</sup> needs (N/2) log<sub>2</sub>(N) -– see [[Fast Fourier transform#Definition and speed|FFT -– Definition and speed]]</ref> Each iteration produces '''N-M+1''' output samples, so the number of complex multiplications per output sample is about''':'''
The overlap-saveoverlap–save algorithm may be extended to include other common operations of a system:<ref group=note>[[#refCarlin|Carlin et al. 1999]], p 31, col 20.</ref><ref>{{Citation |last=Borgerding |first=Mark |title=Turning Overlap-SaveOverlap–Save into a Multiband Mixing, Downsampling Filter Bank |journal=IEEE Signal Processing Magazine |issue= March 2006 |pages=158–161 |year=2006 |url=http://www.3db-labs.com/01598092_MultibandFilterbank.pdf}}</ref>
* additional channels can be processed more cheaply than the first by reusing the forward FFT
