5.1 Decimation and interpolation

Decimation

Decimation reduces the sampling rate of a discrete-time signal by an integer factor. It's a two-step process: first you filter, then you downsample. Getting the order wrong (or skipping the filter) introduces aliasing that you can't undo.

Decimation shows up constantly in multirate systems where you need to reduce computational load, cut storage requirements, or match the sampling rate of a downstream processor.

Decimation Factor

The decimation factor $M$ is the integer ratio by which you reduce the sampling rate. If your original rate is $f_s$, the output rate is $f_s / M$.

A concrete example: starting at 48 kHz with $M = 6$ gives you 8 kHz at the output. The choice of $M$ depends on your target rate and on how much of the input signal's bandwidth you actually need to preserve.

Anti-Aliasing Filtering

Before you throw away any samples, you must low-pass filter the signal. The cutoff frequency for this anti-aliasing filter is:

$f_c = \frac{f_s}{2M}$

where $f_s$ is the original sampling rate. This ensures that no frequency content above the new Nyquist frequency ($f_s / 2M$) survives into the downsampled signal.

In the normalized discrete-time frequency domain, the filter's cutoff is $\pi / M$. The filter needs a sharp transition band and high stopband attenuation; any energy that leaks through will alias and corrupt your signal permanently.

Downsampling

Downsampling by $M$ means keeping every $M$-th sample and discarding the rest. If your input sequence is $x[n]$, the downsampled output is:

$y[n] = x[nM]$

Downsampling without prior filtering is the classic mistake. High-frequency components fold back into the baseband, and once that aliasing happens, there's no way to separate the folded components from the original signal.

Decimation in Time vs. Frequency

• Time domain: Apply the anti-aliasing low-pass filter to $x[n]$, then keep every $M$-th sample. This is the standard approach and the most common in practice.
• Frequency domain: Transform to the frequency domain via DFT/FFT, zero out components above $\pi/M$, then inverse-transform and downsample. This can be useful when you're already working in the frequency domain, but it introduces DFT windowing effects you need to manage.

Applications of Decimation

• Sample rate conversion: Reducing 96 kHz audio to 48 kHz for CD-quality output
• Data compression: Fewer samples means less data to store or transmit, provided the bandwidth reduction is acceptable
• Multirate filter banks: Subband decomposition relies on decimation to bring each band down to its minimum necessary rate, saving computation across the entire bank

Interpolation

Interpolation increases the sampling rate of a discrete-time signal by an integer factor. The process is the mirror image of decimation: first you upsample (insert zeros), then you filter out the spectral images that upsampling creates.

Interpolation Factor

The interpolation factor $L$ is the integer ratio by which you increase the sampling rate. The output rate becomes $L \cdot f_s$.

Example: starting at 8 kHz with $L = 6$ yields 48 kHz. You choose $L$ based on the target rate and any constraints imposed by downstream processing.

Upsampling

Upsampling by $L$ inserts $L - 1$ zeros between each original sample:

$x_u[n] = \begin{cases} x[n/L], & n = 0, \pm L, \pm 2L, \dots \\ 0, & \text{otherwise} \end{cases}$

This increases the sample count but doesn't add new information. In the frequency domain, upsampling compresses the original spectrum by a factor of $L$ and creates $L - 1$ spectral images (replicas) across the new Nyquist band.

Anti-Imaging Filtering

After upsampling, you apply a low-pass filter to remove the spectral images. The cutoff frequency is:

$f_c = \frac{f_s}{2}$

where $f_s$ is the original (pre-upsampling) sampling rate. Equivalently, in terms of the new higher rate $L \cdot f_s$, the cutoff is $\frac{L \cdot f_s}{2L} = \frac{f_s}{2}$, which corresponds to a normalized frequency of $\pi / L$ at the upsampled rate.

The filter also needs a gain of $L$ to compensate for the amplitude reduction caused by zero-insertion. Without this gain correction, your output signal will be $L$ times smaller than expected.

Interpolation in Time vs. Frequency

• Time domain: Insert $L - 1$ zeros between samples, then apply the anti-imaging low-pass filter. This is the standard implementation.
• Frequency domain: Take the DFT of the original signal, zero-pad the spectrum symmetrically to $L$ times its original length, then inverse-transform. This effectively creates the interpolated samples in one step.

