×
Filip, Silviu-Ioan

A robust and scalable implementation of the Parks-McClellan algorithm for designing FIR filters. (English) Zbl 1371.65013

ACM Trans. Math. Softw. 43, No. 1, Article No. 7, 24 p. (2016).

Cited in 2 Documents

MSC:

65C60 Computational problems in statistics (MSC2010)
65D05 Numerical interpolation
41A10 Approximation by polynomials
41A50 Best approximation, Chebyshev systems
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
62M20 Inference from stochastic processes and prediction

Keywords:

barycentric interpolation; Chebyshev approximation; Lebesgue constant; colleague matrix; finite impulse response filters; signal processing; weighted minimax polynomial approximation; algorithm

Software:

firpm; Chebfun; MPFR; Eigen; LAPACK
Cite Review PDF
Full Text: DOI HAL

References:

[1] 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. · doi:10.1109/TSP.2004.834242
[2] 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. · doi:10.1109/TCS.1985.1085807
[3] 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/39374
[4] 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. · Zbl 0934.65030 · doi:10.1137/1.9780898719604
[5] A. Antoniou. 1982. Accelerated procedure for the design of equiripple nonrecursive digital filters. IEE Proceedings G: Electronic Circuits and Systems 129, 1, 1–10. · doi:10.1049/ip-g-1.1982.0001
[6] 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. · Zbl 0517.94007 · doi:10.1109/TCS.1983.1085296
[7] A. Antoniou. 2005. Digital Signal Processing: Signals, Systems, and Filters. McGraw-Hill Education.
[8] J.-P. Berrut and L. N. Trefethen. 2004. Barycentric Lagrange interpolation. SIAM Review 46, 3, 501–517. · Zbl 1061.65006 · doi:10.1137/S0036144502417715
[9] 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. · doi:10.1109/ICASSP.1982.1171739
[10] 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. · Zbl 1228.41002 · doi:10.1090/S0025-5718-2011-02442-7
[11] 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. · Zbl 1176.41001
[12] 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. · Zbl 1110.65037 · doi:10.1007/s10665-006-9087-5
[13] 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. · Zbl 1270.65023 · doi:10.1137/110838297
[14] 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. · Zbl 1118.65032 · doi:10.1016/j.cam.2006.05.006
[15] J.-P. Calvi and N. Levenberg. 2008. Uniform approximation by discrete least squares polynomials. Journal of Approximation Theory 152, 1, 82–100. · Zbl 1145.41001 · doi:10.1016/j.jat.2007.05.005
[16] 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. · Zbl 1181.15002 · doi:10.1016/j.tcs.2009.06.018
[17] E. W. Cheney. 1982. Introduction to Approximation Theory. AMS Chelsea Publications. · Zbl 0535.41001
[18] L. Dagum and R. Menon. 1998. OpenMP: An industry standard API for shared-memory programming. IEEE Computational Science Engineering 5, 1, 46–55. · doi:10.1109/99.660313
[19] D. Day and L. Romero. 2005. Roots of polynomials expressed in terms of orthogonal polynomials. SIAM Journal on Numerical Analysis 43, 5, 1969–1987. · Zbl 1101.65048 · doi:10.1137/040609847
[20] 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. · doi:10.1109/ASAP.2014.6868629
[21] T. A. Driscoll, N. Hale, and L. N. Trefethen. 2014. Chebfun Guide. Pafnuty Publications, Oxford, UK.
[22] 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. · Zbl 0862.65005 · doi:10.1137/0733082
[23] 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. · doi:10.1049/ip-g-1.1983.0050
[24] M. Embree and L. N. Trefethen. 1999. Green’s functions for multiply connected domains via conformal mapping. SIAM Review 41, 4, 745–761. · Zbl 0938.30003 · doi:10.1137/S0036144598349277
[25] M. S. Floater and K. Hormann. 2007. Barycentric rational interpolation with no poles and high rates of approximation. Numerische Mathematik 107, 2, 315–331. · Zbl 1221.41002 · doi:10.1007/s00211-007-0093-y
[26] 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. · Zbl 1365.65302
[27] G. Guennebaud and B. Jacob. 2010. Eigen v3. Available at http://eigen.tuxfamily.org.
[28] N. J. Higham. 2004. The numerical stability of barycentric Lagrange interpolation. IMA Journal of Numerical Analysis 24, 547–556. · Zbl 1067.65016 · doi:10.1093/imanum/24.4.547
[29] 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. · Zbl 0835.93029 · doi:10.1109/82.372870
[30] 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. · doi:10.1109/ISCAS.1996.541727
[31] D. M. Kodek. 2012. LLL algorithm and the optimal finite wordlength FIR design. IEEE Transactions on Signal Processing 60, 3, 1493–1498. · Zbl 1393.94304 · doi:10.1109/TSP.2011.2177974
[32] 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. · Zbl 1146.41001 · doi:10.1007/11601609_5
[33] W. F. Mascarenhas. 2014. The stability of barycentric interpolation at the Chebyshev points of the second kind. Numerische Mathematik 128, 2, 265–300. · Zbl 1305.65090 · doi:10.1007/s00211-014-0612-6
[34] 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.
[35] J. H. McClellan and T. W. Parks. 2005. A personal history of the Parks-McClellan algorithm. IEEE Signal Processing Magazine 22, 2, 82–86. · doi:10.1109/MSP.2005.1406492
[36] 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. · doi:10.1109/TAU.1973.1162525
[37] 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. · Zbl 1197.65001
[38] A. V. Oppenheim and R. W. Schafer. 2010. Discrete-Time Signal Processing. Prentice Hall. · Zbl 0676.42001
[39] 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. · Zbl 1179.65012 · doi:10.1007/s10543-009-0240-1
[40] 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. · doi:10.1109/TCT.1972.1083419
[41] D. Pelloni and F. Bonzanigo. 1980. On the design of high-order linear phase FIR filters. Digital Signal Processing 1, 3–10.
[42] M. J. D. Powell. 1981. Approximation Theory and Methods. Cambridge University Press, Cambridge, MA. · Zbl 0453.41001
[43] 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. · Zbl 1132.65001
[44] 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. · doi:10.1109/LSP.2002.806701
[45] 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. · doi:10.1109/TASSP.1974.1162607
[46] 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. · Zbl 0477.65007 · doi:10.1007/BF01934399
[47] 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. · Zbl 0010.01702
[48] 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.
[49] 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. · doi:10.1109/ISCAS.1992.230459
[50] 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. · doi:10.1109/ISCAS.1994.409047
[51] 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. · doi:10.1109/ICASSP.1997.599489
[52] 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. · doi:10.1109/DSP.1994.379882
[53] 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. · Zbl 0983.41006 · doi:10.1007/s00245-001-0011-0
[54] 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. · doi:10.1109/31.45709
[55] 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. · Zbl 1186.65028 · doi:10.1016/j.camwa.2008.11.011
[56] A. Sommariva and M. Vianello. 2010. Approximate Fekete points for weighted polynomial interpolation. Electronic Transactions on Numerical Analysis 37, 1–22. · Zbl 1192.41002
[57] G. Strang. 1999. The discrete cosine transform. SIAM Review 41, 1, 135–147. · Zbl 0939.42021 · doi:10.1137/S0036144598336745
[58] L. N. Trefethen. 2013. Approximation Theory and Approximation Practice. SIAM. · Zbl 1264.41001
[59] L. Veidinger. 1960. On the numerical determination of the best approximation in the Chebyshev sense. Numerische Mathematik 2, 1, 99–105. · Zbl 0090.33702 · doi:10.1007/BF01386215
[60] 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. · Zbl 1261.65015 · doi:10.1137/110848797
[61] 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. · doi:10.1109/ISCAS.2008.4541621
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.