Building 4-bit Gray by reflection — Gray code
corewhy it is called reflected binary
Answer
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
Why this example is worth doing
The construction that gives the code its proper name: take the n-bit sequence, write it out, mirror it, prefix 0 to the original half and 1 to the mirrored half. The single-bit-change property survives the join because the two entries at the mirror line are identical apart from the new leading bit. The page animates the reflection, since seeing it built once makes the definition permanent.
Try your own input in the Gray code. Convert binary to reflected Gray code and back, and build the sequence by reflection.
How the answer is reached
4-bit binary reflected Gray code
L1 = [0, 1]. For each extra bit, write the list, write it reversed below the mirror line, then prefix 0 to the top half and 1 to the bottom half.
| bits | sequence |
|---|---|
| 1 | 0, 1 |
| 2 | 00, 01, 11, 10 |
| 3 | 000, 001, 011, 010, 110, 111, 101, 100 |
| 4 | 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000 |
Consecutive codewords differ in exactly one bit, and so do the last and the first: the code is cyclic.
This is the binary reflected Gray code. It is one Gray code among many: any single-bit-change ordering of the codewords is a Gray code, and other constructions give different tables.
Source: Frank Gray, US Patent 2,632,058, "Pulse Code Communication" (filed 1947, granted 1953)