Applications of Interpolation

• Sample rate conversion: Bringing a 44.1 kHz audio stream up to 192 kHz for high-resolution DAC output
• Image resizing: Increasing spatial resolution by interpolating between pixel rows and columns
• Digital communications: Pulse shaping in transmitters often involves upsampling followed by filtering to generate the baseband waveform at the DAC rate

Multirate Signal Processing

Multirate systems operate on signals at two or more different sampling rates within the same processing chain. Decimation and interpolation are the building blocks, but the real power comes from combining them and exploiting structural efficiencies.

Decimation and Interpolation Combined

To convert between two rates that don't share a simple integer relationship, you combine interpolation and decimation. The standard approach for rational rate conversion by a factor of $L/M$:

1. Interpolate by $L$ (upsample by $L$, then low-pass filter)
2. Decimate by $M$ (low-pass filter, then downsample by $M$)

Since both steps require a low-pass filter, you can merge them into a single filter whose cutoff is $\min(\pi/L, \, \pi/M)$. Interpolation is done first so you don't lose information by decimating prematurely.

Sample Rate Conversion

Sample rate conversion changes the rate of a signal while preserving its spectral content up to the bandwidth supported by the lower rate. Whether you're going up or down (or both), the key constraint is that the signal's bandwidth must fit within the Nyquist limit of the output rate.

Rational vs. Irrational Factors

• Rational factors can be expressed as $L/M$ where both are integers. Example: converting 44.1 kHz to 48 kHz requires $L/M = 480/441 = 160/147$. You interpolate by 160, then decimate by 147 (in practice, done in multiple stages).
• Irrational factors (like $\sqrt{2}$) can't be expressed as an integer ratio. These require either a rational approximation or continuously variable resampling techniques such as Farrow filters, which compute output samples at arbitrary fractional delays.

Polyphase Decomposition

Polyphase decomposition restructures a single FIR filter into $M$ (or $L$) smaller subfilters, each operating at the lower sampling rate. This avoids computing filter outputs for samples that will be discarded (in decimation) or from zero-valued inputs (in interpolation).

The steps for decimation by $M$ with polyphase structure:

1. Decompose the anti-aliasing filter $H(z)$ into $M$ polyphase components: $H(z) = \sum_{k=0}^{M-1} z^{-k} E_k(z^M)$
2. Each subfilter $E_k(z)$ operates at the decimated rate $f_s/M$
3. The total number of multiplications per output sample drops by a factor of $M$

For interpolation by $L$, the decomposition is analogous but applied to the synthesis (anti-imaging) filter.

Noble Identities

The Noble identities let you move filters across downsamplers and upsamplers, which is essential for deriving efficient polyphase structures and analyzing multirate systems.

• First identity (decimation): A filter $H(z)$ followed by downsampling by $M$ is equivalent to downsampling by $M$ followed by $H(z^M)$. Formally: $H(z)$ then $\downarrow M$ = $\downarrow M$ then $H(z^M)$.
• Second identity (interpolation): Upsampling by $L$ followed by a filter $H(z)$ is equivalent to $H(z^L)$ followed by upsampling by $L$. Formally: $\uparrow L$ then $H(z)$ = $H(z^L)$ then $\uparrow L$.

Filter Design for Multirate Systems

The filters in a multirate system directly determine aliasing rejection, image suppression, passband distortion, and computational cost. Designing them well is where theory meets engineering trade-offs.

Decimation Filter Design

The decimation (anti-aliasing) filter is a low-pass filter with normalized cutoff at $\pi/M$. Key specs:

• Passband: $0$ to $\pi/M - \delta$, where $\delta$ accounts for the transition band
• Stopband: $\pi/M + \delta$ to $\pi$
• Stopband attenuation: Must be high enough to suppress aliased components below the noise floor of your system (typically 60-100 dB for audio, more for instrumentation)
• Transition bandwidth: Narrower is better for aliasing rejection, but requires a higher filter order

Interpolation Filter Design

The interpolation (anti-imaging) filter has the same cutoff at $\pi/L$ (normalized to the upsampled rate) but with a gain of $L$ in the passband to compensate for zero-insertion. The design priorities are:

