access icon free Design of high-speed, low-power, and area-efficient FIR filters

© The Institution of Engineering and Technology
Received 19/02/2017, Accepted 13/08/2017, Revised 01/07/2017, Published 23/08/2017

In a recent work, we have introduced a new multiple constant multiplication (MCM) algorithm, denoted as RADIX-2 r . The latter exhibits the best results in speed and power, comparatively with the most prominent algorithms. In this paper, the area aspect of RADIX-2 r is more specially investigated. RADIX-2 r is confronted to area efficient algorithms, notably to the cumulative benefit heuristic (Hcub) known for its lowest adder-cost. A number of benchmark FIR filters of growing complexity served for comparison. The results showed that RADIX-2 r is better than Hcub in area, especially for high order filters where the saving ranges from 1.50% up to 3.46%. This advantage is analytically proved and experimentally confirmed using a 65nm CMOS technology. Area efficiency is achieved along with important savings in speed and power, ranging from 6.37% up to 38.01% and from 9.30% up to 25.85%, respectively. When MCM blocks are implemented alone, the savings are higher: 10.18%, 47.24%, and 41.27% in area, speed, and power, respectively. Most importantly, we prove that MCM heuristics using similar addition pattern (A-operation with the same shift spans) as Hcub yield excessive bit-adder overhead in MCM problems of high complexity. As such, they are not competitive to RADIX-2 r in high order filters.

Inspec keywords: CMOS logic circuits; adders; digital arithmetic; FIR filters

Other keywords: complementary metal oxide semiconductor technology; FIR filter design; RADIX-2r; multiple constant multiplication algorithm; lowest adder cost; MCM algorithm

Subjects: Digital arithmetic methods; CMOS integrated circuits; Digital filters; Logic and switching circuits; Logic circuits; Digital filters

