Polyphase FIR Filters for Efficient Multirate Systems

1. The "Noble Identity": A Glimpse of the Solution

The inefficiency of the standard "filter-then-decimate" structure motivated a search for a more elegant solution. The breakthrough came in the mid-1970s from the work of M. G. Bellanger and his colleagues, who formalized the polyphase filter bank. The core principle behind this efficiency is a set of relationships that P. P. Vaidyanathan later termed the "noble identities" because of their "outstanding qualities."

The following video provides an excellent introduction to the problem and the conceptual solution, including some of the historical context you appreciate.

As the video explains, the "miracle" is the ability to swap the order of filtering and downsampling. This seems to violate the Nyquist criterion, but as we are about to see, it is made possible by first decomposing the filter into a set of smaller sub-filters. This decomposition is the polyphase representation.

2. Deriving the Polyphase Representation

Let's now formally derive this representation. Our goal is to take the transfer function of a long FIR filter, $H(z)$, and rewrite it in terms of several shorter filters that can operate at a lower sampling rate.

Consider an FIR filter of length $N$ with transfer function:
$H(z)={\sum }_{n=0}^{N-1}h[n]z^{-n}$

Let's decompose this filter into $M$ components, where $M$ is our desired decimation factor. We can do this by grouping the coefficients of $h[n]$ into $M$ subsequences. The $l$-th subsequence, for $l=0,1,\dots ,M-1$, consists of the coefficients $h[l],h[l+M],h[l+2M],\dots$.

The video below provides a clear, step-by-step derivation of how this grouping in the time domain translates to a new structure in the z-domain.

Let's summarize the key steps from the video.

1. Decompose the Summation: We can rewrite the index $n$ as $n=iM+l$, where $l$ is the subsequence index ($0\le l<M$) and $i$ is the index within that subsequence. The single sum for $H(z)$ becomes a double summation:
   $H(z)={\sum }_{l=0}^{M-1}{\sum }_{i=0}^{\lfloor (N-1-l)/M\rfloor }h[iM+l]z^{-(iM+l)}$

2. Rearrange Terms: We can separate the $z^{-l}$ term from the inner sum:
   $H(z)={\sum }_{l=0}^{M-1}{z}^{-l}\left({\sum }_{i=0}^{\lfloor (N-1-l)/M\rfloor }h[iM+l](z^M{)}^{-i}\right)$

3. Define the Polyphase Components: The expression in the parentheses is a new polynomial, but in the variable $z^M$. We define the $l$-th polyphase component filter, $E_l(z)$, as:
   $E_l(z)={\sum }_{i=0}^{\lfloor (N-1-l)/M\rfloor }h[iM+l]z^{-i}$
   The impulse response of this component is $e_l[i]=h[iM+l]$. Notice that $E_l(z)$ is an FIR filter whose coefficients are every $M$-th coefficient of the original filter $H(z)$, starting at index $l$. Each polyphase filter is approximately $M$ times shorter than the original filter.

4. Final Representation: Substituting this definition back, we get the Type 1 Polyphase Representation of $H(z)$:
   $H(z)={\sum }_{l=0}^{M-1}{z}^{-l}{E}_l(z^M)=E_0(z^M)+z^{-1}{E}_1(z^M)+\cdots +z^{-(M-1)}{E}_{M-1}(z^M)$

This equation is the heart of the derivation. It shows that any FIR filter can be perfectly represented by a parallel bank of $M$ shorter filters whose inputs are delayed by $0,1,\dots ,M-1$ samples.

For a concise written summary of this derivation, refer to the following resource.

3. The Efficient Implementation

Now we can finally see how this decomposition achieves efficiency. Recall the inefficient structure: input $x[n]$ goes to filter $H(z)$, and its output goes to a downsampler by $M$.

If we replace $H(z)$ with its polyphase representation, we get the structure shown in Figure 6(a) of the following document.

The key insight is the First Noble Identity, which states that a downsampler of factor $M$ can be moved from the output to the input of a filter $G(z^M)$, transforming it into a filter $G(z)$.

Applying this identity to each of the parallel branches in the diagram allows us to move the downsampler from the final output to a position just after the initial delays $z^{-l}$. This leads to the efficient structure shown in Figure 6(b).

To see this transformation and its implications clearly, please study the following material.

In the efficient structure:

1. The input signal is first split into $M$ paths.
2. Each path is downsampled by $M$.
3. Each downsampled stream is filtered by its corresponding short polyphase filter $E_l(z)$.
4. The outputs are summed to produce the final signal.

The computational gain is enormous. Instead of one long filter running at the high rate, we have $M$ short filters (each of length $\approx N/M$) running at the low rate. The total number of multiplications per output sample drops from $N\times M$ in the naive implementation to just $N$ in the polyphase implementation—a saving of factor $M$.

Conclusion

In this lesson, we have tackled a fundamental problem in multirate signal processing and derived its elegant solution. By starting with the goal of computational efficiency, we were led to a powerful mathematical construction.

Key Takeaways:

• The naive "filter-then-decimate" approach is inefficient because it computes many samples that are immediately discarded.
• An FIR filter $H(z)$ can be decomposed into $M$ shorter sub-filters called polyphase components $E_l(z)$. The impulse response of $E_l(z)$ is formed by taking every $M$-th coefficient of $H(z)$ starting at index $l$.
• The relationship is given by the polyphase representation: $H(z)={\sum }_{l=0}^{M-1}{z}^{-l}{E}_l(z^M)$.
• Using the Noble Identity, we can reconfigure the decimation architecture to perform the downsampling before the filtering.
• This efficient polyphase structure allows the short component filters to operate at the low sampling rate, reducing the computational load by a factor of $M$.

Preview of the Next Lesson:

We have now covered the core concepts of multirate processing: decimation, interpolation, and their efficient implementation using polyphase filters. These tools are primarily for changing a signal's sampling rate or for building efficient filter banks.

In the next lesson, we will shift our focus to a different but equally important challenge in signal analysis: how to analyze signals whose frequency content changes over time. We will explore the Short-Time Fourier Transform (STFT), a foundational technique for time-frequency analysis of such non-stationary signals.