ArticleslgStudy

computer science

Parks–McClellan filter design algorithm

Parks–McClellan filter design algorithm is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Parks–McClellan filter design algorithm rather than just read about it. In short: The Parks–McClellan algorithm, published by James McClellan and Thomas Parks in 1972, is an iterative algorithm for finding the optimal Chebyshev finite impulse response (FIR) filter. The Parks–McClellan algorithm is utilized to design and implement efficient and optimal FIR filters.

Parks–McClellan filter design algorithm — main illustration
Parks–McClellan filter design algorithm — illustration

Key takeaways

  • Parks–McClellan filter design algorithm belongs to computer science; place it in that map before memorising details.
  • Learn the definition first, then one example that makes the definition concrete.
  • Connect Parks–McClellan filter design algorithm to a quantity you can measure, compute or draw — that is where exam questions come from.
  • Reproduce the core statement of Parks–McClellan filter design algorithm from memory before moving on to harder problems.

Reference excerpt

The Parks–McClellan algorithm, published by James McClellan and Thomas Parks in 1972, is an iterative algorithm for finding the optimal Chebyshev finite impulse response (FIR) filter. 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 exchange algorithm, with the change that it is specifically designed for FIR filters. It has become a standard method for FIR filter design.

History

History of optimal FIR filter design 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 (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 to produce infinite impulse response (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 In August 1970, James McClellan entered graduate school at Rice University with a concentration in mathematical models of analog filter design and 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. 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 McClellan took as well. During spring break of the semester, Parks drove from Houston to Princeton in order to attend a conference, where 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, McClellan and Parks were attempting to write a variation of the Remez exchange algorithm for FIR filters. It took about six weeks to develop and some optimal filters had been designed successfully by the end of May.

The algorithm

The Parks–McClellan Algorithm is implemented using the following steps:

Initialization: Choose an extremal set of frequences {ωi(0)}. Finite Set Approximation: Calculate the best Chebyshev approximation

f ( x ) ≈ ∑ i = 0 n c i T i ( x ) {\displaystyle f(x)\approx \sum _{i=0}^{n}c_{i}T_{i}(x)} , where c𝑖 are Chebyshev coefficients 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(0)} and the interpolation formula to compute an inverse discrete Fourier transform to obtain the filter coefficients. The Parks–McClellan Algorithm may be restated as the following steps:

… excerpt ends here. Continue reading the full article.

Illustrations

Parks–McClellan filter design algorithm: Pass and stop bands of a filter designed by the Parks–McClellan algorithm The y-axis is the frequency response H(ω) and the x-axis are the various radian frequencies, ωi. It can be noted that the two frequences marked on the x-axis, ωp and ωs. ωp indicates the pass band cutoff frequency and ωs indicates the stop band cutoff frequency. The ripple like plot on the upper left is the pass band ripple and the ripple on the bottom right is the stop band ripple. The two dashed lines on the top left of the graph indicate the δp and the two dashed lines on the bottom right indicate the δs. All other frequencies listed indicate the extremal frequencies of the frequency response plot. As a result, there are six extremal frequencies, and then we add the pass band and stop band frequencies to give a total of eight extremal frequencies on the plot.
Pass and stop bands of a filter designed by the Parks–McClellan algorithm The y-axis is the frequency response H(ω) and the x-axis are the various radian frequencies, ωi. It can be noted that the two frequences marked on the x-axis, ωp and ωs. ωp indicates the pass band cutoff frequency and ωs indicates the stop band cutoff frequency. The ripple like plot on the upper left is the pass band ripple and the ripple on the bottom right is the stop band ripple. The two dashed lines on the top left of the graph indicate the δp and the two dashed lines on the bottom right indicate the δs. All other frequencies listed indicate the extremal frequencies of the frequency response plot. As a result, there are six extremal frequencies, and then we add the pass band and stop band frequencies to give a total of eight extremal frequencies on the plot.

Worked examples

Example 1 — a first encounter with Parks–McClellan filter design algorithm

Start with the simplest possible case. Write down what Parks–McClellan filter design algorithm claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Parks–McClellan filter design algorithm before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Parks–McClellan filter design algorithm ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Parks–McClellan filter design algorithm

In research
Parks–McClellan filter design algorithm appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry
Engineering practice reuses Parks–McClellan filter design algorithm in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom
Parks–McClellan filter design algorithm is common in secondary-school and first-year university syllabi. It links to neighbouring topics Digital signal processing, Filter theory, so understanding it makes those chapters shorter.
In everyday life
Look for Parks–McClellan filter design algorithm outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.
Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Parks–McClellan filter design algorithm” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Parks–McClellan filter design algorithm in 20 minutes

  1. Read the reference excerpt below once, without taking notes.
  2. Close the page and write down what Parks–McClellan filter design algorithm means in your own words.
  3. Compare your version with the excerpt and mark what you missed.
  4. Work through the three examples above with pen and paper.
  5. Explain Parks–McClellan filter design algorithm out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Parks–McClellan filter design algorithm in simple terms?

The Parks–McClellan algorithm, published by James McClellan and Thomas Parks in 1972, is an iterative algorithm for finding the optimal Chebyshev finite impulse response (FIR) filter. The Parks–McClellan algorithm is utilized to design and implement efficient and optimal FIR filters.

Why does Parks–McClellan filter design algorithm matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Parks–McClellan filter design algorithm?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Parks–McClellan filter design algorithm.

Tags

  • Digital signal processing
  • Filter theory

Keep exploring