Redundant binary representation

A redundant binary representation (RBR) is a numeral system that uses more bits than needed to represent a single binary digit so that most numbers have several representations. RBR is unlike usual binary numeral systems, including two's complement, which use a single bit for each digit. Many of RBR's properties differ from those of regular binary representation systems. Most importantly, RBR allows addition without using a typical carry [Dhananjay Phatak, I. Koren, Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains, 1994, [http://citeseer.ist.psu.edu/phatak94hybrid.html] ] , but makes bitwise logical operation slower. Usually, every bit has a sign that is not necessarily the same as the sign of the number represented. When digits have signs, the RBR is also a signed-digit representation.

Conversion from RBR

RBR is a place-value notation system. In RBR, digits are "pairs" of bits, that is, for every place, RBR uses a pair of bits. The value represented by an RBR digit can be found using a translation table. This table indicates the mathematical value of each possible pair of bits.

As in conventional binary representation, the integer value of a given representation is a weighted sum of the values of the digits. The weight starts at 1 for the rightmost position and goes up by a factor of 2 for each next position. Usually, RBR allows negative values. There is no single sign bit that tells if a RBR represented number is positive or negative. Most integers have several possible representations in a RBR.

An integer value can be converted back from RBR using the following formula, where "n" is the number of digit and "d_k" is the interpreted value of the "k"-th digit, where "k" starts at 0 at the rightmost position::$sum\_\{k=0\}^\{n-1\}\; d\_k\; 2^k$

The conversion from RBR to two's complement can be done in O(log(n)) using prefix adder where "n" is the number of digit. [Sreehari Veeramachaneni, M.Kirthi Krishna, Lingamneni Avinash, Sreekanth Reddy P, M.B. Srinivas, Novel High-Speed Redundant Binary to Binary converter using Prefix Networks, 2007, [http://ieeexplore.ieee.org/iel5/4252534/4252535/04253377.pdf?isnumber=4252535&prod=CNF&arnumber=4253377] ]

Example of redundant binary representation

Not all RBR have the same properties. For example, using the translation table on the right, the number 1 can be represented in RBR in many ways: "01·01·01·11", "01·01·10·11", "01·01·11·00", "11·00·00·00". Also, for this translation table, flipping all bits (NOT gate) corresponds to finding the additive inverse (multiplication by −1) of the integer represented.

In this case: $d\_k\; isin\; \{\; -1,\; 0,\; 1\; \}$

Arithmetic operations

RBR is used by particular arithmetic logic units.

Addition

The addition operation in RBR is carry-free, which means that the carry does not have to propagate through all the width of the addition unit. In effect, the addition in RBR is a constant-time operation. The addition will always take the same amount of time independent of the bit width of the operands. This does not imply that the addition is always faster in RBR than is two's complement representation, but that the addition will eventually be faster in RBR with increasing bit width because the two's complement addition unit's delay is proportional to log("n") (where "n" is the bit width) [Yu-Ting Pai, Yu-Kumg Chen, The fastest carry lookahead adder, 2004, [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1409882] ] . The addition in RBR take a constant time because each digit of the result can be calculated independently of one another, implying that each digit of the result can be calculated in parallel.

ubtraction

Subtraction is the same as the addition except that the additive inverse of one of the operands needs to be computed first. The additive inverse is usually found using a translation table.

Logical operations

Implementing logical operations in RBR using digital logic is more complicated than in usual representations. For example, the expected result of the bitwise AND operation on a pair of representations of 1 is expected to have value 1 in usual representations. Since there are many ways to represent 1 in RBR, it is not possible to simply use the basic logic gate AND between every digit. The same problem apply to the OR and XOR operations. While it is possible to do bitwise operations directly in RBR, it is not clear that this is a meaningful operation. Assuming one wants the result to represent the same integer value as if the operation had been carried out using a standard binary representation, it is necessary to convert the two operands first to non-redundant representations. Consequently, logical operations are slower in RBR. More precisely, they take a time proportional to log("n") (where "n" is the number of digit) compared to a constant-time in two's complement.

References