Synchronous & Asynchronous FIFO Design in Verilog - Full/Empty Flags, Gray Codes & CDC

The first sentence of the 2015 version of this post said FIFOs are "essential for clock domain crossing" — and then presented a single-clock FIFO and never mentioned clocks again. Somewhere out there, an engineer read a post like that, dropped a synchronous FIFO across a two-clock boundary, and got a design that passed every simulation and corrupted data on the bench at temperature. This rewrite keeps the promise the old opening made: the synchronous FIFO in full, honestly taught — and then the async FIFO, gray-code pointers, and the CDC reasoning that makes crossing clock domains actually safe.

There's a second reason this post earns its length: "design me a FIFO" is the most-asked whiteboard question in digital design interviews, and every section below — the extra-bit trick, full/empty corner cases, gray codes, depth sizing — is a question you will eventually be asked with a marker in your hand.

Note Originally published in 2015; rewritten in 2026. The original taught only the synchronous FIFO despite advertising CDC; this version adds the asynchronous FIFO, pointer synchronization, an interview section, and a depth-sizing treatment. The ASCII timing diagram is now a real waveform.

~17 min read · Intermediate body, Advanced tail · The 2-FF synchronizer here is the same one built in D Flip-Flop with Async Reset.

Architecture: Four Parts, One Race

flowchart LR
    WD["wr_data"] --> MEM["mem[0:DEPTH-1]"]
    WP["wr_ptr
(ADDR_WIDTH+1 bits)"] --> MEM
    RP["rd_ptr
(ADDR_WIDTH+1 bits)"] --> MEM
    MEM --> RD["rd_data"]
    WP --> CMP["compare logic"]
    RP --> CMP
    CMP --> FULL["full"]
    CMP --> EMPTY["empty"]

    style MEM fill:#e0f2fe,stroke:#0284c7
    style CMP fill:#fef3c7,stroke:#d97706
    style FULL fill:#fee2e2,stroke:#ef4444
    style EMPTY fill:#fee2e2,stroke:#ef4444

A FIFO is a memory, two pointers chasing each other around it, and comparison logic. The entire intellectual content lives in one corner case: when rd_ptr == wr_ptr, is the FIFO empty or full? Both states put the pointers in the same place — empty because the reader caught the writer, full because the writer lapped the reader. Every FIFO design is a strategy for telling those two apart.

The Extra-Bit Trick

Widen both pointers by one MSB beyond what addressing needs. The low bits address memory; the extra bit counts wraps (odd or even lap):

Condition	Detection	Meaning
Empty	entire pointers equal (MSB included)	same address, same lap — reader caught writer
Full	address bits equal, MSBs differ	same address, one lap apart — writer lapped reader

Tip The alternative strategy is a separate occupancy counter (increment on write, decrement on read; empty = 0, full = DEPTH). It's arguably clearer — and it's what you can't use in an async FIFO, because the counter would need updates from two clock domains at once. The extra-bit scheme keeps each pointer owned by exactly one domain, which is why it's the one worth internalizing. It also gives you occupancy for free: wr_ptr - rd_ptr, MSB and all.

RTL Implementation

module sync_fifo #(
  parameter DATA_WIDTH = 8,
  parameter DEPTH      = 16,
  parameter ADDR_WIDTH = $clog2(DEPTH)
)(
  input  wire                  clk,
  input  wire                  rst_n,
  // Write side
  input  wire                  wr_en,
  input  wire [DATA_WIDTH-1:0] wr_data,
  output wire                  full,
  // Read side
  input  wire                  rd_en,
  output reg  [DATA_WIDTH-1:0] rd_data,
  output wire                  empty
);

  // One extra MSB: the "lap counter"
  reg [ADDR_WIDTH:0] wr_ptr, rd_ptr;
  reg [DATA_WIDTH-1:0] mem [0:DEPTH-1];

  assign empty = (wr_ptr == rd_ptr);
  assign full  = (wr_ptr[ADDR_WIDTH-1:0] == rd_ptr[ADDR_WIDTH-1:0]) &&
                 (wr_ptr[ADDR_WIDTH]     != rd_ptr[ADDR_WIDTH]);

  // The extra-bit scheme requires power-of-2 depth: make the
  // constraint enforceable instead of a footnote someone misses.
  initial begin
    depth_pow2_chk: assert ((DEPTH & (DEPTH-1)) == 0)
      else $fatal(1, "sync_fifo: DEPTH=%0d is not a power of 2", DEPTH);
  end

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) wr_ptr <= '0;
    else if (wr_en && !full) begin
      mem[wr_ptr[ADDR_WIDTH-1:0]] <= wr_data;
      wr_ptr <= wr_ptr + 1'b1;
    end
  end

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      rd_ptr  <= '0;
      rd_data <= '0;
    end else if (rd_en && !empty) begin
      rd_data <= mem[rd_ptr[ADDR_WIDTH-1:0]];
      rd_ptr  <= rd_ptr + 1'b1;
    end
  end

