Gray-Code Counters

A Gray counter changes one bit per count, so another clock domain can read it safely when the value comes from flip-flops.

You Will Be Able To

  • Build a Gray counter from a binary register and a converter.
  • Predict which bit a Gray counter flips next, using the parity rule.
  • Explain why a pointer that crosses clock domains is Gray coded.
  • Explain why the Gray value must be the register, not logic after it.
Lesson
G6.8
Time
25 min
Runs on
Your browser
Check
5 questions

A FIFO between two clocks must tell the reader how far the writer has got. The reader samples the write pointer with its own clock, at any moment. If several pointer bits change at once, the sample can be a value the pointer never held.

A 4-bit Gray Counter: One Bit Changes per EdgeFrom the lab: g after each edge, and the bit that flipped.
012345678910111213141516clkg00000001001100100110011101010100110011011111111010101011100110000000flipped-0102010301020103
Scroll horizontally ↔
  1. Cycle 1

    The first edge flips bit 0: 0000 to 0001.

  2. Cycle 8

    Count 7 to count 8: binary changes all four bits (0111 to 1000). Gray changes one: 0100 to 1100.

  3. Cycle 16

    The wrap from 1000 back to 0000 also changes one bit.

Measured: the values are the lines the lab prints.

A Binary Register Plus a Converter

The quickest Gray counter keeps a binary count and converts it with g = b ^ (b >> 1), as in G1.7. It counts correctly, and each count changes one bit of g.

Where the Gray Value Comes FromArrows carry data. The register is clocked; the adder and the converter are gates.
  • Storage
  • Datapath
  • I/O
  • Data
Where the Gray value comes fromArrows carry data. The register is clocked; the adder and the converter are gates. storage b register 4 flip-flops datapath b + 1 next count datapath b ^ (b >> 1) 3 XOR gates io g the Gray output D inputs
  1. storage b register4 flip-flops
    • b + 1
    • b ^ (b >> 1)
  2. datapath b + 1next count
    • D inputs → b register
  3. datapath b ^ (b >> 1)3 XOR gates
    • g
  4. io gthe Gray output
  1. Count

    The register and the adder form an ordinary binary counter.

  2. Convert

    Gates turn b into g. So g is logic after the register, not a register output.

Read the diagram as text
  • b register: 4 flip-flops
  • b + 1: next count
  • b ^ (b >> 1): 3 XOR gates
  • g: the Gray output
  • b register → b + 1
  • b + 1 → b register: D inputs
  • b register → b ^ (b >> 1)
  • b ^ (b >> 1) → g

The count lives in b. The Gray value g is computed from it.

Press Synthesize on the lab: 12 cells, 4 of them flip-flops, and 3 levels. The output g comes out of XOR gates. The next section shows why that matters.

Why the Gray Value Must Come from Flip-Flops

Real flip-flops do not switch at the same instant. Their clock-to-Q delays differ, and so do the wires. During those few picoseconds, b holds values in between.

The converter turns each in-between binary value into a Gray value. So g can show several wrong values in one count, even though the final change is one bit.

Now give a Gray register the same unequal delays. Only one of its bits changes, so there is nothing in between.

A 4-bit Gray countFlip-flopsCellsLevelsg straight from flip-flops?
Binary register, converter after it (the lab)4123No: XOR gates
Binary register beside a Gray register7183Yes
Native: g is the only register4122Yes

Measured on the pinned Yosys flow. The middle design has 8 flip-flops in the code. The flow shares one, since the top bits of b and g are equal.

The middle row fixes the problem with a second register. The last row fixes it for free: the Gray value is the register. That is a native Gray counter.

Counting in Gray Directly

A native counter needs its next value from g alone. The lab shows the pattern. Before each edge, look at the parity of g: is the number of 1s even or odd?

g beforeParityLowest 1Bit that flippedg after
0000even—bit 00001
0001oddbit 0bit 10011
0011even—bit 00010
0010oddbit 1bit 20110
0110even—bit 00111
0111oddbit 0bit 10101
0101even—bit 00100
0100oddbit 2bit 31100
1100even—bit 01101
1101oddbit 0bit 11111
1111even—bit 01110
1110oddbit 1bit 21010
1010even—bit 01011
1011oddbit 0bit 11001
1001even—bit 01000
1000oddbit 3bit 30000

Measured: the lab's 16 edges. Even parity flips bit 0. Odd parity flips the bit just left of the lowest 1, and 1000 flips its top bit back to 0.

So the rule is: with even parity, flip bit 0. With odd parity, flip the bit to the left of the lowest 1. When the only 1 is the top bit, flip it back to 0. That is the wrap.

