Parks-McClellan filter design algorithm

The Parks-McClellan algorithm, published by James McClellan and Thomas Parks

Thomas W. Parks

Thomas W. Parks is an American electrical engineer and Professor Emeritus of Electrical and Computer Engineering at Cornell University. He is best known for his contributions to digital signal processing, especially digital filter design and computation of the fast Fourier transform...

in 1972, is an iterative algorithm for finding the optimal Chebyshev finite impulse response

Finite impulse response

A finite impulse response filter is a type of a signal processing filter whose impulse response is of finite duration, because it settles to zero in finite time. This is in contrast to infinite impulse response filters, which have internal feedback and may continue to respond indefinitely...

(FIR) filter

Digital filter

In electronics, computer science and mathematics, a digital filter is a system that performs mathematical operations on a sampled, discrete-time signal to reduce or enhance certain aspects of that signal. This is in contrast to the other major type of electronic filter, the analog filter, which is...

. The Parks-McClellan algorithm is utilized to design and implement efficient and optimal FIR filters. It uses an indirect method for finding the optimal filter coefficients.

The goal of the algorithm is to minimize the error in the pass and stop bands by utilizing the Chebyshev approximation. The Parks-McClellan algorithm is a variation of the Remez algorithm

Remez algorithm

The Remez algorithm , published by Evgeny Yakovlevich Remez in 1934 is an iterative algorithm used to find simple approximations to functions, specifically, approximations by functions in a Chebyshev space that are the best in the uniform norm L∞ sense.A typical...

or Remez exchange algorithm, with the change that it is specifically designed for FIR filters and has become a standard method for FIR filter design.

History of Designing Optimal FIR Filter

In the 1960s, researchers within the field of analog filter design were using the Chebyshev approximation for filter design. During this time, it was well-known that the best filters contain an equiripple characteristic in their frequency response magnitude and the elliptic filter

Elliptic filter

An elliptic filter is a signal processing filter with equalized ripple behavior in both the passband and the stopband...

(or Cauer filter) was optimal with regards to the Chebyshev approximation. When the digital filter revolution began in the 1960s, researchers used a bilinear transform

Bilinear transform

The bilinear transform is used in digital signal processing and discrete-time control theory to transform continuous-time system representations to discrete-time and vice versa....

to produce infinite impulse response

Infinite impulse response

Infinite impulse response is a property of signal processing systems. Systems with this property are known as IIR systems or, when dealing with filter systems, as IIR filters. IIR systems have an impulse response function that is non-zero over an infinite length of time...

(IIR) digital elliptic filters. They also recognized the potential for designing FIR filters to accomplish the same filtering task and soon the search was on for the optimal FIR filter using the Chebyshev approximation.

It was well known in both mathematics and engineering that the optimal response would exhibit an equiripple behavior and that the number of ripples could be counted using the Chebyshev approximation. Several attempts to produce a design program for the optimal Chebyshev FIR filter were undertaken in the period between 1962 and 1971. Despite the numerous attempts, most did not succeed, usually due to problems in the algorithmic implementation or problem formulation. Otto Herrmann, for example, proposed a method for designing equiripple filters with restricted band edges. This method obtained an equiripple frequency response with the maximum number of ripples by solving a set of nonlinear equations. Another method introduced at the time implemented an optimal Chebyshev approximation, but the algorithm was limited to the design of relatively low-order filters.

Similar to Herrmann's method, Ed Hofstetter presented an algorithm that designed FIR filters with as many ripples as possible. This has become known as the Maximal Ripple algorithm. The Maximal Ripple algorithm imposed an alternating error condition via interpolation and then solved a set of equations that the alternating solution had to satisfy. One notable limitation of the Maximal Ripple algorithm was that the band edges were not specified as inputs to the design procedure. Rather, the initial frequency set {ω_i} and the desired function D(ω_i) defined the pass and stop band implicitly. Unlike previous attempts to design an optimal filter, the Maximal Ripple algorithm used an exchange method that tried to find the frequency set {ω_i} where the best filter had its ripples. Thus, the Maximal Ripple algorithm was not an optimal filter design but it had quite a significant impact on how the Parks-McClellan algorithm would formulate.

History of Parks-McClellan Algorithm

In August 1970, James McClellan entered graduate school at Rice University with a concentration in mathematical models of analog filter design. James McClellan enrolled in a new course called "Digital Filters" due to his interest in filter design. The course was taught jointly by Thomas Parks and Sid Burrus

C. Sidney Burrus

Charles Sidney Burrus is an American electrical engineer and the Maxfield and Oshman Professor Emeritus of Electrical and Computer Engineering at Rice University in Houston, Texas...

