Compact SD: a new encoding algorithm and its application in multiplication
Abdalhossein Rezai, Parviz Keshavarzi · International Journal of Computer Mathematics · 2015
This paper presents and evaluates a compact Signed-Digit (SD) encoding algorithm which is an efficient class of the large integer encoding algorithms. The compact SD algorithm results in a series of digits which show the number of consecutive zero bits. Using the proof-of-concept code, we proved that the optimal range for the limit on the number of consecutive zero bits in each digit and average Hamming weight of n-bit integers in the compact SD representation are ℓ=2 to ℓ=6 and n/3, respectively. In the modular multiplication algorithm, the compact SD is applied to the multiplier. The compact SD modular multiplication processes consecutive zero bits and followed nonzero digits in one clock cycle. Implementation results on Xilinx Virtex 5 FPGA show that the compact SD modular multiplication outperforms previous modified modular multiplication algorithms in terms of throughput and area × time complexity.