Skip to content
Digital Signal Processing

Multirate processing: decimation, interpolation and polyphase filters

Spectrum of the downsampled signal with proof, the decimator, upsampling and images, rational rate conversion, the noble identity proved, the polyphase structure, sigma-delta converters and software radio.

4 min read 0 comments

Many systems work with different sampling rates at different points: an oversampled converter produces millions of samples per second that must be reduced, audio goes from 44.1 to 48 kHz, a digital radio extracts a narrow channel from a wide band. Multirate processing changes the sampling rate numerically. In this lesson we prove what happens to the spectrum when downsampling and upsampling, look at the filters needed, rational rate conversion, and the polyphase structure with the noble identities that make it all efficient.

Downsampling

Downsampling by an integer factor M means keeping one sample every M: y[n] = x[Mn].

Theorem. The spectrum of the downsampled signal is

    \[ Y(e^{j\omega}) = \frac{1}{M}\sum_{k=0}^{M-1}X\!\left(e^{j(\omega - 2\pi k)/M}\right) \]

Proof. Introduce the intermediate signal x_p[n] = x[n]\,p[n], where p[n] is 1 when n is a multiple of M and 0 otherwise. This comb can be written as an average of exponentials, p[n] = \frac{1}{M}\sum_{k=0}^{M-1}e^{j2\pi kn/M} (the sum is M if n is a multiple of M and 0 otherwise, by the geometric series). Multiplying by e^{j2\pi kn/M} shifts the spectrum by 2\pi k/M, so X_p(e^{j\omega}) = \frac{1}{M}\sum_k X(e^{j(\omega - 2\pi k/M)}). Finally y[n] = x_p[Mn] only removes zeros, and its transform is Y(e^{j\omega}) = \sum_n x_p[Mn]e^{-j\omega n} = X_p(e^{j\omega/M}). Substituting gives the formula. ∎

The spectrum is stretched M times and M shifted copies are added. If the original signal had components above \pi/M, the copies overlap: this is aliasing, and it can no longer be removed.

Spectrum of a signal before and after downsampling by 2 without a filter
Top, the original spectrum, with bandwidth up to 0.6 pi. Bottom, after keeping one sample out of two, the spectrum is stretched and halved in amplitude, and adjacent copies overlap around plus and minus pi: high frequencies fold onto low ones.

That is why, before downsampling, the signal is filtered with a low-pass filter at \pi/M: filter plus downsampler together are called a decimator.

Upsampling

Upsampling by a factor L means inserting L - 1 zeros between samples: y[n] = x[n/L] if n is a multiple of L, 0 otherwise. The spectrum is Y(e^{j\omega}) = X(e^{j\omega L}), because only the terms n = Lm remain in the transform sum, with e^{-j\omega Lm}. The spectrum is compressed L times, and L copies appear in the interval [-\pi, \pi]: the images. A low-pass filter at \pi/L with gain L removes them and fills the zeros with interpolated values: this is the interpolator.

Rational rate conversion

To multiply the sampling rate by L/M, upsample by L, filter with a single low-pass filter with cutoff \min(\pi/L, \pi/M), which removes the images and prevents aliasing at the same time, and downsample by M. Converting from CD audio (44.1 kHz) to professional audio (48 kHz) has ratio 48\,000/44\,100 = 160/147: upsampling by 160 followed by downsampling by 147. Done literally it would be an enormous computation, at 7 MHz in the middle; polyphase structures make it practical.

The noble identities and the polyphase structure

The obvious flaw of the decimator is that the filter works at the high rate and then M - 1 samples out of M are thrown away: most multiplications are wasted.

Theorem (noble identity). Filtering with G(z^M) and then downsampling by M is equivalent to downsampling by M and then filtering with G(z).

Proof. G(z^M) has an impulse response that is non-zero only at multiples of M: g_M[Mk] = g[k]. The filter output at instant Mn is \sum_k g[k]\,x[Mn - Mk] = \sum_k g[k]\,x[M(n - k)], which is exactly the convolution of g with the downsampled signal x[Mm]. ∎

Every FIR filter H(z) can be split into M polyphase components, collecting the coefficients with index k, k + M, k + 2M, \dots:

    \[ H(z) = \sum_{k=0}^{M-1}z^{-k}E_k(z^M) \]

Applying the noble identity to each branch, the downsampling moves before the filters E_k, which work at the low rate. The number of multiplications per output sample is still that of the filter, but the number per unit time drops by a factor M. The same holds, dually, for the interpolator. For the 160/147 conversion only the output samples that are needed are computed, each time using the right subset of coefficients.

Applications

  • Oversampled converters. A sigma-delta converter samples at many megahertz with few bits and pushes the quantisation noise to high frequencies; a digital decimator filters it out and reduces the rate, gaining bits (Applied Electronics lesson on converters). The first stages often use CIC filters, cascades of integrators and differentiators that need no multiplications.
  • Software-defined radio. A wide band is sampled, the desired channel is brought to baseband with a numerical oscillator and decimated down to the channel width.
  • Filter banks. A signal is split into sub-bands, each downsampled and coded with the appropriate number of bits: this is the basis of audio compression (MP3, AAC) and of the polyphase banks of OFDM.

Related articles

Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
0
Would love your thoughts, please comment.x
()
x