Gray Code, in depth: the reflected construction, conversions, the ruler sequence, async FIFO pointers and O(1) subset enumeration

Why one-bit changes matter

Consider a three-bit counter going from 3 to 4: binary 011 to 100. All three bits change. In hardware they never change at exactly the same instant, and a reader that samples during the transition can see any mix of old and new bits: 111 (7), 000 (0), 101 (5) and so on. A shaft encoder with binary tracks has the same problem mechanically: at the boundary between sectors 3 and 4, the three sensors cross their edges at slightly different angles, so the reported position can jump to anything.

If only one bit changes per step, the only possible readings during a transition are the old value and the new value. The error is bounded by one step, which is exactly the behaviour a sampler needs. That is the whole idea; everything else is construction and engineering.

The reflected construction

The reflected construction builds the n-bit list from the (n-1)-bit list: write the list with a 0 in front, then write it in reverse order with a 1 in front. Inside each half, neighbours differ in one bit by induction. At the seam, the last item of the first half and the first item of the second half are the same (n-1)-bit word, so only the new leading bit differs. The last item of the whole list is 1 followed by the first word of the old list, so the list wraps around to the start with one change as well: it is a cycle.

def reflected(n):
    codes = [""]
    for _ in range(n):
        codes = ["0" + c for c in codes] + ["1" + c for c in reversed(codes)]
    return codes

assert reflected(3) == [format(i ^ (i >> 1), "03b") for i in range(8)]

The assertion is the bridge to the closed form. Bit i of n ^ (n >> 1) is bit i of n XOR bit i+1 of n: a Gray bit is 1 exactly where the binary number changes between adjacent positions. Seen geometrically, the code is a Hamiltonian cycle on the n-dimensional hypercube, whose vertices are the n-bit words and whose edges join words one bit apart; see Hamiltonian paths for the general problem, which is hard, unlike this special case.

Converting both ways

Binary to Gray is one shift and one XOR. Gray to binary undoes it: binary bit i is the XOR of all Gray bits at positions i and above, a prefix XOR from the top. The loop version does one step per bit; the fixed-width version doubles the shift each step and finishes a 32-bit word in five steps.

def to_gray(n: int) -> int:
    return n ^ (n >> 1)

def from_gray(g: int) -> int:
    n = 0
    while g:
        n ^= g
        g >>= 1
    return n

def from_gray32(g: int) -> int:      # log2(32) = 5 doubling steps
    g ^= g >> 16
    g ^= g >> 8
    g ^= g >> 4
    g ^= g >> 2
    g ^= g >> 1
    return g

assert all(from_gray(to_gray(i)) == i == from_gray32(to_gray(i)) for i in range(1 << 16))

In hardware, Gray to binary is a chain of XOR gates whose depth grows with width, which is why FIFO designs keep a binary counter for arithmetic and convert to Gray only for the value that crosses the clock boundary.

Which bit flips: the ruler sequence

Going from step k-1 to step k, the bit that flips is the position of the lowest set bit of k, counting k from 1. Proof: g(k) ^ g(k-1) equals (k ^ (k-1)) ^ ((k ^ (k-1)) >> 1). The value k ^ (k-1) is a run of ones from bit 0 up to the lowest set bit of k, and XOR with its own shift leaves only the top one. So the flip sequence is the ruler sequence 0, 1, 0, 2, 0, 1, 0, 3 and so on, the same lowest-set-bit quantity that drives a Fenwick tree. It is also the move sequence of the Towers of Hanoi: at move k, move disk number ctz(k).

Read the table down the Gray column: each row differs from the one above in one position, and row 7 (100) differs from row 0 (000) in one position too. Read the binary column at 3 to 4 to see the three-bit change the Gray code removes.

Position encoders

An absolute rotary encoder has one concentric track per bit, read by a row of sensors. With Gray-coded tracks, a sensor misalignment at any sector boundary produces either the sector before or the sector after, never a distant one, so the position error is at most one sector without any extra logic. Incremental quadrature encoders use the same idea with two bits: the A and B channels step through 00, 01, 11, 10, a two-bit Gray cycle, and the direction of travel is which way around the cycle the state moves. Software that decodes them treats any two-bit jump as an error: a missed sample, or noise.

Async FIFO pointers across clock domains

