Gray Code Counter

Why Gray code exists

Counting in plain binary is unsafe whenever bits are physically observed during a transition. The increment from 3 to 4 flips three bits: 011 → 100. In a noiseless world the three flips happen simultaneously and there is no transient. In every real-world sensor — rotary encoder disk, photodetector array, asynchronously sampled bus — the flips don't happen at exactly the same moment. For some sliver of time you can observe any of 000, 001, 010, 011, 100, 101, 110, 111. The controller reading the position sees a glitch.

Frank Gray, working at Bell Labs in 1947 (patent issued 1953), solved this by reordering the binary codes so that any two consecutive values differ in only one bit position. A glitch is now impossible: the only intermediate value during a transition is one of the two valid endpoints. The 3-bit reflected Gray code sequence is:

decimal   binary   gray
0         000      000
1         001      001
2         010      011
3         011      010
4         100      110
5         101      111
6         110      101
7         111      100

Notice that between adjacent rows exactly one bit flips: 000→001 (bit 0), 001→011 (bit 1), 011→010 (bit 0), 010→110 (bit 2), and so on. The cyclic transition 100→000 also flips just one bit (bit 2), so a Gray-coded counter wraps around safely too.

The two-line conversion

Binary-to-Gray is a single XOR. Take the binary number, shift right by one, XOR with itself:

uint32_t bin_to_gray(uint32_t b) {
    return b ^ (b >> 1);
}

Why does this work? Bit i of the Gray code is bit i XOR bit i+1 of the binary number. When the binary increments by 1, the bits that flip are bit 0 and all the leading 1s that ripple into the next position. The XOR pair cancels all but the highest-order flip, leaving exactly one bit changed in Gray.

Gray-to-binary is a prefix XOR. Each binary bit is the XOR of all Gray bits at higher or equal positions:

uint32_t gray_to_bin(uint32_t g) {
    g ^= g >> 16;
    g ^= g >>  8;
    g ^= g >>  4;
    g ^= g >>  2;
    g ^= g >>  1;
    return g;
}

That's a parallel-prefix XOR, finishing in O(log n) shifts for n-bit values. The straightforward serial loop does it in n XOR operations. In hardware the prefix-XOR is a Brent-Kung adder shape — log₂ depth, n−1 gates.

Incrementing a Gray counter without converting

You can count in Gray code without round-tripping through binary. The rule:

• If the parity (number of 1 bits) of the current value is even, flip bit 0.
• If the parity is odd, find the lowest set bit, then flip the bit immediately to its left.

