access icon free H-RADIX a new heuristic for a single constant multiplication

In the authors’ previous work on the multiplication by a constant, optimisations have been done on the RADIX-2 r heuristic based on Radix-2 r arithmetic, which is a fully predictable, and a sub-linear-runtime heuristic. This improved version of RADIX-2 r is called RADIX-2 r +. The latter makes the former more competitive in term of average number of additions compared with existing heuristics. In this study, the authors propose a new heuristic for multiplication by a constant, denoted H-RADIX, which combines RADIX-2 r + with a common sub-pattern (Lefevre's CSP) heuristic. It belongs to the category of common subexpression elimination algorithm. Results of the designed hybrid algorithm (H-RADIX), namely, the average number of additions and the smallest value that requires q adders, are compared with the standard canonical signed digit (CSD) representation, RADIX-2 r +, and Lefevre's CSP algorithms. The results highlight the efficiency of the designed heuristic, up to N-bits = 64. H-RADIX uses 37.496, 5.015 and 3.082% less additions than CSD, RADIX-2 r +, and Lefevre's CSP, respectively.

Inspec keywords: optimisation; digital arithmetic

Other keywords: efficiency 37.496 percent; subpattern heuristic; single constant multiplication; adder; efficiency 5.015 percent; optimisation; CSD representation; standard canonical signed digit representation; radix-2r arithmetic; Lefevre CSP algorithm; radix-2r heuristic; sublinear-runtime heuristic; H-RADIX; efficiency 3.082 percent; subexpression elimination algorithm; RADIX-2r+

Subjects: Optimisation techniques; Optimisation techniques; Digital arithmetic methods; Digital electronics

References

    1. 1)
      • 7. Bernstein, R.L.: ‘Multiplication by integer constant’, Softw. Pract. Exper., 1986, 16, (7), pp. 641652.
    2. 2)
      • 2. Avizienis, A.: ‘Signed-digit number representation for fast parallel arithmetic’, IRE Trans. Electron. Comput., 1961, EC-10, (3), pp. 389400.
    3. 3)
      • 16. Aksoy, L., Gunes, E.O., Costa, E., et al: ‘Effect of number representation on the achievable minimum number of operations in multiple constant multiplications’. IEEE Workshop on Signal Processing Systems, Shanghai, China, October 2007, pp. 424429.
    4. 4)
      • 6. Ding, J., Chen, J., Chang, C.H.: ‘A new paradigm of common subexpression elimination by unification of addition and subtraction’, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 2016, 35, (10), pp. 16051617.
    5. 5)
      • 14. Gustafsson, O.: ‘Lower bounds for constant multiplication problems’, IEEE Trans. Circuits Syst. II Express Brief, 2007, 54, (11), pp. 974978.
    6. 6)
      • 18. Oudjida, A.K.: ‘Binary arithmetic for finite-word-length linear controllers: MEMS applications’. PhD Thesis, Université de Franche-Compté (UFC), FEMTO-ST Institute, Besançon, France, 2014.
    7. 7)
      • 4. 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, 2015, 62, (4), pp. 372376.
    8. 8)
      • 17. Mahesh, R., Vinod, A.P.: ‘A new common subexpression elimination algorithm for realizing low-complexity higher order digital filters’, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 2008, 27, (2), pp. 217229.
    9. 9)
      • 8. Gustafsson, O., Dempster, A.G., Wanhammar, L.: ‘Extended results for minimum-adder constant integer multipliers’. Proc. of the IEEE Int. Symp. on Circuits and Systems, Arizona, U.S.A, May 2002, pp. 7376.
    10. 10)
      • 1. Khiter, B., Oudjida, A.K., Belhocine, M.: ‘On the optimization of the average number of additions in the RADIX-2r recoding heuristic’. 3rd Int. Conf. on Control, Engineering and Information Technology, Tlemcen, Algeria, May 2015, pp. 14.
    11. 11)
      • 9. Dempster, A., Macleod, M.: ‘Using signed-digit representations to design single integer multipliers using subexpression elimination’. Proc. of the IEEE Int. Symp. on Circuits and Systems, Vancouver, Canada, May 2004, pp. 1651168.
    12. 12)
      • 3. Oudjida, A.K., Chaillet, N.: ‘RADIX-2r arithmetic for multiplication by a constant’, IEEE Trans. Circuits Syst. II Express Brief, 2014, 61, (5), pp. 349353.
    13. 13)
      • 13. Choo, H., Muhammad, K., Roy, K.: ‘Complexity reduction of digital filters using shift inclusive differential coefficients’, IEEE Trans. Signal Process., 2004, 52, (6), pp. 17601772.
    14. 14)
      • 11. 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, 63, (2), pp. 233244.
    15. 15)
      • 5. Lefevre, V.: ‘Multiplication by an Integer Constant’, INRIA Research Report, 4192, 2001, pp. 1–20.
    16. 16)
      • 15. Potkonjak, M., Srivastava, M.B., Chandrakasan, A.P.: ‘Multiple constant multiplications: efficient and versatile framework and algorithms for exploring common subexpression elimination’, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 1996, 15, (2), pp. 151165.
    17. 17)
      • 12. Thong, J., Nicolici, N.: ‘An optimal and practical approach to single constant multiplication’, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 2011, 30, (9), pp. 13731386.
    18. 18)
      • 10. Voronenko, Y., Pschel, M.: ‘Multiplierless multiple constant multiplication’, ACM Trans. Algorithms, 2007, 3, (2), pp. 138.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds.2016.0238
Loading

Related content

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