A Systematic Algorithm for the Design of Multiplierless FIR Filters
J. Yli-Kaakinen and T. Saramäki, "A systematic algorithm for the design of multiplierless FIR filters," in Proc. IEEE Int. Symp. Circuits Syst., Sydney, Australia, May 6–9 2001, vol II, pp. 185–188.
Digital Object Identifier: 10.1109/ISCAS.2001.921038Full text available as: PDF (172 kB) – Requires Adobe Acrobat Reader or other PDF viewer.
©2001 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Abstract
A systematic algorithm is proposed for designing multiplierless finiteimpulse response (FIR) filters. This algorithm minimizes the number of adders required to implement the overall filter to meet the given amplitude criteria. The optimization is performed in two basic steps. First, a linear programming algorithm is used for determining a parameter space of the infinite-precision coefficients including the feasible space where the filter meets the given amplitude specifications. The second step involves finding the filter parameters in this space such that the resulting filter meets the given criteria with the simplest coefficient representation forms. The efficiency of the proposed algorithm is illustrated by means of several examples taken from the literature.BibTeX
@Article{ylikaaISCAS01,
author = {J. Yli-Kaakinen and T. Saram{\"a}ki},
title = {A systematic algorithm for
the design of multiplierless {FIR} filters},
booktitle = {Proc. IEEE Int. Symp. Circuits Syst.},
year = 2001,
pages = {185--188},
address = {Sydney, Australia},
month = {May} # "~6--9"
}
Citing Documents (57)
| 2002 | [1] | "Frequency-response masking based FIR filter design with power-of-two coefficients and optimum PWR,"e in Proc. IEEE Int. Conf. Electr. Circuits, Syst., Dubrovnik, Croatia, Sep. 15–18, 2002, pp. 1175–1178. |
| 2003 | [2] | "The design of low-cost fixed-point FIR digital filters using an improved local search," Proc. IEEE Pacific Rim Conf. Commun., Computers and Signal Process., Victoria, BC, USA, vol. 1, Aug. 2003 pp. 249–252. |
| [3] | "Frequency-response masking based FIR filter design with power-of-two coefficients and suboptimum PWR," Journal of Circuits, Systems, and Computers, vol. 12, no. 5, pp. 591–599, Oct. 2003. | |
| [4] | "Low-voltage micropower asynchronous multiplier for a multiplierless FIR filter," in Proc. IEEE Int. Symp. Circuits Syst., Bangkok, Thailand, May 25–28, 2003, pp. 381–384. | |
| [5] | "A hybrid CSA tree for merged arithmetic architecture of FIR filter," in Proc. 3th IEEE/EURASIP Int. Symp. on Image and Signal Processing and Analysis (ISPA-2003), Rome, Italy, Sep. 18–20, 2003, pp. 449–453. | |
| 2004 | [6] | "Синтез цифровых фильтров для высокоскоростных систем на кристалле," Цифровая Обработка Сигналов, no. 2, pp. 14–23, Apr. 2004. |
| [7] | "Design of multiplierless linear phase FIR filters with minimum number of power-of-two terms coefficients," in Proc. Electronics 2004, Sozopol, Bulgaria, Sep. 22–24, 2004, pp. 168–173. | |
| [8] | "Local search method for FIR filter coefficients synthesis," in Proc. 2nd IEEE Int. Workshop on Electronic Design, Test, and Applications (DELTA-2004), Perth, Australia, Jan. 28–30, 2004, pp. 255–260. | |
| [9] | "One simple method for design of multiplierless FIR filters," Innovations Through Information Technology, ed. Mehdi Khosrow-Pour, IGPPress, 2004, pp. 593–594. | |
| 2005 | [10] | "Design of digital filters for low power applications using integer quadratic programming," Integrated Circuit and System Design, Springer Berlin / Heidelber, 2005, pp. 137–145. |
| [11] | "Design and implementation of a low power FIR filter bank," Journal of The Institution of Engineers, Singapore vol. 45, no. 5, pp. 77–87, 2005. | |
| [12] | "Hardware-efficient FIR filters with reduced adder step," Electronics Letters, vol. 41, no. 22, pp. 1211–1213, Oct. 2005. | |
| [13] | "Variation of initial parameters of weighted Chebyshev approximation in multiplierless FIR filter design," in Proc. Int. Conf. Digital Signal Processing and its Applications (DSPA 2005), Moscow, Russia, Mar. 16–18, 2005, pp. 56–59. | |
| [14] | "Power-aware scheduling for hard real-time embedded systems using voltage-scaling enabled architectures," in 15th Int. Workshop on Power and Timing Optimization and Simulation, Leuven, Belgium, Sep. 21–23, 2005, pp. 127–136. | |
| [15] | "Design of an efficient multiplier-less architecture for multi-dimensional convolution," in Proc. 10th Asia-Pacific Conf. Advances in Comput. Syst. Arch., Singapore, 2005, pp. 65–78. | |
| [16] | "One simple method for design of multiplierless FIR filters," J. of Appl. Research and Technol., vol. 3, no. 2, pp. 125–138, Aug. 2005. | |
| 2006 | [17] | "Design of FIR filters with discrete coefficients via sphere relaxation," in Proc. Int. Symp. Circuits Syst., Island of Kos, Greece, May 21–24, 2005, pp. 2509–2512. |
| [18] | "A new integrated approach to the design of low-complexity FIR filters," in Proc. Int. Symp. Circuits Syst., Island of Kos, Greece, May 21–24, 2005, pp. 601–604. | |
| [19] | "The design of multiplierless FIR filters with a minimum adder step and reduced hardware complexity," in Proc. Int. Symp. Circuits Syst., Island of Kos, Greece, May 21–24, 2005, pp. 605–608. | |
| [20] | "A high performance architecture for color image enhancement using a machine learning approach," Int. Journal of Computational Intelligence Research vol. 2, no. 1, pp. 40–47, 2006. | |
| [21] | "Design methods of FIR filters with signed power of two coefficients using a new linear programming relaxation with triangle inequalities," Int. J. of Innovative Comput., Inform. Control vol. 2, no. 2, pp. 441–448, Apr. 2006. | |
| [22] | "Design of an efficient flexible architecture for color image enhancement," Advances in Computer Systems Architecture pringer Berlin / Heidelberg, 2006, pp. 323–336 | |
| [23] | "A hardware architecture for color image enhancement using a machine learning approach with adaptive parameterization," in Int. Joint Conf. on Neural Networks, Vancouver, BC, Canada, July 16–21, 2006, pp. 358–40. | |
| 2007 | [24] | "Design of efficient multiplierless FIR filters," IET Circuits, Devices, Syst., vol. 1, no. 2, pp. 175–180, Apr. 2007. |
| [25] | "Multiplier-less VLSI architecture for real-time computation of multi-dimensional convolution," Microprocessors & Microsystems archive, vol. 31, no. 1, pp. 25–37, 2007 | |
| [26] | "An efficient multiplier-less architecture for 2-D convolution with quadrant symmetric kernels," The VLSI Journal Integration, vol. 40, no. 4, pp. 490–502, Jul. 2007 | |
| [27] | "Design of FIR filters with discrete coefficients via polynomial programming: Towards the global solution," in Proc. Int. Symp. Circuits Syst., New Orleans, LA, USA, May 27–30, 2007, pp. 2048–2051. | |
| [28] | "Design of an efficient architecture for enhancement of stream video captured in non-uniform lighting conditions," in Int. Symp. Signals, Circuits Syst., Jul. 13–14, 2007, pp. 1–4. | |
| [29] | "Design of low-complexity FIR filters based on signed-powers-of-two coefficients with reusable common subexpressions," IEEE Trans. Comput.-Aided Design of Integr. Circuits Syst., vol. 26, no. 10, pp. 1898–1907, Jul. 2007 | |
| [30] | "A design methodology for performance-resource optimization of a generalized 2D convolution architecture with quadrant symmetric kernels," Advances in Computer Systems Architecture, Springer Berlin / Heidelber, 2007, pp. 220–234. | |
| [31] | "High-level power efficient synthesis of FIR based digital systems," PhD Thesis, Boğaziçi University, Istanbul, Turkey, 2007. | |
| 2008 | [32] | "An algorithm for the design of low-power hardware-efficient FIR filters," IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 55, no. 6, pp. 1536–1545, Jul. 2008. |
| [33] | "A tunable high-performance architecture for enhancement of stream video captured under non-uniform lighting conditions," Microprocessors & Microsystems archive, vol. 32, no. 7, pp. 386–393, 2008. | |
| [34] | "FIR Φίλτρα Σταθερών Συντελεστών (FIR filters of fixed coefficients)," MSc Thesis, Dept. Physics, Univ. Patras, Greece, 2008. | |
| [35] | "Efficient multiplierless channel filters for multi-standard SDR," in Proc. Int. Conf. Computer and Inform. Technol., Sydney, Australia, Jul 8–11, 2008, pp. 237–242. | |
| [36] | "Multiplierless multi-standard SDR channel filters," in Proc. IEEE 2008 Int. Workshop on Multimedia Signal Process.,, Cairns, Australia, Oct 8–11, 2008, pp. 815–819. | |
| 2009 | [37] | "Design of extrapolated impulse response FIR filters with residual compensation in subexpression space," IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 56, no. 12, pp. 1328–1338, Dec. 2009. |
| [38] | "Branch-and-bound algorithm for design of FIR filters with discrete coefficients," Computer Engineering and Applications, vol. 45, no. 13, pp. 72–74, 2009. | |
| [39] | "Digital Filters," Encyclopedia of Multimedia Technology and Networking, ed. Margherita Pagani, Information Science Reference, 2009, pp. 364–372. | |
| [40] | "Design and Applications of Digital Filters," Encyclopedia of Information Science and Technology, ed. Margherita Pagani, Information Science Reference, 2009, pp. 1016–1023. | |
| 2010 | [41] | "Optimization of linear phase FIR filters in dynamically expanding subexpression space," Circuits, Syst., Signal Process., vol. 29, no. 1, pp. 65–80, Feb. 2010. |
| 2011 | [42] | "Design of linear phase FIR filters with high probability of achieving minimum number of adders," IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 58, no. 1, Jan. 2011. |
| [43] | "Complexity-aware quantization and lightweight VLSI implementation of FIR filters," EURASIP J. Advances in Signal Process., vol. 2011, Article ID 357906, 14 pages, 2011. | |
| [44] | "Design of discrete-valued linear phase FIR filters in cascade form," IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 58, no. 7, pp. 1627–1637, July 2011. | |
| [45] | "Successive approximation FIR filter design," in Proc. IEEE Int. Conf. Circuits Syst., Rio de Janeiro, Brazil, May 15–18 2011, pp. 149–152. | |
| [46] | "Design of a low power and area efficient digital down converter and SINC filter in CMOS 90-nm technology," M.Sc. Thesis, Dept. Elect. Eng., Wright State University, USA, 2011. | |
| [47] | "Design of Discrete-Time Filters for Efficient Implementation," Ph.D. Thesis, Dept. of Elect. Eng. and Computer Sci., Massachusetts Institute of Technology, USA 2011. | |
| [48] | "A novel hybrid monotonic local search algorithm for FIR filter coefficients optimization," to appear in IEEE Trans. Circuits Syst. I, Reg. Papers. doi: 10.1109/TCSI.2011.2165409. | |
| [49] | "Low complexity low power non-recursive digital filters with unconstrained topology," in Proc. Euro. Conf. Circuit Theory and Design, Linköping, Sweden, Aug. 29–31 2011, pp. 865–868. | |
| [50] | "Algoritmos genéticos aplicados ao projeto de filtros com coeficientes em soma de potências de dois," Ph.D. Thesis, Faculdade de Engenharia, Universidade do Estado do Rio de Janeiro, Brazil 2011. | |
| 2012 | [51] | "Novel approach of designing multiplier-less finite impulse response filter using differential evolution algorithm," International Journal of Intelligent Systems and Applications, vol. 4, no. 4, pp. 54–62, Apr.doi: 10.5815/ijisa.2012.04.08. 2012. |
| [52] | "FIR filter synthesis based on interleaved processing of coefficient generation and multiplier-block synthesis," in IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 31, no. 8, pp. 1169–1179, Aug. 2012. doi: 10.1109/TCSI.2011.2165409. | |
| [53] | "An algorithm for jointly optimizing quantization and multiple constant multiplication," in ACM Trans. Design Autom. Electr. Syst., vol. 17, no. 4, Oct. 2012. doi: 10.1145/2348839.2348846. | |
| [54] | "A novel approach for coefficient quantization of low-pass finite impulse response filter using differential evolution algorithm," in Signal, Image and Video Processing, July 2012. doi: 10.1007/s11760-012-0359-4. | |
| [55] | "Role of mutation strategies of differential evolution algorithm in designing hardware efficient multiplier-less low-pass FIR filter," in J. Multimedia, vol. 7, no. 5, pp. 353–363, Oct. 2012. doi: 10.4304/jmm.7.5.353-363. | |
| [56] | "Differential evolution based design of multiplier-less FIR filter using canonical signed digit representation," in Proc. Int. Conf. Communications, Devices and Intelligent Systems, Kolkata, India, Dec. 28–29, 2012, pp. 425–428. doi: 10.1109/CODIS.2012.6422229. | |
| [57] | "Design space exploration for hardware-efficient FIR filter design," M.Sc. Thesis, Department of Electronics Engineering, Institute of Electronics, National Chiao Tung University, Taiwan, 2012. | |
| 2013 | [58] | "SIREN: A depth-first search algorithm for the filter design optimization problem," in 23rd ACM Int. Conf. Great Lakes Symposium on VLSI (GLSVLSI 2013), Paris, France, May 2–3, 2013, pp. 179–184. doi: 10.1145/2483028.2483087. |
| [59] | "Single-stage and cascade design of high order multiplierless linear phase FIR filters using genetic algorithm," IEEE Trans. Circuits Syst. I, vol. 60, no. 11, pp. 2987–2997, Nov. 2013. doi: 10.1109/TCSI.2013.2256211. | |
| [60] | "Design of 6 tap FIR filter using VLSI for low power MAC," in Int. Conf. Emerging Trends in Engineering and Techno - Sciences, Coimbatore, India, Dec. 22, 2013, pp. 48–52. | |
| [61] | "Canonic signed digit based design of multiplier-less FIR filter using self-organizing random immigrants genetic algorithm," Int. J. Artificial Intelligence & Applications, vol. 4, no. 4, pp. 21–34, July 2013. doi: 10.5121/ijaia.2013.4403. | |
| 2014 | [62] | "Designing hardware-efficient fixed-point FIR filters in an expanding subexpression space," IEEE Trans. Circuits Syst. I, vol. 61, no. 1, pp. 202–212,. 2014. doi: 10.1109/TCSI.2013.2268551. |
| [63] | "Novel design strategy of multiplier-less low-pass finite impulse response filter using selforganizing random immigrants genetic algorithm," Signal, Image and Video Processing, vol. 8, no. 3, pp. 507–522, Mar. 2014. doi: 10.1007/s11760-013-0494-6. | |
| [64] | "Supremacy of differential evolution algorithm in designing multiplier-less low-pass FIR filter," Int. J. Electrical, Electronic Science and Engineering, vol. 8, no. 2, pp. 120–129, 2014. url: http://waset.org/publication/Supremacy-of-Differential-Evolution-Algorithm-in-Designing-Multiplier-Less-Low-Pass-FIR-Filter/9997723. | |
| [65] | "FIR filter design based on successive approximation of vectors," IEEE Trans. Signal Processing, vol. 62, no. 15, pp. 3833–3848, July 2014. doi: 10.1109/TSP.2014.2324992. | |
| [66] | "A polynomial-time algorithm for the design of multiplierless linear-phase FIR filters with low hardware cost," in Proc. Int. Symp. Circuits Syst., Melbourne, Australia , Jun 1–5, 2013, pp. 970–973. doi: 10.1109/ISCAS.2014.6865299. | |
| [67] | "Bit-level multiplierless FIR filter optimization incorporating sparse filter technique," IEEE Trans. Circuits Syst. I, vol. 61, no. 11, pp. 3206–3215, 2014. doi: 10.1109/TCSI.2014.2327287. | |
| [68] | "Novel design strategy of multiplier-less low-pass finite impulse response filter using selforganizing random immigrants genetic algorithm," Signal, Image and Video Processing, vol. 8, no. 3, pp. 507–522, Mar. 2014. doi: 10.1007/s11760-013-0494-6. | |
| [69] | "A novel approach for coefficient quantization of low-pass finite impulse response filter using differential evolution algorithm," Signal, Image and Video Processing, vol. 8, no. 7, pp. 1307–1321, Oct. 2014.doi: 10.1007/s11760-012-0359-4. | |
| [70] | "Power optimization methodologies for digital FIR decimation filters," Ph.D. Thesis, University of Freiburg, Freiburg im Breisgau, Germany, 2014. | |
| 2015 | [71] | "Variants of genetic algorithm for efficient design of multiplier-less finite impulse response digital Filter," in Encyclopedia of Information Science and Technology, Ed. M. Khosrow-Pour, pp. 1304–1313, 2014, IGI Global. doi: 10.4018/978-1-4666-5888-2.ch124. |
| [72] | "Design of hardware efficient FIR filter: A review of the state-of-the-art approaches," Int. J. Engineering Science and Technology, 2015. doi: 10.1016/j.jestch.2015.06.006. | |
| [73] | "Design optimisation of powers-of-two FIR filter using self-organising random immigrants GA," Signal, Image and Video Processing, vol. 102, no. 1, Mar. 2015. doi: 10.1080/00207217.2014.938311. | |
| [74] | "Design optimisation of powers-of-two FIR filter using self-organising random immigrants GA," Signal, Image and Video Processing, vol. 63, no. 1, pp. 142–154, Jan. 2015. doi: 10.1109/TSP.2014.2366713. |