Editing Upsampling

{{Short description|Digital signal resampling method}}
In [[digital signal processing]], '''upsampling''', '''expansion''', and '''interpolation''' are terms associated with the process of [[sample rate conversion|resampling]] in a [[multi-rate digital signal processing]] system. ''Upsampling'' can be synonymous with ''expansion'', or it can describe an entire process of ''expansion'' and filtering (''interpolation'').<ref name=Oppenheim/><ref name=Crochiere/><ref name=Poularikas/> When upsampling is performed on a sequence of samples of a ''signal'' or other continuous function, it produces an approximation of the sequence that would have been obtained by sampling the signal at a higher rate (or [[Dots per inch|density]], as in the case of a photograph). For example, if [[compact disc]] audio at 44,100 samples/second is upsampled by a factor of 5/4, the resulting sample-rate is 55,125.

[[File:Multirate_upsampling_(interpolation)_filter.svg|thumb|350px|Fig 1: Depiction of one dot product, resulting in one output sample (in green), for the case L=4, n=9, j=3. Three conceptual "inserted zeros" are depicted between each pair of input samples. Omitting them from the calculation is what distinguishes a multirate filter from a monorate filter.]]
==Upsampling by an integer factor==

Rate increase by an integer factor <math>L</math> can be explained as a 2-step process, with an equivalent implementation that is more efficient''':'''<ref name=f.harris/>
#Expansion''':''' Create a sequence, <math>x_L[n],</math> comprising the original samples, <math>x[n],</math> separated by <math>L-1</math> zeros.&nbsp; A notation for this operation is''':'''&nbsp; <math>x_L[n] = x[n]_{\uparrow L}.</math>
#Interpolation''':''' Smooth out the discontinuities using a [[lowpass filter]], which replaces the zeros.