A 3-Bit Gray Counter as a State Machine
A 3-Bit Gray Counter as a State Machine0101010101010101S000000count 0S001001count 1S011011count 2S010010count 3S110110count 4S111111count 5S101101count 6S100100count 7
  1. count 0 · S000000
    • ↓0 → S000
    • ↓1 → S001
  2. count 1 · S001001
    • ↓0 → S001
    • ↓1 → S011
  3. count 2 · S011011
    • ↓0 → S011
    • ↓1 → S010
  4. count 3 · S010010
    • ↓0 → S010
    • ↓1 → S110
  5. count 4 · S110110
    • ↓0 → S110
    • ↓1 → S111
  6. count 5 · S111111
    • ↓0 → S111
    • ↓1 → S101
  7. count 6 · S101101
    • ↓0 → S101
    • ↓1 → S100
  8. count 7 · S100100
    • ↓0 → S100
    • ↓1 → S000
StateInputNextOutput in state
S0000S000000
S0001S001000
S0010S001001
S0011S011001
S0110S011011
S0111S010011
S0100S010010
S0101S110010
S1100S110110
S1101S111110
S1110S111111
S1111S101111
S1010S101101
S1011S100101
S1000S100100
S1001S000100

Current state: S000 · Output: 000

Sampled input, state and output waveformStepState0S0001S0012S0113S0104S1105S1116S1017S1008S000en—11111111g2000011110g1001111000g0011001100
Scroll horizontally ↔
Sampled waveform: Moore output after each edge; Mealy output on the taken arc.
Step012345678
Input—11111111
StateS000S001S011S010S110S111S101S100S000
Output000001011010110111101100000

  1. Step 4. From 010 the counter goes to 110: the parity was odd and the lowest 1 was bit 1, so bit 2 flips.
  2. Step 8. From 100 it wraps to 000: only the top bit was 1, so the top bit flips back.

Each state is the register value itself. Every arc with en = 1 changes one bit, the wrap from 100 to 000 included.

G6.8.1 asks you to build this counter for any width from 2 to 16. Any next-state logic that reads only g will do: this rule, or another route you can derive.

Gray Pointers Across Clock Domains

An asynchronous FIFO keeps a write pointer in the write clock domain and a read pointer in the read clock domain. Each side needs the other's pointer to tell full from empty.

A Gray Write Pointer Crossing into the Read Clock DomainArrows carry the pointer. Two flip-flops on the read clock form a synchronizer (G5.12).
  • Storage
  • Control / FSM
  • Data
A Gray write pointer crossing into the read clock domainArrows carry the pointer. Two flip-flops on the read clock form a synchronizer (G5.12). storage Write pointer native Gray counter,write clock storage Sync flop 1 read clock storage Sync flop 2 read clock storage Read pointer Gray, read clock control Empty? equal pointers one bit changes
  1. storage Write pointernative Gray counter, write clock
    • one bit changes → Sync flop 1
  2. storage Sync flop 1read clock
    • Sync flop 2
  3. storage Sync flop 2read clock
    • Empty?
  4. storage Read pointerGray, read clock
    • Empty?
  5. control Empty?equal pointers
  1. Write

    Each write moves the pointer one count: exactly one bit changes.

  2. Sample

    Sync flop 1 may sample while that bit is changing. It gets the old count or the new one, never a third.

  3. Compare

    After the second flop the reader compares pointers. At worst it sees the write a few clocks late: it waits, but never reads a wrong word.

Read the diagram as text
  • Write pointer: native Gray counter, write clock
  • Sync flop 1: read clock
  • Sync flop 2: read clock
  • Read pointer: Gray, read clock
  • Empty?: equal pointers
  • Write pointer → Sync flop 1: one bit changes
  • Sync flop 1 → Sync flop 2
  • Sync flop 2 → Empty?
  • Read pointer → Empty?

Gray coding turns an unsafe multi-bit crossing into a one-bit crossing. It works because the pointer moves one count at a time.

A binary pointer would be unsafe here. A change from 0111 to 1000 can be sampled as any mix of the two, 0000 to 1111. The reader could think a full FIFO is empty.

Asked in interviews
  1. Why are FIFO pointers Gray coded before they cross clock domains?

    Consecutive counts differ in one bit. A synchronizer that samples during a change then gets the old or the new count, never a wild value.

  2. Can you synchronize the output of a binary-to-Gray converter?

    Not safely. The binary bits settle at different times, so the converter output passes through false values. Register the Gray value first, or count in Gray.

  3. How do you increment a Gray counter without a binary register?

    Work out the next value from g: convert to binary in logic, add one, convert back. Or use the parity rule: even flips bit 0, odd flips the bit left of the lowest 1.

