Binary to
Gray Code

1. The Multi-Bit Glitch Problem

Standard binary counting has a silent hazard. When a counter increments from 7 to 8, the value transitions from 0111 to 1000 — four bits change simultaneously. In real silicon, those four wires do not switch at exactly the same picosecond. For a brief window, the bus carries values like 0110, 0100, or 1100 — none of which are valid states in the intended sequence.

In a single clock domain this is usually harmless; combinational logic settles before the next edge. But when this multi-bit bus crosses a clock domain boundary, a receiving flip-flop can sample the bus mid-transition and capture one of those illegal intermediate values. The result is a corrupted address, counter, or pointer that can cause a FIFO to overwrite data, underflow, or corrupt an entire transfer.

2. Gray Code Property

Named after Frank Gray, Gray code (also called reflected binary code) is a sequence where every pair of adjacent values differs in exactly one bit position. This is the unit-distance property.

The highlighted row shows the 7→8 transition. Binary flips 4 bits; Gray code flips just 1. This is true at every counter step, including the rollover from 2ⁿ−1 back to 0.

3. Binary-to-Gray Conversion

The conversion from binary B to Gray code G uses only XOR gates — one per bit except the MSB. The formula applies bitwise from MSB to LSB:

RTL Implementation — Binary to Gray

module bin2gray #(
  parameter WIDTH = 8
)(
  input  logic [WIDTH-1:0] bin,
  output logic [WIDTH-1:0] gray
);
  // G = B ^ (B >> 1) — purely combinational, no clock needed
  assign gray = bin ^ (bin >> 1);

endmodule

4. Gray-to-Binary Conversion

The reverse operation is iterative — each binary bit depends on the result above it, making it a cascaded XOR chain from the MSB downward:

RTL Implementation — Gray to Binary

module gray2bin #(
  parameter WIDTH = 8
)(
  input  logic [WIDTH-1:0] gray,
  output logic [WIDTH-1:0] bin
);
  always_comb begin
    for (int i = 0; i < WIDTH; i++) begin
      // bin[i] = XOR of all gray bits from MSB down to i
      bin[i] = ^(gray >> i);
    end
  end
endmodule

5. Async FIFO Pointer Application

The most critical use of Gray code in VLSI is in asynchronous FIFO write and read pointer synchronization. The write pointer increments in the write clock domain and must be read in the read clock domain to determine if the FIFO is full or empty — and vice versa.

// Async FIFO pointer synchronization pattern
module async_fifo_ptr #(
  parameter DEPTH = 16,
  parameter AW    = 4   // log2(DEPTH)
)(
  input  logic        wclk, wrst_n, winc,
  input  logic        rclk, rrst_n,
  output logic [AW:0] wptr_gray,  // crosses to read domain
  output logic [AW:0] rptr_gray   // crosses to write domain
);
  logic [AW:0] wptr_bin, rptr_bin;

  // Write pointer: binary counter + Gray encode
  always_ff @(posedge wclk or negedge wrst_n)
    if (!wrst_n) wptr_bin <= '0;
    else if (winc) wptr_bin <= wptr_bin + 1;

  assign wptr_gray = wptr_bin ^ (wptr_bin >> 1);

  // wptr_gray synchronizes safely into rclk with 2-FF synchronizer
  // because only 1 bit changes per increment
endmodule

• Write pointer (binary) is XOR-shifted into Gray before crossing the domain
• The Gray pointer passes through a 2-FF synchronizer in the receiving domain
• Only one bit can change per clock, so metastability affects at most one bit — the pointer is still ±1 from the true value, not an arbitrary garbage address
• After synchronization, the receiving domain decodes Gray back to binary for address comparison and empty/full logic

6. Other Applications

• Karnaugh Maps: K-map axes are Gray-code ordered so adjacent cells differ by one variable, enabling logical grouping and minimal SOP/POS expressions
• Rotary Encoders: Position sensors use Gray code to avoid spurious counts when the mechanical disk is between positions
• ADC flash converters: Thermometer-to-binary conversion uses Gray encoding to reduce glitches from simultaneous comparator transitions
• Error detection: Single-bit errors in a Gray counter produce at most an off-by-one output — easier to detect and tolerate

Frequently Asked Questions

Gray Code in Async FIFO Design — The Full Picture

The asynchronous FIFO (First-In First-Out) is where Gray code matters most in professional RTL design. An async FIFO has two independent clock domains: the write domain (producer, drives wptr) and the read domain (consumer, drives rptr). The FULL flag is generated in the write domain by comparing wptr with rptr; the EMPTY flag is generated in the read domain by the reverse comparison. Since wptr must be readable in the read domain and rptr must be readable in the write domain, both pointers must cross clock domain boundaries.

If the pointers were standard binary, crossing them would be dangerous. Consider a 4-bit pointer transitioning from 0111 (7) to 1000 (8): all four bits change simultaneously. If the receiving domain samples this pointer mid-transition due to its own clock edge, it might see 1010, 0100, or any other intermediate value — none of which represent valid FIFO pointer states. The FIFO would compute incorrect fill level, generate spurious FULL or EMPTY flags, and potentially overflow or underflow.

Gray code solves this cleanly. The 4-bit Gray code for 7 is 0100; for 8 it is 1100. Only one bit (the MSB) changes. When the receiving domain samples during this single-bit transition, it captures either 0100 (7) or 1100 (8) — both of which are valid pointer values. The off-by-one error is acceptable because FIFO margins are designed to tolerate it: the FULL flag is asserted one entry early (conservatively), and the EMPTY flag is asserted one entry late. This intentional conservatism prevents overflow and underflow while accommodating the inherent latency of the 2-FF synchronizer that crosses the pointer.

In RTL implementation, the write pointer and read pointer are maintained as binary counters (binary arithmetic is simpler) and converted to Gray code only at the CDC crossing point. The typical pattern: wptr_gray = wptr ^ (wptr >> 1) in the write domain, then synchronized into the read domain via a 2-FF synchronizer. The read domain uses the synchronized Gray-coded write pointer for EMPTY detection. The same process runs in the other direction for FULL detection. This "count in binary, cross in Gray, compare in Gray" pattern is the VLSI industry standard for async FIFO design and appears in virtually every production SoC with clock domain crossings.

An important subtlety: the Gray-to-binary conversion for comparison must also be done correctly. When comparing the synchronized write pointer (Gray code in the read domain) to the read pointer (also in Gray code in the read domain), the comparison can be done directly in Gray code — if wptr_gray_sync == rptr_gray, the FIFO is empty. This avoids the iterative Gray-to-binary conversion chain entirely, saving both area and critical path delay. The standard Clifford Cummings async FIFO design uses this direct Gray-code comparison, and understanding this optimization distinguishes candidates who have implemented async FIFOs from those who have only read about them.