Weighted bit-set encodings for redundant digit sets: theory and applications

This paper aims to fill the gap between theoretical studies of redundant number representation dealing with digit-level algorithms, without considering circuit-level details or impact of digit-set encodings, and implementation-oriented studies that typically focus on one particular digit-set encoding. We recognize that radices of practical interest are powers of two, giving each high-radix digit a weight that is a power of two. Furthermore, digit sets are typically encoded in such a way that each bit of the encoded form has a power-of-2 weight within the corresponding position. These observations lead us to define the class of weighted bit-set (WBS) encodings for redundant number systems and study the general properties of this class of representations. While by no means completely general, the class of WBS encodings includes virtually every implementation of redundant arithmetic that we have encountered, including those based on hybrid redundancy. We derive general conditions for a WBS encoding to be viable or efficient and describe how arithmetic operations can be performed on redundant numbers of this type using standard arithmetic components such as full/half-adders and multiplexers.