Try It

Each edge flips exactly one bit of g. With even parity before the edge, bit 0 flips; with odd parity, a higher bit flips.

Press Synthesize: 4 flip-flops for b and gates for the adder and the converter. The g outputs come from XOR gates.

Change the converter to g = b and run again. Edge 8 now changes all four bits.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: edge 1: 0000 -> 0001 parity even flipped bit 0 edge 2: 0001 -> 0011 parity odd flipped bit 1 edge 3: 0011 -> 0010 parity even flipped bit 0 edge 4: 0010 -> 0110 parity odd flipped bit 2 edge 5: 0110 -> 0111 parity even flipped bit 0 edge 6: 0111 -> 0101 parity odd flipped bit 1 edge 7: 0101 -> 0100 parity even flipped bit 0 edge 8: 0100 -> 1100 parity odd flipped bit 3 edge 9: 1100 -> 1101 parity even flipped bit 0 edge 10: 1101 -> 1111 parity odd flipped bit 1 edge 11: 1111 -> 1110 parity even flipped bit 0 edge 12: 1110 -> 1010 parity odd flipped bit 2 edge 13: 1010 -> 1011 parity even flipped bit 0 edge 14: 1011 -> 1001 parity odd flipped bit 1 edge 15: 1001 -> 1000 parity even flipped bit 0 edge 16: 1000 -> 0000 parity odd flipped bit 3

Original design · 12 cells · 4 flip-flops · 0 latches · 3 logic levels. Synthesis uses Yosys; counts depend on the toolchain.

Read included file: tb.sv
// tb.sv: 16 edges after a reset. For each edge: g before and after, the parity of g before, the bit that flipped.
`timescale 1ns/1ns
module tb;
  logic clk = 0, rst = 1;
  wire  [3:0] g;
  logic [3:0] prev, diff;
  int         flipped;
  gray4 dut (.clk(clk), .rst(rst), .g(g));
  initial begin
    #5 clk = 1; #5 clk = 0; rst = 0;
    for (int k = 1; k <= 16; k++) begin
      prev = g;
      #5 clk = 1; #5 clk = 0;
      diff = g ^ prev;
      for (int i = 0; i < 4; i++) if (diff[i]) flipped = i;
      $display("edge %2d: %b -> %b  parity %s  flipped bit %0d", k, prev, g, (^prev) ? "odd " : "even", flipped);
    end
  end
endmodule

Check Yourself

ConceptA 4-bit Gray counter wraps from count 15 back to count 0. How many bits change?
ConceptWhy is the output of a binary register plus converter unsafe to synchronize into another clock domain?
ConceptA native 4-bit Gray counter holds 1101. What does it hold after the next edge?
Predict the outputThe lab's binary register is loaded with 5 and the program makes three edges. Predict the exact line.
module tb;
  logic       clk = 0;
  logic [3:0] b = 4'd5;
  wire  [3:0] g = b ^ (b >> 1);
  always @(posedge clk) b <= b + 4'd1;
  initial begin
    repeat (3) begin #1 clk = 1; #1 clk = 0; end
    $display("g=%b", g);
  end
endmodule
ConceptWhich value is safe to send across clock domains in Gray code?

Common Mistakes

Wrong Send the output of a binary-to-Gray converter to another clock domain.

The binary bits change at slightly different times, so the XOR outputs pass through false values. A reader can catch one.

Fix Send a Gray value that comes straight from flip-flops: a native Gray counter, or a Gray register after the converter.

Wrong Compare or subtract two Gray values as if they were numbers.

Gray order is not numeric order: 0100 is count 7 and 0110 is count 4.

Fix Convert both to binary first, then compare or subtract.

Wrong Gray-code a value that can jump by more than one step, such as a loaded counter or a data bus.

Only neighbouring counts differ in one bit. A jump from count 1 (0001) to count 3 (0010) changes two bits.

Fix Use Gray code only for a value that moves one count at a time; use a handshake for anything else.

Wrong Keep a binary counter and a Gray register side by side when one register will do.

Measured at 4 bits: 7 flip-flops and 18 cells, against 4 flip-flops and 12 cells for the native counter.

Fix Make the Gray value the register, and compute its next value from it.

Remember

  • A Gray counter changes exactly one bit per count, the wrap included.
  • A binary register plus a converter counts in Gray, but its output comes from gates and can show false values.
  • A native Gray counter keeps the Gray value in its register. Even parity flips bit 0; odd parity flips the bit left of the lowest 1.
  • A Gray pointer sampled by another clock reads the old or the new count, never a wild value.

Practice

Report a problem with this page