Abstract
We propose the minimally redundant signed-digit (MRSD) number system, including its subsets the asymmetric high-radix signed-digit (AHSD), the minimal redundant positive-digit (MRPD), the symmetric high-radix signed-digit (SHSD) and the binary signed-digit (BSD) number systems, for fast binary addition and multiplication, and show that the MRSD number system supports carry-free (CF) addition. The CF additions in MRSD, to be classified as fully-closed, quasi-closed and sub-closed additions, use only one redundant digit for any radix r≧2. The criterion for the existence of carry-free additions, in terms of redundancy-index and radix, is thus from tightly bounded down to loosely bounded. Novel algorithms for constructing the two-stage and three-stage CF adders (CFA) based on the MRSD number system are also presented. Moreover, if the radix is specified as r=, where m is any positive integer, the binary-to-MRSD conversion can be done in constant time regardless of the word-length. Hence, the MRSD-to-binary conversion dominates the performance of an MRSD-based arithmetic system. We also propose two efficient algorithms for converting MRSD numbers to binary ones. The first one uses a novel structure to achieve high speed, while the second one uses simple transformations and conventional additions to provide hardware reusability. These results are important since the conversion from MRSD numbers to binary ones has been considered the performance bottleneck of the MRSD-based arithmetic systems. Algorithms for converting from asymmetric high-radix signed-digit (AHSD) numbers and minimal redundant positive-digit (MRPD) numbers to binary numbers are proposed. Our approach is based on simple transformation among AHSD, MRPD, and conventional radix-r (CR) number systems. We also show that the conversion from AHSD or MRPD numbers to binary numbers can be reduced to r's-complement addition. The result is important since the conversion from AHSD or MRPD to binary has been considered the performance bottleneck of the AHSD-based or MRPD-based arithmetic systems. We show that the AHSD-to-binary conversion is similar to the MRPD-to-binary conversion. Therefore, a good hardware architecture for any of the following three applications can be used for the other two: 1) r's-complement addition, 2) AHSD-to-binary conversion, and 3) MRPD-to-binary conversion. In addition to performance improvement, the main contribution of this work is hardware reusability and design flexibility, so far as the involved number systems are concerned. We also show that Blair's work is just a special case (for r=2) as discussed in this dissertation. Examples are given to demonstrate the proposed algorithms. The CF adder based on MRSD is especially suited to high-performance arithmetic with long sequences of addition-related computations performed on a massive amount of data. Practical implementations of the high-performance CF adder and array multiplier are presented. We conclude that MRSD is one of the excellent number systems to have the possibility to achieve high-performance operations with the smaller integrated circuits in high circuitry density. The conditions for the existence of various carry-free additions, performed over different digit sets with sufficient redundancy, are also concluded as loosely-bounded, Parhami's, tightly-bounded and uppermost-bounded criteria in terms of redundancy-index and radix.