Title :
A new low-power recoding algorithm for multiplierless single/multiple constant multiplication
Author :
Oudjida, A.K. ; Berrandjia, M.L. ; Chaillet, N.
Author_Institution :
Centre de Dev. des Technol. Av., Microelectron. & Nanotechnol. Div., Algiers, Algeria
Abstract :
Optimizing the number of additions in constant coefficient multiplication is conjectured to be a NP-hard problem. In this paper, we report a new heuristic requiring an average of 29.10% and 10.61 % less additions than the standard canonical signed digit representation (CSD) and the double base number system (DBNS), respectively, for 64-bit coefficients. The maximum number of additions per coefficient is bounded by (N/4)+2, and the time-complexity of the recoding is linearly proportional to N, where N is the bit-size of the constant. These performances are achieved using a new redundant version of radix-28 recoding.
Keywords :
computational complexity; digital arithmetic; NP-hard problem; canonical signed digit representation; constant coefficient multiplication; double base number system; low-power recoding algorithm; multiplierless single/multiple constant multiplication; radix-28 recoding; time-complexity; word length 64 bit; Adders; Complexity theory; Computers; Equations; Optimization; Runtime; Double Base Number System (DBNS); High-Speed and Low-Power Design; Multiplierless Single/Mutiple Constant Multiplication (SCM/MCM); Radix-2r Booth recoding;
Conference_Titel :
Faible Tension Faible Consommation (FTFC), 2013 IEEE
Conference_Location :
Paris
Print_ISBN :
978-1-4673-6105-7
DOI :
10.1109/FTFC.2013.6577750
