Gray Code & the Hypercube | mysimulator.uk

The problem with plain binary

Counting in ordinary binary looks smooth on paper, but the number of bits that flip between consecutive values is wildly uneven. Going from 3 to 4 flips three bits (011 → 100); going from 7 to 8 flips four (0111 → 1000). If a physical sensor — a rotary shaft encoder, a mechanical switch bank — is read at the exact instant several bits are supposed to change, the bits rarely all flip in perfect synchrony. A reader can catch some bits already flipped and others not yet flipped, producing a bogus intermediate value that is nowhere near either the old or the new position.

Reflected binary: g = b XOR (b >> 1)

Frank Gray's 1953 patent (building on earlier work by Émile Baudot) fixes this with a reordering of the same 2ⁿ values so that every consecutive pair differs in exactly one bit. Given an ordinary binary number b, its Gray code g is:

g = b XOR (b >> 1)

  b (binary)   g (Gray)
  000          000
  001          001
  010          011
  011          010
  100          110
  101          111
  110          101
  111          100

The name "reflected binary" comes from the recursive construction: the n-bit Gray sequence is the (n-1)-bit sequence written forwards with a leading 0, followed by the same (n-1)-bit sequence written backwards (reflected) with a leading 1. Each reflection guarantees the join between the two halves differs by exactly one bit — the new leading bit — while the interior of each half already satisfies the single-bit-change property by induction.

Decoding it back to binary

The XOR that built the Gray code is easy to undo with a cumulative XOR scan from the most significant bit down: the top output bit equals the top Gray bit, and every bit after that is the XOR of the previous output bit with the current Gray bit.

// decode: Gray -> binary, most-significant bit first
b[0] = g[0];
for (i = 1; i < n; i++) {
  b[i] = b[i - 1] XOR g[i];
}

A Hamiltonian path on the hypercube

live demo · stepping through the n-cube one edge at a time● LIVE

Picture the graph whose 2ⁿ vertices are all n-bit strings, with an edge between any two strings that differ in exactly one bit — this is the n-dimensional hypercube graph. Because consecutive Gray codewords differ in one bit by construction, the Gray code sequence is precisely a Hamiltonian path through this graph: a route that visits every vertex exactly once, moving only along edges. The standard Gray code is in fact a Hamiltonian cycle, since the last codeword and the first also differ by one bit (only the top bit, by the reflection construction).

This graph view explains why Gray code generalises so well: any Hamiltonian cycle on the hypercube gives a valid "single bit change" ordering, and Gray code is simply the most systematic, easiest-to-compute one. It is also the basis of the classic recursive/iterative algorithm for generating all subsets of a set one element at a time — walking the Gray sequence toggles exactly one set membership per step.

Where it actually gets used

Absolute rotary and linear position encoders print a Gray-coded pattern onto a disc or strip precisely because of the single-bit guarantee: a misread near a transition boundary is off by at most one position instead of jumping wildly. Karnaugh maps in digital logic design order their rows and columns in Gray code so that adjacent cells always differ by one input bit, which is what makes visually grouping adjacent 1s into rectangles a valid way to spot minimal Boolean simplifications. Gray code also shows up in genetic algorithms (mutating one bit changes the decoded value by a small, predictable amount, unlike plain binary where a single high-bit mutation can jump the value enormously) and in error-correcting communication schemes, where it minimises the numeric damage caused by a single-bit transmission error.

Frequently asked questions

Why is Gray code used in rotary encoders instead of plain binary?

Because only one bit changes between adjacent positions. With ordinary binary, a transition like 0111 to 1000 flips four bits at once, and if the sensor reads them a few nanoseconds apart it can briefly output a wildly wrong value such as 1111 or 0000. Gray code makes every neighbouring reading differ by exactly one bit, so a misread mid-transition is off by at most one position.

How do you convert Gray code back to binary?

Cumulative XOR from the most significant bit downward: the top bit is unchanged, and each subsequent binary bit is the XOR of the previous binary bit with the corresponding Gray bit. It undoes the XOR-with-shifted-copy that produced the Gray code in the first place, and takes O(log n) sequential steps in the naive form or O(log log n) with a parallel-prefix trick.

Is Gray code the same thing as a Hamiltonian path?

The standard n-bit Gray code sequence is one specific Hamiltonian path through the n-dimensional hypercube graph, where vertices are the 2^n bit strings and edges join strings that differ in one bit. There are many other Hamiltonian paths and even Hamiltonian cycles on the same graph — Gray code is simply the most famous, most systematically constructible one.

Try it live

Everything above runs in your browser — open Gray Code and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Gray Code simulation

Gray Code: One Bit Flip at a Time