References

    1. 1)
      • 1. Thong, J., Nicolici, N.: ‘An optimal and practical approach to single constant multiplication’, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 2011, 30, (9), pp. 1373–1386.
    2. 2)
      • 13. Oudjida, A.K., Chaillet, N.: ‘Radix-2r arithmetic for multiplication by a constant’, IEEE Trans. Circuits Syst. II Exp. Brief, 2014, 61, (5), pp. 349–353.
    3. 3)
      • 14. Oudjida, A.K., Chaillet, N., Berrandjia, M.L.: ‘Radix-2r arithmetic for multiplication by a constant: further results and improvements’, IEEE Trans. Circuits Syst. II Exp. Brief, 2015, 62, (4), pp. 372–376.
    4. 4)
      • 35. Copyright © UMC Ver. B02: ‘UMC 65 nm Data Book’, December 2011.
    5. 5)
      • 24. Dimitrov, V.S., Eskritt, J., Imbert, L., et al: ‘The use of the multi-dimensional logarithmic number system in DSP applications’. Proc. Int. (ARITH) Conf. Computer Arithmetic, Vail, CO, USA, June 2001, pp. 247–254.
    6. 6)
      • 32. Faust, M., Chang, C.H.: ‘Optimization of structural adders in fixed coefficient transposed direct form FIR filters’. Proc. Int. IEEE (ISCAS) Conf. Circuits and Systems, Taiwan, May 2009, pp. 2185–2188.
    7. 7)
      • 21. Aksoy, L., Flores, P., Monteiro, J.: ‘Exact and approximate algorithms for the filter design optimization problem’, IEEE Trans. Signal Process., 2015, 63, (1), pp. 142–154.
    8. 8)
      • 8. Voronenko, Y., Püschel, M.: ‘Multiplierless multiple constant multiplication’, ACM Trans. Algorithms, 2007, 3, (2), pp. 1–38.
    9. 9)
      • 12. Thong, J., Nicolici, N.: ‘Combined optimal and heuristic approaches for multiple constant multiplication’. Proc. Int. Conf. Computer Design (ICCD), Amsterdam, Netherlands, October 2010, pp. 266–273.
    10. 10)
      • 5. Xu, F., Chang, C.H., Jong, C.C.: ‘Contention resolution algorithm for common subexpression elimination in digital filter design’, IEEE Trans. Circuits Syst. II Exp. Brief, 2005, 52, (10), pp. 695–700.
    11. 11)
      • 11. Gustafsson, O.: ‘A difference based adder graph heuristic for multiple constant multiplication problems’. Proc. Int. IEEE (ISCAS) Conf. Circuits and Systems, New Orleans, USA, May 2007, pp. 1097–1100.
    12. 12)
      • 7. Dempster, A.G., Macleod, M.D.: ‘Use of minimum-adder multiplier blocks in FIR digital filters’, IEEE Trans. Circuits Syst. II Analog Digit. Signal Process., 1995, 42, (9), pp. 569–577.
    13. 13)
      • 36. Liacha, A., Oudjida, A.K., Ferguene, F., et al: ‘A variable Radix-2r algorithm for single constant multiplication’. Proc. Int. IEEE (NEWCAS) Conf. New Circuits and Systems, Strasbourg, France, June 2017, pp. 1–4DOI: 10.1109/NEWCAS.2017.8010156.
    14. 14)
      • 30. Kumm, M., Zipf, P., Faust, M., et al: ‘Pipelined adder graph optimization for high speed multiple constant multiplication’. Proc. Int. IEEE (ISCAS) Conf. Circuits and Systems, Seoul, South Korea, May 2012, pp. 49–52.
    15. 15)
      • 17. Johansson, K., Gustafsson, O., DeBrunner, L.S., et al: ‘Minimum adder depth multiple constant multiplication algorithm for low power FIR filters’. Proc. Int. IEEE (ISCAS) Conf. Circuits and Systems, Rio de Janeiro, Brazil, May 2011, pp. 1439–1442.
    16. 16)
      • 10. Gustafsson, O.: ‘Lower bounds for constant multiplication problems’, IEEE Trans. Circuits Syst. II Exp. Brief, 2007, 54, (11), pp. 974–978.
    17. 17)
      • 18. Aksoy, L., Günes, E.O., Flores, P.: ‘Search algorithms for the multiple constant multiplications problem: exact and approximate’, Microprocess. Microsyst., 2010, 34, (5), pp. 151–162.
    18. 18)
      • 26. Johansson, K., Gustafsson, O., Wanhammar, L.: ‘A detailed complexity model for multiple constant multiplication and an algorithm to minimize the complexity’. Proc. IEEE European (ECCTD) Conf. Circuit Theory and Design, Cork, Ireland, September 2005, vol. 3, pp. 465–468.
    19. 19)
      • 31. Ye, W.B., Yu, Y.J.: ‘Bit-level multiplierless FIR filter optimization incorporating sparce filter technique’, IEEE Trans. Circuits Syst. I Reg. Papers, 2014, 61, (11), pp. 3206–3215.
    20. 20)
      • 20. Avizienis, A.: ‘Signed-digit number representation for fast parallel arithmetic’, IRE Trans. Electron. Comput., 1961, EC-10, (3), pp. 389–400.
    21. 21)
      • 29. Faust, M., Chang, C.H.: ‘Minimal logic depth adder tree optimization for multiple constant multiplication’. Proc. Int. IEEE (ISCAS) Conf. Circuits and Systems, Paris, France, June 2010, pp. 457–460.
    22. 22)
      • 15. Nanyang Technological University, Singapore: ‘FIRsuite Suite of constant coefficient FIR filters’, http://www.firsuite.net, November 2009.
    23. 23)
      • 33. Feng, F., Chen, J., Chang, C.H.: ‘Hypergraph based minimum arborescence algorithm for the optimization and reoptimization of multiple constant multiplications’, IEEE Trans. Circuits Syst. I, 2016, doi: 10.1109/TCSI.2015.2512742.
    24. 24)
      • 25. Aksoy, L., Costa, E., Flores, P., et al: ‘Optimization of area in digital FIR filters using gate-level metrics’. Proc. Int. (DAC) Conf. Design Automation, San Diego, CA, USA, June 2007, pp. 420–423.
    25. 25)
      • 16. Fraust, M., Gustafsson, O., Chip-Hong, C.: ‘Reconfigurable multiple constant multiplication using minimum adder depth’. Proc. IEEE ASILOMAR Conf. Signals, Systems, and Computers, CA, USA, November 2010, pp. 1293–1301.
    26. 26)
      • 9. Chang, C.H., Faust, M.: ‘On “a new common subexpression elimination algorithm for realizing low-complexity higher order digital filters”’, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 2010, 29, (5), pp. 844–848.
    27. 27)
      • 19. Oudjida, A.K., Berrandjia, M.L., Liacha, A.: ‘RADIX-2r MCM, ver. 2.0.2’. Available athttp://www.cdta.dz/products/mcm, June 2016.
    28. 28)
      • 23. Samueli, H.: ‘An improved search algorithm for the design of multiplierless FIR filters with powers-of-two coefficients’, IEEE Trans. Circuits Syst., 1989, 36, (7), pp. 1044–1047.
    29. 29)
      • 27. Lou, X., Yu, Y.J., Meher, P.K.: ‘New approach to the reduction of sign-extension overhead for efficient implementation of multiple constant multiplications’, IEEE Trans. Circuits Syst. I: Reg. Papers, 2015, 62, (11), pp. 2695–2705.
    30. 30)
      • 6. Martinez-Peiro, M., Boemo, E.I., Wanhammar, L.: ‘Design of high-speed multiplierless filters using a nonrecursive signed common subexpression algorithm’, IEEE Trans. Circuits Syst. II Analog Digit. Signal Process., 2002, 49, (3), pp. 196–203.
    31. 31)
      • 3. Oudjida, A.K., Liacha, A., Bakiri, M., et al: ‘Multiple constant multiplication algorithm for high speed and low power design’, IEEE Trans. Circuits Syst. II Exp. Brief., 2016, 63, (2), pp. 176–180.
    32. 32)
      • 28. Huang, R., Chang, C.H., Faust, M., et al: ‘Sign-extension avoidance and word-length optimization by positive-offset representation for FIR filter design’, IEEE Trans. Circuits Syst. II Exp. Brief, 2011, 58, (12), pp. 916–920.
    33. 33)
      • 4. Mahesh, R., Vinod, A.P.: ‘A new common subexpression elimination algorithm for realizing low-complexity higher order digital filters’, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 2008, 27, (2), pp. 217–229.
    34. 34)
      • 2. Aksoy, L., da Costa, E., Flores, P.: ‘Exact and approximate algorithms for the optimisation of area and delay in multiple constant multiplication’, IEEE Trans. Comput. -Aided Des. Integr. Circuits Syst., 2008, 27, (6), pp. 1013–1026.
    35. 35)
      • 22. Aksoy, L., Gunes, E., Flores, P.: ‘An exact breadth-first search algorithm for the multiple constant multiplications problem’. Proc. Int. 26th Edition of IEEE NORCHIP Conf., Tallinn, Estonia, November 2008, pp. 41–44.
    36. 36)
      • 34. Lou, X., Yu, Y.J., Meher, P.K.: ‘Fine-grained critical path analysis and optimization for area-time efficient realization of multiple constant multiplications’, IEEE Trans. Circuits Syst. I Reg. Papers, 2014, 62, (3), pp. 863–872.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds.2017.0058
Loading

Related content

content/journals/10.1049/iet-cds.2017.0058
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading