Decimation (Downsampling) | DSP-101

Reducing the Data Rate

Every digital signal has a sample rate — the number of samples collected per second. Often, that rate is higher than the task at hand requires. A wideband radio receiver digitizes at 100 MHz but the signal of interest occupies only 200 kHz. An audio workstation records at 96 kHz even though the mix will ultimately play back at 44.1 kHz. In both cases, carrying unnecessary samples wastes memory, storage, and processing power. Decimation is the systematic process of reducing the sample rate by discarding samples in a controlled, mathematically principled way.

The word comes from the Latin decimatio — taking one in ten. In DSP it is generalized: decimation by integer factor M means keeping every M-th sample and discarding the rest. The result is a signal at 1/M of the original sample rate. But there is a critical catch: you cannot simply throw away samples without first removing the frequencies that would alias into the lower-rate signal. Getting that step right is the heart of decimation.

Core Idea

Decimation by M = anti-aliasing lowpass filter followed by keeping every M-th sample. The filter is mandatory — skipping it introduces aliasing that permanently corrupts the signal.

Naive Downsampling: What Goes Wrong

Suppose you have a signal sampled at f_s = 8 kHz and you want to reduce the rate to 2 kHz (M = 4). The naive approach: keep sample 0, discard samples 1, 2, 3; keep sample 4, discard samples 5, 6, 7; and so on. The output sequence is y[n] = x[4n].

The problem is the Nyquist theorem applied at the new rate. At 2 kHz, only frequencies below 1 kHz can be represented without aliasing. But the original 8 kHz signal may contain energy up to 4 kHz. When you keep every 4th sample, the frequency axis compresses by a factor of 4: a component at 3 kHz in the original maps to 3000/4 = 750 Hz in the output — right on top of a legitimate 750 Hz component. The two are inseparably mixed. This contamination is irreversible; no later processing can undo aliasing once it has occurred.

Downsampling

y[n] = x[Mn]

The downsampled sequence y[n] is obtained by keeping every M-th sample of x[n]. In the frequency domain, the spectrum is compressed by M and M copies are summed — causing aliasing if the signal is not bandlimited to π/M.

The Anti-aliasing Filter

The solution is straightforward in principle: before downsampling by M, apply a lowpass filter with cutoff frequency f_c = f_s/(2M). This removes all energy at or above the new Nyquist frequency, so there is nothing to alias. The complete decimator consists of two stages in series: first the lowpass filter, then the sample-selector.

Decimator Cutoff

f_c = \frac{f_s}{2M} \quad\Leftrightarrow\quad \omega_c = \frac{\pi}{M}

The anti-aliasing filter must cut off at or below the Nyquist frequency of the output rate — that is f_c = f_s/(2M), half of the output sampling rate f_s/M. (Keep the two terms apart: the Nyquist rate is the minimum sampling rate 2f_max; the Nyquist frequency is the highest representable frequency, half the sampling rate. Halving the Nyquist frequency here would put the cutoff an octave too low.) In normalized digital frequency (radians/sample at the original rate), the cutoff is π/M.

The anti-aliasing filter can be either FIR or IIR. For most decimation applications, FIR filters are preferred because they offer linear phase (no waveform distortion), guaranteed stability, and straightforward design. The order of the filter depends on the required stopband attenuation and transition band width — a sharper transition requires more taps.

Filter Design Rule

For decimation by M, design a lowpass FIR filter with cutoff ω_c = π/M (radians/sample at the input rate). The filter order sets the trade-off between transition band sharpness and computational cost: more taps → sharper rolloff but more multiplications per input sample.

What Happens in the Frequency Domain

The frequency domain perspective makes decimation intuitive. Consider a signal whose spectrum occupies the band [0, π/M] radians/sample (after the anti-aliasing filter has removed everything above that). When we keep every M-th sample, the DTFT of the output is the sum of M shifted copies of the input spectrum, each scaled by 1/M:

