Parks–McClellan filter design algorithm

<h2 id="history">History</h2>
<h3>History of optimal FIR filter design</h3>
In the 1960s, researchers within the field of analog filter design were using the <a href="/facts/Chebyshev_approximation/87AaPXLp">Chebyshev approximation</a> 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 <a href="/facts/Elliptic_filter/X5RGIuWs">elliptic filter</a> (or Cauer filter) was optimal with regards to the Chebyshev approximation. When the digital filter revolution began in the 1960s, researchers used a <a href="/facts/Bilinear_transform/hstbQ7y8">bilinear transform</a> to produce <a href="/facts/Infinite_impulse_response/0KLkxylJ">infinite impulse response</a> (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.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>
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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> 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.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> 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.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
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.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> 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.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> 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.

<h3>History of Parks–McClellan</h3>
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.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> The course was taught jointly by Thomas Parks and <a href="/facts/C._Sidney_Burrus/E4tsUg4S">Sid Burrus</a>. 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.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> 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.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> 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.

<h2 id="the-algorithm">The algorithm</h2>

The Parks–McClellan Algorithm is implemented using the following steps:<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

<ol><li>Initialization: Choose an extremal set of frequences {ωi(0)}.</li>
<li>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.</li>
<li>Interpolation: Calculate the error function E(ω) over the entire set of frequencies Ω using (2).</li>
<li>Look for local maxima of |E(m)(ω)| on the set Ω.</li>
<li>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.</li>
<li>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.</li></ol>
The Parks–McClellan Algorithm may be restated as the following steps:<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

<ol><li>Make an initial guess of the L+2 extremal frequencies.</li>
<li>Compute δ using the equation given.</li>
<li>Using Lagrange Interpolation, we compute the dense set of samples of A(ω) over the passband and stopband.</li>
<li>Determine the new L+2 largest extrema.</li>
<li>If the alternation theorem is not satisfied, then we go back to (2) and iterate until the alternation theorem is satisfied.</li>
<li>If the alternation theorem is satisfied, then we compute h(n) and we are done.</li></ol>
To gain a basic understanding of the Parks–McClellan Algorithm mentioned above, we can rewrite the algorithm above in a simpler form as:

<ol><li>Guess the positions of the extrema are evenly spaced in the pass and stop band.</li>
<li>Perform polynomial interpolation and re-estimate positions of the local extrema.</li>
<li>Move extrema to new positions and iterate until the extrema stop shifting.</li></ol>
<h2 id="explanation">Explanation</h2>
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.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h2 id="additional-notes">Additional notes</h2>
Before applying the Chebyshev approximation, a set of steps were necessary:

<ol><li>Define the set of basis function for the approximation, and</li>
<li>Exploit the fact that the pass and stop bands of bandpass filters would always be separated by transition regions.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a></li></ol>
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 Parks-McClellan algorithm, two difficulties have to be overcome:

<ol><li>Defining a flexible exchange strategy, and</li>
<li>Implementing a robust interpolation method.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a></li></ol>
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:

<ol><li>Allocating the extremal frequencies between the pass and stop bands, and</li>
<li>Enabling movement of the extremals between the bands as the program iterated.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a></li></ol>
At initialization, the number of extremals in the pass and stop band 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.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> The extrema must occur at the pass and stop band edges and at either ω=0 or ω=π or both. 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.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> 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.

<h2 id="additional-references">Additional references</h2>
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:

<ol><li><a href="https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1083419&isnumber=23416">Chebyshev Approximation for Nonrecursive Digital Filters with Linear Phase</a></li>
<li><a href="http://vise.www.ecn.purdue.edu/VISE/ee438L/matlab/help/pdf/firpm.pdf">Short Help on Parks–McClellan Design of FIR Low Pass Filters Using MATLAB</a></li>
<li><a href="http://www.bores.com/courses/intro/filters/4_equi.htm">Intro to DSP</a></li>
<li><a href="http://www.mathworks.com/access/helpdesk/help/toolbox/signal/index.html?/access/helpdesk/help/toolbox/signal/firpm.html">The MathWorks MATLAB documentation</a></li>
<li><a href="https://web.archive.org/web/20120415164342/http://www.itee.uq.edu.au/~elec4600/elec4600_lectures/1perpage/lectremez.pdf">ELEC4600 Lecture Notes</a> (<a href="http://www.itee.uq.edu.au/~elec4600/elec4600_lectures/1perpage/lectremez.pdf">original link</a>, archived on 15 Apr 2012)</li>
<li><a href="https://github.com/janovetz/remez-exchange">C Code Implementation (LGPL License) – By Jake Janovetz</a></li>
<li>Iowa Hills Software. <a href="http://iowahills.com/Index.html">"Example C Code"</a>. Retrieved 3 May 2014.</li>
<li><a href="http://michaelgellis.tripod.com/dsp/pgm21.html">Revised and expanded algorithm</a> McClellan, Parks, & Rabiner, 1975; Fortran code.</li></ol>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">McClellan, J.H.; Parks, T.W. (2005). "A personal history of the Parks-Mc Clellan algorithm". IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM...22...82M. doi:10.1109/MSP.2005.1406492. S2CID 15400093. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">McClellan, J.H.; Parks, T.W. (2005). "A personal history of the Parks-Mc Clellan algorithm". IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM...22...82M. doi:10.1109/MSP.2005.1406492. S2CID 15400093. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">McClellan, J.H.; Parks, T.W. (2005). "A personal history of the Parks-Mc Clellan algorithm". IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM...22...82M. doi:10.1109/MSP.2005.1406492. S2CID 15400093. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">McClellan, J.H.; Parks, T.W. (2005). "A personal history of the Parks-Mc Clellan algorithm". IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM...22...82M. doi:10.1109/MSP.2005.1406492. S2CID 15400093. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">McClellan, J.H.; Parks, T.W. (2005). "A personal history of the Parks-Mc Clellan algorithm". IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM...22...82M. doi:10.1109/MSP.2005.1406492. S2CID 15400093. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">McClellan, J.H.; Parks, T.W. (2005). "A personal history of the Parks-Mc Clellan algorithm". IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM...22...82M. doi:10.1109/MSP.2005.1406492. S2CID 15400093. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">McClellan, J.H.; Parks, T.W. (2005). "A personal history of the Parks-Mc Clellan algorithm". IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM...22...82M. doi:10.1109/MSP.2005.1406492. S2CID 15400093. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">McClellan, J.H.; Parks, T.W. (2005). "A personal history of the Parks-Mc Clellan algorithm". IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM...22...82M. doi:10.1109/MSP.2005.1406492. S2CID 15400093. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">McClellan, J.H.; Parks, T.W. (2005). "A personal history of the Parks-Mc Clellan algorithm". IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM...22...82M. doi:10.1109/MSP.2005.1406492. S2CID 15400093. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">McClellan, J.H.; Parks, T.W. (2005). "A personal history of the Parks-Mc Clellan algorithm". IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM...22...82M. doi:10.1109/MSP.2005.1406492. S2CID 15400093. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Jones, Douglas (2007), Parks–McClellan FIR Filter Design, retrieved 2009-03-29 <a href="http://cnx.org/content/m12799/latest/" target="_blank">http://cnx.org/content/m12799/latest/</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Lovell, Brian (2003), Parks–McClellan Method (PDF), retrieved 2009-03-30 <a href="http://www.itee.uq.edu.au/~elec4600/elec4600_lectures/1perpage/lectremez.pdf" target="_blank">http://www.itee.uq.edu.au/~elec4600/elec4600_lectures/1perpage/lectremez.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">McClellan, J.H.; Parks, T.W. (2005). "A personal history of the Parks-Mc Clellan algorithm". IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM...22...82M. doi:10.1109/MSP.2005.1406492. S2CID 15400093. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">McClellan, J.H.; Parks, T.W. (2005). "A personal history of the Parks-Mc Clellan algorithm". IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM...22...82M. doi:10.1109/MSP.2005.1406492. S2CID 15400093. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">McClellan, J.H.; Parks, T.W. (2005). "A personal history of the Parks-Mc Clellan algorithm". IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM...22...82M. doi:10.1109/MSP.2005.1406492. S2CID 15400093. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Lovell, Brian (2003), Parks–McClellan Method (PDF), retrieved 2009-03-30 <a href="http://www.itee.uq.edu.au/~elec4600/elec4600_lectures/1perpage/lectremez.pdf" target="_blank">http://www.itee.uq.edu.au/~elec4600/elec4600_lectures/1perpage/lectremez.pdf</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Lovell, Brian (2003), Parks–McClellan Method (PDF), retrieved 2009-03-30 <a href="http://www.itee.uq.edu.au/~elec4600/elec4600_lectures/1perpage/lectremez.pdf" target="_blank">http://www.itee.uq.edu.au/~elec4600/elec4600_lectures/1perpage/lectremez.pdf</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
</ol>

Parks–McClellan filter design algorithm open-in-new

Parks–McClellan filter design algorithm