Parks-McClellan Algorithm for FIR Filter Design

1. The Minimax Criterion and Equiripple Filters

The goal of the Parks-McClellan algorithm is to design a filter whose frequency response is the best possible approximation to a desired ideal response. "Best" here is defined by the minimax criterion: we want to minimize the maximum absolute error between the actual frequency response and the desired one.

To make this more flexible, we introduce a weighting function, $W(\omega )$, allowing us to specify that errors at some frequencies are more important than others. The weighted error function is:

$E(\omega )=W(\omega )[H_d(e^{j\omega })-H(e^{j\omega })]$

where:

• $H_d(e^{j\omega })$ is the ideal or desired frequency response (e.g., 1 in the passband, 0 in the stopband).
• $H(e^{j\omega })$ is the frequency response of the actual FIR filter we are designing.
• $W(\omega )$ is the weighting function.

The goal is to find the filter coefficients that minimize $\max |E(\omega )|$ over the frequency bands we care about.

A remarkable property of filters that satisfy the minimax criterion is that their error is spread out evenly. The error oscillates with a constant maximum magnitude, $\delta$, across the passband and stopband. This is why these filters are called equiripple filters.

This image illustrates the key characteristics of an equiripple filter designed using the Parks-McClellan method. The top plot shows the magnitude response with uniform ripples in the passband and stopband. The bottom plot shows the weighted error function, which oscillates between a maximum positive value $+\delta$ and a maximum negative value $-\delta$.

2. The Alternation Theorem: The Mathematical Foundation

The reason optimal filters have this equiripple property is explained by a beautiful piece of mathematics called the Alternation Theorem.

First, it's important to recognize that the frequency response of a linear-phase FIR filter can be written as a sum of cosines, which is a type of trigonometric polynomial. For example, a Type I filter (odd length $N=2L+1$, even symmetry) has a frequency response of the form:
$H(e^{j\omega })={\sum }_{k=0}^L{a}_k\cos (k\omega )$
where $a_k$ are related to the impulse response coefficients $h[n]$. Designing the filter means finding the best set of $a_k$.

The Alternation Theorem provides the precise condition that this best polynomial approximation must satisfy.

The Alternation Theorem states: For a Type I FIR filter with $L+1$ independent coefficients (e.g., $a_0,\dots ,a_L$), the unique best approximation that minimizes the maximum weighted error is the one for which the error function $E(\omega )$ exhibits at least $L+2$ extremal frequencies. At these frequencies, the error must reach its maximum magnitude $\pm \delta$ and alternate in sign.

The theorem is the key because it turns the abstract optimization problem ("find the best filter") into a concrete, testable condition ("find the filter whose error alternates $L+2$ times"). The Parks-McClellan algorithm is an iterative method designed to find exactly this filter.

3. The Parks-McClellan (Remez Exchange) Algorithm

The algorithm doesn't solve for the filter coefficients directly. Instead, it iteratively searches for the correct set of extremal frequencies. Once these are known, the filter and its error are uniquely determined. The algorithm is an application of the Remez exchange algorithm from approximation theory.

The steps are as follows:

1. Guess: Choose an initial set of $L+2$ guessed extremal frequencies, $\{{\omega }_0,{\omega }_1,\dots ,{\omega }_{L+1}\}$. These are typically spread across the passband(s) and stopband(s).

2. Solve: For this set of frequencies, we force the alternation property. We set up a system of $L+2$ linear equations with $L+2$ unknowns: the $L+1$ filter coefficients ($a_k$) and the error magnitude $\delta$.
   $W({\omega }_i)[H_d(e^{j{\omega }_i})-H(e^{j{\omega }_i})]=(-1{)}^i\delta \text{for }i=0,1,\dots ,L+1$
   This can be rearranged into a standard matrix form $A\mathbf{x}=\mathbf{b}$ and solved.

*This image shows the structure of the system of linear equations that must be solved at each iteration of the algorithm. The matrix contains cosine terms evaluated at the guessed extremal frequencies, the unknown vector contains the filter coefficients and the error $\delta$, and the right-hand side contains the desired response values.*

3. Find Extrema: Using the filter coefficients found in Step 2, calculate the dense frequency response $H(e^{j\omega })$ and the resulting error function $E(\omega )$ over the entire frequency range. Then, find the actual local extrema of this error function.

4. Exchange & Repeat: The new set of extrema found in Step 3 will likely be different from our initial guess. The "exchange" step involves replacing the old guessed extrema with these new ones. Now, we go back to Step 2 and repeat the process.

The algorithm converges (usually in a small number of iterations) when the extremal frequencies found in Step 3 are the same as the ones used in Step 2. At this point, the filter satisfies the Alternation Theorem and is therefore the optimal minimax filter.

4. Practical Design Considerations

Using the Weighting Function

The minimax criterion minimizes the weighted error $W(\omega )|H_d-H|$. This is extremely useful for controlling the trade-off between passband ripple (${\delta }_p$) and stopband attenuation (${\delta }_s$).

The ripple in any band is inversely proportional to the weight in that band. If we want the stopband ripple ${\delta }_s$ to be 10 times smaller than the passband ripple ${\delta }_p$, we must set the weight in the stopband to be 10 times larger than the weight in the passband. A common practice is to set $W_{pass}=1$ and $W_{stop}={\delta }_p/{\delta }_s$.

Historical Context and Modern Implementations

The Parks-McClellan algorithm was a major breakthrough in digital signal processing. It provided a systematic way to design the best possible FIR filters.

One key point from this reading is that the core algorithm is designed for Type I filters. Other filter types (Type II, III, and IV, for things like even-length filters, differentiators, or Hilbert transformers) are handled by cleverly transforming their design specifications into an equivalent Type I problem, solving it, and then transforming the resulting coefficients back. This demonstrates the power and generality of the underlying mathematical framework.

Conclusion

Today we delved into the principles behind optimal FIR filter design using the Parks-McClellan algorithm. This method stands in contrast to the more heuristic window and frequency sampling methods by providing a filter that is provably the best for a given length and design specification.

Key Takeaways:

• The Parks-McClellan algorithm designs optimal equiripple FIR filters based on the minimax error criterion.
• The filter is "optimal" in that it minimizes the maximum weighted error in the passband and stopband.
• The design is mathematically guaranteed by the Alternation Theorem, which states the optimal filter's error must alternate at least $L+2$ times.
• The algorithm is an iterative application of the Remez exchange algorithm, which finds the set of extremal frequencies that satisfies the theorem.
• The weighting function is a powerful tool for controlling the relative ripple between different frequency bands (e.g., achieving higher stopband attenuation).

Preview of the Next Lesson:

We have now covered the three main FIR filter design paradigms: windowing, frequency sampling, and optimal equiripple design. We will now shift our focus from FIR filters to Infinite Impulse Response (IIR) filters. While FIR filters offer the advantages of guaranteed stability and linear phase, IIR filters can often achieve a similar magnitude response with a significantly lower filter order, making them much more computationally efficient. Our next lesson will begin by exploring the historical context of digital filter design, before we dive into methods for designing IIR filters, often by transforming classic analog filter prototypes into the digital domain.