Digital Design / Module 10: Clock domain crossing
57. Gray code pointers
Use one-bit-change encodings.
See it move
The idea
In Gray code, consecutive values differ in exactly one bit. If you sample a Gray counter while it changes, that one bit reads as either old or new. So the sample is always either the old value or the new value, and never a false one. That's what makes multi-bit crossing possible for counters.
Converting
// Binary to Gray
assign gray = bin ^ (bin >> 1);
// Gray to binary: each bit is the XOR of all higher Gray bits
always_comb begin
bin[N-1] = gray[N-1];
for (int i = N-2; i >= 0; i--)
bin[i] = bin[i+1] ^ gray[i];
endThe first is one XOR per bit. The second is a chain of XORs, so it is slower.
The sequence
| Value | Binary | Gray |
|---|---|---|
| 3 | 011 | 010 |
| 4 | 100 | 110 |
| 7 | 111 | 100 |
| 0 | 000 | 000 |
From 3 to 4, binary flips all three bits, while Gray flips one. The wrap from 7 to 0 also flips just one, and this only works for wraps at a power of two.
The conditions
All of these must hold for a Gray crossing to be safe:
- The value changes by at most one step per source clock.
- The Gray value comes straight from a register, with no logic after it, because a combinational converter could .
- The path across the bus is less than about one period of the destination clock. Modern constraints check this using
set_max_delay.
Sampling a fast counter
If the source is much faster, the destination can miss some values and go from, for instance, 5 to 8. That's fine, because each sampled value was real. pointers rely on this: the other side's pointer is merely old, and "old" is always safe.
Common mistake
Applying Gray code to arbitrary data. It helps only for sequences that move in single steps. If a value can jump by two or more, then multiple bits can change, and you lose the guarantee. Try value 7 in the animation above, and note how many values binary can produce.
Key ideas
- Binary to Gray: g = b xor (b >> 1).
- A one-bit change gives either old or new value on capture, never a false one.
- Applies only for sequences changing by one step at a time.
Lab: Clock crossing lab
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
The fix
assign gray = bin ^ (bin >> 1);
Why it failed
The correct formula is bin ^ (bin >> 1). Shifting left mixes each bit with the one below instead, and that doesn't give the single-bit-change property. Since the output still looks plausible, you need to check every step to catch this.
Interview questions
coreWhy does a Gray pointer cross safely?
One bit changes per step, so a sampled value is either the old pointer or the new one.
basicConvert binary 1011 to Gray code, and convert the result back to binary.
Binary to Gray is bin ^ (bin >> 1): 1011 ^ 0101 = 1110. Going back, the top binary bit copies the top Gray bit, and each lower bit is its Gray bit XOR the binary bit above it. That gives 1, then 1 ^ 1 = 0, then 0 ^ 1 = 1, then 1 ^ 0 = 1, so 1011 again. Both directions agree, which is a quick self-check.
basicA 4-bit counter steps from 7 to 8. If each bit is sampled independently while it changes, how many different values could the destination read in binary, and in Gray code?
In binary, 0111 to 1000 flips all four bits, and each one can be caught old or new, so any of 2^4 = 16 values can appear. In Gray, 7 is 0100 and 8 is 1100, so only one bit changes. That bit is caught either old or new, so the only possible readings are 7 and 8. That is the whole reason Gray code is used for pointers.
coreWrite a Gray-to-binary converter for a 4-bit value in Verilog-2005 and say why it is slower than binary-to-Gray.
function [3:0] g2b;
input [3:0] g;
integer i;
begin
g2b[3] = g[3];
for (i = 2; i >= 0; i = i - 1)
g2b[i] = g2b[i+1] ^ g[i];
end
endfunctionThe top bit is copied, and each lower bit is its Gray bit XOR the binary bit just above it, so a loop from the top down builds the result. Binary-to-Gray is one XOR per bit, all in parallel. Gray-to-binary is a chain: each bit waits for the one above it, so its delay grows with the width of the pointer. Synthesis can restructure the chain somewhat, but it is still more logic depth than the forward conversion.
coreA 4-bit binary-to-Gray converter is written with a shift in the wrong direction. What goes wrong?
assign gray = bin ^ (bin << 1);
Shifting left gives bin ^ (bin << 1), which is not Gray code. Checking all sixteen steps of a 4-bit counter, 14 of them change two bits instead of one; only the steps into 0 and into 8 change one bit. So the crossing loses its guarantee, and a capture can again produce a value that was never sent. The correct line is assign gray = bin ^ (bin >> 1);.
coreA counter that adds 2 every cycle is sent across a clock boundary in Gray code. Is it safe?
No. Gray code only promises one changed bit between neighbouring values. Stepping from 6 to 8 goes from Gray 0101 to 1100, which changes two bits, so a capture can mix them into a value that was neither 6 nor 8. Gray crossing requires that the value moves by at most one step per source clock. For arbitrary data, Gray code changes nothing.
coreWhy must the Gray value that crosses come straight from a register, rather than from XOR gates after a binary register?
If the conversion happens in logic right before the crossing, the binary bits reach the XOR gates at slightly different times, and the gate outputs can pass through several patterns before settling. A destination edge can catch one of those intermediate patterns, which recreates the binary problem. Computing the next Gray value from the next binary value and registering it means exactly one flop output changes, once, after each clock edge.
advancedA Gray counter runs at 300 MHz and is read through a synchronizer at 100 MHz. The destination sees 5 and then 8. Is that a bug?
No. Several source steps happen between destination edges, so the destination naturally skips values. What matters is that every value it reads is one the counter really held, which Gray code guarantees as long as the counter steps by one per source clock. For a FIFO pointer, an old or skipped value just means the other side sees slightly less data or space than there really is, which is safe.
advancedWhy do the bits of a Gray-coded bus need to arrive close together, and roughly how close?
Gray code is safe because only one bit is in flight at any moment. If one wire were slow enough that the next step's change arrived before its own, two bits would be changing at once and a capture could again be a value never held. So the skew across the bus must stay below the time between steps, and the lesson's guideline is under about one destination period; using the smaller of the source and destination periods is a safe bound. This is checked with a maximum delay constraint on the crossing paths.