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. An RBR is unlike usual binary numeral systems, 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.[1] When compared to non-redundant representation, an RBR makes bitwise logical operation slower, but arithmetic operations are faster when a greater bit width is used.[2] 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.
YouTube Encyclopedic
-
1/3Views:295 53494 88529 709
-
Introduction to number systems and binary | Pre-Algebra | Khan Academy
-
Redundancy Theorem (Boolean Algebra Trick)
-
Integer Linear Programming - Binary (0-1) Variables 1, Fixed Cost
Transcription
- [Voiceover] For as long as human beings have been around we've been counting things, and we've been looking for ways to keep track and represent those things that we counted. So, for example if you were an early human and you were trying to keep track of the days since it last rained you might say okay let's see it didn't rain today so one day has gone by, and we now use the word one, but they might have not used it back then. Now another day goes by. Then another day goes by. Then another day goes by. Another day goes by. Another day goes by. Another day goes by, then it rained. And so when his friend comes he says, "Well, how long has it been since we last rained." Well you would say, "Well, this is how many days it's been." And your friend would say, "Okay, I think I have a general sense of that." And at some point they probably realized that it's useful to have names for these. So they would call this one, two, three, four, five, six, seven. Obviously every language in the world has different names for these. I'm sure there are lost languages that had other names for them. But very quickly you start to realize that this is a pretty bulky way of representing numbers. One it takes a long time to write down. It takes up a lot of space, and then later if someone wants to read the number they have to sit here and count. It's hard enough with seven, but you could imagine if there were what we call 27 of it, or 1000 of it. Then it would take up, possibly, a whole page and even when you counted you might make a mistake. And to solve this human beings have invented number systems. And it's something that we take for granted. You might say, "Oh, isn't that just the way you've always counted? But hopefully over the course of this video you'll start to appreciate the beauty of a number system and to realize our number system isn't the only number system that is around. The number system that most of us are familiar with is the base 10 number system. Often called the decimal, the decimal number system. And why 10? Well probably because we have 10 fingers. Or most of us have 10 fingers. So, it was very natural to think in terms of bundles of 10 or to have 10 symbols. So however many bundles you have you can use your fingers and eventually your symbols to think about how many there are. And since we needed 10 symbols we came up with zero, one, two, three, four, five, six, seven, eight, nine. These 10 digits, these are our 10 symbols that we use in the base 10 system. To just give us a little bit of a reminder how we use them imagine the number 231. So, 231. 231. What does this represent? Well, what's neat about number systems is we have place value. This place all the way to the right, this is the ones place. This is the ones place. This literally means one, one. One bundle of one. So, this is one, one right over here. This right over here, this is in the 10s place. This is in the 10s place. This three here, literally means three 10s. So this literally means three 10s. And this two here, this two here is in the 100s place. It's in the 100s place. So, this represent two 100s. You add them together and once again I'm still thinking in base 10, you'd get 231. This is two 100s plus three 10s plus one. In our base 10 system notice every time we move to the left we're thinking in bundles of 10 of the space to the right. So, this is the ones place. You multiply by 10, you go to the 10s place. You want to go to the next place you multiply by 10 again. You get the 100s place. If you're familiar with exponents, one is the same thing as 10 to the zero power. 10 is the same thing as 10 to the first power. So this is the 10s place. Three tens. And 100 is the same thing as 10 to the second power. Obviously we could keep going on and on and on and on and on. That is the power of the base 10 system. So, you might be curious now. "Well, what if this wasn't 10 here? What if we did, let's just go as simple as we can. You can almost view this as a base one system. You only have one symbol right over here. But what if we went to something slightly more complex, a base two system. You'd be happy to know that not only can we do this, but the base two system often called the binary system. This is called the decimal system. The base two system often called the binary system is the basis of all modern computing. It's the underlying mathematics and operations that computers perform are based on binary. And in binary you have two symbols. You have zero and you have one. The reason why this is useful for computation is because all the hardware that we use to make our modern computers, all of the transistors and the logic gates they either result in an on or an off state. On or an off state. And so what we do is when you use your calculator or whatever you might be operating in base 10, but underlying everything it is doing the operations in binary. But you might say well how do we actually think in terms of binary? Well, we can construct similar places here, but instead of them being powers of 10 they're going to be powers of two. So, let's set up some places here. So, all the way on the right two to the zero power is still one. So we can still call that the ones place. Then we can move to the left of that. We can move to the left of that. That would be two to the first power. So we could call that the twos place, and I can even write it out if I want. Twos place instead of the 10s place. Then I could keep going. Instead of this space being the 10 to the second or the 100s place, it will be the two to the second, or the fours place. And I can keep going. I encourage you actually to pause the video and try to build this out for yourself. What would this be? Well this would be two to the third, or the eights place. Notice every time we're doing this we're multiplying by two. Everytime we go to the left, just like we multiplied by 10 here. So notice everywhere you see this 10s we're now dealing with twos. Let's keep going. Let's keep going and then we can actually represent this number using binary. So, let's do that. So, this right over here I've already used that color. This right over here, this is two to the fourth. We could call that the 16s place. Then we could have -- I'll reuse some of these colors. This is two to the fifth. We could call this the 32s place. Then we can go two to the sixth. We can call that, multiply by two again, or two to the six is 64. So this is the 64s place. Tells us how many 64s we have. Zero or one 64s. We'll see that in a second. Then we can go over here. This would be two to the seventh. That would be the 128s place. And we can obviously keep going on and on and on, but this should be enough for me to represent this number. In future videos I will show you how to do that, but let's actually represent the number. It turns out that this number in decimal can be represented as 11100111 in binary. What does this mean? This means you have one 128 plus one 64, plus one 32, plus no 16s, plus no eights, plus one four, plus one two, plus one one. So you can see that these are going to be the same thing. Notice, this is one 128. So it's 128, plus 64, plus 32. We have zero 16s, zero eights. So we're not going to add those. Plus four, one four. Plus one two. Plus one one. And add these together, and once again when we're doing this, when I'm writing it this way I'm kind of using the number system that we're most familiar with. We're most used to doing the operations in, but when you do it you will see that this is the exact same number as 231. This is just another representation. One isn't better than the other. The only reason why I converted this is this is what I'm used to thinking in. It's what I'm used to doing operations in. So, hopefully you find that pretty interesting. To me, this kind of opened my mind to the power of even our decimal system. In future videos we'll explore other number systems. The most used ones, base 10 is used very heavily, binary and there's also hexadecimal where you don't have two digits or not 10 digits, but you have 16 digits. And we'll explore those in future videos and how to convert between or rewrite the the different representations and different bases.
Conversion from RBR
An RBR is a place-value notation system. In an RBR, digits 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 dk is the interpreted value of the k-th digit, where k starts at 0 at the rightmost position:
The conversion from an RBR to n-bit two's complement can be done in O(log(n)) time using a prefix adder.[3]
Example of redundant binary representation
| 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.[4]
In this case:
Arithmetic operations
Redundant representations are commonly used inside high-speed arithmetic logic units.
In particular, a carry-save adder uses a redundant representation.[citation needed]
Addition
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 operands. 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).[5] 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.[6]
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 multipliers internally use Booth encoding, a redundant binary representation.
Logical operations
Bitwise logical operations, such as AND, OR and XOR, are not possible in redundant representations. While it is possible to do bitwise operations 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 digit) compared to a 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 can be done in log(k) time.
References
- ^ Phatak, Dhananjay S.; Koren, Israel (August 1994). "Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains" (PDF). IEEE Transactions on Computers. 43 (8): 880–891. CiteSeerX 10.1.1.352.6407. doi:10.1109/12.295850.
- ^ Lessard, Louis Philippe (2008). "Fast Arithmetic on FPGA Using Redundant Binary Apparatus". Retrieved 2015-09-12.
- ^ Veeramachaneni, Sreehari; Krishna, M. Kirthi; Avinash, Lingamneni; Reddy P., Sreekanth; Srinivas, M.B. (May 2007). Novel High-Speed Redundant Binary to Binary converter using Prefix Networks (PDF). IEEE International Symposium on Circuits and Systems (ISCAS 2007). New Orleans. doi:10.1109/ISCAS.2007.378170.
- ^ Lapointe, Marcel; Huynh, Huu Tue; Fortier, Paul (April 1993). "Systematic Design of Pipelined Recursive Filters". IEEE Transactions on Computers. 42 (4): 413–426. doi:10.1109/12.214688.
- ^ Yu-Ting Pai; Yu-Kumg Chen (January 2004). The fastest carry lookahead adder (PDF). Second IEEE International Workshop on Electronic Design, Test and Applications (DELTA '04). Perth. doi:10.1109/DELTA.2004.10071.
- ^ Jose, Bijoy; Radhakrishnan, Damu (December 2006). Delay Optimized Redundant Binary Adders. 13th IEEE International Conference on Electronics, Circuits and Systems, 2006. (ICECS '06). Nice. doi:10.1109/ICECS.2006.379838.
This page was last edited on 24 November 2022, at 23:39