Walking through: 000 (even parity, flip bit 0) → 001 (odd, lowest set is bit 0, flip bit 1) → 011 (even, flip bit 0) → 010 (odd, lowest set is bit 1, flip bit 2) → 110 (even, flip bit 0) → 111 (odd, lowest set is bit 0, flip bit 1) → 101 (even, flip bit 0) → 100 (odd, lowest set is bit 2, flip bit 3 — which doesn't exist in 3-bit, so wraps to 000). Single-bit transition every step.

Application: rotary encoders

An absolute rotary encoder reads a Gray-coded pattern off a disk. A 10-bit encoder has 1024 positions per revolution — 10 concentric tracks, each with a printed bit pattern. As the disk rotates, photodetectors or contact brushes read the 10-bit value. Encoded in Gray, the transition between any two adjacent positions flips exactly one bit, so the only possible mid-transition reading is the old position or the new — never an arbitrary spurious value. Encoded in plain binary, the transition 511→512 flips all 10 bits and any of 1024 spurious values could be sampled mid-flight.

Industrial servo controllers and CNC machine spindles use Gray-coded absolute encoders for exactly this reason. The cost is one XOR gate to convert the reading back to position-as-an-integer for downstream arithmetic. The benefit is that a single noisy sample during rotation never produces a catastrophically wrong angle.

Application: asynchronous FIFOs

A clock-domain-crossing FIFO has a write pointer ticked by the producer's clock and a read pointer ticked by the consumer's clock. Each domain needs to observe the other's pointer to compute fullness or emptiness. Naïvely synchronizing a multi-bit pointer through flip-flop chains creates a metastability hazard: when the source value transitions across multiple bits, the destination clock can sample some bits before they update and others after, latching a value that was never written.

Encode each pointer in Gray code. Each increment flips one bit. A mid-transition sample sees either the pre-increment value or the post-increment value — never a garbage in-between. After two flip-flop synchronizer stages (so metastability has resolved with probability essentially 1), the receiving domain has a correct pointer. This is the textbook async-FIFO architecture, used in PCIe controllers, DDR memory controllers, network MAC interfaces.

Application: FSM state encoding

A finite-state machine's state register transitions through a sequence of values. If the encoding is plain binary and a state transition flips many bits, transient logic hazards can briefly drive the next-state outputs to a wrong value before settling. With Gray coding adjacent reachable states differ in one bit, so the worst-case hazard window is shorter and the FSM's output is more likely to glitch-free. For low-power designs, Gray coding also reduces total bit-flip energy because expected hamming distance per transition is 1 instead of n/2.

This is a softer argument than encoders or FIFOs — modern synchronous FSMs latch state on a clock edge so glitches in the combinational next-state logic don't matter as long as they settle in time. But Gray coding remains common in low-power IoT controllers and in safety-critical FSMs where a single-bit upset is recoverable.

Gray code vs plain binary vs one-hot

	Plain binary	Gray code	One-hot
Bits per state (n states)	⌈log₂ n⌉	⌈log₂ n⌉	n
Hamming distance per step	up to log n	1	2
Glitch on transition	Yes	No	No
Arithmetic friendly	Yes	No — convert first	No
Decoding logic	Trivial	One-XOR per bit	Single 1 detect
Power per transition	~n/2 flips	1 flip	2 flips
Use cases	ALUs, counters, addresses	Encoders, async FIFOs, K-maps	FSM next-state, FPGA
Cyclic safe	No	Yes (reflected Gray)	N/A

Python — Gray counter, conversion, and verification

def bin_to_gray(b):
    return b ^ (b >> 1)

def gray_to_bin(g):
    b = 0
    while g:
        b ^= g
        g >>= 1
    return b

def gray_sequence(n_bits):
    return [bin_to_gray(i) for i in range(1 << n_bits)]

def hamming(a, b):
    return bin(a ^ b).count('1')

# Verify single-bit transitions
seq = gray_sequence(8)
diffs = [hamming(seq[i], seq[(i + 1) % len(seq)]) for i in range(len(seq))]
assert all(d == 1 for d in diffs)
print(f"All {len(seq)} consecutive transitions flip exactly 1 bit, including the wrap-around.")

Verilog — a 4-bit Gray counter

module gray_counter (
    input  wire clk,
    input  wire rst_n,
    output reg  [3:0] gray
);
    reg [3:0] bin;

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            bin  <= 4'b0000;
            gray <= 4'b0000;
        end else begin
            bin  <= bin + 4'b0001;
            gray <= (bin + 4'b0001) ^ ((bin + 4'b0001) >> 1);
        end
    end
endmodule

The synthesis tool maps the XOR to a thin layer of combinational logic between the binary counter and the output register. Total gate count: 4 flip-flops for the binary counter, 4 flip-flops for the Gray output, 3 XOR gates for the conversion. Single-bit transitions on the gray output are guaranteed by construction.

Variants and curiosities

Balanced Gray code

In the standard reflected Gray code, bit 0 changes every step (2ⁿ⁻¹ times per cycle) while the most significant bit changes only twice. A balanced Gray code equalizes the count: every bit changes roughly the same number of times. Useful for FSM encodings where you want uniform switching activity to minimize peak current.

Beckett-Gray codes

Constrained Gray codes where the bit that changes follows a queue discipline (first in, first out). Used in robotic motion-planning and certain combinatorial enumeration problems.

n-ary Gray codes

Generalizations beyond binary: each digit is in 0..m-1, consecutive values differ in exactly one digit by ±1. Used for non-binary encoder disks and combinatorial Gray-code enumeration of tuples.

Snake-in-the-box

A longest cyclic Gray-code path on the n-dimensional hypercube that never revisits a vertex. Active research topic; lengths for n > 8 still aren't known exactly.

Common pitfalls

• Doing arithmetic in Gray. Don't. Convert to binary, add, convert back. The conversion is two cheap XOR-prefix steps; doing addition in Gray directly takes more gates and the result is wrong.
• Assuming all Gray codes are reflected Gray. Reflected Gray is the most common but not unique. Verify your encoder's Gray flavor before designing the decode logic.
• Forgetting the cyclic property only holds when the bit width matches. A 3-bit Gray sequence wraps 100→000 in one bit, but if you treat it as a 4-bit value and pad with a zero, the wrap is no longer single-bit.
• Gray-coding a counter that needs to compare ≤. Gray code is not order-preserving with respect to numeric comparison. Convert to binary before comparing fullness in an async FIFO.
• Believing Gray code eliminates metastability. It doesn't — metastability is a flip-flop phenomenon when the input changes within the setup/hold window. Gray code eliminates one specific consequence (multi-bit ambiguity) but you still need a synchronizer chain for the single-bit transitions.
• Using Gray code outside its niche. If you're not crossing clock domains, reading from a physical sensor, or building a K-map, plain binary is simpler and faster.