2.3 Chebyshev or equal ripple error approximation filters  (Page 4/9)

The basic parks-mcclellan formulation and algorithm

Parks and McClellan formulated the basic Chebyshev FIR filter design problem by specifying the desired amplitude response $A\left(\omega \right)$ and the transition band edges, then minimizing the weighted Chebyshev error overthe pass and stop bands. For the basic lowpass filter illustrated in [link] , the pass band edge ${\omega }_p$ and the stop band edge ${\omega }_s$ are specified, the maximum passband error is related to the maximum stop band error by ${\delta }_p=K{\delta }_s$ and they are minimized.

Notice that if there is no transition band, i.e. ${\omega }_p={\omega }_s$ , that ${\delta }_p+{\delta }_s=1$ and no minimization is possible. While not the case for a least squares approximation, a transition band is necessaryfor the Chebyshev approximation problem to be well-posed. The effects of a small transition band are large pass and stopband ripple as illustratedin [link] b.

The alternation theorem states that the optimal approximation for this problem will have an error function with $R+1$ extremal points with alternating signs. The theorem also states that there exists $R+1$ frequencies such that, if the Chebyshev error at those frequencies are equal and alternate in sign, it will be minimized over the pass band andstop band. Note that there are nine extremal points in the length-15 example shown in [link] , counting those at the band edges in addition to those that are interior to the pass and stopbands. For this case, $R=(L+1)/2$ which agree with the example.

Parks and McClellan applied the Remez exchange algorithm [link] to this filter design problem by writing $R+1$ equations using Equation 37 from FIR Digital Filters and Equation 1 from Design of IIR Filters by Frequency Transformations evaluated at the $R+1$ extremal frequencies with $R$ unknown cosine parameters $a\left(n\right)$ and the unknown ripple value, $\delta$ . In matrix form this becomes

These equations are solved for $a\left(n\right)$ and $\delta$ using an initial guess as to the location of the extremal frequencies ${\omega }_i$ . This design is optimal but only over the guessed frequencies, and we want optimality overall of the pass and stopbands. Therefore, the amplitude response of the filter is calculated over a dense set of frequency samples using Equation 34 from FIR Digital Filters and a new set of estimates of the extremal frequencies is found from the local minima and maxima and these are used to replace the initialguesses (they are exchanged). This process is iteratively performed until the guaranteed convergence is achieved and the optimal filter is designed.

The detailed steps of the Parks-McClellan algorithm are:

1. Specify the ideal amplitude, $A_d\left(\omega \right)$ , the stop and pass band edges, ${\omega }_p$ and ${\omega }_s$ , the error weight $K$ where ${\delta }_p=K{\delta }_s$ , and the length $L$ .
2. Choose $R+1$ initial guesses for the extremal frequencies, ${\omega }_i$ , in the bands of approximation, $\Omega$ . This is often done uniformly over the pass and stop bands, including $\omega =0,{\omega }_p,{\omega }_s,$ and $\pi$ .
3. Calculate the cosine matrix at the current ${\omega }_i$ and solve [link] for $a\left(n\right)$ and $\delta$ which are optimal over these current extremal frequencies, ${\omega }_i$ .
4. Using the $a\left(n\right)$ or the equivalent $h\left(n\right)$ from step 3, evaluate $A\left(\omega \right)$ over a dense set of frequencies. This amplitude response will interpolate $A\left({\omega }_i\right)=A_d\left({\omega }_i\right)\pm \delta$ at the extremal frequencies.
5. Find $R+1$ new extremal frequencies where the error has a local maximum or minimum and has alternating sign. This includes the band edges.
6. If the largest error is the same as $\delta$ found in step 3, then convergence has occured and the optimal filter has been designed, otherwise,exchange the old extremal frequencies ${\omega }_i$ used in step 2 and return to step 3 for the next iteration.
7. This iterative algorithm is guaranteed to converge to the unique optimal solution using almost any starting points in step 2.