. At that time, DSP was an emerging field and, as a result, lectures often involved recently published research papers. The following semester, the spring of 1971, Thomas Parks offered a course called "Signal Theory," which James McClellan took as well. During spring break of the semester, Thomas drove from Houston to Princeton in order to attend a conference. At the conference, he heard Ed Hofstetter's presentation about a new FIR filter design algorithm (Maximal Ripple algorithm). He brought the paper by Hofstetter, Oppenheim, and Siegel, back to Houston, thinking about the possibility of using the Chebyshev approximation theory to design FIR filters. He heard that the method implemented in Hofstetter's algorithm was similar to the Remez exchange algorithm and decided to pursue the path of using the Remez exchange algorithm. The students in the "Signal Theory" course were required to do a project and since Chebyshev approximation was a major topic in the course, the implementation of this new algorithm became James McClellan's course project. This ultimately led to the Parks-McClellan algorithm, which involved the theory of optimal Chebyshev approximation and an efficient implementation. By the end of the spring semester, James McClellan and Thomas Parks were attempting to write a variation of the Remez exchange algorithm for FIR filters. It took about six weeks to develop and by the end of May, some optimal filters had been designed successfully.

James McClellan and Thomas Parks

James McClellan was born on October 5, 1947 in Guam

Guam

Guam is an organized, unincorporated territory of the United States located in the western Pacific Ocean. It is one of five U.S. territories with an established civilian government. Guam is listed as one of 16 Non-Self-Governing Territories by the Special Committee on Decolonization of the United...

. He received his Bachelor of Science in Electrical Engineering

Electrical engineering

Electrical engineering is a field of engineering that generally deals with the study and application of electricity, electronics and electromagnetism. The field first became an identifiable occupation in the late nineteenth century after commercialization of the electric telegraph and electrical...

(1969) from Louisiana State University

Louisiana State University

Louisiana State University and Agricultural and Mechanical College, most often referred to as Louisiana State University, or LSU, is a public coeducational university located in Baton Rouge, Louisiana. The University was founded in 1853 in what is now known as Pineville, Louisiana, under the name...

. After receiving his Master of Science (1972) and Doctorate (1973) degrees from Rice University

Rice University

William Marsh Rice University, commonly referred to as Rice University or Rice, is a private research university located on a heavily wooded campus in Houston, Texas, United States...

, Dr. McClellan worked at the MIT Lincoln Laboratory from 1973 to 1975. He became a professor in the MIT Electrical Engineering and Computer Science Department in 1975. After working at the university for seven years, Dr. McClellan joined Schlumberger

Schlumberger

Schlumberger Limited is the world's largest oilfield services company. Schlumberger employs over 110,000 people of more than 140 nationalities working in approximately 80 countries...

in 1982, where he worked for five years. Since 1987, Dr. McClellan has been a Professor of Electrical Engineering at the Georgia Institute of Technology

Georgia Institute of Technology

The Georgia Institute of Technology is a public research university in Atlanta, Georgia, in the United States...

. Dr. McClellan has received numerous awards for his work in digital signal processing

Signal processing

Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...

and its application to sensor array processing: IEEE Signal Processing Technical Achievement Award (1987), IEEE Signal Processing Society Award (1996), and IEEE Jack S. Kilby Signal Processing Medal (2004). In addition to the awards he has received, Dr. McClellan has published a number of significant pieces of literature: Computer-Based Exercises for Signal Processing Using MATLAB 5 (1994), DSP First (1997), Signal Processing First (2003), and Number Theory in DSP (1979).

Thomas Parks was born on March 16, 1939 in Buffalo, New York. He received his Bachelor (1961), Master of Science (1964), and Doctorate (1967) degrees in Electrical Engineering from Cornell University

Cornell University

Cornell University is an Ivy League university located in Ithaca, New York, United States. It is a private land-grant university, receiving annual funding from the State of New York for certain educational missions...

. After graduating with his doctorate, Dr. Parks joined the faculty at Rice University. He was a faculty member from 1967 to 1986, when he joined the faculty at Cornell University. Dr. Parks is the recipient of multiple awards based on his research focused on digital signal processing with its application to signal theory, multirate systems, interpolation

Interpolation

In the mathematical field of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points....

, and filter design: IEEE ASSP Society Technical Achievement Award (1981), IEEE ASSP Society Award (1988), Rice University President's Award (1999), IEEE Third Millennium Medal (2000), and IEEE Jack S. Kilby Signal Processing Medal (2004). In addition to the awards he has received, Dr. Parks has published numerous contributions to the electrical engineering field: DFT/FFT Convolution Algorithms (1985), Digital Filter Design (1987), A Digital Signal Processing Laboratory Using the TMS 32010 (1988), A Digital Signal Processing Laboratory Using the TMS 320C25 (1990), Computer-Based Exercises for Signal Processing (1994), and Computer-Based Exercises for Signal Processing Using MATLAB 5 (1994).

