Graycodes

Gray codes are a binary numeral system in which two successive values differ in only one bit. This single-bit change property minimizes errors during transitions in digital systems. The most common form is the binary-reflected Gray code (BRGC), which can be generated by the rule g = b XOR (b >> 1), where b is the binary representation and g is the Gray code. BRGC sequences are of length 2^n for n bits and form a cyclic sequence, so the first and last codewords differ by a single bit.

For example, the three-bit BRGC is: 000, 001, 011, 010, 110, 111, 101, 100. Gray codes traverse all 2^n codewords while changing only one bit at each step, which makes them equivalent to a Hamiltonian cycle on the n-dimensional hypercube.

Conversions between binary and Gray code are standard: binary to Gray uses g = b XOR (b >> 1). To recover binary from Gray, the most significant bit equals the Gray MSB, and each subsequent binary bit is obtained by XORing the previous binary bit with the current Gray bit (b_i = b_{i-1} XOR g_i).

Applications include rotary encoders, where Gray coding prevents misreadings during motion, and certain digital-to-analog or analog-to-digital interfaces that benefit from reduced transition errors. Gray codes also appear in Karnaugh maps, where Gray ordering minimizes changes between adjacent cells, aiding logic minimization. Variants of Gray codes exist beyond BRGC, including other n-bit and d-ary forms, but BRGC remains the most widely used in hardware and software implementations.