Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]


Journal of Information Science and Engineering, Vol.19 No.6, pp.1015-1039 (November 2003)

Assymmetric High-Radix Signed-Digit Number Systems
for Carry-Free Addition

Shao-Hui Shieh and Cheng-Wen Wu*
Department of Electronic Engineering
National Chinyi Institute of Technology
Taichung, 411 Taiwan
*Department of Electrical Engineering
National Tsing Hua University
Hsinchu, 300 Taiwan

We propose an asymmetric high-radix signed-digit (AHSD) number system for fast binary addition, and show that the AHSD number system supports carry-free (CF) addition. The CF additions in AHSD, to be classified as quasi-closed and subclosed additions, use only one redundant digit for any radix r ? 2. Novel algorithms for constructing the three-stage CF adder (CFA) based on the AHSD number system are also presented. Moreover, if the radix is specified as r = 2m, where m is any positive integer, the binary-to-AHSD conversion can be done in constant time regardless of the word-length. Hence, the AHSD-to-binary conversion dominates the performance of an AHSD-based arithmetic system. We also propose two efficient algorithms for converting AHSD numbers to binary format. The first uses a novel structure to achieve high speed, while the second uses simple transformations and conventional additions to provide hardware reusability. These results are important since the conversion from AHSD numbers to binary format has been considered the performance bottleneck of AHSD-based arithmetic systems.

Keywords: asymmetric high-radix signed-digit number, computer arithmetic, number system conversion, redundant number system, signed-digit numbers, VLSI design

Full Text () Retrieve PDF document (200311_07.pdf)

Received January 29, 2002; revised July 23, 2002; accepted February 24, 2003.
Communicated by Gen-Huey Chen.