Day 79: The async FIFO: gray-code pointers
The async FIFO: gray-code pointers
An asynchronous FIFO buffers data between a write clock and a read clock — the standard, safe multi-bit CDC structure. Its challenge: each side must compare its pointer against the *other* domain's pointer to compute full/empty, which means crossing a multi-bit pointer between domains. The solution is gray coding: encode the pointers so only one bit changes per increment, making them safe to synchronize.
// gray = binary XOR (binary >> 1) -- only one bit flips per increment
function [W-1:0] bin2gray(input [W-1:0] b);
bin2gray = b ^ (b >> 1);
endfunction
// binary = gray XOR (gray>>1) XOR (gray>>2) ... (prefix-XOR)
function [W-1:0] gray2bin(input [W-1:0] g);
integer i; reg [W-1:0] b;
begin b = g; for (i=1;i<W;i=i+1) b = b ^ (g >> i); gray2bin = b; end
endfunction
// write side: increment binary wptr, convert to gray, SYNC into read domain
// read side: increment binary rptr, convert to gray, SYNC into write domainWhy gray code is the key
This is the deep idea foreshadowed all the way back in Stage 0's K-maps (Day 20). Because a gray-coded pointer changes only one bit per step, synchronizing it can only ever be 'off by one count' at worst — never a wildly wrong value from multiple bits resolving differently. That single-bit-change property is what makes the multi-bit crossing safe.
Key terms
- Asynchronous FIFO
- A FIFO with independent write and read clocks; the standard safe multi-bit CDC structure.
- Gray code
- An encoding where consecutive values differ in exactly one bit — safe to synchronize across domains.
- Pointer synchronization
- Passing a gray-coded read/write pointer into the other clock domain via 2-FF synchronizers.
- bin2gray / gray2bin
- Conversions: gray = b ^ (b>>1); binary via prefix-XOR of the gray value.
Progress for Day 79
Why are async-FIFO pointers gray-coded before crossing clock domains?
