Asymmetric high-radix signed-digit number systems for carry-free addition

Shao Hui Shieh, Cheng Wen Wu

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

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 = 2 m , 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.

Original languageEnglish
Pages (from-to)1015-1039
Number of pages25
JournalJournal of Information Science and Engineering
Volume19
Issue number6
Publication statusPublished - 2003 Nov 1

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Hardware and Architecture
  • Library and Information Sciences
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Asymmetric high-radix signed-digit number systems for carry-free addition'. Together they form a unique fingerprint.

Cite this