Silviu-Ioan Filip
Skip Abstract Section
Abstract
With a long history dating back to the beginning of the 1970s, the Parks-McClellan algorithm is probably the most well known approach for designing finite impulse response filters. Despite being a standard routine in many signal processing packages, it is possible to find practical design specifications where existing codes fail to work. Our goal is twofold. We first examine and present solutions for the practical difficulties related to weighted minimax polynomial approximation problems on multi-interval domains (i.e., the general setting under which the Parks-McClellan algorithm operates). Using these ideas, we then describe a robust implementation of this algorithm. It routinely outperforms existing minimax filter design routines.
- W. A. Abu-Al-Saud and G. L. Stüber. 2004. Efficient wideband channelizer for software radio systems using modulated PR filterbanks. IEEE Transactions on Signal Processing, 52, 10, 2807--2820. Google Scholar
Digital Library
- J. W. Adams and A. N. Wilson. 1985. On the fast design of high-order FIR digital filters. IEEE Transactions on Circuits and Systems 32, 9, 958--960.Google ScholarCross Ref
- M. Ahsan and T. Saramäki. 2012. Two Novel Implementations of the Remez Multiple Exchange Algorithm for Optimum FIR Filter Design. Retrieved July 16, 2016, from http://www.intechopen.com/download/pdf/39374Google Scholar
- E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen. 1999. LAPACK Users' Guide. Vol. 9. SIAM. Google ScholarDigital Library
- A. Antoniou. 1982. Accelerated procedure for the design of equiripple nonrecursive digital filters. IEE Proceedings G: Electronic Circuits and Systems 129, 1, 1--10.Google ScholarCross Ref
- A. Antoniou. 1983. New improved method for the design of weighted-Chebyshev, nonrecursive, digital filters. IEEE Transactions on Circuits and Systems 30, 10, 740--750.Google ScholarCross Ref
- A. Antoniou. 2005. Digital Signal Processing: Signals, Systems, and Filters. McGraw-Hill Education.Google Scholar
- J.-P. Berrut and L. N. Trefethen. 2004. Barycentric Lagrange interpolation. SIAM Review 46, 3, 501--517.Google ScholarDigital Library
- F. Bonzanigo. 1982. Some improvements to the design programs for equiripple FIR filters. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'82), Vol. 7. 274--277.Google ScholarCross Ref
- L. P. Bos, J.-P. Calvi, N. Levenberg, A. Sommariva, and M. Vianello. 2011. Geometric weakly admissible meshes, discrete least squares approximations and approximate Fekete points. Mathematics of Computation 80, 275, 1623--1638.Google Scholar
- L. P. Bos and N. Levenberg. 2008. On the calculation of approximate Fekete points: The univariate case. Electronic Transactions on Numerical Analysis 30, 377--397.Google Scholar
- J. P. Boyd. 2006. Computing the zeros, maxima and inflection points of Chebyshev, Legendre and Fourier series: Solving transcendental equations by spectral interpolation and polynomial rootfinding. Journal of Engineering Mathematics 56, 3, 203--219.Google ScholarCross Ref
- J. P. Boyd. 2013. Finding the zeros of a univariate equation: Proxy rootfinders, Chebyshev interpolation, and the companion matrix. SIAM Review 55, 2, 375--396.Google ScholarDigital Library
- J. P. Boyd and D. H. Gally. 2007. Numerical experiments on the accuracy of the Chebyshev-Frobenius companion matrix method for finding the zeros of a truncated series of Chebyshev polynomials. Journal of Computational and Applied Mathematics 205, 1, 281--295. Google ScholarDigital Library
- J.-P. Calvi and N. Levenberg. 2008. Uniform approximation by discrete least squares polynomials. Journal of Approximation Theory 152, 1, 82--100. Google ScholarDigital Library
- A. Çivril and M. Magdon-Ismail. 2009. On selecting a maximum volume sub-matrix of a matrix and related problems. Theoretical Computer Science 410, 47--49, 4801--4811. Google ScholarDigital Library
- E. W. Cheney. 1982. Introduction to Approximation Theory. AMS Chelsea Publications.Google Scholar
- L. Dagum and R. Menon. 1998. OpenMP: An industry standard API for shared-memory programming. IEEE Computational Science Engineering 5, 1, 46--55. Google ScholarDigital Library
- D. Day and L. Romero. 2005. Roots of polynomials expressed in terms of orthogonal polynomials. SIAM Journal on Numerical Analysis 43, 5, 1969--1987. Google ScholarDigital Library
- F. De Dinechin, M. Istoan, and A. Massouri. 2014. Sum-of-product architectures computing just right. In Proceedings of the 2014 IEEE 25th International Conference on Application-Specific Systems, Architectures, and Processors (ASAP'14). 41--47.Google Scholar
- T. A. Driscoll, N. Hale, and L. N. Trefethen. 2014. Chebfun Guide. Pafnuty Publications, Oxford, UK.Google Scholar
- A. Dutt, M. Gu, and V. Rokhlin. 1996. Fast algorithms for polynomial interpolation, integration, and differentiation. SIAM Journal on Numerical Analysis 33, 5, 1689--1711. Google ScholarDigital Library
- S. Ebert and U. Heute. 1983. Accelerated design of linear or minimum phase FIR filters with a Chebyshev magnitude response. IEE Proceedings G: Electronic Circuits and Systems 130, 6, 267--270.Google ScholarCross Ref
- M. Embree and L. N. Trefethen. 1999. Green's functions for multiply connected domains via conformal mapping. SIAM Review 41, 4, 745--761. Google ScholarDigital Library
- M. S. Floater and K. Hormann. 2007. Barycentric rational interpolation with no poles and high rates of approximation. Numerische Mathematik 107, 2, 315--331. Google ScholarDigital Library
- L. Fousse, G. Hanrot, V. Lefèvre, P. Pélissier, and P. Zimmermann. 2007. MPFR: A multiple-precision binary floating-point library with correct rounding. ACM Transactions on Mathematical Software 33, 2, 13. Google ScholarDigital Library
- G. Guennebaud and B. Jacob. 2010. Eigen v3. Available at http://eigen.tuxfamily.org.Google Scholar
- N. J. Higham. 2004. The numerical stability of barycentric Lagrange interpolation. IMA Journal of Numerical Analysis 24, 547--556.Google ScholarCross Ref
- L. J. Karam and J. H. McClellan. 1995. Complex Chebyshev approximation for FIR filter design. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 42, 3, 207--216.Google ScholarCross Ref
- L. J. Karam and J. H. McClellan. 1996. Design of optimal digital FIR filters with arbitrary magnitude and phase responses. In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS'96), Vol. 2. 385--388.Google Scholar
- D. M. Kodek. 2012. LLL algorithm and the optimal finite wordlength FIR design. IEEE Transactions on Signal Processing 60, 3, 1493--1498. Google ScholarDigital Library
- E. Levin and E. B. Saff. 2006. Potential theoretic tools in polynomial and rational approximation. In Harmonic Analysis and Rational Approximation. Lecture Notes in Control and Information Science, Vol. 327. Springer, 71--94.Google Scholar
- W. F. Mascarenhas. 2014. The stability of barycentric interpolation at the Chebyshev points of the second kind. Numerische Mathematik 128, 2, 265--300. Google ScholarDigital Library
- W. F. Mascarenhas and A. Camargo. 2014. On the backward stability of the second barycentric formula for interpolation. Dolomites Research Notes on Approximation 7, 1--12.Google Scholar
- J. H. McClellan and T. W. Parks. 2005. A personal history of the Parks-McClellan algorithm. IEEE Signal Processing Magazine 22, 2, 82--86.Google ScholarCross Ref
- J. H. McClellan, T. W. Parks, and L. Rabiner. 1973. A computer program for designing optimum FIR linear phase digital filters. IEEE Transactions on Audio and Electroacoustics 21, 6, 506--526.Google ScholarCross Ref
- J. M. Muller, N. Brisebarre, F. de Dinechin, C. P. Jeannerod, V. Lefèvre, G. Melquiond, N. Revol, D. Stehlé, and S. Torres. 2009. Handbook of Floating-Point Arithmetic. Birkhäuser, Boston, MA. Google ScholarDigital Library
- A. V. Oppenheim and R. W. Schafer. 2010. Discrete-Time Signal Processing. Prentice Hall. Google ScholarDigital Library
- R. Pachón and L. N. Trefethen. 2009. Barycentric-Remez algorithms for best polynomial approximation in the Chebfun system. BIT Numerical Mathematics 49, 4, 721--741.Google ScholarCross Ref
- T. W. Parks and J. H. McClellan. 1972. Chebyshev approximation for nonrecursive digital filters with linear phase. IEEE Transactions on Circuit Theory 19, 2 (March 1972), 189--194.Google ScholarCross Ref
- D. Pelloni and F. Bonzanigo. 1980. On the design of high-order linear phase FIR filters. Digital Signal Processing 1, 3--10.Google Scholar
- M. J. D. Powell. 1981. Approximation Theory and Methods. Cambridge University Press, Cambridge, MA.Google Scholar
- W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. 2007. Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press, Cambridge, MA. Google ScholarDigital Library
- E. Z. Psarakis and G. V. Moustakides. 2003. A robust initialization scheme for the Remez exchange algorithm. IEEE Signal Processing Letters 10, 1, 1--3.Google ScholarCross Ref
- L. Rabiner, J. Kaiser, and R. W. Schafer. 1974. Some considerations in the design of multiband finite-impulse-response digital filters. IEEE Transactions on Acoustics, Speech, and Signal Processing 22, 6, 462--472.Google ScholarCross Ref
- H.-J. Rack and M. Reimer. 1982. The numerical stability of evaluation schemes for polynomials based on the Lagrange interpolation form. BIT Numerical Mathematics 22, 1, 101--107.Google ScholarCross Ref
- E. Remes. 1934. Sur le calcul effectif des polynômes d'approximation de tchebichef. Comptes Rendus Hebdomadaires Des séances De l'Académie Des Sciences 199, 337--340.Google Scholar
- H. Rutishauser. 1976. Vorlesungen Über Numerische Mathematik. Birkhäuser Basel, Stuttgard. English translation, 1990. Lectures on Numerical Mathematics, W. Gautschi (Ed.). Birkhäuser, Boston, MA.Google Scholar
- T. Saramäki. 1992. An efficient Remez-type algorithm for the design of optimum IIR filters with arbitrary partially constrained specifications. In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS'92), Vol. 5. 2577--2580.Google ScholarCross Ref
- T. Saramäki. 1994. Generalizations of classical recursive digital filters and their design with the aid of a Remez-type algorithm. In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS'94), Vol. 2. 549--552.Google ScholarCross Ref
- I. W. Selesnick. 1997. New exchange rules for IIR filter design. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'97), Vol. 3. 2209--2212. Google ScholarDigital Library
- I. W. Selesnick, M. Lang, and C. S. Burrus. 1994. Magnitude squared design of recursive filters with the Chebyshev norm using a constrained rational Remez algorithm. In Proceedings of the 6th IEEE Digital Signal Processing Workshop. 23--26.Google Scholar
- J. Shen, G. Strang, and A. J. Wathen. 2001. The potential theory of several intervals and its applications. Applied Mathematics and Optimization 44, 1, 67--85.Google ScholarDigital Library
- D. J. Shpak and A. Antoniou. 1990. A generalized Remez method for the design of FIR digital filters. IEEE Transactions on Circuits and Systems 37, 2, 161--174.Google ScholarCross Ref
- A. Sommariva and M. Vianello. 2009. Computing approximate Fekete points by QR factorizations of Vandermonde matrices. Computers and Mathematics with Applications 57, 8, 1324--1336. Google ScholarDigital Library
- A. Sommariva and M. Vianello. 2010. Approximate Fekete points for weighted polynomial interpolation. Electronic Transactions on Numerical Analysis 37, 1--22.Google Scholar
- G. Strang. 1999. The discrete cosine transform. SIAM Review 41, 1, 135--147. Google ScholarDigital Library
- L. N. Trefethen. 2013. Approximation Theory and Approximation Practice. SIAM. Google ScholarDigital Library
- L. Veidinger. 1960. On the numerical determination of the best approximation in the Chebyshev sense. Numerische Mathematik 2, 1, 99--105. Google ScholarDigital Library
- M. Webb, L. N. Trefethen, and P. Gonnet. 2012. Stability of barycentric interpolation formulas for extrapolation. SIAM Journal on Scientific Computing 34, 6, A3009--A3015.Google ScholarCross Ref
- P. Zahradnik and M. Vlcek. 2008. Robust analytical design of equiripple comb FIR filters. In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS'08). 1128--1131.Google Scholar
Index Terms
- A Robust and Scalable Implementation of the Parks-McClellan Algorithm for Designing FIR Filters
Recommendations
Design of two-channel linear phase IIR PRQMF banks based on the approximation of FIR filters
ASILOMAR '95: Proceedings of the 29th Asilomar Conference on Signals, Systems and Computers (2-Volume Set)This paper presents an algorithm to design two-channel linear phase IIR PRQMF (LP IIR PRQMF) banks. This algorithm is based on the approximation of the FIR by IIR digital filters matching a finite portion of the impulse response and the autocorrelation ...
On arbitrary-length, M-channel linear-phase FIR filter banks
ASILOMAR '95: Proceedings of the 29th Asilomar Conference on Signals, Systems and Computers (2-Volume Set)Tree-structured IIR/FIR uniform-band and octave-band filter banks with very low-complexity analysis or synthesis filters
This paper introduces new tree-structured uniform-band and octave-band digital filter banks (FBs). These FBs make use of half-band IIR filters in the analysis FBs and FIR filters in the synthesis FBs. The resulting FBs are asymmetric in the sense that ...
Comments