*** Welcome to piglix ***

Gray code

Gray code
by bit width
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
Subpaths in the Savage–Winkler algorithm
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 a binary numeral system where 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

...