RTL Design Patterns · Chapter 1 · Combinational Building Blocks
Encoding Conversions (binary/gray/one-hot)
The same numeric value wants different encodings in different places. Counters increment in binary because addition is natural there, an FSM decodes fastest when its state is one-hot, and a pointer that crosses a clock domain travels as gray code where only one bit changes per step. Every boundary between these forms needs a small combinational converter. Binary to gray is a one-liner, binary to one-hot is a decoder, and one-hot to binary is an encoder. Gray to binary is the one people get wrong. It is a cumulative prefix-XOR scan across the whole word, not a local XOR of adjacent bits, and coding it wrong quietly corrupts a FIFO pointer. This lesson builds every conversion and proves each with the round-trip invariant, in SystemVerilog, Verilog, and VHDL.
Foundation16 min readRTL Design PatternsGray CodeOne-HotBinary EncodingCDCCombinational Logic
Chapter 1 · Section 1.7 · Combinational Building Blocks
1. The Engineering Problem
You are wiring together three blocks that were each designed to be correct on their own. A counter increments a value in binary, because +1 is trivial there. That value indexes a small state machine whose next-state logic is fastest when the state is one-hot — one flop per state, no decode on the critical path. And the same counter is also a FIFO write pointer that must be read by logic running on a different clock, so it has to travel as gray code, where consecutive values differ in exactly one bit and a mid-transition sample can only ever land on the old value or the new one — never on a corrupt in-between.
The value never changes meaning. Five is five in all three encodings. What changes is the bit pattern, and at every boundary between two blocks something must translate one pattern into another: binary into one-hot to drive the select, gray back into binary so the other clock domain can compare pointers, binary into gray to send a pointer across. These translators are tiny combinational circuits — a shift and an XOR here, a decoder there — and precisely because they look trivial, they are a recurring source of bugs.
The dangerous one is gray-to-binary. It is not the mirror of binary-to-gray, and it is not an XOR of neighbouring bits. Do it wrong and nothing complains: the RTL compiles, a width-2 test passes, and then a width-3 async-FIFO read pointer is decoded incorrectly in the write clock domain, the full/empty comparison sees a pointer that never existed, and the FIFO reports phantom full or phantom empty and drops data. The failure shows up as a system corruption three modules away from the four-line converter that caused it. Getting these conversions right — and knowing which one is the trap — is the whole point of this pattern.
// The SAME value, represented three ways at three boundaries:
wire [2:0] bin; // 3-bit binary count — natural for +1 arithmetic
wire [2:0] gray; // gray-coded pointer — one bit changes per step (safe to sample across a clock)
wire [7:0] onehot; // 8-way one-hot select — one line high, fast FSM/mux decode
// Boundaries that MUST convert (this page builds each one):
// bin -> gray : g = b ^ (b >> 1) (an XOR-shift, latch-proof)
// gray -> bin : a PREFIX-XOR SCAN (NOT an adjacent-bit XOR — the trap)
// bin -> onehot : 1 << bin (this IS a decoder — see 1.2)
// onehot -> bin : encode the hot bit's index (this IS an encoder — see 1.3)
//
// Get gray->bin wrong (adjacent XOR) and a width>=3 CDC pointer is silently corrupted:
// the bug passes a width-2 unit test and surfaces as phantom FIFO full/empty. (see §7)2. Mental Model
3. Pattern Anatomy
The family is four converters over one value, plus the single property that makes gray special.
Binary → gray (XOR-shift). The gray code of a binary number is g = b ^ (b >> 1): XOR each bit with the bit above it (the MSB passes through unchanged because there is no bit above it). This is a flat row of two-input XOR gates — combinational, latch-proof, WIDTH gates deep of exactly one level. It is trivial and everyone gets it right.
Gray → binary (prefix-XOR SCAN — the one that matters). The inverse is not symmetric. To recover binary bit i you XOR all gray bits from the MSB down to and including bit i: bin[MSB] = gray[MSB], then bin[i] = bin[i+1] ^ gray[i] walking downward. That recurrence is a prefix (running) XOR — each binary bit accumulates every gray bit above it. Equivalently bin[i] = gray[MSB] ^ gray[MSB-1] ^ … ^ gray[i]. The critical error is to compute bin[i] = gray[i] ^ gray[i+1] (a local, adjacent-bit XOR) and stop — that is the derivative, not the integral, and it only coincides with the scan for the top two bits. The scan is a cumulative fold; the naive version is a local difference. This asymmetry is the reason to internalize the word scan.
Binary → one-hot (a decoder). Setting bit bin of an otherwise-zero word — onehot = 1 << bin — is exactly the decoder of Chapter 1.2: an N-value binary index becomes a 2^N-wide vector with one bit high. Nothing new; it is the decoder, reused as a converter.
One-hot → binary (an encoder). Going back — find which bit is set and output its index — is exactly the encoder of Chapter 1.3: OR-reduce the position bits of the hot line into a binary index, valid only when the input is genuinely one-hot. Feed it a non-one-hot vector and it produces garbage, which is the failure mode you inherit straight from 1.3.
Why gray changes exactly one bit per step. From g = b ^ (b>>1), incrementing b by 1 flips a contiguous run of low binary bits (a carry chain), but the XOR-with-shift folds that run so the gray code differs from its predecessor in a single bit. That single-transition property is why gray is safe to sample across a clock boundary: a receiver latching mid-change can only capture the old code or the new code, never a spurious third value — the guarantee an async-FIFO pointer relies on.
One value, four converters — and the asymmetry that bites
data flowWhere each encoding belongs. Binary lives wherever you do arithmetic or index memory. One-hot lives at fast selects and FSM state registers, where the decode cost is zero and you can afford a flop per state (it stops paying off once the state count is large — the flop cost dominates). Gray lives on any multi-bit value that a different clock must sample: FIFO read/write pointers above all, but also any counter observed across a domain. Put a plain binary counter where a gray pointer was required and a multi-bit sample can land on a value that never existed — the CDC failure the gray encoding exists to prevent.
4. Real RTL Implementation
This is the core of the page. We build the converters — (a) binary↔gray (parameterized bin2gray and gray2bin, the latter as the correct prefix-XOR scan), (b) binary↔one-hot (bin2onehot decoder and onehot2bin encoder), and (c) the wrong gray→binary (naive adjacent-XOR, buggy vs fixed) — each in SystemVerilog, Verilog, and VHDL, with an RTL block and a self-checking testbench. Every testbench is anchored on the round-trip invariant: converting a value out and back must return the original, for all values of a small WIDTH.
All converters here are purely combinational (assign / always_comb / a combinational process), so latch-freedom comes for free as long as every output bit is driven on every path — which a total assign or a fully-populated loop guarantees.
4a. binary↔gray — the XOR-shift and the prefix-XOR scan
Binary→gray is the easy direction: g = b ^ (b>>1), a flat row of XORs, latch-proof by construction. Gray→binary is the direction that matters: the prefix-XOR scan bin[i] = bin[i+1] ^ gray[i], walking from the MSB down. Write the scan, never the adjacent XOR.
module bin2gray #(
parameter int WIDTH = 4
)(
input logic [WIDTH-1:0] bin, // binary value in
output logic [WIDTH-1:0] gray // gray code out
);
// MSB passes through; every other bit XORs with the bit above it.
// A right shift feeds "the bit above", so this is a flat, one-level XOR row.
assign gray = bin ^ (bin >> 1);
endmodule
module gray2bin #(
parameter int WIDTH = 4
)(
input logic [WIDTH-1:0] gray, // gray code in
output logic [WIDTH-1:0] bin // recovered binary out
);
// PREFIX-XOR SCAN, not an adjacent XOR. bin[MSB] = gray[MSB]; each lower bit
// XORs the gray bit with the ALREADY-computed binary bit above it, so bin[i]
// accumulates every gray bit from MSB down to i (bin[i] = ^gray[WIDTH-1:i]).
always_comb begin
bin[WIDTH-1] = gray[WIDTH-1]; // top bit is a pass-through
for (int i = WIDTH-2; i >= 0; i--)
bin[i] = bin[i+1] ^ gray[i]; // running XOR — the SCAN
end
endmoduleThe self-check is the round-trip: for every binary value of a small WIDTH, gray2bin(bin2gray(bin)) must equal bin. Because WIDTH=4 has only 16 values, the sweep is exhaustive. The same loop also asserts the single-bit-change property between consecutive gray codes.
module bin_gray_tb;
localparam int WIDTH = 4;
logic [WIDTH-1:0] bin, gray, back, prev_gray;
int errors = 0;
bin2gray #(.WIDTH(WIDTH)) enc (.bin(bin), .gray(gray));
gray2bin #(.WIDTH(WIDTH)) dec (.gray(gray), .bin(back));
// popcount helper for the single-transition check
function automatic int ones(input logic [WIDTH-1:0] v);
ones = 0;
for (int k = 0; k < WIDTH; k++) ones += v[k];
endfunction
initial begin
prev_gray = '0;
for (int v = 0; v < (1<<WIDTH); v++) begin // EXHAUSTIVE over all values
bin = v[WIDTH-1:0];
#1;
// Round-trip invariant: out-and-back must return the original.
assert (back === bin)
else begin $error("round-trip: bin=%0d back=%0d", bin, back); errors++; end
// Consecutive gray codes must differ in exactly ONE bit (CDC safety).
if (v > 0) assert (ones(gray ^ prev_gray) == 1)
else begin $error("gray step v=%0d not single-bit", v); errors++; end
prev_gray = gray;
end
if (errors == 0) $display("PASS: bin<->gray round-trips and steps by one bit");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleThe Verilog form is identical in intent. The scan uses an integer loop index inside always @(*), and the round-trip check prints PASS/FAIL rather than using assert.
module bin2gray #(
parameter WIDTH = 4
)(
input wire [WIDTH-1:0] bin,
output wire [WIDTH-1:0] gray
);
assign gray = bin ^ (bin >> 1); // XOR-shift, latch-proof
endmodule
module gray2bin #(
parameter WIDTH = 4
)(
input wire [WIDTH-1:0] gray,
output reg [WIDTH-1:0] bin
);
integer i;
always @(*) begin
bin[WIDTH-1] = gray[WIDTH-1]; // MSB pass-through
for (i = WIDTH-2; i >= 0; i = i - 1)
bin[i] = bin[i+1] ^ gray[i]; // running XOR — the SCAN, not adjacent XOR
end
endmodule module bin_gray_tb;
parameter WIDTH = 4;
reg [WIDTH-1:0] bin;
wire [WIDTH-1:0] gray, back;
reg [WIDTH-1:0] prev_gray, diff;
integer v, k, ones, errors;
bin2gray #(.WIDTH(WIDTH)) enc (.bin(bin), .gray(gray));
gray2bin #(.WIDTH(WIDTH)) dec (.gray(gray), .bin(back));
initial begin
errors = 0; prev_gray = {WIDTH{1'b0}};
for (v = 0; v < (1<<WIDTH); v = v + 1) begin // EXHAUSTIVE
bin = v[WIDTH-1:0];
#1;
if (back !== bin) begin // round-trip invariant
$display("FAIL: round-trip bin=%0d back=%0d", bin, back);
errors = errors + 1;
end
if (v > 0) begin // single-bit gray step
diff = gray ^ prev_gray; ones = 0;
for (k = 0; k < WIDTH; k = k + 1) ones = ones + diff[k];
if (ones !== 1) begin
$display("FAIL: gray step v=%0d changed %0d bits", v, ones);
errors = errors + 1;
end
end
prev_gray = gray;
end
if (errors == 0) $display("PASS: bin<->gray round-trips, single-bit steps");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleIn VHDL the scan is a for loop over the vector inside a combinational process; bin2gray is a concurrent XOR of the vector with its own shifted copy. A generic sets the width, matching the Verilog parameter.
library ieee;
use ieee.std_logic_1164.all;
entity bin2gray is
generic ( WIDTH : positive := 4 );
port (
bin : in std_logic_vector(WIDTH-1 downto 0);
gray : out std_logic_vector(WIDTH-1 downto 0)
);
end entity;
architecture rtl of bin2gray is
begin
-- MSB passes through; each lower bit XORs with the bit above it.
gray(WIDTH-1) <= bin(WIDTH-1);
gen : for i in WIDTH-2 downto 0 generate
gray(i) <= bin(i) xor bin(i+1);
end generate;
end architecture;
library ieee;
use ieee.std_logic_1164.all;
entity gray2bin is
generic ( WIDTH : positive := 4 );
port (
gray : in std_logic_vector(WIDTH-1 downto 0);
bin : out std_logic_vector(WIDTH-1 downto 0)
);
end entity;
architecture rtl of gray2bin is
begin
-- PREFIX-XOR SCAN: walk from the MSB down, XOR-ing each gray bit into the
-- accumulated binary bit above it. This is a running fold, NOT a local XOR.
process (gray)
variable acc : std_logic;
begin
acc := gray(WIDTH-1); -- top bit is a pass-through
bin(WIDTH-1) <= acc;
for i in WIDTH-2 downto 0 loop
acc := acc xor gray(i); -- accumulate every gray bit from MSB down
bin(i) <= acc; -- bin(i) = xor of gray(WIDTH-1 downto i)
end loop;
end process;
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity bin_gray_tb is
end entity;
architecture sim of bin_gray_tb is
constant WIDTH : positive := 4;
signal bin, gray, back : std_logic_vector(WIDTH-1 downto 0);
begin
enc : entity work.bin2gray generic map (WIDTH => WIDTH) port map (bin => bin, gray => gray);
dec : entity work.gray2bin generic map (WIDTH => WIDTH) port map (gray => gray, bin => back);
stim : process
variable prev : std_logic_vector(WIDTH-1 downto 0) := (others => '0');
variable diff : std_logic_vector(WIDTH-1 downto 0);
variable cnt : integer;
begin
for v in 0 to (2**WIDTH)-1 loop -- EXHAUSTIVE over all values
bin <= std_logic_vector(to_unsigned(v, WIDTH));
wait for 1 ns;
-- Round-trip invariant: out-and-back returns the original.
assert back = bin
report "bin<->gray round-trip mismatch" severity error;
if v > 0 then -- single-bit gray step
diff := gray xor prev; cnt := 0;
for k in 0 to WIDTH-1 loop
if diff(k) = '1' then cnt := cnt + 1; end if;
end loop;
assert cnt = 1
report "gray step changed more than one bit" severity error;
end if;
prev := gray;
end loop;
report "bin<->gray self-check complete" severity note;
wait;
end process;
end architecture;4b. binary↔one-hot — a decoder and an encoder, reused as converters
Binary→one-hot is the decoder of Chapter 1.2: 1 << bin sets exactly one bit. One-hot→binary is the encoder of Chapter 1.3: OR-reduce the index of the set bit. The encoder is correct only when its input is genuinely one-hot — a valid flag makes that contract explicit.
module bin2onehot #(
parameter int WIDTH = 3, // binary index width
localparam int N = 1 << WIDTH // one-hot width = 2^WIDTH
)(
input logic [WIDTH-1:0] bin, // binary index in
output logic [N-1:0] onehot // one bit high out
);
// Decoder: place a single 1 at position `bin`. Latch-proof — one total assign.
assign onehot = ({{(N-1){1'b0}}, 1'b1}) << bin;
endmodule
module onehot2bin #(
parameter int N = 8, // one-hot width
localparam int WIDTH = $clog2(N) // binary index width
)(
input logic [N-1:0] onehot, // exactly one bit high (invariant)
output logic [WIDTH-1:0] idx, // index of the hot bit
output logic valid // high iff exactly one bit set
);
always_comb begin
idx = '0;
valid = ^onehot & ~|(onehot & (onehot - 1)); // odd parity AND power-of-two => one-hot
for (int i = 0; i < N; i++) // OR-reduce the hot index
if (onehot[i]) idx |= i[WIDTH-1:0];
end
endmoduleThe round-trip here is onehot2bin(bin2onehot(bin)).idx == bin, exhaustive over the binary index. The testbench also drives a non-one-hot vector and checks that valid drops — the encoder's contract from Chapter 1.3.
module bin_onehot_tb;
localparam int WIDTH = 3;
localparam int N = 1 << WIDTH;
logic [WIDTH-1:0] bin, idx;
logic [N-1:0] onehot;
logic valid;
int errors = 0;
bin2onehot #(.WIDTH(WIDTH)) enc (.bin(bin), .onehot(onehot));
onehot2bin #(.N(N)) dec (.onehot(onehot), .idx(idx), .valid(valid));
initial begin
for (int v = 0; v < N; v++) begin // EXHAUSTIVE over the index
bin = v[WIDTH-1:0];
#1;
assert ($onehot(onehot)); // decoder output is one-hot
assert (idx === bin && valid) // round-trip: index recovered
else begin $error("round-trip bin=%0d idx=%0d valid=%b", bin, idx, valid); errors++; end
end
onehot = 8'b0000_0011; #1; // TWO bits set — illegal input
assert (!valid) else begin $error("non-one-hot should not be valid"); errors++; end
if (errors == 0) $display("PASS: bin<->one-hot round-trips; valid guards one-hotness");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleThe Verilog pair mirrors this with reg outputs and a for loop for the encoder; one-hotness is checked with the classic (v & (v-1))==0 && v!=0 reduction since Verilog has no $onehot.
module bin2onehot #(
parameter WIDTH = 3,
parameter N = 8 // = 1<<WIDTH; set by instantiator
)(
input wire [WIDTH-1:0] bin,
output wire [N-1:0] onehot
);
assign onehot = {{(N-1){1'b0}}, 1'b1} << bin; // decoder: one 1 at position bin
endmodule
module onehot2bin #(
parameter N = 8,
parameter WIDTH = 3 // = clog2(N)
)(
input wire [N-1:0] onehot,
output reg [WIDTH-1:0] idx,
output reg valid
);
integer i;
always @(*) begin
idx = {WIDTH{1'b0}};
valid = (onehot != 0) && ((onehot & (onehot - 1)) == 0); // exactly one bit
for (i = 0; i < N; i = i + 1)
if (onehot[i]) idx = idx | i[WIDTH-1:0]; // OR-reduce hot index
end
endmodule module bin_onehot_tb;
parameter WIDTH = 3;
parameter N = 8;
reg [WIDTH-1:0] bin;
wire [N-1:0] onehot;
wire [WIDTH-1:0] idx;
wire valid;
integer v, errors;
bin2onehot #(.WIDTH(WIDTH), .N(N)) enc (.bin(bin), .onehot(onehot));
onehot2bin #(.N(N), .WIDTH(WIDTH)) dec (.onehot(onehot), .idx(idx), .valid(valid));
initial begin
errors = 0;
for (v = 0; v < N; v = v + 1) begin // EXHAUSTIVE over the index
bin = v[WIDTH-1:0];
#1;
if (idx !== bin || !valid) begin // round-trip invariant
$display("FAIL: bin=%0d idx=%0d valid=%b", bin, idx, valid);
errors = errors + 1;
end
end
#1 force onehot = 8'b0000_0011; // TWO bits set (illegal)
#1;
if (valid) begin $display("FAIL: non-one-hot reported valid"); errors = errors + 1; end
if (errors == 0) $display("PASS: bin<->one-hot round-trips; valid guards one-hotness");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleIn VHDL the decoder shifts a '1' left by the integer value of bin; the encoder loops to find the set bit and reports valid from a bit count. to_integer(unsigned(...)) bridges the vector and the loop bound.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity bin2onehot is
generic ( WIDTH : positive := 3 );
port (
bin : in std_logic_vector(WIDTH-1 downto 0);
onehot : out std_logic_vector((2**WIDTH)-1 downto 0)
);
end entity;
architecture rtl of bin2onehot is
begin
-- Decoder: a single '1' shifted to position bin (a power-of-two mask).
process (bin)
variable m : unsigned((2**WIDTH)-1 downto 0);
begin
m := (others => '0');
m(to_integer(unsigned(bin))) := '1';
onehot <= std_logic_vector(m);
end process;
end architecture;
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity onehot2bin is
generic ( N : positive := 8; WIDTH : positive := 3 ); -- WIDTH = clog2(N)
port (
onehot : in std_logic_vector(N-1 downto 0);
idx : out std_logic_vector(WIDTH-1 downto 0);
valid : out std_logic
);
end entity;
architecture rtl of onehot2bin is
begin
process (onehot)
variable acc : unsigned(WIDTH-1 downto 0);
variable cnt : integer;
begin
acc := (others => '0'); cnt := 0;
for i in 0 to N-1 loop
if onehot(i) = '1' then
acc := acc or to_unsigned(i, WIDTH); -- OR-reduce the hot index
cnt := cnt + 1;
end if;
end loop;
idx <= std_logic_vector(acc);
valid <= '1' when cnt = 1 else '0'; -- exactly one bit set
end process;
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity bin_onehot_tb is
end entity;
architecture sim of bin_onehot_tb is
constant WIDTH : positive := 3;
constant N : positive := 8;
signal bin : std_logic_vector(WIDTH-1 downto 0);
signal onehot : std_logic_vector(N-1 downto 0);
signal idx : std_logic_vector(WIDTH-1 downto 0);
signal valid : std_logic;
begin
enc : entity work.bin2onehot generic map (WIDTH => WIDTH)
port map (bin => bin, onehot => onehot);
dec : entity work.onehot2bin generic map (N => N, WIDTH => WIDTH)
port map (onehot => onehot, idx => idx, valid => valid);
stim : process
begin
for v in 0 to N-1 loop -- EXHAUSTIVE over the index
bin <= std_logic_vector(to_unsigned(v, WIDTH));
wait for 1 ns;
-- Round-trip invariant: recovered index equals the original.
assert idx = bin and valid = '1'
report "bin<->one-hot round-trip mismatch" severity error;
end loop;
report "bin<->one-hot self-check complete" severity note;
wait;
end process;
end architecture;4c. The wrong gray→binary — buggy adjacent-XOR vs fixed prefix-XOR scan
This is the signature bug, shown here as buggy vs fixed RTL in each language and dramatized in §7. The buggy converter computes each binary bit as an XOR of adjacent gray bits (bin[i] = gray[i] ^ gray[i+1]) instead of the cumulative scan. It is correct for the top two bits, so a width-2 test passes — and wrong for every bit below, so a width-3 pointer is silently corrupted.
// BUGGY: each bit is a LOCAL XOR of adjacent gray bits, with no accumulation.
// Matches the scan only for the top two bits => passes width-2, fails width>=3.
module gray2bin_bad #(parameter int WIDTH = 4)(
input logic [WIDTH-1:0] gray,
output logic [WIDTH-1:0] bin
);
always_comb begin
bin[WIDTH-1] = gray[WIDTH-1];
for (int i = WIDTH-2; i >= 0; i--)
bin[i] = gray[i] ^ gray[i+1]; // WRONG: adjacent bits, not the running XOR
end
endmodule
// FIXED: accumulate — each bit XORs gray[i] with the ALREADY-computed bin[i+1].
module gray2bin_good #(parameter int WIDTH = 4)(
input logic [WIDTH-1:0] gray,
output logic [WIDTH-1:0] bin
);
always_comb begin
bin[WIDTH-1] = gray[WIDTH-1];
for (int i = WIDTH-2; i >= 0; i--)
bin[i] = bin[i+1] ^ gray[i]; // RIGHT: prefix-XOR SCAN
end
endmodule module gray2bin_bug_tb;
localparam int WIDTH = 4; // >=3 so the bug is visible
logic [WIDTH-1:0] bin, gray, back;
int errors = 0;
// bin2gray reused as the reference forward converter.
bin2gray #(.WIDTH(WIDTH)) enc (.bin(bin), .gray(gray));
// Point at gray2bin_good to PASS; at gray2bin_bad to watch the round-trip break.
gray2bin_good #(.WIDTH(WIDTH)) dec (.gray(gray), .bin(back));
initial begin
for (int v = 0; v < (1<<WIDTH); v++) begin // EXHAUSTIVE
bin = v[WIDTH-1:0];
#1;
assert (back === bin) // round-trip catches the bug
else begin $error("round-trip v=%0d back=%0d (adjacent-XOR bug?)", v, back); errors++; end
end
if (errors == 0) $display("PASS: gray2bin round-trips for all values");
else $display("FAIL: %0d mismatches — gray2bin is not a scan", errors);
$finish;
end
endmoduleThe Verilog buggy/fixed pair is the same story with reg outputs. The whole difference is one operand: gray[i+1] (adjacent, wrong) versus bin[i+1] (accumulated, right).
// BUGGY: local XOR of adjacent gray bits — no accumulation.
module gray2bin_bad #(parameter WIDTH = 4)(
input wire [WIDTH-1:0] gray,
output reg [WIDTH-1:0] bin
);
integer i;
always @(*) begin
bin[WIDTH-1] = gray[WIDTH-1];
for (i = WIDTH-2; i >= 0; i = i - 1)
bin[i] = gray[i] ^ gray[i+1]; // WRONG operand: adjacent gray bit
end
endmodule
// FIXED: running XOR — accumulate into the computed bin bit above.
module gray2bin_good #(parameter WIDTH = 4)(
input wire [WIDTH-1:0] gray,
output reg [WIDTH-1:0] bin
);
integer i;
always @(*) begin
bin[WIDTH-1] = gray[WIDTH-1];
for (i = WIDTH-2; i >= 0; i = i - 1)
bin[i] = bin[i+1] ^ gray[i]; // RIGHT: prefix-XOR SCAN
end
endmodule module gray2bin_bug_tb;
parameter WIDTH = 4;
reg [WIDTH-1:0] bin;
wire [WIDTH-1:0] gray, back;
integer v, errors;
bin2gray #(.WIDTH(WIDTH)) enc (.bin(bin), .gray(gray));
// Bind to gray2bin_good to PASS; to gray2bin_bad to observe the corruption.
gray2bin_good #(.WIDTH(WIDTH)) dec (.gray(gray), .bin(back));
initial begin
errors = 0;
for (v = 0; v < (1<<WIDTH); v = v + 1) begin // EXHAUSTIVE
bin = v[WIDTH-1:0];
#1;
if (back !== bin) begin // round-trip invariant
$display("FAIL: v=%0d back=%0d (gray2bin not a scan)", v, back);
errors = errors + 1;
end
end
if (errors == 0) $display("PASS: gray2bin round-trips for all values");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleIn VHDL the same bug is XOR-ing gray(i) with gray(i+1) instead of accumulating into a running variable. The fixed version threads the accumulator; the buggy one reads a neighbour and forgets everything above it.
library ieee;
use ieee.std_logic_1164.all;
-- BUGGY: bin(i) = gray(i) xor gray(i+1) — a local difference, no running fold.
entity gray2bin_bad is
generic ( WIDTH : positive := 4 );
port ( gray : in std_logic_vector(WIDTH-1 downto 0);
bin : out std_logic_vector(WIDTH-1 downto 0) );
end entity;
architecture rtl of gray2bin_bad is
begin
bin(WIDTH-1) <= gray(WIDTH-1);
gen : for i in WIDTH-2 downto 0 generate
bin(i) <= gray(i) xor gray(i+1); -- WRONG: adjacent gray bits
end generate;
end architecture;
library ieee;
use ieee.std_logic_1164.all;
-- FIXED: accumulate every gray bit from the MSB down into a running XOR.
entity gray2bin_good is
generic ( WIDTH : positive := 4 );
port ( gray : in std_logic_vector(WIDTH-1 downto 0);
bin : out std_logic_vector(WIDTH-1 downto 0) );
end entity;
architecture rtl of gray2bin_good is
begin
process (gray)
variable acc : std_logic;
begin
acc := gray(WIDTH-1);
bin(WIDTH-1) <= acc;
for i in WIDTH-2 downto 0 loop
acc := acc xor gray(i); -- RIGHT: prefix-XOR SCAN
bin(i) <= acc;
end loop;
end process;
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity gray2bin_bug_tb is
end entity;
architecture sim of gray2bin_bug_tb is
constant WIDTH : positive := 4;
signal bin, gray, back : std_logic_vector(WIDTH-1 downto 0);
begin
enc : entity work.bin2gray generic map (WIDTH => WIDTH) port map (bin => bin, gray => gray);
-- Bind to gray2bin_good to PASS; to gray2bin_bad to observe the corruption.
dec : entity work.gray2bin_good generic map (WIDTH => WIDTH) port map (gray => gray, bin => back);
stim : process
begin
for v in 0 to (2**WIDTH)-1 loop -- EXHAUSTIVE
bin <= std_logic_vector(to_unsigned(v, WIDTH));
wait for 1 ns;
assert back = bin -- round-trip invariant
report "gray2bin round-trip mismatch — not a scan" severity error;
end loop;
report "gray2bin self-check complete" severity note;
wait;
end process;
end architecture;Across all three languages the lesson is one sentence: gray→binary is a cumulative prefix-XOR scan — accumulate every gray bit from the MSB down — and the round-trip bin→gray→bin == bin is the test that catches it the moment you write the adjacent-XOR by mistake.
5. Verification Strategy
Every converter is combinational, so its correctness is a function table, and for a small WIDTH the table is small enough to check exhaustively. The single self-check that dominates the whole page is the round-trip invariant:
Convert a value out and back, and you must recover the original — exactly, for every value.
gray2bin(bin2gray(bin)) == binandonehot2bin(bin2onehot(bin)).idx == bin, swept over all values of a smallWIDTH.
Everything below is that invariant made checkable, and it maps directly onto the testbenches in §4.
- Round-trip, exhaustive (self-checking). For
WIDTH = 4there are only 16 binary values; loop over all of them, convertbin→gray→bin, and assert the recovered value equals the original. This is complete, not sampled — the whole function table, both directions, proven in one loop. The threebin_graytestbenches do exactly this: SVassert (back === bin), Verilogif (back !== bin) $display("FAIL…"), VHDLassert back = bin report … severity error. The same structure provesbin→one-hot→binin thebin_onehottestbenches. - The round-trip is what catches the scan bug. The naive adjacent-XOR gray→binary matches the correct scan only for the top two bits. At
WIDTH = 2the round-trip passes; atWIDTH ≥ 3it fails on the lower bits. So run the round-trip atWIDTH = 2, 3, 4— the failure appears exactly when width crosses 3, which is the fingerprint of "gray→binary was coded as a local op, not a scan" (the §7 bug, and the §4c buggy variant). - Gray's single-bit-change property. Beyond the round-trip, verify the property that makes gray worth using: between consecutive values, the gray codes differ in exactly one bit. Compute the popcount of
gray[v] ^ gray[v-1]for every step and assert it equals 1 (theones(...)/popcount check in thebin_graytestbenches). A converter that round-trips but does not step by one bit is not producing gray code — and would be unsafe for CDC. - One-hot output is genuinely one-hot; the encoder guards it. For
bin→one-hot, assert$onehot(onehot)(SV) or(v & (v-1))==0 && v!=0(Verilog) or a bit count == 1 (VHDL) on the decoder's output. Forone-hot→binary, drive a non-one-hot vector (two bits set) and assert the encoder'svaliddrops — the contract inherited from Chapter 1.3. Feeding a multi-hot input to an encoder produces a garbage index, andvalidis what surfaces it. - Corner values and parameter-generic runs. Include all-zeros and all-ones binary; for gray,
0and the top code; for one-hot, index 0 and indexN-1. Then re-run the exhaustive round-trip for several widths (WIDTH = 2, 3, 4, 5) — a parameterized converter must be verified generic, not assumed generic, and the scan bug specifically hides at small widths. - Expected waveform. These converters have no clock, so "correct" is immediate: as
binsteps0 → 1 → 2 → …,graytracks it changing exactly one bit per step,onehotshows a single high line marching across, andback(the round-tripped value) tracksbincombinationally. The visual signature of the scan bug is abackthat diverges frombinon the lower bits once the value exceeds the width-2 range.
6. Common Mistakes
Gray→binary as an adjacent-bit XOR instead of the prefix-XOR scan. The signature error. Recovering binary from gray means XOR-ing all gray bits from the MSB down to the current bit (bin[i] = bin[i+1] ^ gray[i], a running fold). Writing bin[i] = gray[i] ^ gray[i+1] (a local, adjacent XOR) is right only for the top two bits and wrong for every bit below — so it passes a width-2 test and silently corrupts width ≥ 3. The tell is a converter that "works in the small test" and fails in the real design; the fix is to accumulate, threading the computed binary bit above into each new bit. (Full post-mortem in §7; buggy-vs-fixed RTL for all three HDLs in §4c.)
Feeding a non-one-hot vector to the one-hot→binary encoder. The encoder assumes exactly one bit is set; give it zero bits (index undefined) or two bits (index is the OR of two positions — a value equal to neither) and it emits garbage with no complaint unless you check. This is the Chapter 1.3 failure inherited verbatim: always pair the encoder with a valid output (exactly-one-bit-set) and assert it, and make whatever drives the vector guarantee one-hotness.
Using multi-bit binary where a gray pointer was required for CDC. A plain binary counter sampled by a different clock can be caught mid-increment, when several bits are flipping at once, and the receiver may latch a value that is neither the old nor the new count — a phantom pointer. Gray exists precisely to prevent this: only one bit changes per step, so a mid-transition sample is always either the old or the new value. Any multi-bit value crossing a clock domain (FIFO pointers above all) must travel as gray, not binary.
Ignoring one-hot's flop cost for large state counts. One-hot buys zero-logic decode by spending one flop per value. That is a bargain for a handful of states or select lines, and a poor trade for many: a 64-state FSM in one-hot is 64 flops versus 6 in binary, and the wide state register can hurt routing and power. Match the encoding to the count — one-hot for small, hot-path selects and modest FSMs; binary when the value space is large.
7. DebugLab
The FIFO that reported full when it was nearly empty — a gray→binary scan coded as an adjacent XOR
The engineering lesson: gray↔binary is a scan, not a local operation, and the cost of getting it wrong is paid far from the converter. Binary→gray is a symmetric-looking one-liner, which tempts you to write gray→binary as its mirror — but the inverse is a cumulative fold, and the adjacent-XOR shortcut is right for exactly the two bits a small test exercises, so it ships and then corrupts a real CDC pointer as a system-level phantom-full/empty failure. Two habits make it impossible, and they are identical across SystemVerilog, Verilog, and VHDL: write gray→binary as an accumulating prefix-XOR scan (thread the computed binary bit above into each new bit), and prove every converter with the round-trip invariant swept over all values at width ≥ 3, where the difference between the scan and the local XOR first becomes visible.
8. Interview Q&A
9. Exercises
Design and reasoning exercises — no syntax drills. Each rehearses "which encoding, and is this converter a scan or a local op?"
Exercise 1 — Derive gray→binary from scratch
Starting only from g = b ^ (b>>1), derive the inverse. Show that bin[MSB] = gray[MSB] and, by substituting downward, that bin[i] = bin[i+1] ^ gray[i]. Then unroll that recurrence to prove bin[i] = gray[MSB] ^ gray[MSB-1] ^ … ^ gray[i] (a prefix XOR). Finally, write out the 4-bit conversion for gray = 4'b1110 two ways — with the correct scan and with the naive bin[i] = gray[i] ^ gray[i+1] — and identify exactly which bits disagree and why.
Exercise 2 — Predict where the adjacent-XOR bug hides
An engineer's gray2bin uses the adjacent-XOR form. State the smallest WIDTH at which a round-trip test (bin→gray→bin) fails, and prove why it passes at every smaller width. Then explain, for a depth-8 async FIFO (pointer width 3), why the failure surfaces as phantom full/empty in the opposite clock domain rather than as an obvious error at the converter — and what single test, run at what width, would have caught it before tape-out.
Exercise 3 — Pick the encoding for each boundary
For each location, name the right encoding (binary / gray / one-hot) and the converter (if any) needed to get there from a binary counter, in one line: (a) the increment logic of the counter itself; (b) the read pointer sampled by the write clock in an async FIFO; (c) the select line of a fast 8:1 output mux driven by the counter's low 3 bits; (d) the current-state test in a 5-state control FSM on the critical path; (e) the state register of a 128-state descriptor FSM where flop count is the constraint. Justify (b) and (e) specifically.
Exercise 4 — One-hot round-trip and its guard
You build bin2onehot (decoder) and onehot2bin (encoder) and the round-trip bin→onehot→bin passes exhaustively. A colleague then wires the output of an arbiter (which is supposed to be one-hot but can momentarily assert two grants) into onehot2bin. Describe what index the encoder produces when two bits are set, why the round-trip test never exercised this case, and what one output signal plus one assertion you add so the illegal input is caught rather than silently decoded.
10. Related Tutorials
Direct prerequisites in RTL Design Patterns:
- Decoders — Chapter 1.2; binary→one-hot is a decoder (
1<<b) — this page reuses it as a converter. - Encoders — Chapter 1.3; one-hot→binary is an encoder, and its "valid only when one-hot" contract is the failure mode this page inherits.
- Priority Encoders — Chapter 1.4; what to reach for when the vector is not guaranteed one-hot and you need "the highest set bit" instead of "the one set bit."
Continue in RTL Design Patterns (forward links unlock as they ship):
- Gray Counters — Chapter 3; a counter that increments in gray, using the
bin2gray/gray2binconverters built here. - Gray Pointer Synchronization — Chapter 11; crossing a gray pointer through a two-flop synchronizer — the CDC step the §7 bug lives inside.
- Asynchronous FIFO — Chapter 11; the full dual-clock FIFO where gray pointers and this exact gray→binary conversion decide full/empty.
- FSM State Encoding — Chapter 4; choosing binary vs one-hot (vs gray) for a state register — the encoding trade-off applied to control.
Backward / method:
- The RTL Design Mindset — Chapter 0.2; the Interface → State → Datapath → Control → Verification lenses — an encoding converter is pure datapath glue.
- What Is an RTL Design Pattern? — Chapter 0.1; why a converter earns the name "pattern" — a recurring boundary, a reusable form, a synthesis reality, and a signature failure.
- Multiplexers (2:1, N:1, one-hot) — Chapter 1.1; the one-hot select a
bin2onehotconverter feeds, and where one-hot vs binary select is decided.
Verilog v1 prerequisites (the grammar these converters transcribe into):
- Bitwise Operators — the XOR that builds both gray conversions and the AND/OR of the one-hot forms.
- Shift Operators — the
b >> 1in binary→gray and the1 << bdecoder in binary→one-hot. - Continuous Assignments — the dataflow
assignform of the latch-proof converters (gray = bin ^ (bin>>1)). - Case Statements — the alternative structure for a small hand-written decoder/encoder, and where completeness keeps it latch-free.
- Generate Blocks — the elaboration-time replication used to parameterize the per-bit scan and the one-hot AND-OR across
WIDTH.
11. Summary
- One value, three encodings, chosen for the job. Binary is compact and arithmetic-friendly (counters, ALU, indexing); one-hot spends a flop per value for zero-logic decode (fast selects, small FSMs); gray changes exactly one bit per step, the only encoding safe to sample across a clock domain (FIFO pointers). A value legitimately changes costume as it moves through a design.
- Most converters are obvious one-liners. Binary→gray is
b ^ (b>>1)(a flat XOR row); binary→one-hot is a decoder (1<<b, Chapter 1.2); one-hot→binary is an encoder (Chapter 1.3, valid only when one-hot). All latch-proof by construction. - Gray→binary is the exception — a prefix-XOR SCAN. Each binary bit is the XOR of all gray bits from the MSB down (
bin[i] = bin[i+1] ^ gray[i]), an accumulating fold — not an XOR of adjacent bits. The adjacent-XOR shortcut is right only for the top two bits, so it passes a width-2 test and silently corrupts width ≥ 3. - The round-trip invariant is the killer self-check.
bin→gray→bin == binandbin→one-hot→bin == bin, swept exhaustively over a small width, prove the whole function table both ways — and catch the scan bug the moment you cross width 3. Also verify gray's single-bit step (popcount == 1) and the encoder'svalidon a non-one-hot input. - Gray↔binary is a scan, and its bug is a system failure. Coded as a local XOR, the converter passes a small unit test and then corrupts an async-FIFO read pointer decoded in the write domain — phantom full/empty, lost data, far from the four-line bug (§7). Write the scan; prove it with the round-trip at width ≥ 3. Every converter here is built and self-check-verified in SystemVerilog, Verilog, and VHDL.