Compact SD: a new encoding algorithm and its application in multiplication

ABSTRACT

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 $\ell =2$ to $\ell =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.

KEYWORDS:

• Computer arithmetic
• modular multiplication
• Signed-Digit representation
• hardware implementation
• FPGA

2010 AMS SUBJECT CLASSIFICATIONS:

• 68P25
• 94A60
• 14G50
• 11Y16
• 11R58

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Abdalhossein Rezai http://orcid.org/0000-0001-8529-499X