109.243.0.15 at 20:28, 28 February 2025

2025-02-28T20:28:23Z

New page

A '''redundant binary representation (RBR)''' is a [[numeral system]] that uses more bits than needed to represent a single binary [[Numerical digit|digit]] so that most numbers have several representations. An RBR is unlike usual [[binary numeral system]]s, including [[two's complement]], which use a single bit for each digit. Many of an RBR's properties differ from those of regular binary representation systems. Most importantly, an RBR allows addition without using a typical carry.<ref>{{Cite journal |first1=Dhananjay S. |last1=Phatak |first2=Israel |last2=Koren |title=Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains |date=August 1994 |journal=IEEE Transactions on Computers |volume=43 |issue=8 |pages=880–891 |doi=10.1109/12.295850 |url=http://euler.ecs.umass.edu/research/PhKo-IEEETC-1994.pdf|citeseerx=10.1.1.352.6407 }}</ref> When compared to non-redundant representation, an RBR makes [[bitwise operation|bitwise logical operation]] slower, but [[arithmetic operation#Arithmetic operations|arithmetic operations]] are faster when a greater bit width is used.<ref>{{cite web |first=Louis Philippe |last=Lessard |title=Fast Arithmetic on FPGA Using Redundant Binary Apparatus |year=2008 |url=http://www.louislessard.com/rbin/ |access-date=2015-09-12}}</ref> Usually, each digit has its own sign that is not necessarily the same as the sign of the number represented. When digits have signs, that RBR is also a [[signed-digit representation]].

==Conversion from RBR==
An RBR is a [[positional notation|place-value notation system]]. In an RBR, [[Numerical digit|digit]]s are ''pairs'' of bits, that is, for every place, an RBR uses a pair of bits. The value represented by a redundant 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, an RBR allows negative values. There is no single sign bit that tells if a redundantly represented number is positive or negative. Most integers have several possible representations in an RBR.

Often one of the several possible representations of an integer is chosen as the "canonical" form, so each integer has only one possible "canonical" representation; [[non-adjacent form]] and two's complement are popular choices for that canonical form.

An [[integer]] value can be converted back from an RBR using the following formula, where ''n'' is the number of digits and ''d<sub>k</sub>'' is the interpreted value of the ''k''-th digit, where ''k'' starts at 0 at the rightmost position:
:<math>
\sum_{k=0}^{n-1} d_k 2^k
</math>

The conversion from an RBR to ''n''-bit two's complement can be done in O(log(''n'')) time using a [[prefix adder]].<ref>{{Cite conference |first1=Sreehari |last1=Veeramachaneni |first2=M. Kirthi |last2=Krishna |first3=Lingamneni |last3=Avinash |first4=Sreekanth |last4=Reddy P. |first5=M.B. |last5=Srinivas |title=Novel High-Speed Redundant Binary to Binary converter using Prefix Networks |conference=IEEE International Symposium on Circuits and Systems (ISCAS 2007) |date=May 2007 |location=New Orleans |doi=10.1109/ISCAS.2007.378170 |url=http://euler.ecs.umass.edu/research/PhKo-IEEETC-1994.pdf}}</ref>

==Example of redundant binary representation==
{| class="wikitable" align="right" style="margin-left: 3em; text-align:center;"
|+ Example of translation table for a digit
! Digit !! Interpreted value
|-
| 00 || −1
|-
| 01 ||  0
|-
| 10 ||  0
|-
| 11 ||  1
|}
Not all redundant representations have the same properties. For example, using the translation table on the right, the number 1 can be represented in this RBR in many ways: "01·01·01·11" (0+0+0+1), "01·01·10·11" (0+0+0+1), "01·01·11·00" (0+0+2−1), or "11·00·00·00" (8−4−2−1). Also, for this translation table, flipping all bits ([[NOT gate]]) corresponds to finding the [[additive inverse]] ([[multiplication]] by [[−1]]) of the integer represented.<ref>{{Cite journal |first1=Marcel |last1=Lapointe |first2=Huu Tue |last2=Huynh |first3=Paul |last3=Fortier |title=Systematic Design of Pipelined Recursive Filters |journal=IEEE Transactions on Computers |volume=42 |issue=4 |date=April 1993 |pages=413–426 |doi=10.1109/12.214688}}</ref>

In this case: <math>d_k \isin \{ -1, 0, 1 \}</math>

==Arithmetic operations==
Redundant representations are commonly used inside high-speed [[arithmetic logic unit]]s.

In particular, a [[carry-save adder]] uses a redundant representation.{{Cn|date=September 2015}}

===Addition===
[[Image:Redundant binary adder.png|thumb|right|Schematic of an adder unit using [[full adder]] block (z = x + y)]]
The addition operation in all RBRs is carry-free, which means that the carry does not have to propagate through the full width of the addition unit. In effect, the addition in all RBRs is a constant-time operation. The addition will always take the same amount of time independently of the bit-width of the [[operand]]s. This does not imply that the addition is always faster in an RBR than its [[two's complement]] equivalent, but that the addition will eventually be faster in an 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).<ref>{{Cite conference |author1=Yu-Ting Pai |author2=Yu-Kumg Chen |title=The fastest carry lookahead adder |conference=Second IEEE International Workshop on Electronic Design, Test and Applications (DELTA '04) |location=Perth |date=January 2004 |doi=10.1109/DELTA.2004.10071 |url=http://galia.fc.uaslp.mx/~rmariela/digital/FastCLA.pdf}}</ref> Addition in an RBR takes 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.<ref>{{Cite conference |first1=Bijoy |last1=Jose |first2=Damu |last2=Radhakrishnan |title=Delay Optimized Redundant Binary Adders |conference=13th IEEE International Conference on Electronics, Circuits and Systems, 2006. (ICECS '06) |date=December 2006 |location=Nice |doi=10.1109/ICECS.2006.379838}}</ref>

===Subtraction===
Subtraction is the same as the addition except that the additive inverse of the second operand needs to be computed first. For common representations, this can be done on a digit-by-digit basis.

=== Multiplication ===

Many [[hardware multiplier]]s internally use [[Booth encoding]], a redundant binary representation.

==Logical operations==
Bitwise logical operations, such as [[AND gate|AND]], [[logical disjunction|OR]] and [[XOR]], are not possible in redundant representations. While it is possible to do [[bitwise operation]]s directly on the underlying bits inside an RBR, it is not clear that this is a meaningful operation; there are many ways to represent a value in an RBR, and the value of the result would depend on the representation used.

To get the expected results, it is necessary to convert the two operands first to non-redundant representations. Consequently, logical operations are slower in an RBR. More precisely, they take a time proportional to log(''n'') (where ''n'' is the number of digits) compared to constant time in [[two's complement]].

It is, however, possible to ''partially'' convert only the least-significant portion of a redundantly represented number to non-redundant form. This allows operations, such as masking off the low ''k'' bits, to be done in log(''k'') time.

==References==
{{reflist}}

{{DEFAULTSORT:Redundant Binary Representation}}
{{Processor technologies|state=collapsed}}
[[Category:Binary arithmetic]]
[[Category:Non-standard positional numeral systems]]

Redundant binary representation - Revision history

109.243.0.15 at 20:28, 28 February 2025