Q1Digital Signal Processing

(a) Decimation

Decimation is the process of reducing a discrete-time signal's effective sampling rate by an integer factor M, achieved by retaining only every Mth sample of the original sequence and discarding the rest: y(n) = x(nM).

Frequency-domain derivation: the relationship between the decimated signal's DTFT, Y(e^jw), and the original signal's DTFT, X(e^jw), can be derived by expressing the downsampling operation in terms of an intermediate signal formed by multiplying x(n) by an impulse train that is 1 at multiples of M and 0 elsewhere, then formally relating this to y(n) via a change of index. The resulting standard relationship is:

This shows that the decimated signal's spectrum consists of M scaled and shifted copies of the original spectrum X(e^jw), each stretched by the factor M (since w in Y corresponds to w/M in X) and shifted by multiples of 2*pi/M. If the original signal x(n) already occupies more than 1/M of the full normalized frequency range (i.e., is not sufficiently band-limited relative to the decimation factor M), these M shifted/stretched copies will overlap, causing aliasing distortion in the decimated signal.

Because of this aliasing risk, decimation is always preceded (in a properly-designed decimator, as discussed in the corresponding sampling-rate-alteration-devices answer elsewhere in this paper) by an anti-aliasing low-pass filter with cutoff frequency pi/M applied to x(n) before the actual downsampling (sample-discarding) step, ensuring the signal is adequately band-limited relative to the new, reduced sampling rate before any samples are discarded, preventing the aliasing that would otherwise corrupt the decimated result.

(b) Interpolation

Interpolation is the process of increasing a discrete-time signal's effective sampling rate by an integer factor L, achieved in two stages: first, inserting L-1 zero-valued samples between each pair of consecutive original samples (zero-stuffing/expansion), producing v(n)=x(n/L) for n a multiple of L, and v(n)=0 otherwise; second, applying a low-pass interpolation (anti-imaging) filter to smooth these zero-stuffed samples into meaningful interpolated values.

Frequency-domain derivation: the zero-stuffed intermediate signal v(n)'s DTFT relates to the original signal's DTFT via the simple compression relationship:

This shows that zero-stuffing by factor L compresses the original spectrum X(e^jw) by a factor of L when viewed as a function of the new frequency variable, causing L compressed copies (images) of the original spectrum to appear within the full normalized frequency range of the zero-stuffed signal - the subsequent low-pass filtering stage, with cutoff frequency pi/L and passband gain L (to restore correct amplitude scaling, since the zero-stuffing operation itself reduces the signal's average energy per sample), removes all these unwanted image copies except the single desired baseband copy, yielding the final, properly-interpolated signal whose spectrum matches the original signal's spectrum, now simply represented at the new, L-times-higher sampling rate.

Decimation and interpolation, though often introduced as isolated rate-conversion operations, are more properly understood as the two elementary building blocks from which arbitrary rational sampling-rate conversion (by a factor L/M) can be constructed: decimation by M reduces the sampling rate by discarding samples, but critically must be preceded by a digital low-pass anti-aliasing filter with cutoff at pi/M (in the decimated sequence's normalized frequency scale) to prevent high-frequency signal content from folding back (aliasing) into the baseband of the reduced-rate output sequence, whereas interpolation by L increases the sampling rate by inserting L-1 zero-valued samples between each original sample, which must then be followed by a digital low-pass filter with cutoff at pi/L to remove the spurious high-frequency spectral images introduced by the zero-insertion (imaging) process.

The waveform-domain picture reinforces this filtering necessity: zero-insertion alone, without the subsequent interpolation low-pass filter, produces a 'staircase-like' zero-stuffed waveform whose spectrum consists of L compressed (in frequency) copies of the original spectrum repeated periodically across the full digital frequency range from 0 to 2*pi, and only after low-pass filtering (which suppresses all but the baseband copy) does the waveform take on the smooth, correctly-interpolated appearance of the original continuous-time signal resampled at the higher rate - similarly, decimation without prior anti-alias filtering can produce a severely distorted waveform in which high-frequency content of the original signal reappears, folded, as spurious low-frequency content in the decimated output, a form of distortion that cannot be removed after the fact by any subsequent processing once the aliasing has occurred at the decimation step itself.

The efficient (polyphase) implementation of decimation and interpolation exploits the key observation that it is wasteful to compute filter outputs (in decimation) or filter over inserted zero samples (in interpolation) if those outputs are simply going to be discarded or trivially zero respectively - polyphase decomposition splits the anti-aliasing or anti-imaging filter into M (or L) sub-filters, each operating at the lower of the two sampling rates involved, allowing multirate systems built from cascades of decimators and interpolators (such as those used in audio sample-rate converters, software-defined radios, and filter banks) to achieve dramatic computational savings compared to a naive direct implementation that first filters at the higher rate and only afterward discards or inserts samples.

A practical example clarifies the roles of decimation and interpolation together: consider an audio signal originally sampled at 48kHz that must be converted to 44.1kHz for a different playback standard - this is a rational rate conversion by the factor 44100/48000 = 147/160, achieved in practice by first interpolating (up-sampling) by L=147, low-pass filtering to remove the resulting spectral images, then decimating (down-sampling) by M=160, with a further low-pass anti-aliasing filter applied before the final sample discarding, and the two low-pass filtering stages are, in an efficient implementation, typically merged into a single combined filter operating at the intermediate (interpolated) sampling rate, rather than being implemented as two entirely separate filtering operations.

This decimation/interpolation combination also underlies the design of efficient multi-stage sample-rate converters, in which a large rate-change factor is decomposed into a cascade of several smaller-factor stages rather than implemented as a single large-factor stage - because the computational cost of the anti-aliasing or anti-imaging filter at each stage depends strongly on the transition bandwidth required (relative to that stage's own sampling rate), splitting a large conversion factor into multiple smaller stages, each operating at a progressively different intermediate sampling rate, very often achieves substantially lower total computational cost than a single-stage design, a widely used practical technique in audio and communications sample-rate conversion hardware and software.