Cummings Asynchronous FIFO — Clock Domain Crossing

Problem

The CDC Challenge

When data crosses between two unrelated clock domains, metastability can corrupt signals. A naive binary counter FIFO can produce glitches where multiple bits change simultaneously, causing the receiving domain to read a completely wrong pointer value. Cummings' solution uses Gray code — where only one bit changes per increment — to make pointer synchronization safe.

Architecture

Dual-Clock FIFO Structure

WRITE CLOCK DOMAIN (wclk) READ CLOCK DOMAIN (rclk) ───────────────────────── ───────────────────────── ┌─────────────────┐ ┌─────────────────┐ │ Write Logic │ │ Read Logic │ │ │ │ │ │ waddr (binary) │ │ raddr (binary) │ │ wptr (Gray) │ │ rptr (Gray) │ └────────┬────────┘ └────────┬────────┘ │ │ │ ┌─────────────────────┐ │ │ │ DUAL-PORT SRAM │ │ ├───▶│ │◀──────┤ │ │ waddr → Write Port │ │ │ │ raddr → Read Port │ │ │ └─────────────────────┘ │ │ │ │ SYNCHRONIZERS │ │ │ ┌────────┴───────┐ ┌───────────┴──────┐ │ rptr_sync │◀─── 2-FF ───│ rptr (Gray) │ │ (Gray → rclk) │ sync │ │ └────────┬───────┘ └──────────────────┘ │ ┌────────┴───────┐ ┌──────────────────┐ │ wptr (Gray) │─── 2-FF ───▶│ wptr_sync │ │ │ sync │ (Gray → wclk) │ └────────────────┘ └───────────┬──────┘ │ ┌─────────────────┐ ┌───────────┴──────┐ │ FULL Flag │ │ EMPTY Flag │ │ wptr == rptr_sync│ │ rptr == wptr_sync│ │ (with MSB trick)│ │ (exact match) │ └─────────────────┘ └──────────────────┘

Theory

Key Design Decisions

🔢

Gray Code vs Binary Pointers

Binary counters can have multi-bit transitions (e.g., 0111 → 1000 = 4 bits change). If sampled mid-transition, the synchronized value could be completely wrong. Gray code guarantees only 1 bit changes per increment, making 2-FF synchronization safe.

⏱️

2-FF Synchronizer Chain

Two flip-flop stages reduce metastability probability to negligible levels (MTBF > millions of years at typical clock rates). The first FF may go metastable; the second resolves to a valid logic level before being used.

🚩

Full/Empty Flag Generation

Empty: read pointer equals synchronized write pointer (exact match). Full: write pointer equals synchronized read pointer with the two MSBs inverted. The extra MSB distinguishes "same address, full" from "same address, empty."

📏

Power-of-2 Depth Constraint

FIFO depth must be 2^N for Gray code math to work correctly. The binary-to-Gray and Gray-to-binary conversions exploit XOR properties that only hold for power-of-2 address spaces.

Implementation

Verilog Snippet — Gray Code Conversion

// Binary to Gray code conversion
assign gray_ptr = (binary_ptr >> 1) ^ binary_ptr;

// Gray to Binary conversion (for address generation)
assign binary_ptr[N]   = gray_ptr[N];
genvar i;
generate
  for (i = N-1; i >= 0; i = i - 1) begin
    assign binary_ptr[i] = binary_ptr[i+1] ^ gray_ptr[i];
  end
endgenerate

// 2-FF Synchronizer
always @(posedge rclk or negedge rrst_n) begin
  if (!rrst_n) {wq2_rptr, wq1_rptr} <= 0;
  else          {wq2_rptr, wq1_rptr} <= {wq1_rptr, wptr};
end

Stack

Technology & References

Component	Technology	Purpose
HDL	`Verilog / SystemVerilog`	RTL implementation
Simulation	`ModelSim / Vivado Sim`	Functional verification
Synthesis	`Vivado / Synopsys DC`	FPGA and ASIC targeting
CDC Analysis	`CDC Lint Tools`	Structural CDC checks
Reference Paper	`Cummings SNUG 2002`	"Simulation and Synthesis Techniques for Asynchronous FIFO Design"
Application	`72ns Gateway`	CDC between market data and order logic clocks