Gray code counter

This page draws the counter's side only. The crossing itself is the two-flop synchronizer's, one per bit of g2 g1 g0, each on the clock of the domain that reads the count.

How it works, edge by edge

Follow the rows of the waveform: b2 b1 b0 is the binary count, most significant bit first, and g2 g1 g0 its Gray code. rst_n is low at tick 0, and all six rows are 0 before any edge has arrived: the reset is asynchronous. Its release at tick 1 changes nothing by itself.

At the first edge, tick 4, the count becomes 1: b2 b1 b0 read 001, and so do g2 g1 g0. At the edge at 12 the count is 2, and two b rows move, b1 rising as b0 falls, against one g row, g1. At the edge at 20, 2 to 3, b0 rises and g0 falls.

The fourth edge, tick 28, is the one the Gray code is for. From 3 to 4 the binary count goes 011 to 100, and all three b rows move in the same tick: b2 rises as b1 and b0 fall. The Gray code goes 010 to 110, and only g2 moves. However many bits the binary count changes at a step, the Gray code changes one.

Both registers load at the same edge, so the g rows move in the same tick as the b rows, and the g2 row is the b2 row tick for tick: the top bit of a Gray code is the top bit of the count.

The wrap carries on to 7 and back. At the edges at 36, 44 and 52 the count goes to 5, 6 and 7, and g2 g1 g0 read 111, 101 and 100, one row moving at each. At the edge at 60, 7 wraps to 0: b2 b1 b0 go 111 to 000, all three rows falling at once, and g2 g1 g0 go 100 to 000, only g2 falling. The wrap is one step like any other.

Reset counts to 5, where b2 b1 b0 read 101 and g2 g1 g0 read 111 from the edge at 36. rst_n falls at tick 38, between edges, and every flop clears in that same tick: b2 and b0 fall, and all three g rows fall together, 111 to 000. rst_n rises again at 42, and nothing moves until the edge at 44 loads 1 into both registers.

A count read in another clock domain crosses on one wire per bit, each through its own synchronizer on the receiving clock. The two clocks are unrelated, so sooner or later a synchronizer samples its bit as it changes, and it resolves to the old value or the new one. With one bit changing, either answer is a count the counter held, and the sampling costs the receiving side at most one step, on top of its synchronizers' own delay. In binary, 3 to 4 changes three bits, and each synchronizer can resolve its own way: the receiving side can read 111, 000, 101 or another mix of old and new bits that is neither count. That is the reason behind the traffic-light controller's note on its queue count: a count that only moves by one can cross in Gray code.

The code

// A 3-bit binary counter with its Gray code beside it, both held in
// flip-flops. Between neighbouring counts, the wrap from 7 to 0 included,
// exactly one bit of gray changes.
//
// Reset style for this module: asynchronous, active low.
module gray_counter (
    input  logic       clk,
    input  logic       rst_n,
    output logic [2:0] bin,
    output logic [2:0] gray
);

  // One flip-flop a bit, named as the drawing names them.
  logic b2, b1, b0;
  logic g2, g1, g0;

  // The next count, and its Gray code: each bit XORed with the one above it.
  logic [2:0] bin_next;
  logic [2:0] gray_next;
  assign bin_next  = {b2, b1, b0} + 3'd1;
  assign gray_next = bin_next ^ (bin_next >> 1);

  // gray is loaded from the next count, not decoded from this one: it changes
  // at the same edge as bin, and straight out of flip-flops.
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      {b2, b1, b0} <= '0;
      {g2, g1, g0} <= '0;
    end else begin
      {b2, b1, b0} <= bin_next;
      {g2, g1, g0} <= gray_next;
    end
  end

  assign bin  = {b2, b1, b0};
  assign gray = {g2, g1, g0};

endmodule

The reset style is stated at the top of the file and used once: asynchronous, active low. bin_next is the count plus one, which the drawing builds from gates: a NOT for bit 0, an XOR for bit 1, and for bit 2 an AND that forms the carry and an XOR that adds it. gray_next XORs each bit of the next count with the bit above it. Bit 2 has none and passes through, so two XORs make the Gray code and g2 loads b2's next value itself. The one always_ff loads both registers from those two lines at every edge and clears both when rst_n falls.

The cells below count one flip-flop fewer than the drawing. g2 and b2 load the same next value at every edge and reset to the same 0, so they always hold the same bit, and Yosys keeps a single flop for both: g2 still comes straight out of a flip-flop, the one b2 does. The netlist after the cells is drawn before synthesis and still has all six.

Synthesis result

Yosys's generic synthesis turns gray_counter.sv into 12 cells, 5 of them flip-flops. The cells are Yosys's own gate library, not an FPGA's or a standard-cell library's: the count measures the logic, not the area of any chip.

Lint by Verilator 5.052, the testbench by Icarus Verilog 13.0, synthesis by Yosys 0.66.

Icarus replayed this page's three scenarios on this code, and all 1,200 values the waveform draws match.

Pitfalls

A reset, or any step other than one. The one-bit promise covers a step of one and nothing else. Reset shows the exception: g2 g1 g0 drop from 111 to 000 in one tick, three bits at once. A load, a skip or a step of two breaks it the same way, and the receiving side has to learn of such a step from something other than the count.

Decoding the Gray code after the flops. assign gray = bin ^ (bin >> 1); gives the same value at every tick of a simulation without delays, and saves the g flops. But the binary flip-flops do not change at exactly the same instant, so at every step where more than one of them changes, 1 to 2, 3 to 4, 5 to 6 and 7 to 0, the XORs pass for a moment through codes that are neither the old one nor the new one, and a synchronizer in the reading domain can sample that moment. Tried in Icarus with unequal delays on the binary flops, a decoded Gray code went from 100 through 111 and 110, the Gray codes of 5 and 4, before it settled at 000 during 7 to 0; the registered one changed one bit, once. No zero-delay run can tell the two apart: a decoded copy passes this page's testbench and the replay of its three scenarios. That is why the code registers the Gray code, and why the check that it does is the synthesis result's flip-flops, not the waveform.

A count that wraps short of a power of two. The 4-bit decade counter wraps from 9 to 0: the Gray code of its count would step one bit at a time from 0 to 9, but 9 to 0 would be 1101 to 0000, three bits at once, one more than its binary count changes there. With this code, counted from 0, every length that is not a power of two moves more than one bit at its wrap: the code of its last count has more than one bit set.

An even length can still wrap in one bit if it counts through the middle of the code. The Gray codes of k and of 2ⁿ − 1 − k differ only in the top bit, so a decade that runs through the 4-bit codes of 3 to 12 steps one bit everywhere, the wrap from 12 to 3 included. No odd length can: every one-bit step changes whether the code has an odd or an even number of ones, so a cycle of such steps has an even length.

Skew on the way to the synchronizers. One bit per step holds on the far side only while the bits reach their synchronizers in the order they changed. If one bit's path is slower than another's by more than the time between two steps, the receiving side can see a later step's bit before an earlier one's, and read a code that is none of the counts the counter passed through. Those paths have to be kept within that bound.