Open AccessH‐RADIX a new heuristic for a single constant multiplication
Author(s) -
Khiter Belkacem,
Oudjida Abdelkrim Kamel,
Belhocine Mahmoud
Publication year - 2017
Publication title -
iet circuits, devices and systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.251
H-Index - 49
ISSN - 1751-8598
DOI - 10.1049/iet-cds.2016.0238
Subject(s) - radix (gastropod) , multiplication (music) , arithmetic , heuristic , heuristics , adder , constant (computer programming) , mathematics , algorithm , computer science , combinatorics , mathematical optimization , telecommunications , botany , biology , programming language , latency (audio)
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.