Polyphase Decomposition

Polyphase decomposition is a mathematical technique for restructuring a digital filter into a set of parallel subfilters called polyphase components, each operating at a reduced sample rate. It is the theoretical foundation behind efficient multirate filter implementations and plays a central role in fast interpolation, decimation, and filter bank design. For GATE aspirants, understanding polyphase decomposition is essential for solving problems on computational complexity reduction in multirate systems.

Core Concept: What Polyphase Decomposition Achieves

Consider a FIR lowpass filter H(z) with N coefficients used inside an interpolator by factor M. In the straightforward implementation, the filter runs at the high output rate M.Fs, computing N multiplications for every output sample. Since there are M output samples per input sample, the total computation per input sample is N.M multiplications. Polyphase decomposition restructures this same computation into M parallel subfilters, each with N/M coefficients and each running at the original input rate Fs. The total computation per input sample becomes M x (N/M) = N multiplications, a reduction by a factor of M.

The decomposition is based on grouping the impulse response coefficients into M interleaved subsequences. For a factor of M, the k-th polyphase component Ek(z) contains coefficients h[k], h[k+M], h[k+2M], h[k+3M] and so on. These components are related to the original filter by:

H(z) = sum from k=0 to M-1 of z^(-k) . Ek(z^M)

This identity shows that the original filter can be exactly reconstructed from its polyphase components. No approximation is involved; polyphase is a mathematical reformulation, not a simplification of the filter.

Mathematical Expression

For a filter H(z) with impulse response h[n], the M-fold polyphase decomposition is:

Ek(z) = sum over n of h[Mn + k] . z^(-n) for k = 0, 1, 2, ..., M-1

And the reconstruction identity is:

H(z) = E0(z^M) + z^(-1).E1(z^M) + z^(-2).E2(z^M) + ... + z^(-(M-1)).E(M-1)(z^M)

In a polyphase decimator, the input is commutated (distributed round-robin) to M branches, each filtered by Ek(z), and the outputs are summed. In a polyphase interpolator, the input is broadcast to all M branches, filtered, and the outputs are commutated to form the high-rate sequence. Noble identities allow moving the downsampler or upsampler past the filter to operate at the lowest possible rate.

Practical Understanding

The computational benefit of polyphase decomposition becomes critical in real-time DSP applications where the processor must handle large filter lengths and high sampling rates simultaneously. For example, a 240-tap interpolation filter with M = 8 would require 240 x 8 = 1920 multiplications per input sample in a naive implementation. With polyphase decomposition, only 240 multiplications per input sample are needed, an 8x reduction.

Polyphase structures are also the backbone of efficient filter bank implementations. In both analysis and synthesis filter banks, the filters applied to each subband can be expressed as polyphase components of a prototype lowpass filter, allowing the entire bank to be implemented with a single fast convolution plus a DFT or modulation matrix.

For GATE problems, the key relationships to remember are: the number of polyphase components equals the decimation or interpolation factor M or L, each component has N/M taps (assuming N divisible by M), and each runs at the base rate Fs. Noble identities describe when decimators and upsamplers can be moved past LTI filters.

Given:
FIR lowpass filter: h[n] = {1, 2, 3, 4, 5, 6} (N = 6 taps)
Polyphase factor M = 3

Why this formula applies:
Polyphase decomposition groups coefficients by their index mod M.
Ek(z) collects h[k], h[k+M], h[k+2M], ...

Formula:
Ek(z) = sum_n h[Mn+k] * z^(-n), for k = 0,1,...,M-1
H(z) = sum_k z^(-k) * Ek(z^M)

Substitution:
E0(z): h[0], h[3] => 1 + 4*z^-1
E1(z): h[1], h[4] => 2 + 5*z^-1
E2(z): h[2], h[5] => 3 + 6*z^-1

Calculation:
Verification:
H(z) = E0(z^3) + z^-1*E1(z^3) + z^-2*E2(z^3)
     = (1 + 4z^-3) + z^-1(2 + 5z^-3) + z^-2(3 + 6z^-3)
     = 1 + 2z^-1 + 3z^-2 + 4z^-3 + 5z^-4 + 6z^-5 (matches h[n])

Final Answer:
E0(z) = 1 + 4z^-1
E1(z) = 2 + 5z^-1
E2(z) = 3 + 6z^-1
Each subfilter: 2 taps (N/M = 6/3 = 2), runs at Fs instead of 3Fs
Computation saving: factor of M = 3

Exam Tip: In GATE, polyphase component Ek(z) for decimation by M collects coefficients h[k], h[k+M], h[k+2M]... starting at index k. The number of polyphase components always equals M and each has N/M taps. Noble identities allow commuting upsamplers and downsamplers past LTI systems.

Mechanism Summary

• Polyphase decomposition splits H(z) into M subfilters Ek(z), where Ek contains every M-th coefficient starting at index k. No approximation is involved.
• The reconstruction identity H(z) = sum of z^(-k) . Ek(z^M) holds exactly for all z.
• Each polyphase subfilter has N/M taps and operates at the base rate Fs, giving a computational saving factor of M compared to the naive implementation.
• Noble Identity 1: A filter H(z) followed by a downsampler by M is equivalent to H(z^M) preceded by the downsampler.
• Noble Identity 2: An upsampler by L followed by filter H(z) is equivalent to H(z^L) followed by the upsampler.

Quick Revision

• Polyphase component: Ek(z) = sum_n h[Mn+k] . z^(-n) for k = 0, 1, ..., M-1.
• Reconstruction: H(z) = E0(z^M) + z^-1 E1(z^M) + ... + z^(-(M-1)) E(M-1)(z^M).
• Computation savings: each of M branches has N/M taps at rate Fs vs original N taps at M.Fs.
• Noble Identity 1 (decimation): H(z) then Downsample-M = Downsample-M then H(z^M).
• Noble Identity 2 (interpolation): Upsample-L then H(z) = H(z^L) then Upsample-L.
• Exam trap: confusing the argument of Ek. It is Ek(z^M), not Ek(z), in the reconstruction formula.
• Polyphase decomposition is the basis for efficient filter banks, DFT filter banks, and fast convolution algorithms.