• Flat passband response (minimal ripple)
• High stopband attenuation to suppress spectral images
• The transition band width determines the filter order, just as with decimation filters

Halfband Filters

When $M = 2$ (or $L = 2$), halfband filters offer a significant computational shortcut. A halfband filter has its cutoff at $\pi/2$ and a symmetric frequency response around that point.

The key property: every other coefficient (except the center tap) is exactly zero. For an $N$-tap halfband filter, roughly half the coefficients vanish, cutting the multiply count nearly in half. This makes halfband filters the go-to choice for factor-of-2 rate changes, and they're often cascaded in multistage designs.

Cascaded Integrator-Comb (CIC) Filters

CIC filters are multiplier-free structures built from cascaded integrators and comb (differentiator) stages. Their transfer function for a single-stage CIC decimator with differential delay $D$ is:

$H(z) = \frac{1 - z^{-DM}}{1 - z^{-1}}$

Advantages:

• No multiplications, only additions and subtractions
• Very efficient for large decimation/interpolation factors (common in sigma-delta ADC/DAC chains)

Limitations:

• The frequency response has a $\text{sinc}^N$ shape, which means passband droop and modest stopband attenuation
• Usually followed by a short compensating FIR filter to flatten the passband and improve stopband rejection

Computational Efficiency Considerations

Reducing computation in multirate filters is not just an optimization nicety; for real-time systems running on FPGAs or DSPs, it's often a hard constraint. The main strategies:

• Polyphase decomposition reduces multiplications by a factor of $M$ (or $L$)
• Halfband filters cut computation roughly in half for factor-of-2 stages
• CIC filters eliminate multiplications entirely for the coarse rate change
• Multistage designs split a large rate change into smaller cascaded stages, each with a relaxed filter spec
• Frequency-response masking (FRM) uses a pair of short filters to synthesize a very narrow transition band without a very long single filter

The trade-off is always filter performance (passband flatness, stopband depth, transition width) versus computational budget.

Practical Considerations

Finite Word Length Effects

Digital hardware uses fixed bit widths, and every operation introduces small errors. In multirate systems, these accumulate across filter stages and rate-change operations. The main manifestations:

• Coefficient quantization: Rounding filter coefficients to fit your word length shifts pole/zero locations, which can distort the frequency response or even destabilize IIR filters
• Roundoff noise: Each multiply-accumulate introduces a small error that propagates through the system
• Mitigation: Use proper internal scaling, choose filter structures with low coefficient sensitivity (e.g., lattice or state-space forms), and perform fixed-point simulation before committing to hardware

Quantization Noise

When you represent a continuous-amplitude signal with $B$ bits, the quantization noise power is approximately $\frac{\Delta^2}{12}$, where $\Delta = \frac{2 \cdot x_{\max}}{2^B}$ is the quantization step size. The resulting SNR for a full-scale sinusoid is roughly:

$\text{SNR} \approx 6.02B + 1.76 \text{ dB}$

In multirate systems, oversampling by a factor of $K$ spreads quantization noise over a wider band, and subsequent decimation filtering removes the out-of-band noise, effectively gaining $10\log_{10}(K)$ dB of SNR. This is the principle behind sigma-delta converters. Noise shaping pushes even more noise out of band for additional gains.

Overflow and Underflow

• Overflow wraps or clips when a computation exceeds the maximum representable value. In two's-complement arithmetic, overflow causes a sign flip, which is catastrophic.
• Underflow occurs when values are too small to represent, effectively rounding to zero.

Prevention strategies:

• Scale inputs and intermediate signals to keep values within range
• Use saturation arithmetic (clamp at max/min instead of wrapping)
• Add guard bits to intermediate accumulators (a common approach in FPGAs where accumulator widths are flexible)

Computational Complexity vs. Performance

Higher-order filters give sharper transitions and deeper stopbands but cost more multiplications per sample. In a multirate context, the polyphase structure means the per-output-sample cost depends on the filter length divided by the rate-change factor. The design process typically involves:

