Gray Code Converter

Gray code is a re-ordering of the same 2ⁿ bit patterns so that neighbouring entries differ in exactly one bit. Nothing is added and nothing is removed: all sixteen four-bit patterns appear in a four-bit Gray sequence, in a different order from counting.

Gray code is not a number system. It has no place values, you cannot add two Gray codewords digit by digit, and the codeword 1110does not “mean” 14 — it is position 11 in a sequence.

Each Gray bit is the XOR of the binary bit in the same column and the binary bit to its left: gᵢ = bᵢ ⊕ bᵢ₊₁, with the most significant bit copied through unchanged. For 1011: g₃ = 1, g₂ = 1 ⊕ 0 = 1, g₁ = 0 ⊕ 1 = 1, g₀ = 1 ⊕ 1 = 0, giving 1110.

As one whole-word operation that is g = b ⊕ (b ≫ 1), which is why the conversion is a single instruction in hardware and every column can be computed at the same time.

The inverse is a prefix XOR and it runs from the most significant bit down: the top binary bit is the top Gray bit, and every bit after it is the Gray bit XORed with the binary bit just produced. For 1110: b₃ = 1, b₂ = 1 ⊕ 1 = 0, b₁ = 1 ⊕ 0 = 1, b₀ = 0 ⊕ 1 = 1, giving 1011.

This direction is sequential — each bit needs the one before it — which is why implementations use the logarithmic form b ^= b ≫ 1; b ^= b ≫ 2; b ^= b ≫ 4; … instead of a loop over the bits.

The code’s real name is the reflected binary code, and the name is the construction. Start with 0, 1. To get the next width, write the list, then write it again in reverse, then prefix 0 to the first half and 1 to the second. The mirror line is where the one-bit-change property is preserved: the two entries either side of it differ only in the new leading bit.

A rotary encoder that reads plain binary can report any value at all while several tracks change at once. Going from 0111 to 1000 all four tracks flip, and if the sensors are read mid-transition the output can be anything from 0 to 15. With Gray code exactly one track changes per step, so a mid-transition reading is either the old position or the new one — the worst case is an error of one position.

The same argument covers a counter passed between two clock domains. If only one bit can change per increment, the sampling domain can never latch a value that was never a real count.

The K-map’s row and column labels are a Gray code. That is the whole reason adjacent cells combine. Labelling the axes 00 01 11 10 rather than 00 01 10 11 makes physically neighbouring cells differ in exactly one variable, which is what lets a pair of them collapse into a single product term. See the Karnaugh map solver.

• Consecutive codewords differ in exactly one bit.
• The sequence is cyclic: the last codeword and the first also differ in one bit, so the code wraps.
• Every one of the 2ⁿ patterns appears exactly once.
• 0 and 1 are their own Gray codes; every larger power of two is not — 4 is 100 in binary and 110 in Gray.
• The parity of a Gray codeword equals the parity of the number of ones in the binary value it encodes, because the XOR fold of b ⊕ (b ≫ 1) keeps the top bit and cancels each other bit exactly twice.

This page computes the binary-reflectedGray code (BRGC), which is what “the Gray code” almost always means. It is not the only code with the one-bit-change property; balanced Gray codes, monotonic Gray codes and non-Boolean Gray codes over other alphabets all exist. If a question says only “Gray code”, it means this one.

The Gray code of 5 is 111 at three bits and 00000111 at eight. It is the same codeword; only the padding differs. Leading zeros are part of the codeword. State the width.

• Most significant bit first, left to right; bits are 0-indexed from the least significant end.
• ⊕ is XOR and ≫ is a logical right shift with zero shifted in.
• The sequence table is indexed by the decimal value of the binary word, so row i holds the Gray codeword for i.

Frank Gray, Pulse Code Communication, US Patent 2,632,058 (opens in a new tab), filed 13 November 1947 and granted 17 March 1953. Gray himself called it the “reflected binary code”; the name “Gray code” was attached later by others.