In this application, the filter is called an '''interpolation filter''', and its design is discussed below. When the interpolation filter is an [[Finite impulse response|FIR]] type, its efficiency can be improved, because the zeros contribute nothing to its [[dot product]] calculations. It is an easy matter to omit them from both the data stream and the calculations. The calculation performed by a multirate interpolating FIR filter for each output sample is a dot product''':'''{{efn-la
|[[#Crochiere|Crochiere and Rabiner]] "2.3". p 38. eq 2.80, where &nbsp;<math>m \triangleq j+nL,</math>&nbsp; which also requires &nbsp;<math> n = \bigl\lfloor \tfrac{m}{L} \bigr\rfloor,</math>&nbsp; and &nbsp;<math>j = m - nL.</math>
}}
{{Equation box 1|title=
|indent=:|cellpadding=0|border=0|background colour=white
|equation={{NumBlk||
<math>y[j+nL] = \sum_{k=0}^K x[n-k]\cdot h[j+kL],\ \ j = 0,1,\ldots,L-1,</math> &nbsp; and for any <math>n,</math> &nbsp; &nbsp;
|{{EquationRef|Eq.1}} }} }}

where the <math>h</math> sequence is the impulse response of the interpolation filter, and <math>K</math> is the largest value of <math>k</math> for which <math>h[j+kL]</math> is non-zero. 
{{Collapse top|title=Derivation of Eq.1}}
The interpolation filter output sequence is defined by a convolution''':'''
:<math>y[m] = \sum_{r=-\infty}^\infty x_L[m-r]\cdot h[r]</math>
The only terms for which <math>x_L[m-r]</math> can be non-zero are those for which <math>m-r</math> is an integer multiple of <math>L.</math>&nbsp; Thus''':'''
<math>m-r = \bigl\lfloor\tfrac{m}{L}\bigr\rfloor L - kL</math>&nbsp; for integer values of <math>k,</math>&nbsp; and the convolution can be rewritten as''':'''
:<math>
\begin{align}
y[m] &= \sum_{k=-\infty}^{\infty} x_L\left[\bigl\lfloor\tfrac{m}{L}\bigr\rfloor L - kL\right]\cdot h\Bigl[\overbrace{m - \bigl\lfloor\tfrac{m}{L}\bigr\rfloor L + kL}^{r}\Bigr]\\
&= \sum_{k=-\infty}^{\infty} x\left[\bigl\lfloor\tfrac{m}{L}\bigr\rfloor - k\right]\cdot h\left[m - \bigl\lfloor\tfrac{m}{L}\bigr\rfloor L + kL\right]\quad
\stackrel{m\ \triangleq\ j + nL}{\longrightarrow}\quad y[j+nL] = \sum_{k=0}^K x[n-k]\cdot h[j+kL],\ \ j = 0,1,\ldots,L-1
\end{align}
</math>
{{Collapse bottom}}


In the case <math>L=2,</math>&nbsp; function <math>h</math> can be designed as a [[half-band filter]], where almost half of the coefficients are zero and need not be included in the dot products. Impulse response coefficients taken at intervals of <math>L</math> form a subsequence, and there are <math>L</math> such subsequences (called '''phases''') multiplexed together. Each of <math>L</math> phases of the impulse response is filtering the same sequential values of the <math>x</math> data stream and producing one of <math>L</math> sequential output values. In some multi-processor architectures, these dot products are performed simultaneously, in which case it is called a '''polyphase''' filter.

For completeness, we now mention that a possible, but unlikely, implementation of each phase is to replace the coefficients of the other phases with zeros in a copy of the <math>h</math> array, and process the <math>x_L[n]</math>&nbsp; sequence at <math>L</math> times faster than the original input rate. Then <math>L-1</math> of every <math>L</math> outputs are zero. The desired <math>y</math> sequence is the sum of the phases, where <math>L-1</math> terms of the each sum are identically zero.&nbsp; Computing <math>L-1</math> zeros between the useful outputs of a phase and adding them to a sum is effectively decimation. It's the same result as not computing them at all. That equivalence is known as the ''second Noble identity''.<ref name=Strang/> It is sometimes used in derivations of the polyphase method.

==Interpolation filter design==
[[File:Spectral views of zero-fill and interpolation by lowpass filtering.pdf|thumb|400px|Fig 2: The first triangle of the first graph represents the Fourier transform ''X''(''f'') of a continuous function ''x(t)''. The entirety of the first graph depicts the discrete-time Fourier transform of a sequence ''x[n]'' formed by sampling the continuous function ''x(t)'' at a low-rate of ''1/T''. The second graph depicts the application of a lowpass filter at a higher data-rate, implemented by inserting zero-valued samples between the original ones.  And the third graph is the DTFT of the filter output. The bottom table expresses the maximum filter bandwidth in various frequency units used by filter design tools.]]

Let <math>X(f)</math> be the [[continuous Fourier transform|Fourier transform]] of any function, <math>x(t),</math> whose samples at some interval, <math>T,</math> equal the <math>x[n]</math> sequence. Then the [[discrete-time Fourier transform]] (DTFT) of the <math>x[n]</math> sequence is the [[Fourier series]] representation of a [[periodic summation]] of <math>X(f):</math>{{efn-la
|[[#f.harris|Harris 2004]]. "2.2". p 23. fig 2.12 (top).
}}
{{Equation box 1|title=
|indent=:|cellpadding=0|border=0|background colour=white
|equation={{NumBlk||
<math>\underbrace{ \sum_{n=-\infty}^\infty \overbrace{x(nT)}^{x[n]}\ e^{-i 2\pi f nT}}_{\text{DTFT}} = \frac{1}{T}\sum_{k=-\infty}^{\infty} X\Bigl(f - \frac{k}{T}\Bigr).</math> &nbsp; &nbsp;
|{{EquationRef|Eq.2}} }} }}

When <math>T</math> has units of seconds, <math>f</math> has units of [[hertz|hertz (Hz)]]. Sampling <math>L</math> times faster (at interval <math>T/L</math>) increases the periodicity by a factor of <math>L:</math>{{efn-la
|[[#f.harris|Harris 2004]]. "2.2". p 23. fig 2.12 (bottom).
}}
{{Equation box 1|title=
|indent=:|cellpadding=0|border=0|background colour=white
|equation={{NumBlk||
<math>\frac{L}{T}\sum_{k=-\infty}^\infty X\left(f-k\cdot \frac{L}{T}\right),</math> &nbsp; &nbsp;
|{{EquationRef|Eq.3}} }} }}

which is also the desired '''result''' of interpolation. An example of both these distributions is depicted in the first and third graphs of Fig 2.<ref name=LiTan/>&nbsp; 

When the additional samples are inserted zeros, they decrease the sample-interval to <math>T/L.</math>  Omitting the zero-valued terms of the Fourier series, it can be written as:

:<math>\sum_{n=0, \pm L, \pm 2L,..., \pm \infty}{} x(nT/L)\ e^{-i 2\pi f nT/L}
\quad \stackrel{m\ \triangleq\ n/L}{\longrightarrow} 
\sum_{m=0, \pm 1, \pm 2,..., \pm \infty}{} x(mT)\ e^{-i 2\pi f mT},</math>

which is equivalent to {{EquationNote|Eq.2,}} regardless of the value of <math>L.</math>  That equivalence is depicted in the second graph of Fig.2.  The only difference is that the available digital bandwidth is expanded to <math>L/T</math>, which increases the number of periodic spectral images within the new bandwidth.  Some authors describe that as new frequency components.<ref name=Lyons/>&nbsp; The second graph also depicts a lowpass filter and <math>L=3,</math> resulting in the desired spectral distribution (third graph).  The filter's bandwidth is the [[Nyquist frequency]] of the original <math>x[n]</math> sequence.{{efn-ua|Realizable low-pass filters have a [[transition band]] where the response diminishes from near unity to near zero. So in practice the cutoff frequency is placed far enough below the theoretical cutoff that the filter's transition band is contained below the theoretical cutoff.
}}&nbsp; In units of Hz that value is <math>\tfrac{0.5}{T},</math>&nbsp; but filter design applications usually require [[Normalized frequency (unit)|normalized units]]. (see Fig 2, table)

==Upsampling by a fractional factor==

Let ''L''/''M'' denote the upsampling factor, where ''L''&nbsp;>&nbsp;''M''.

#Upsample by a factor of ''L''
#[[Downsampling (signal processing)|Downsample]] by a factor of ''M''

Upsampling requires a lowpass filter after increasing the data rate, and downsampling requires a lowpass filter before decimation. Therefore, both operations can be accomplished by a single filter with the lower of the two cutoff frequencies. For the ''L''&nbsp;>&nbsp;''M'' case, the interpolation filter cutoff, &nbsp;<math>\tfrac{0.5}{L}</math> ''cycles per intermediate sample'', is the lower frequency.

==See also==

* [[Downsampling (signal processing)|Downsampling ]]
* [[Multi-rate digital signal processing]]
* [[Half-band filter]]
* [[Oversampling]]
* [[Sampling (information theory)]]
* [[Signal (information theory)]]
* [[Data conversion]]
* [[Interpolation#In_digital_signal_processing|Interpolation]]
* [[Poisson summation formula]]

== Notes ==
{{notelist-ua}}

== Page citations ==
{{notelist-la}}

==References==
{{reflist|refs=
<ref name=Oppenheim>
{{cite book |first1=Alan V. |last1=Oppenheim |authorlink=Alan V Oppenheim |first2=Ronald W. |last2=Schafer |first3=John R. |last3=Buck |title=Discrete-Time Signal Processing |edition=2nd |chapter=4.6.2 |publisher=Prentice Hall |location=Upper Saddle River, N.J. |year=1999 |isbn=0-13-754920-2 |page=172 |chapter-url-access=registration |chapter-url=https://archive.org/details/discretetimesign00alan/page/172
}}</ref>

<ref name=Crochiere>
{{cite book |last1=Crochiere |first1=R.E. |last2=Rabiner |first2=L.R. |authorlink2=Lawrence Rabiner |title=Multirate Digital Signal Processing |year=1983 |chapter=2.3 |pages=35–36 |publisher=Prentice-Hall |location=Englewood Cliffs, NJ |isbn=0136051626 |url=https://kupdf.net/download/multirate-digital-signal-processing-crochiere-rabiner_58a7065b6454a7e80bb1e993_pdf
}}</ref>

<ref name=Poularikas>
{{cite book |last=Poularikas |first=Alexander D. |title=Handbook of Formulas and Tables for Signal Processing |publisher=CRC Press |edition=1 |date=September 1998 |pages=42–48 |isbn=0849385792
}}</ref>

<ref name=f.harris>
{{cite book |last=Harris |first=Frederic J. |authorlink=Fredric J. Harris |title=Multirate Signal Processing for Communication Systems |publisher=Prentice Hall PTR |location=Upper Saddle River, NJ |date=2004-05-24 |chapter=2.2 |pages=20–21 |isbn=0131465112 |quote=The process of up sampling can be visualized as a two-step progression. The process starts by increasing the sample-rate of an input series x(n) by resampling [expansion].  The zero-packed time series is processed by a filter h(n).  In reality the processes of sample-rate increase and bandwidth reduction are merged in a single process called a multirate filter.
}}</ref>

<ref name=Strang>
{{cite book |last1=Strang |first1=Gilbert |authorlink=Gilbert Strang |title=Wavelets and Filter Banks |publisher=Wellesley-Cambridge Press |location=Wellesley, MA |isbn=0961408871 |page=[https://archive.org/details/waveletsfilterba00stra/page/101 101] |url=https://archive.org/details/waveletsfilterba00stra |url-access=registration |quote=the Noble Identities apply to each polyphase component ... they don't apply to the whole filter. |first2=Truong |last2=Nguyen |edition=2 |date=1996-10-01
}}</ref>

<ref name=LiTan>
{{cite web 
|url=https://www.eetimes.com/multirate-dsp-part-1-upsampling-and-downsampling/ |title=Upsampling and downsampling |last=Tan |first=Li |date=2008-04-21 
|website=eetimes.com |publisher=EE Times |access-date=2024-06-27 |quote= chapter 12.1.2, figure 12-5B
}}</ref>

<ref name=Lyons>
{{Cite web |last=Lyons |first=Rick |date=2015-03-23 |title=Why Time-Domain Zero Stuffing Produces Multiple Frequency-Domain Spectral Images |url=https://www.dsprelated.com/showarticle/761.php |url-status=live |archive-url=https://web.archive.org/web/20230930093550/https://www.dsprelated.com/showarticle/761.php |archive-date=2023-09-30 |access-date=2024-01-31 |website=dsprelated.com}}</ref>
}}

==Further reading==
* {{cite web |url=http://ccrma.stanford.edu/~jos/resample/resample.html |title=Digital Audio Resampling Home Page}} (discusses a technique for bandlimited interpolation)
* {{cite web |title=Matlab example of using polyphase filters for interpolation |url=http://www.dsplog.com/2007/05/12/polyphase-filters-for-interpolation/ }}
{{DSP}}

[[Category:Digital signal processing]]
[[Category:Signal processing]]