graycode

Gray code, named after Frank Gray, is a binary numeral system in which two successive values differ in only one bit. An n-bit Gray code contains 2^n code words arranged so that adjacent codes differ by a single bit, and the sequence is cyclic (the first and last codes also differ by one bit). The most widely used variant is the binary-reflected Gray code (BRGC).

Conversion between binary and Gray code can be performed with simple bitwise operations. To convert binary b to Gray g: g = b XOR (b >> 1). To recover binary from Gray: set b0 = g0 and for i > 0, bi = bi-1 XOR gi. These properties ensure that only one bit changes between successive codes, which minimizes error during transitions.

Construction: BRGC can be generated recursively. Start with 1-bit sequence: 0, 1. For each additional bit, reflect the previous sequence and prefix the original half with 0 and the reflected half with 1. The resulting sequence is cyclic, and the first and last entries differ in one bit. Other Gray code variants exist, including non-reflected formulations and Gray codes for irregular bit-widths.

Applications: Gray code is widely used in rotary and linear encoders to prevent misreadings during motion, since adjacent positions differ by only one bit. It is also used in some analog-to-digital converters, digital logic design, and Karnaugh map ordering to preserve adjacency and simplify minimization. In communications, Gray coding helps reduce bit errors during symbol mapping.

History: The code was introduced by Frank Gray in 1953 for imaging and data transmission. The binary-reflected Gray code remains the standard form due to its simplicity and cyclic property.