Async FIFO Design: Gray Codes, Full/Empty Flags, and Gotchas

Why an async FIFO at all

Two clock domains need to exchange data without dropping it or corrupting it. A FIFO decouples them: the writer pushes at wclk, the reader pops at rclk, and the only thing that crosses domains is a pointer comparison – never the data itself.

The gray-code trick

If you send a binary pointer across a clock domain, every increment flips up to N bits simultaneously, and each bit samples independently – you can capture a garbage pointer. Gray code flips exactly one bit per increment, so a mis-sampled pointer is always "one behind", never garbage. A stale full/empty flag costs you a bubble of latency; a garbage flag corrupts data.

Empty is generated in the read domain: rptr == gray-synced-wptr.
Full is generated in the write domain: wptr == gray-synced-rptr, with the write-side pointer offset by one full revolution so it can never equal the read pointer prematurely.

The gotchas

1. Multi-bit flags are fine – because they are gray, each bit settles independently and the worst case is a one-cycle-stale flag. Never synchronize a multi-bit data bus with a handshake; that's where corruption happens.
2. Almost-full/almost-empty are single-cycle signals, not safe for direct use in the other domain – generate them locally from the synchronized pointers.
3. Depth must be ≥ 2 × the synchronizer latency (usually 4–8 words minimum) or the FIFO can neither fill nor drain without bubbles – the classic "dead FIFO" interview trap.
4. Fall-through vs standard: a standard sync FIFO shows the write data after the write pointer catches up; a fall-through FIFO makes data visible immediately. Synthesis always_ff implementations differ – know which one your spec demands.

The depth math nobody remembers

Worst case burst = B, write/read frequencies = f_w, f_r, synchronizer latency = L (in read-clock cycles). Rule of thumb:

Depth ≈ B − (f_w / f_r) × (B + L)

For a 16-deep FIFO with a 2-cycle sync chain and 3:2 write:read ratio, a burst of 16 requires at least 16 − 1.5 × 18 → negative → underflow risk. That negative answer is what separates engineers who run the numbers from engineers who "just add 32".

If you're asked to code it

The outline interviewers accept: dual-port RAM + binary pointers + binary-to-gray converters + two two-flop synchronizers + gray-to-binary converters for the full/empty comparator. The full/empty logic must use the binary (converted) pointers, not raw gray. Remember that and the rest is syntax.