endmodule

Note the guard assertion — the 2015 version mentioned the power-of-2 requirement in a gotcha box and left it as prose. A constraint the compiler can check should never be a comment (the same philosophy as pure virtual methods: make illegal states fail loudly at time zero, not mysteriously at hour three). Note also this is a standard (registered-output) FIFO: rd_data appears one cycle after rd_en — a latency contract that matters enormously and gets its own section below.

The Timing Contract, as a Real Waveform

{ "signal": [
  { "name": "clk",     "wave": "p........." },
  { "name": "wr_en",   "wave": "01...0....", "node": ".a" },
  { "name": "wr_data", "wave": "x3456x....", "data": ["A0","A1","A2","A3"] },
  { "name": "full",    "wave": "0....1.0..", "node": ".....b" },
  { "name": "rd_en",   "wave": "0......1.0", "node": ".......c" },
  { "name": "rd_data", "wave": "x.......34", "data": ["A0","A1"], "node": "........d" },
  { "name": "empty",   "wave": "10........" }
], "edge": ["a-b DEPTH=4 writes -> full", "c-d one-cycle read latency"],
   "head": { "text": "Standard FIFO: burst to full, then read (registered output)" },
   "config": { "hscale": 1.5 } }

Two contract details the waveform makes visible: full asserts on the cycle after the fourth write commits, and rd_data trails rd_en by one cycle. Every consumer of this FIFO must be designed against those two facts — most "FIFO bugs" in integration are actually contract misreadings by the modules around it.

Verification: the Corner Cases That Matter

The original testbench walked write-to-full, read-to-empty, and a simultaneous read/write whose results it never checked. The upgrade principle: every test asserts, and the interesting tests live at the flag boundaries.

// Test 4, done properly: simultaneous rd/wr must preserve occupancy
// (and is only defined when neither full nor empty!)
@(posedge clk);
wr_en = 1; rd_en = 1; wr_data = 8'hEE;
@(posedge clk);
wr_en = 0; rd_en = 0;
occ_chk: assert (dut.wr_ptr - dut.rd_ptr == occupancy_before)
  else $error("simultaneous rd/wr changed occupancy");

// The two boundary races every FIFO bug hides in:
//   write attempt while full  -> must be ignored, data preserved
//   read attempt while empty  -> must be ignored, rd_data unchanged
wr_full_chk: assert (!(wr_en && full) || $stable(dut.mem[dut.rd_ptr[ADDR_WIDTH-1:0]]));

For continuous checking rather than directed tests, this is exactly the shape the SystemVerilog checker construct was made for — the Concurrent Assertions guide builds a bindable fifo_occupancy_check with its own occupancy counter and push-to-full/pop-from-empty assertions. Bind it to this module and the corner cases are watched in every test forever, not just the directed one.

First-Word Fall-Through (FWFT)

The registered-output FIFO answers a read request; a FWFT FIFO holds the oldest word already visible on rd_data, and rd_en means "I took it — advance." The 2015 version showed the one-line combinational read and stopped; the honest version includes the contract change:

