Overlap–save method: Difference between revisions

Revision as of 13:52, 27 January 2020

Revision as of 03:15, 16 February 2020

Line 2:

In [[signal processing]], '''''Overlap–save''''' is the traditional name for an efficient way to evaluate the [[Convolution#Discrete convolution|discrete convolution]] between a very long signal <math>x[n]</math> and a [[finite impulse response]] (FIR) filter <math>h[n]</math>''':'''

[[Image:Overlap-save algorithm.svg|thumb|500px400px|Fig 1: A sequence of 4 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.]]

Line 86:

==Overlap–discard==

''Overlap–discard''<ref>Harris, Fname=f.J. (1987). "Time ___domain signal processing with the DFT". ''Handbook of Digital Signal Processing'', D.F.Elliot, ed., San Diego: Academic Press. pp 633–699. {{ISBN|0122370759}}.<harris/ref> and ''Overlap–scrap''<ref> name=Frerking, Marvin (1994). ''Digital Signal Processing in Communication Systems''. New York: Van Nostrand Reinhold. {{ISBN|0442016166}}.</ref> are less commonly used labels for the same method described here. However, these labels are actually better (than ''overlap–save'') to distinguish from [[Overlap–add method|overlap–add]], because <u>both</u> methods "save", but only one discards. "Save" merely refers to the fact that ''M''&nbsp;−&nbsp;1 input (or output) samples from segment ''k'' are needed to process segment ''k'' + 1.

===Extending overlap–save===

The overlap–save algorithm can be extended to include other common operations of a system:{{efn-ua

|[[#refCarlin|Carlin et al. 1999]], p 31, col 20.

}}<ref name=Borgerding/>

}}<ref>{{Citation |last=Borgerding |first=Mark |title=Turning Overlap–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 IFFT channels can be processed more cheaply than the first by reusing the forward FFT

Line 104:

==References==

{{reflist}}|refs=

<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=Frerking>

{{cite book |author=Frerking, Marvin |year=1994 |title=Digital Signal Processing in Communication Systems |___location=New York |publisher=Van Nostrand Reinhold |isbn=0442016166

}}</ref>

<ref name=Borgerding>

{{cite journal

| last =Borgerding |first=Mark |title=Turning Overlap–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>

}}

{{refbegin}}

#<li value="4">{{Cite book

| ref=refRabiner

| author1=Rabiner, Lawrence R.

| author2=Gold, Bernard