Gray coding
| 2-bit | 4-bit |
|---|---|
| 00 01 11 10 |
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 |
| 3-bit | |
| 000 001 011 010 110 111 101 100 |
| j = 0 | j = 1 | j = 2 | j = 3 | |
|---|---|---|---|---|
| n = 1 | 0, 1 | |||
| n = 2 | 00, 01 | 10, 11 | ||
| n = 3 | 000, 001 | 100, 110, 010, 011 | 101, 111 | |
| n = 4 | 0000, 0001 | 1000, 1100, 0100, 0110, 0010, 0011 | 1010, 1011, 1001, 1101, 0101, 0111 | 1110, 1111 |
The reflected binary code (RBC), also known as Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). The reflected binary code was originally designed to prevent spurious output from electromechanical switches. Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.
Bell Labs researcher Frank Gray introduced the term reflected binary code in his 1947 patent application, remarking that the code had "as yet no recognized name". He derived the name from the fact that it "may be built up from the conventional binary code by a sort of reflection process".
The code was later named after Gray by others who used it. Two different 1953 patent applications use "Gray code" as an alternative name for the "reflected binary code"; one of those also lists "minimum error code" and "cyclic permutation code" among the names. A 1954 patent application refers to "the Bell Telephone Gray code".
Many devices indicate position by closing and opening switches. If that device uses natural binary codes, positions 3 and 4 are next to each other but all three bits of the binary representation differ:
The problem with natural binary codes is that physical switches are not ideal: it is very unlikely that physical switches will change states exactly in synchrony. In the transition between the two states shown above, all three switches change state. In the brief period while all are changing, the switches will read some spurious position. Even without keybounce, the transition might look like 011 — 001 — 101 — 100. When the switches appear to be in position 001, the observer cannot tell if that is the "real" position 001, or a transitional state between two other positions. If the output feeds into a sequential system, possibly via combinational logic, then the sequential system may store a false value.
...
Wikipedia