Redundant Binary Representation - Conversion From RBR

Conversion From RBR

A RBR is a place-value notation system. In a RBR, digits are pairs of bits, that is, for every place, a 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, a 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 an RBR.

An integer value can be converted back from a 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:

The conversion from a RBR to two's complement can be done in O(log(n)) using prefix adder where n is the number of digit.