Editing Upsampling (section)

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