Parks-McClellan Algorithm

According to the IEEE Signal Processing Magazine, the Parks-McClellan Algorithm is implemented using the following steps:

Initialization: Choose an extremal set of frequences {ω_i⁽⁰⁾}.
Finite Set Approximation: Calculate the best Chebyshev approximation on the present extremal set, giving a value δ^(m) for the min-max error on the present extremal set.
Interpolation: Calculate the error function E(ω) over the entire set of frequencies Ω using (2).
Look for local maxima of |E^(m)(ω)| on the set Ω.
If max_(ωεΩ)|E^(m)(ω)| > δ^(m), then update the extremal set to {ω_i^(m+1)} by picking new frequencies where |E^(m)(ω)| has its local maxima. Make sure that the error alternates on the ordered set of frequencies as described in (4) and (5). Return to Step 2 and iterate.
If max_(ωεΩ)|E^(m)(ω)| ≤ δ^(m), then the algorithm is complete. Use the set {ω_i⁽⁰⁾} and the interpolation formula to compute an inverse discrete Fourier transform to obtain the filter coefficients.

According the Professor Douglas Jones of the University of Illinois, the Parks-McClellan Algorithm may be implemented as the following:

Make an initial guess of the L+2 extremal frequencies.
Compute δ using the equation given.
Using Lagrange Interpolation, we compute the dense set of samples of A(ω) over the passband and stopband.
We Determine the new L+2 largest extrema.
If the Alternation Theorem is not satisfied, then we go back to (2) and iterate until the Alternation Theorem is satisfied.
If the Alternation Theorem is satisfied, then we compute h(n) and we are done.

To gain a basic understanding of the Parks-McClellan Algorithm mentioned above, we can rewrite the algorithm above in a simpler form as:

Guess the positions of the extrema are evenly spaced in the pass and stop band.
Perform polynomial interpolation and re-estimate positions of the local extrema.
Move extrema to new positions and iterate until the extrema stop shifting.

Explanation

The picture above on the right displays the various extremal frequencies for the plot shown. The extremal frequencies are the maximum and minimum points in the stop and pass bands. The stop band ripple is the lower portion of ripples on the bottom right of the plot and the pass band ripple is the upper portion of the ripples on the top left of the plot. The dashed lines going across the plot indicate the δ or maximum error. Given the positions of the extremal frequencies, there is a formula for the optimum δ or optimum error. Since we do not know the optimum δ or the exact positions of the extrema on the first attempt, we iterate. Effectively, we assume the positions of the extrema initially, and calculate δ. We then re-estimate and move the extrema and recalculate δ, or the error. We repeat this process until δ stops changing. The algorithm will cause the δ error to converge, generally within ten to twelve iterations.

Additional Notes

Before applying the Chebyshev approximation, a set of steps were necessary:

Define the set of basis function for the approximation, and
Exploit the fact that the pass and stop bands of bandpass filters would always be separated by transition regions.

Since FIR filters could be reduced to the sum of cosines case, the same core program could be used to perform all possible linear-phase FIR filters. In contrast to the Maximum Ripple approach, the band edges could now be specified ahead of time.

To achieve an efficient implementation of the optimal filter design using the Park-McClellan algorithm, two difficulties have to be overcome:

Defining a flexible exchange strategy, and
Implementing a robust interpolation method.

In some sense, the programming involved the implementation and adaptation of a known algorithm for use in FIR filter design. Two faces of the exchange strategy were taken to make the program more efficient:

Allocating the extremal frequencies between the pass and stop bands, and
Enabling movement of the extremals between the bands as the program iterated.

At initialization, the number of extremals in the pass and stop bad could be assigned by using the ratio of the sizes of the bands. Furthermore, the pass and stop band edge would always be placed in the extremal set, and the program's logic kept those edge frequencies in the extremal set. The movement between bands was controlled by comparing the size of the errors at all the candidate extremal frequencies and taking the largest. The second element of the algorithm was the interpolation step needed to evaluate the error function. They used a method called the Barycentric form of Lagrange interpolation, which was very robust.

All conditions for the Parks-McClellan algorithm are based on Chebyshev's Alternation Theorem. The Alternation Theorem states that the polynomial of degree L that minimizes the maximum error will have at least L+2 extrema. The optimal frequency response will barely reach the maximum ripple bounds. The extrema must occur at the pass and stop band edges and at either ω=0 or ω=π or both. Now the derivative of a polynomial of degree L is a polynomial of degree L-1, which can be zero at most at L-1 places. So the maximum number of local extrema is the L-1 local extrema plus the 4 band edges, giving a total of L+3 extrema.

Additional References

The following additional links provide information on the Parks-McClellan Algorithm, as well as on other research and papers written by James McClellan and Thomas Parks:

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.