// FWFT read side: data visible while !empty, rd_en acknowledges
assign rd_data = mem[rd_ptr[ADDR_WIDTH-1:0]];   // combinational — no latency
always @(posedge clk or negedge rst_n)
  if (!rst_n)               rd_ptr <= '0;
  else if (rd_en && !empty) rd_ptr <= rd_ptr + 1'b1;

	Standard (registered)	FWFT
Read semantics	request → data next cycle	data showing → rd_en acknowledges
Latency to first word	1 cycle after rd_en	0 — visible while !empty
Timing cost	clean registered output	memory read in the output path — check your setup budget
Natural fit	CPU-style pop interfaces	valid/ready streaming (it is valid/ready: !empty=valid, rd_en=ready)

The Async FIFO: Keeping the CDC Promise

Now the part the 2015 post owed you. Two clock domains, writer on wclk, reader on rclk. Each side needs the other side's pointer to compute its flag — and that pointer must cross a clock boundary. Synchronizing a multi-bit binary pointer with 2-FF synchronizers per bit does not work, for a reason worth stating precisely:

Warning A binary counter increment can change many bits at once (7→8 flips four bits: 0111→1000). Each bit's synchronizer resolves independently — one bit's flop catches the new value while its neighbor catches the old — so the receiving domain can briefly observe a value that never existed: mid-flip garbage like 1111 or 0000. A full/empty computed from a phantom pointer value is a data-corrupting bug that appears only under specific clock phase alignments — the classic "passes RTL sim, fails on silicon" defect, because simulation without CDC modeling never misaligns the phases.

The fix is Gray code: an encoding where consecutive values differ in exactly one bit. Synchronize a Gray-coded pointer and the worst case is that the one changing bit resolves late — the receiver sees either the old value or the new value, both of which are real pointer states. Never a phantom:

// Binary-to-Gray: one XOR
assign wr_ptr_gray = wr_ptr_bin ^ (wr_ptr_bin >> 1);

// Each pointer crosses in Gray, through a 2-FF synchronizer
always @(posedge rclk or negedge rrst_n)
  if (!rrst_n) {wr_gray_r2, wr_gray_r1} <= '0;
  else         {wr_gray_r2, wr_gray_r1} <= {wr_gray_r1, wr_ptr_gray};

// Read domain computes empty from the SYNCHRONIZED write pointer
assign empty = (rd_ptr_gray == wr_gray_r2);

// Full in Gray: top two bits inverted, rest equal (the extra-bit
// test, translated through the Gray encoding)
assign full = (wr_ptr_gray == {~rd_gray_w2[ADDR_WIDTH:ADDR_WIDTH-1],
                                rd_gray_w2[ADDR_WIDTH-2:0]});

