Gray Code

What is Gray code?

Gray code (also called reflected binary code) is a clever ordering of binary numbers in which every two adjacent values differ by exactly one bit. It was devised by the physicist Frank Gray at Bell Labs — the patent was filed in 1947 and granted in 1953.

Why, when we already have plain binary?

In plain binary, going e.g. from $0111$ to $1000$ requires four bits to change at once. If they did not switch perfectly simultaneously (which happens in mechanical devices), momentary wrong intermediate values would appear. Gray code removes this problem — only one bit ever changes, so no spurious intermediate state can arise.

How is it generated?

Elegantly, with a single formula — $k$ XORed with $k$ shifted one bit to the right:

where $\oplus$ is the bitwise XOR and $\gg 1$ is a one-position right bit shift. For $n = 3$ this gives, in order: $000,\,001,\,011,\,010,\,110,\,111,\,101,\,100$ — and indeed every two adjacent values differ by one bit.

Invariant: Hamming distance = 1

The Hamming distance counts the positions at which two bit strings differ. For consecutive Gray-code values it is always exactly $1$. It is this guarantee that makes Gray code robust against read errors.

Where is it used?

In position encoders (rotation-angle sensors — the dial on the right), switches, digital communication and anywhere we want to minimise errors during a change of state. Without Gray code, a rotating encoder could briefly report a completely wrong position.

Why this matters for your exams:

Gray code is a beautiful example at the boundary of mathematics and computer science: it shows how a well-thought-out mathematical representation of numbers solves a concrete engineering problem. Bitwise operations (XOR, shift) and positional number systems are a recurring element of computer-science and discrete-mathematics problems.

Remember: Gray code orders numbers so that neighbours differ by one bit (Hamming = 1). It is generated by the formula $G(k) = k \oplus (k \gg 1)$, and it is used in encoders and everywhere robustness against errors matters.