Digital Electronics · Topic 28
Gray Code —
Binary Conversion & Async FIFO
Binary vs Gray Code — Bit Transitions at Each Count Step
What Is Gray Code?
Gray code (also called reflected binary code) is a sequence of binary numbers where adjacent values differ by exactly one bit. Invented by Frank Gray at Bell Labs in 1947, it was originally designed to reduce errors in mechanical encoders — if the reading head is between two positions, only one bit is ambiguous.
The key property: unit distance — any two consecutive Gray code values (including the wraparound from the last code back to the first) differ in exactly one bit position.
4-Bit Binary vs Gray Code Truth Table
| Decimal | Binary (B3B2B1B0) | Gray (G3G2G1G0) | Bits Changed from Previous |
|---|---|---|---|
| 0 | 0000 | 0000 | — |
| 1 | 0001 | 0001 | 1 (G0) |
| 2 | 0010 | 0011 | 1 (G1) |
| 3 | 0011 | 0010 | 1 (G0) |
| 4 | 0100 | 0110 | 1 (G2) |
| 5 | 0101 | 0111 | 1 (G0) |
| 6 | 0110 | 0101 | 1 (G1) |
| 7 | 0111 | 0100 | 1 (G0) |
| 8 | 1000 | 1100 | 1 (G3) ← binary changes 4 bits! |
| 9 | 1001 | 1101 | 1 (G0) |
| 10 | 1010 | 1111 | 1 (G1) |
| 11 | 1011 | 1110 | 1 (G0) |
| 12 | 1100 | 1010 | 1 (G2) |
| 13 | 1101 | 1011 | 1 (G0) |
| 14 | 1110 | 1001 | 1 (G1) |
| 15 | 1111 | 1000 | 1 (G0) |
Binary-to-Gray Conversion Formula
The conversion is simple: XOR each binary bit with the bit one position above it. The MSB stays the same.
Formula & Example
Binary to Gray: G[N-1] = B[N-1] // MSB is unchanged G[i] = B[i+1] ^ B[i] // each bit XOR'd with bit above Example: Binary 1011 → Gray B = 1 0 1 1 ↓ ↓ ↓ ↓ G3 = B3 = 1 G2 = B3 ^ B2 = 1 ^ 0 = 1 G1 = B2 ^ B1 = 0 ^ 1 = 1 G0 = B1 ^ B0 = 1 ^ 1 = 0 G = 1 1 1 0 → decimal 11 ✓ (check table above) Verilog one-liner: assign gray = (binary >> 1) ^ binary;
Gray-to-Binary Conversion
The reverse requires a cascade — each binary bit depends on all Gray bits above it:
Formula & Example
Gray to Binary: B[N-1] = G[N-1] // MSB is unchanged B[i] = B[i+1] ^ G[i] // cascading XOR Example: Gray 1110 → Binary G = 1 1 1 0 B3 = G3 = 1 B2 = B3 ^ G2 = 1 ^ 1 = 0 B1 = B2 ^ G1 = 0 ^ 1 = 1 B0 = B1 ^ G0 = 1 ^ 0 = 1 B = 1 0 1 1 → decimal 11 ✓
Verilog Implementation
SystemVerilog — Binary↔Gray converters
module gray_code #(parameter N = 4) ( input logic [N-1:0] binary, output logic [N-1:0] gray, input logic [N-1:0] gray_in, output logic [N-1:0] binary_out ); // Binary → Gray: one-liner (concurrent, combinational) assign gray = (binary >> 1) ^ binary; // Gray → Binary: cascade XOR (needs loop — each bit depends on previous) always_comb begin binary_out[N-1] = gray_in[N-1]; for (int i = N-2; i >= 0; i--) binary_out[i] = binary_out[i+1] ^ gray_in[i]; end endmodule
Why Async FIFOs Use Gray Code Pointers
The core problem: In an async FIFO, the write pointer (write clock domain) must be passed to the read clock domain, and vice versa. The transfer uses a 2-FF synchronizer. If the pointer is binary and changes multiple bits simultaneously (e.g., 0111→1000), the synchronizer may sample mid-transition and see a garbage value like 1111 or 0000 — a corrupt pointer that causes incorrect full/empty detection.
Verilog — Async FIFO pointer with Gray code
module async_fifo #(parameter DEPTH = 16, DW = 8) ( input wr_clk, wr_en, input rd_clk, rd_en, input [DW-1:0] wr_data, output [DW-1:0] rd_data, output full, empty ); localparam AW = $clog2(DEPTH); logic [DW-1:0] mem [0:DEPTH-1]; // Binary pointers (one extra bit for full/empty detection) logic [AW:0] wr_ptr_bin, rd_ptr_bin; // Gray code versions logic [AW:0] wr_ptr_gray, rd_ptr_gray; // Synchronized gray pointers (2-FF) logic [AW:0] wr_gray_sync1, wr_gray_sync2; logic [AW:0] rd_gray_sync1, rd_gray_sync2; // Convert binary → Gray before crossing clock domain assign wr_ptr_gray = (wr_ptr_bin >> 1) ^ wr_ptr_bin; assign rd_ptr_gray = (rd_ptr_bin >> 1) ^ rd_ptr_bin; // 2-FF synchronizer: pass GRAY pointer to opposite domain always @(posedge rd_clk) {rd_gray_sync2, rd_gray_sync1} <= {wr_gray_sync1, wr_ptr_gray}; always @(posedge wr_clk) {wr_gray_sync2, wr_gray_sync1} <= {rd_gray_sync1, rd_ptr_gray}; // Full: wr_gray MSB and MSB-1 differ from synchronized rd_gray, rest same assign full = (wr_ptr_gray == {~wr_gray_sync2[AW:AW-1], wr_gray_sync2[AW-2:0]}); // Empty: wr synchronized gray == rd gray assign empty = (rd_ptr_gray == rd_gray_sync2); endmodule
Why it's safe: Gray code guarantees only one bit changes at a time. Even if the synchronizer samples the pointer during a transition, it sees either the old value or the new value — never a corrupt intermediate with multiple bits in unknown states. The FIFO may appear one entry fuller or emptier than reality, but it never over-fills or under-empties fatally.
Other Applications of Gray Code
| Application | Why Gray Code? |
|---|---|
| Rotary encoders (optical, magnetic) | Physical alignment tolerances — only one track changes at each boundary, avoiding momentary invalid readings |
| Karnaugh maps (K-maps) | Adjacent cells differ by one variable — Gray code ordering makes prime implicants form rectangular groups |
| Async FIFO pointers | Safe clock-domain crossing — only 1 bit changes, 2-FF synchronizer sees valid pointer even mid-transition |
| Error-correcting codes | Hamming distance of 1 between adjacent codewords limits error propagation |
| BCH code construction | Gray code sequences simplify certain algebraic constructions over GF(2) |
| Signal-Gray ADC | Flash ADC thermometer code → Gray code → binary reduces glitches in output |