Why the gray code is also known as the reflected binary code?

Answer 1

Gray Code is known as reflected binary code (RBC) because Frank Gray's 1947 patent application contained the following paragraph:

The binary code with which the present invention deal may take various forms, all of which have the property that the symbol (or pulse group) representing each number (or signal amplitude) differs from the ones representing the next lower or next higher number (or signal amplitude) in only one digit (or pulse position). Because this code in its primary form may be built up from the conventional binary code by a sort of reflection process and because other forms may in turn be built up from the primary form in similar fashion, the code in question, which has as yet no recognized name, is designated in this specification and in the claims as the "reflective binary code."

What he meant by this "reflection process" is that any n-bit RBC sequence could be generated recursively by reflecting the n-1 RBC sequence for all n>0. The minimum RBC sequence is n=1:

0, 1

To generate the n=2 sequence, we reflect the n=1 sequence which simply reverses it:

1, 0

We then prefix the original n=1 sequence with a 0 bit and prefix the reflected sequence with a 1 bit:

00, 01 11,10

Finally, we concatenate these two sequences to produce the n=2 sequence:

00, 01, 11, 10

Note that this sequence represents the decimal sequence 0, 1, 2, 3, and not 0, 1, 3, 2 as per conventional binary notation.

Repeating the process with the n=2 sequence we can produce the n=3 sequence, then the n=4 sequence, and so on, for as many bits as we require.

Note that the sequence is cyclic. The final binary value for any given sequence differs from the first by only one digit (as is common throughout the sequence), thus when we reach the end of an RBC sequence we can simply start over again. This led to RBC becoming known as a "cyclic permutation code" in a 1953 patent. Other names for RBC include "minimum error code" and "the Bell Telephone Gray Code", a reference to Frank Gray's research work at Bell Labs. Today, the term Gray Code almost always refers to Reflected Binary Gray Code, or RBGC, as per Gray's original patent.

We can easily convert any conventional binary value to its RBGC equivalent such that:

rbgc(n) = n ^ (n >> 1)

>> is bitwise right shift and ^ is bitwise exclusive or.

For the decimal value 40 (binary 101000) we find:

101000 ^ (101000 >> 1) = 101000 ^ 010100 = 111100

Thus RBGC (101000) is 111100.

RBGC is typically used wherever we have a sequence of consecutive values and need to represent them in such a way that when we access a value mid-transition, we know that any read error can only be one value up or down from what it should be. For instance, without RGBC, the transition from 3 to 4 would result in 3 bits changing simultaneously (011 to 100), however with mechanical representations, there may be a small but significant delay in the bit transitions so we might read 000, 001, 010, 011, 100, 101, 110 or 110, depending on which bit changes first and at what stage in the transition we read the value. The more bits that change, the greater the range of errors we might encounter. But with RBGC, we guarantee that during the transition phase from 3 to 4 we either read a 3 or we read a 4 because only 1 bit can ever be in transition.