5.2 Polyphase decomposition

Polyphase decomposition fundamentals

Polyphase decomposition is a technique for breaking a filter or signal into a set of smaller sub-components, each operating at a reduced sampling rate. This restructuring is what makes efficient decimation, interpolation, and filter bank implementations possible: instead of filtering at the high rate and then downsampling (wasting computation on samples you'll throw away), you rearrange the operations so filtering happens at the low rate.

This topic ties together the core ideas of Unit 5. If you understand polyphase structure well, decimation filters, interpolation filters, and perfect reconstruction filter banks all become much more straightforward to analyze and implement.

Definition of polyphase decomposition

Polyphase decomposition represents a discrete-time signal or transfer function as a sum of $M$ sub-components, each operating at $1/M$ the original sampling rate. The idea is to split the sequence into $M$ interleaved subsequences based on the sample index modulo $M$.

For a filter $H(z)$ with transfer function $H(z) = \sum_{n} h[n] z^{-n}$, you group the coefficients by their index modulo $M$:

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

Each $E_k(z)$ is a polyphase component containing every $M$-th coefficient starting from index $k$:

$E_k(z) = \sum_{n} h[nM + k] \, z^{-n}$

Key properties of polyphase components

• Each polyphase component $E_k(z)$ operates at $1/M$ the original rate, which is where the computational savings come from.
• The components are obtained by downsampling the impulse response: $e_k[n] = h[nM + k]$.
• Recombining all $M$ components with appropriate delays reconstructs the original filter exactly. No information is lost.
• The overall frequency response of $H(z)$ is fully preserved by the decomposition.

Mathematical notation for polyphase representation

For a signal $x[n]$ decomposed into $M$ polyphase components:

• The $k$-th component is $x_k[n] = x[nM + k]$, where $k = 0, 1, \ldots, M-1$.
• Reconstruction uses upsampling (inserting $M-1$ zeros between each sample) and delaying:

$X(z) = \sum_{k=0}^{M-1} z^{-k} X_k(z^M)$

This z-domain form is the one you'll use most often in derivations. The key insight: replacing $z$ with $z^M$ inside each component corresponds to upsampling, and the $z^{-k}$ factor provides the correct delay to interleave the subsequences back together.

Applications of polyphase decomposition

Role in multirate signal processing

Polyphase decomposition is the structural backbone of multirate DSP. Its primary value is enabling you to move filtering operations to the lower-rate side of a decimator or interpolator. Without polyphase restructuring, a decimation-by-$M$ system filters at the high input rate and then discards $M-1$ out of every $M$ output samples. With polyphase restructuring, you compute only the samples you actually keep.

Efficient implementation of filter banks

In an $M$-channel filter bank, each channel has its own bandpass filter. A direct implementation requires $M$ separate filters all running at the input rate. Polyphase decomposition lets you express the entire analysis bank as a single polyphase matrix followed by a DFT (for uniform DFT filter banks), cutting the total multiply count roughly by a factor of $M$.

Polyphase decomposition in wavelet transforms

The two-channel filter bank at the heart of the discrete wavelet transform (DWT) maps directly to a $2 \times 2$ polyphase matrix. Iterating this structure across scales gives you the standard dyadic wavelet decomposition. The lifting scheme, widely used in modern wavelet implementations (e.g., JPEG 2000), is itself a factorization of this polyphase matrix into elementary lifting steps.

Polyphase decomposition of FIR filters

Type 1 vs Type 2 polyphase decompositions

The two types differ in how coefficients are assigned to components:

• Type 1 (causal polyphase): $H(z) = \sum_{k=0}^{M-1} z^{-k} E_k(z^M)$, where $E_k(z) = \sum_n h[nM+k]\,z^{-n}$. The delay $z^{-k}$ appears after each component.
• Type 2 (anticausal polyphase): $H(z) = \sum_{k=0}^{M-1} z^{-(M-1-k)} R_k(z^M)$, where $R_k(z) = \sum_n h[nM + M - 1 - k]\,z^{-n}$. The indexing is reversed.

Type 1 pairs naturally with decimation structures (filtering then downsampling), while Type 2 pairs with interpolation structures (upsampling then filtering). Using the matching type lets you apply the Noble identities directly.

Noble identities for polyphase structures

The Noble identities are the rules that let you swap the order of filtering and rate changing in the z-domain. They are what make polyphase restructuring valid.

1. Decimation identity: A filter $E(z^M)$ followed by $\downarrow M$ is equivalent to $\downarrow M$ followed by $E(z)$. The key requirement is that the filter's transfer function is a function of $z^M$ (not just $z$).
2. Interpolation identity: $\uparrow L$ followed by a filter $R(z^L)$ is equivalent to $R(z)$ followed by $\uparrow L$.

These identities only hold when the filter argument is $z^M$ (or $z^L$). That's exactly the form you get from polyphase decomposition, which is why the two ideas work hand-in-hand.

Polyphase implementation of decimation filters

Here's the step-by-step process for decimation by $M$ with an FIR lowpass filter $H(z)$:

1. Decompose $H(z)$ into Type 1 polyphase components: $H(z) = \sum_{k=0}^{M-1} z^{-k} E_k(z^M)$.
2. Apply the Noble identity to move each $E_k(z^M)$ past the downsampler, converting it to $E_k(z)$ operating at the low rate.
3. The resulting structure takes $M$ input samples in parallel (via a serial-to-parallel commutator), filters each through its respective $E_k(z)$, and sums the results to produce one output sample.

The computational saving: if $H(z)$ has $N$ coefficients, the direct approach computes $N$ multiplies per input sample but keeps only every $M$-th output. The polyphase approach computes $N/M$ multiplies per output sample. That's a factor-of-$M$ reduction.

Polyphase implementation of interpolation filters

For interpolation by $L$ with filter $H(z)$:

1. Decompose $H(z)$ into Type 2 polyphase components: $H(z) = \sum_{k=0}^{L-1} z^{-(L-1-k)} R_k(z^L)$.
2. Apply the Noble identity to move each $R_k(z^L)$ before the upsampler, converting it to $R_k(z)$ at the low input rate.
3. Each polyphase filter $R_k(z)$ processes the input at the low rate. A parallel-to-serial commutator then interleaves the $L$ outputs to produce the high-rate interpolated signal.

Again, all filtering happens at the low rate, giving the same factor-of-$L$ savings.

Polyphase decomposition of IIR filters

Challenges with IIR polyphase decomposition

IIR filters have feedback paths, which means their transfer functions include poles. When you try to decompose $H(z) = B(z)/A(z)$ into polyphase components, the denominator polynomial creates coupling between the components. You can't simply split the coefficients the way you do with FIR filters, because the recursive structure means each output sample depends on previous outputs across all phases.

Direct polyphase decomposition of a general IIR filter can lead to instability or structures that don't preserve perfect reconstruction.

Approximation methods for IIR polyphase decomposition

Two common workarounds:

• FIR approximation: Truncate or window the IIR impulse response to create a high-order FIR filter, then apply standard polyphase decomposition. This sacrifices the compactness of the IIR design but gives you a straightforward polyphase structure.
• Allpass-based decomposition: Decompose the IIR filter into a sum or cascade of allpass sections. Allpass filters have a special structure that is more amenable to polyphase manipulation while preserving stability.

Allpass decomposition for IIR filters

Allpass filters satisfy $|A(e^{j\omega})| = 1$ for all $\omega$: they pass all frequencies with unit magnitude and only modify the phase. A useful result in filter bank theory is that certain IIR filters (particularly half-band filters) can be expressed as a sum of two allpass filters:

$H(z) = \frac{1}{2}\left[A_0(z^2) + z^{-1} A_1(z^2)\right]$

This is already in polyphase form. Each allpass branch can be implemented efficiently using lattice structures, and stability is guaranteed as long as the allpass coefficients have magnitude less than 1. This approach is the basis for IIR QMF filter banks with perfect reconstruction.

Polyphase filter banks

Uniform vs non-uniform filter banks

• Uniform filter banks split the spectrum into $M$ subbands of equal bandwidth $\pi/M$, each decimated by $M$ (critically sampled). The DFT filter bank is the canonical example.
• Non-uniform filter banks have subbands with different bandwidths and decimation factors. These are useful when the signal's spectral content is unevenly distributed (e.g., audio coding with psychoacoustic models).

Polyphase decomposition applies to both types, though the analysis is simpler for uniform banks because the polyphase matrix has a regular structure.

Perfect reconstruction conditions

A filter bank achieves perfect reconstruction (PR) if the output equals a delayed, possibly scaled version of the input: $\hat{x}[n] = c \cdot x[n - n_0]$.

In polyphase terms, stack the analysis filters' polyphase components into an $M \times M$ matrix $\mathbf{E}(z)$ and the synthesis filters' components into $\mathbf{R}(z)$. Perfect reconstruction requires:

$\mathbf{R}(z) \cdot \mathbf{E}(z) = z^{-n_0} \mathbf{I}$

This means $\mathbf{R}(z) = z^{-n_0} \mathbf{E}^{-1}(z)$. The synthesis polyphase matrix must be the (delayed) inverse of the analysis polyphase matrix. For this inverse to exist, $\det(\mathbf{E}(z))$ must be a pure delay (a monomial in $z^{-1}$).

Cosine modulated filter banks

Cosine modulated filter banks (CMFBs) generate all $M$ analysis and synthesis filters by cosine-modulating a single prototype lowpass filter $p[n]$:

$h_k[n] = 2\, p[n] \cos\left[\frac{\pi}{M}\left(k + \frac{1}{2}\right)\left(n - \frac{N-1}{2}\right) + \theta_k\right]$

The advantage is that you only need to design one prototype filter. The modulation structure means the polyphase implementation can use a DCT-IV (or modified DCT) to combine the subband outputs, making the entire bank very efficient. CMFBs are used extensively in audio coding (e.g., the MPEG audio standard).

Paraunitary filter banks

A filter bank is paraunitary if its polyphase matrix satisfies:

$\tilde{\mathbf{E}}(z) \cdot \mathbf{E}(z) = c \cdot \mathbf{I}$

where $\tilde{\mathbf{E}}(z) = \mathbf{E}^{H}(z^{-1})$ (conjugate transpose with $z \to z^{-1}$). This is the matrix generalization of a lossless transfer function.

Properties of paraunitary filter banks:

• Perfect reconstruction is automatic (the synthesis matrix is just the paraconjugate of the analysis matrix).
• The subbands are orthogonal, and total signal energy is preserved across subbands.
• They can be factored into a product of elementary rotation matrices (Givens rotations) and delays, which gives a lattice implementation with structurally guaranteed PR.

Computational efficiency of polyphase structures

Reduced complexity compared to direct form

The core saving is straightforward: in a decimation-by-$M$ system with an $N$-tap filter, direct implementation requires $N$ multiplies per input sample, but only every $M$-th output is retained. Polyphase implementation requires $N/M$ multiplies per output sample. For interpolation, the same factor-of-$M$ (or $L$) reduction applies.

Beyond the multiply count, polyphase structures also reduce memory bandwidth requirements because each sub-filter accesses a smaller delay line.

Exploiting parallelism in polyphase implementations

The $M$ polyphase branches are independent of each other (for FIR filters), which maps naturally to parallel hardware or multi-threaded software. Each branch processes its own subsequence with its own sub-filter, and the results are combined only at the final summation (decimation) or commutation (interpolation) step.

This makes polyphase structures particularly well-suited for SIMD architectures, GPU-based processing, and multi-core DSP chips.

Polyphase decomposition in hardware implementations

On FPGAs and ASICs, polyphase structures offer several advantages:

• Regular, modular architecture: All $M$ branches have the same structure (same-length sub-filters), simplifying layout and routing.
• Reduced clock rate: Each sub-filter runs at $1/M$ the input rate, relaxing timing constraints.
• Resource sharing: If throughput requirements allow, a single multiply-accumulate unit can be time-shared across branches, trading parallelism for area.
• Pipelining: The natural decomposition into stages makes it easy to insert pipeline registers for higher clock frequencies.

These properties make polyphase the standard implementation strategy for high-speed channelizers, digital down-converters, and wideband spectrum analyzers.

Advanced topics in polyphase decomposition

Multidimensional polyphase decomposition

Polyphase decomposition extends to 2-D and higher-dimensional signals by replacing the scalar decimation factor $M$ with a decimation matrix $\mathbf{M}$. The number of polyphase components equals $|\det(\mathbf{M})|$, and each component corresponds to a coset of the lattice defined by $\mathbf{M}$.

The z-domain notation generalizes using vector exponents: $\mathbf{z}^{-\mathbf{k}}$ for multi-index delays. The Noble identities and perfect reconstruction conditions carry over, though the algebra becomes more involved. Applications include separable and non-separable subband coding for images and video.

Generalized polyphase representation

The standard polyphase framework assumes integer decimation factors. The generalized polyphase representation extends this to systems where different channels may have different (possibly non-integer) rate changes. It provides a unified matrix framework for analyzing arbitrary multirate interconnections.

This representation is useful for designing non-uniform filter banks and for analyzing systems where the decimation factors across channels don't share a common integer structure.

Polyphase decomposition in rational sampling rate systems

A rational sampling rate change by $L/M$ combines interpolation by $L$ and decimation by $M$. The polyphase approach handles this by:

1. Forming the interpolation filter's polyphase decomposition with $L$ branches.
2. Applying the decimation operation to the polyphase outputs.
3. Combining the two operations into a single polyphase structure with $L$ sub-filters, each of length approximately $N/L$, where only every $M$-th phase is computed at each output instant.

The result is that filtering runs at the output rate (not the higher intermediate rate $L \cdot f_s$), and the total computation per output sample is proportional to $N/L$. This is the standard approach in practical sample rate converters (e.g., the Farrow structure combined with polyphase filtering for arbitrary rate conversion).