Spectrum of Downsampled Signal

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

The output spectrum Y(e^jω) is the sum of M frequency-shifted copies of the filtered input spectrum, each spaced 2π/M apart. If the input was bandlimited to π/M, these copies do not overlap — no aliasing.

Because the anti-aliasing filter ensures the input spectrum is zero above π/M, the M copies in the sum are non-overlapping. The output spectrum is simply a stretched version of the passband of the input — frequencies that were in [0, π/M] now span [0, π] at the new (lower) sample rate. The signal is spectrally compressed: the same information occupies the full normalized bandwidth of the output signal.

1/M

Output sample rate relative to input

π/M

Maximum safe cutoff (radians/sample at input rate)

M×

Spectral compression factor in the output

Efficient Implementation: Polyphase Decomposition

A naive decimator computes all N filter output samples and then throws away M−1 out of every M of them — clearly wasteful. The polyphase decomposition exploits the structure of the downsampling to avoid computing samples that will be discarded.

A length-N FIR filter h[n] can be split into M sub-filters (polyphase branches), each of length approximately N/M. The k-th polyphase branch contains the filter coefficients at indices k, k+M, k+2M, … . For a decimator, only the zeroth polyphase branch is needed at each output sample — the computation reduces by a factor of M. The total arithmetic cost drops from N multiplications per input sample to approximately N/M multiplications per output sample.

Polyphase Decomposition

E_k[n] = h[nM + k], \quad k = 0, 1, \ldots, M-1

The filter h[n] is decomposed into M polyphase branches E_k[n] = h[nM + k]. Each branch operates at the lower output rate, reducing computation by a factor of M.

In practice, polyphase implementations are standard in every DSP library and hardware accelerator. Modern SDR (software-defined radio) platforms, audio processing chips, and baseband processors all use polyphase structures to implement sample-rate changes efficiently in real time.

Practical Considerations

Integer vs. rational decimation: The factor M must be a positive integer for the description above. To downsample by a non-integer ratio (e.g., 44.1 kHz to 32 kHz = 320:441), you combine upsampling and downsampling: first upsample by L, then downsample by M, choosing L and M such that L/M is the desired ratio. This is rational sample-rate conversion, covered in Lesson 11.3.

Multistage decimation: For large M values (e.g., M = 64), a single-stage FIR anti-aliasing filter would require many taps to meet the stringent transition band requirements. A multistage approach cascades smaller decimators (e.g., decimate by 4, then by 4, then by 4) with simpler filters at each stage, reducing total computational cost dramatically.

CIC filters for extreme decimation: Cascaded Integrator-Comb (CIC) filters are a computationally free (multiply-free) filter structure ideal for very high decimation ratios (M = 256 or more). They require no multiplications and are commonly used in ΣΔ ADCs and SDR front ends, where the raw oversampled bitstream must be reduced to a usable sample rate.

Next lesson: Interpolation (Upsampling) — the reverse process: inserting samples to increase the rate, with the anti-imaging filter that prevents spectral replicas from appearing in the output.

Key Takeaways

Decimation by M reduces the sample rate by a factor of M by keeping every M-th sample; it is the fundamental tool for reducing data rate in multirate DSP.
Naive downsampling causes aliasing: spectral copies overlap and permanently corrupt the signal. The anti-aliasing lowpass filter (cutoff π/M) is mandatory before downsampling.
In the frequency domain, downsampling by M compresses the spectrum by M and sums M shifted copies; if the signal is bandlimited to π/M, the copies do not overlap.
Polyphase decomposition eliminates wasted computation by operating the filter at the lower output rate, reducing cost by approximately M.
Large decimation ratios are efficiently realized as cascaded stages; CIC filters handle extreme decimation (M in the hundreds) with zero multiplications.
Decimation is the first half of sample-rate conversion; rational ratios combine decimation with interpolation to convert between arbitrary sample rates.