1. Setting performance specs (passband ripple, stopband attenuation, transition width)
2. Estimating the required filter order (e.g., via the Kaiser or Bellanger formulas)
3. Checking whether the resulting computation fits the hardware budget
4. If not, moving to a multistage or CIC-plus-FIR architecture to relax individual stage requirements

Real-Time Implementation Challenges

Real-time multirate processing adds timing and buffering constraints on top of the algorithmic design:

• Latency: Each FIR filter stage adds group delay. Multistage designs accumulate delay across stages, which matters in feedback loops or interactive systems.
• Buffering: Rate changes mean input and output blocks have different sizes. You need ring buffers or FIFO queues to handle the mismatch without stalling the pipeline.
• Throughput: The system must complete all filtering and resampling within one sample period of the fastest clock in the chain.
• Parallelism: FPGAs can exploit polyphase parallelism directly (each subfilter runs on its own hardware). On DSPs, careful loop scheduling and SIMD instructions help meet throughput targets.

Advanced Topics

Multistage Decimation and Interpolation

Instead of decimating by a large factor $M$ in one step (which requires a very sharp, high-order filter), you can split the decimation into $K$ cascaded stages with factors $M_1, M_2, \dots, M_K$ where $M_1 \cdot M_2 \cdots M_K = M$.

Each stage only needs to suppress aliasing within its own (relatively relaxed) transition band, so the individual filters are much shorter. The total computation across all stages is often significantly less than a single-stage design. Optimal stage-factor allocation (choosing the $M_k$ values) can be done analytically or by search.

The same logic applies to multistage interpolation, with the stages applied in reverse order.

Fractional Decimation and Interpolation

Fractional rate conversion by $L/M$ combines interpolation by $L$ and decimation by $M$. The merged system uses a single low-pass filter at cutoff $\min(\pi/L, \pi/M)$, implemented efficiently via polyphase structure.

For rates that aren't related by a convenient small ratio (e.g., 44.1 kHz to 48 kHz, which is 160/147), the polyphase filter bank becomes large. Farrow structures address this by using a polynomial approximation to compute output samples at arbitrary fractional delays, avoiding the need for a massive filter bank. The Farrow filter coefficients are fixed, and only the fractional delay parameter changes per output sample.

Multirate Filter Banks

A multirate filter bank splits a signal into $M$ subbands, each decimated by $M$, for independent processing. The analysis bank decomposes; the synthesis bank reconstructs.

Key design goals:

• Perfect reconstruction (PR): The output equals a delayed version of the input when no subband processing is applied
• Aliasing cancellation: The synthesis filters must cancel the aliasing introduced by decimation in each subband
• Minimal amplitude and phase distortion across the reconstructed signal

Filter banks are the backbone of audio codecs (MP3, AAC), image compression (JPEG 2000), and time-frequency analysis tools.

Quadrature Mirror Filter Banks (QMF)

A two-channel QMF bank uses a low-pass filter $H_0(z)$ and a high-pass filter $H_1(z)$ related by:

$H_1(z) = H_0(-z)$

This mirror symmetry around $\pi/2$ is what gives QMF its name. The synthesis filters are chosen to cancel aliasing, but classic QMF designs achieve only near-perfect reconstruction due to residual amplitude distortion. Conjugate quadrature filters (CQF) and more general PR filter bank designs (e.g., using lossless polyphase matrices) resolve this limitation.

Wavelet Transforms and Multiresolution Analysis

The discrete wavelet transform (DWT) is implemented as an iterated two-channel filter bank. At each level:

1. Filter the signal with a low-pass filter $h[n]$ (scaling function) and a high-pass filter $g[n]$ (wavelet function)
2. Decimate both outputs by 2
3. Repeat on the low-pass output for the next coarser scale

This produces approximation coefficients (low-frequency content at each scale) and detail coefficients (high-frequency content). The inverse DWT reverses the process: upsample by 2, filter with synthesis filters, and sum.

Multiresolution analysis (MRA) provides the theoretical framework: the scaling function and wavelet function generate nested subspaces that tile the time-frequency plane. The connection to multirate processing is direct; every level of the DWT is a decimation-by-2 filter bank stage.

Applications include JPEG 2000 image compression, signal denoising via wavelet thresholding, and feature extraction in biomedical signal analysis.