flowchart LR
    subgraph WDOM["wclk domain"]
        WPB["wr_ptr (binary)"] --> WPG["bin→gray"]
        WPG --> WFULL["full logic"]
        RSYNC["2-FF sync
(rd gray)"] --> WFULL
    end
    subgraph RDOM["rclk domain"]
        RPB["rd_ptr (binary)"] --> RPG["bin→gray"]
        RPG --> REMPTY["empty logic"]
        WSYNC["2-FF sync
(wr gray)"] --> REMPTY
    end
    WPG -.->|crosses domains| WSYNC
    RPG -.->|crosses domains| RSYNC

    style WSYNC fill:#fef3c7,stroke:#d97706
    style RSYNC fill:#fef3c7,stroke:#d97706

One property completes the safety argument: the synchronized pointer is always stale — it lags the true value by up to two receiving-domain cycles. Staleness makes the flags pessimistic: the reader may see empty slightly after data arrived (reads a little late — harmless), the writer may see full slightly after space opened (stalls a little early — harmless). The design converts a metastability hazard into a small, bounded loss of throughput. That trade — correctness paid for with pessimism — is the single most important idea in CDC design, and it's the model answer to the interview follow-up "is the async FIFO's full flag exact?"

(The 2-FF synchronizer itself — why two flops, MTBF reasoning, async-assert/sync-deassert reset — is built from scratch in the D Flip-Flop post; the reset timing it must respect is STA Part 3's recovery/removal.)

Common Mistakes

• Using a sync FIFO across clock domains "because FIFOs do CDC." Only the async FIFO with Gray-coded, synchronized pointers does CDC. The sync FIFO assumes one clock in its very first line.
• Non-power-of-2 DEPTH with the extra-bit scheme. The pointer wrap no longer aligns with the address wrap and the flags lie. Assert it (as above) — don't footnote it.
• Unchecked simultaneous read/write. It's the highest-traffic operating mode of a rate-matching FIFO and the old testbench never asserted its result. Occupancy must be invariant.
• Reading the standard FIFO like FWFT. rd_data is a cycle late; consuming it combinationally with rd_en double-pops or reads garbage. Know which contract you instantiated.
• Synchronizing binary pointers, or Gray-coding but skipping the 2-FF sync. Each half of the protection is useless alone: Gray limits the damage to one ambiguous bit; the synchronizer gives that bit time to resolve.
• Comparing full/empty against the same-domain pointer. Each flag must pair its own domain's true pointer with the synchronized foreign pointer — crossing them the other way defeats the whole scheme.

Interview Corner

Q: Why the extra pointer bit? Walk me through it.

A: With N-bit pointers for a 2^N-deep FIFO, rd_ptr == wr_ptr is ambiguous — it's both the empty and the full condition. The extra MSB counts laps: pointers fully equal (same lap) means empty; address bits equal with MSBs differing (writer one lap ahead) means full. Bonus: the pointer difference is the exact occupancy.

Q: Why can't binary pointers cross clock domains, even through synchronizers?

A: A binary increment can flip multiple bits simultaneously, and per-bit synchronizers resolve independently — the receiver can capture a mix of old and new bits, observing a pointer value that never existed. Gray code restricts each increment to a single changing bit, so the worst case collapses to "old value or new value," both real. Then the 2-FF synchronizer handles the metastability of that one bit.

Q: The async FIFO's flags are computed from stale pointers. Is that a bug?

A: It's the load-bearing feature. Staleness is always in the safe direction — empty persists slightly after data arrives, full persists slightly after space frees — so the FIFO trades a little throughput for the guarantee that it never overflows or underflows. Pessimistic-but-correct is the fundamental CDC design pattern.

Q: How deep must a FIFO be to absorb a burst?

A: Size for the worst-case accumulation: fill rate minus drain rate, integrated over the longest sustained burst, plus latency slack. For a burst of B words arriving at rate f_w while draining at f_r < f_w: accumulation ≈ B × (1 − f_r/f_w), rounded up, plus synchronizer/stall latency margin (and flag-staleness margin in an async FIFO). Then round up to a power of 2 — see the Advanced section for a worked example.

Beyond the Basics: Advanced → Expert

Level 1 — Programmable thresholds: almost_full as a flow-control contract

Binary full/empty is enough for stalling; real systems need warning. almost_full = (occupancy >= DEPTH - MARGIN) — and the engineering content is choosing MARGIN: it must cover every write that can arrive after the warning asserts — pipeline stages already committed upstream, synchronizer delay in async cases, the source's own reaction latency. Undersized MARGIN is an overflow that only happens at full line rate; oversized wastes silicon. This is credit-based flow control in miniature — the same in-flight accounting that PCIe's data link layer runs with explicit credit counters, and the reasoning transfers verbatim.

Level 2 — Depth sizing, worked

The senior-interview classic, with numbers. Writer: 64-word bursts at 200 MHz, one word/cycle. Reader: continuous drain at 133 MHz. Per burst: fill time 64/200 = 320 ns; words drained in that window 320 ns × 0.133 = ~42; accumulation 64 − 42 = 22 words. Add margin — drain stalls, flag staleness (async), rounding — and round up to 32. The general recipe: find the longest window where fill rate exceeds drain rate (worst-case burst back-to-back if the protocol allows it — that assumption is where most sizing errors hide), integrate the rate difference over it, add latency margin, round to power of 2. When bursts can be back-to-back indefinitely and f_w > f_r sustained, no finite FIFO suffices — the answer is backpressure, and saying so is what the interviewer is fishing for.

Level 3 — SRAM-based FIFOs: when mem[] becomes a macro

Beyond a few hundred entries, the register array becomes an SRAM macro, and the macro's realities reshape the design: reads take a full cycle through a registered port (FWFT now needs an output prefetch buffer — a small register FIFO in front of the SRAM that keeps 1-2 words "fallen through" while the bulk sits in RAM); single-port macros can't read and write in the same cycle (banked ping-pong or dual-port cost); and BIST/repair hooks arrive with the macro. The composite pattern — big SRAM ring plus tiny register skid stage — is the production norm, and recognizing it in an unfamiliar codebase ("why is there a 2-deep FIFO in front of this RAM?") saves a day of archaeology.

Level 4 — Elastic buffers: FIFOs inside the pipeline

Shrink the FIFO to depth 2 and it becomes a skid buffer — the standard fix for valid/ready timing closure: registering the ready path adds a cycle of uncertainty, so a 2-deep elastic stage absorbs the one in-flight word that arrives after ready deasserts. Depth 2 is not arbitrary: it's the smallest buffer that lets you register both valid and ready paths while sustaining full throughput. Chain them and you have an elastic pipeline; SerDes links run the same structure as clock-compensation FIFOs, inserting/deleting alignment primitives to absorb ppm-level clock drift — the PCIe series meets these at the physical/link boundary. One mental model, three scales: skid buffer (cycles), rate-matcher (bursts), clock compensator (ppm).

Level 5 — Verifying FIFOs: assertions, formal, and the CDC signoff

FIFOs are the best formal-verification target in digital design: small state, crisp invariants. The property set that closes one: occupancy bounds (never <0 or >DEPTH), flag definitions (empty ⇔ occupancy 0, full ⇔ occupancy DEPTH), no-loss/no-duplication (data ordering via a tracked-word or smart-constraint argument), and for async — the Gray-code invariant itself: assert property (@(posedge wclk) $countones(wr_ptr_gray ^ $past(wr_ptr_gray)) <= 1); — one line that catches any refactor breaking the entire CDC safety argument. Formal proves these exhaustively in minutes on a FIFO-sized module; the same properties run in simulation via a bound checker. The last mile is CDC structural signoff: lint tools that trace every domain crossing and demand a recognized synchronizer on each — necessary because simulation is phase-aligned and will never show you the metastability window. The complete FIFO verification story is all three legs: simulation for integration contracts, formal for invariants, CDC lint for the crossings themselves.

Key Takeaways

• The whole FIFO problem is disambiguating rd_ptr == wr_ptr; the extra MSB solves it and hands you occupancy for free. Assert the power-of-2 constraint instead of footnoting it.
• Standard vs FWFT is a latency contract — most integration bugs are contract misreadings, and FWFT is valid/ready by another name.
• CDC requires the async FIFO: Gray-coded pointers (one changing bit) through 2-FF synchronizers, flags computed pessimistically from stale foreign pointers. Binary pointers across domains produce phantom values that simulation won't show you.
• Depth sizing = rate difference integrated over the worst burst window, plus latency margin — and "no finite depth works, use backpressure" is sometimes the right answer.
• Verify with all three legs: boundary-case simulation (simultaneous rd/wr asserted!), formal on the invariants, CDC lint on the crossings.

Related Posts

• D Flip-Flop with Async Reset - Complete Verilog Guide (Verilog, Digital Design, RTL)
• 2. STA Fundamentals - Setup & Hold with Clock Skew (STA, Digital Design)
• 2. SVA Guide - Concurrent Assertions (SVA, SystemVerilog)
• 3. PCIe for DV Engineers - Data Link Layer (PCIe, Series)