© The Institution of Engineering and Technology
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.
References
-
-
1)
-
7. Bernstein, R.L.: ‘Multiplication by integer constant’, Softw. Pract. Exper., 1986, 16, (7), pp. 641–652.
-
2)
-
2. Avizienis, A.: ‘Signed-digit number representation for fast parallel arithmetic’, IRE Trans. Electron. Comput., 1961, EC-10, (3), pp. 389–400.
-
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. 424–429.
-
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. 1605–1617.
-
5)
-
14. Gustafsson, O.: ‘Lower bounds for constant multiplication problems’, IEEE Trans. Circuits Syst. II Express Brief, 2007, 54, (11), pp. 974–978.
-
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)
-
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. 372–376.
-
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. 217–229.
-
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. 73–76.
-
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. 1–4.
-
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. 165–1168.
-
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. 349–353.
-
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. 1760–1772.
-
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. 233–244.
-
15)
-
5. Lefevre, V.: ‘Multiplication by an Integer Constant’, , 2001, pp. 1–20.
-
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. 151–165.
-
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. 1373–1386.
-
18)
-
10. Voronenko, Y., Pschel, M.: ‘Multiplierless multiple constant multiplication’, ACM Trans. Algorithms, 2007, 3, (2), pp. 1–38.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds.2016.0238
Related content
content/journals/10.1049/iet-cds.2016.0238
pub_keyword,iet_inspecKeyword,pub_concept
6
6