Talk:Redundant binary representation

A RBR or the RBR?

The heading "Example of a table..." suggests that there are several RBR's, but most of the text suggests that the topic is one specific RBR. Which is right?  --Lambiam 16:46, 26 July 2008 (UTC)

There are many RBR. They work similarly. The most importance difference between them is there "translations tables". Off course, when you change the way the value is encoded in a digit, you need to change the operation unit as well to reflect that. The encoding shown in the article is particularly interesting because you can use regular full adder block to build a adder unit. I think that only the following sentences are specific to the encoding presented in this article : "Usually, RBR allows negative values – in fact, flipping all bits corresponds to negation (multiplication by −1) of the integer represented. There is no single sign bit that tells if a RBR represented number is positive or negative. Some integers have many possible representations in a RBR. For example, 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"." Yayay (talk) 00:15, 27 July 2008 (UTC)

Oups! I missed the first sentence of the article that was referring to a single RBR. I had to take some time off this article to spot that one! Yayay (talk) 17:17, 25 August 2008 (UTC)

Carry-free?

How can carry be avoided when incrementing a number like 11·11·11·11·11·11·11·11·11·11·11 by 1? Is something missing, like an invariant restricting the possible digit combinations?  --Lambiam 16:46, 26 July 2008 (UTC)

There is no carry in the typical sense where a carry can propagate from the first digit to the last. Still, the result of "11·11·11·11·11·11·11·11·11·11·11 + 11" would be "11·01·01·01·01·01·01·01·01·01·01·10" again when using the translation table suggested in the article. Yayay (talk) 00:15, 27 July 2008 (UTC)

Now, I see that further explanation on how to build a working redundant binary adder are needed. I'll look into this in the near future. yayay (talk) 04:30, 2 November 2008 (UTC)

Yayay, thank you for adding the "schematic of an adder unit" to the article.

That schematic clarifies for me how the high bits of the result can be directly calculated

without propagating a carry up from the low bits.

In Lambiam's example, all the digits change when incrementing (that particular representation of) 2^n-1, so it *appears* that the least-significant bit effects every digit of the result.

However, the schematic shows that the output "digit" at position N of the redundant-binary sum depends only on the digits at positions N, N-1, and N-2 of the two input values.

Let's say you are adding the value 2^n-1 to some value which is either 0 or 1.

We can immediately calculate the high bits of the result without knowing the low bits:

       1   1   1   ... 1  1  1  1  1 : 2^n-1 in natural binary
       0   0   0   ... 0  0  0  0  ? : either 0 or 1, we don't know yet.
   Expand using simple digit-by-digit expansion to get:
      11  11  11  ... 11 11 11 11 11 : One way to represent 2^n-1
      01  01  01  ... 01 01 01 01 ?? : either -1, 0, or +1
   ------------------------------
   11 01  01  01  ... 01 01 0? ?? ?0 : sum: high bits calculated without carry propagation.

The least-significant bit does not effect every digit of the result.

The "digit" at position N of either redundant-binary input value

affects only the output digits at positions N, N+1, and N+2.

Is there some way to make this clearer in the text of the article?

--DavidCary (talk) 13:35, 3 July 2011 (UTC)

Example of addition

Somewhat related to the above section, would it be reasonable to add an example of how to perform an addition in RBR? Would it be easy to show some steps evoking how ALUs work, that would exemplify how the non-typical carry works? Something like 12 * 34 = 10 * 34 + 2 * 34 = 10 * 30 + 10 * 4 + 2 * 30 + 2 * 4 = ... = 408 --Chealer (talk) 04:04, 3 August 2008 (UTC)

New section name for "Conversion from RBR"

I think Conversion from RBR needs a new name but I'm not able to pin down one. Any idea? Yayay (talk) 22:08, 29 July 2008 (UTC)

I'm not sure what would be a better name, but for a start I believe the third paragraph (about different RBR-s having different properties) should be moved out of that section. That might help others think of a better title for the rest. --Chealer (talk) 04:04, 3 August 2008 (UTC)

Use of "digit"

I am not a native English speaker, but I think the word "digit" is sometimes used incorrectly. For example, the first sentence. What digit(s) would be represented in, say, 00? I also don't really understand what digits the second sentence refers to. In the example of a translation table, 00 is presented as a digit, but that is actually a sequence of digit. --Chealer (talk) 04:04, 3 August 2008 (UTC)

A digit is essentially just any symbol from a finite set of symbols for some numeral system, used to represent numbers in the form of numerals. In many cases each digit symbol is a single glyph, but some systems have multi-glyph digits. In the system described in this article, each digit consists of two bits, each being '0' or '1', giving in total a set of four different symbols for the digits: '00', '01', '10', '11'.  --Lambiam 13:40, 11 August 2008 (UTC)