The most important modern use is the asynchronous FIFO, the standard way to pass data between two clock domains on a chip. The writer increments a write pointer in its clock; the reader increments a read pointer in its clock. To compute empty, the reader needs the write pointer, and to compute full, the writer needs the read pointer. Each pointer is passed through a two-flip-flop synchronizer into the other domain.

If the pointers crossed in binary, a sampled pointer during a multi-bit change could be any value, and the FIFO could report data that was never written. With Gray pointers only one bit is in flight, so the synchronized pointer is always a value the pointer actually held, perhaps a few cycles stale. A stale write pointer makes the reader think the FIFO is emptier than it is, and a stale read pointer makes the writer think it is fuller: both errors are conservative. The pointers are one bit wider than the address so full and empty can be told apart. Empty is pointers equal. Full is, in Gray form, the top two bits inverted and the rest equal:

// write side; pointers are ADDR+1 bits wide, ADDR address bits
assign wbin_next  = wbin + (winc & ~wfull);
assign wgray_next = (wbin_next >> 1) ^ wbin_next;
assign wfull_val  = (wgray_next ==
                     {~wq2_rgray[ADDR:ADDR-1], wq2_rgray[ADDR-2:0]});
always @(posedge wclk or negedge wrst_n)
  if (!wrst_n) {wbin, wptr, wfull} <= 0;
  else         {wbin, wptr, wfull} <= {wbin_next, wgray_next, wfull_val};

Two conditions make this safe. The depth must be a power of two, because only then does the reflected code wrap from its last value to zero with one bit change. And the bits of the Gray bus must arrive at the synchronizer with skew under one source clock period, which is a timing constraint you must write for the tool; without it, place and route can delay one bit enough that two increments overlap at the sampler.

Enumerating subsets in Gray order

In software, the same property makes subset enumeration cheap. Walking all 2^n subsets in Gray order changes one element per step, so any quantity that can be updated by adding or removing one element, a sum, a product modulo p, a bitmask of covered items, costs O(1) per subset instead of O(n).

def subset_sums_gray(items):
    mask, total = 0, 0
    yield mask, total
    for k in range(1, 1 << len(items)):
        bit = (k & -k).bit_length() - 1        # ruler sequence
        mask ^= 1 << bit
        total += items[bit] if mask >> bit & 1 else -items[bit]
        yield mask, total

# worked example: items [3, 5, 9]
# masks 000 001 011 010 110 111 101 100  ->  sums 0 3 8 5 14 17 12 9

This removes a factor of n from exhaustive searches such as the two halves of meet in the middle, and the same loop drives exhaustive testing of hardware where each step should toggle a single input. For counting the subsets themselves see combinatorics.

Beyond binary reflected code

Genetic algorithms sometimes encode integer genes in Gray code, because in binary the neighbours 7 and 8 (0111 and 1000) are four mutations apart, a Hamming cliff, while in Gray they are one. The reverse does not hold: a single mutation of a Gray gene can still move the value far, so the benefit is a smoother landscape, not locality in both directions.

Variants exist for other needs. Cyclic codes of any even length can be taken as a symmetric slice around the midpoint of a reflected code, which is how FIFOs with non-power-of-two depths are sometimes built. Balanced Gray codes spread the flips evenly across bit positions, useful when each flip wears a component. Karnaugh maps order their rows and columns in Gray order so that adjacent cells differ in one variable.

Failure modes

• Gray-coding a counter that skips. A pointer that can advance by two in one cycle changes two bits, and the guarantee is gone.
• Non-power-of-two depth. Wrapping a 0 to 5 Gray count back to 0 changes two bits. Use a power-of-two depth or a symmetric cyclic slice.
• Combinational Gray output. Converting in logic right before the synchronizer can glitch; register the Gray value in the source domain first.
• Doing arithmetic in Gray. Addition and comparison for ordering do not work on Gray words; convert to binary first.
• Missing skew constraint. The design simulates perfectly and fails on silicon or FPGA because bus bits arrive in different sampling cycles.

Trade-offs

What to do next

1. Write to_gray and from_gray and check the round trip over all 16-bit values.
2. Verify the ruler-sequence claim by printing the flipped bit for k from 1 to 32.
3. If you design hardware, read your async FIFO for power-of-two depth, registered Gray pointers, two-flop synchronizers and a written bus-skew constraint.
4. Rewrite one exhaustive subset search to update its state incrementally in Gray order.
5. When decoding quadrature or absolute encoders, reject two-bit jumps as errors.