The Extra Pointer Bit in a FIFO

Where the interviewer goes next. Open a node to practise that follow-up.

WhyWhat IfProve ItBreak ItCompareScale It

1. The Extra Pointer Bit in a FIFO
2. CompareA Level Counter Versus the Extra Pointer BitL1 JuniorL2 Mid-Level

   Compare keeping a level counter with using the extra pointer bit.

   Reveal the Model Answer

   A level counter gives full, empty and the fill level directly, and it works for any depth. It costs a counter and an adder that updates on reads and writes. The extra bit costs one flop per pointer, but it needs a power-of-two depth. Only the extra-bit style carries over to an asynchronous FIFO, where no single counter can see both clocks.

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 A level counter gives full, empty and the fill level directly, and it works for any depth. Key point 2 It costs a counter and an adder that updates on reads and writes. Key point 3 The extra bit costs one flop per pointer, but it needs a power-of-two depth. Key point 4 Only the extra-bit style carries over to an asynchronous FIFO, where no single counter can see both clocks.

   Half-Truth

   "A counter is always simpler."

   In one clock domain it may be. Across two clocks a shared counter would need both clocks, so asynchronous FIFOs compare Gray pointers instead.

   Source Mehta, ASIC/SoC Functional Design Verification (2018) ch. 8.3.5 Design of an asynchronous FIFO using Gray code counters

   • Lesson R5.2The Synchronous FIFO: Pointers, Full, Empty, the Extra Bit
   • Lesson R5.3FIFO Depth from Burst Arithmetic
   • Lesson R6.4Gray Codes and the Asynchronous FIFO
3. Scale ItInside an Asynchronous FIFOL2 Mid-LevelL3 Senior

   Draw an asynchronous FIFO between two unrelated clocks. What crosses between the domains, and how are full and empty computed?

   Reveal the Model Answer

   The memory is written in the write domain and read in the read domain. Only the two pointers cross, each Gray-coded and through two flops. The write side compares its pointer with the synchronized read pointer to compute full. The read side compares the other way to compute empty. Each side sees the other pointer late, so a flag can stay on too long, but it is never wrongly off.

   1. Write

      The write side stores the word and steps its pointer in the same edge.

      Follow the calls, values and waits

      1. data word 16: Write side → Memory
   2. The write pointer crosses

      The pointer goes through two read-clock flops. The read side compares it with its own pointer to compute empty.

      Follow the calls, values and waits

      1. data wptr 0000: Write side → rq1, rq2
      2. data wptr 0000: rq1, rq2 → Read side
   3. Read

      The word itself never goes through a synchronizer. By the time the read side sees the pointer, the word has sat still in memory for two cycles.

      Follow the calls, values and waits

      1. data word 16: Memory → Read side
   4. The read pointer crosses back

      The write side computes full from its own pointer and its copy of the read pointer.

      Follow the calls, values and waits

      1. data rptr: Read side → wq1, wq2
      2. data rptr: wq1, wq2 → Write side

   Read the diagram as text

   • Write side: wbin_q, wptr_q, full
   • wq1, wq2: read pointer, two wclk flops
   • Memory: 8 words of 8 bits
   • rq1, rq2: write pointer, two rclk flops
   • Read side: rbin_q, rptr_q, empty

   • Write side → Memory: write word
   • Memory → Read side: read word
   • Write side → rq1, rq2: wptr_q
   • rq1, rq2 → Read side: seen
   • Read side → wq1, wq2: rptr_q
   • wq1, wq2 → Write side: seen

   Each flag is computed in its own domain, from one local pointer and one synchronized copy.

   1. Write domain

      Binary write pointer for the RAM address, Gray copy registered for the crossing.

   2. Crossing

      Gray write pointer through two read-clock flops; Gray read pointer through two write-clock flops.

   3. Read domain

      Empty when the read Gray pointer equals the synchronized write pointer.

   4. Write domain

      Full when the write Gray pointer equals the synchronized read pointer with its top two bits inverted.

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 The memory is written in the write domain and read in the read domain. Key point 2 Only the two pointers cross, each Gray-coded and through two flops. Key point 3 The write side compares its pointer with the synchronized read pointer to compute full. Key point 4 The read side compares the other way to compute empty. Key point 5 Each side sees the other pointer late, so a flag can stay on too long, but it is never wrongly off.

   What Interviewers Listen For (Mid-Level)

   A good mid-level answer draws both clock domains and shows that only the pointers cross. It explains why the flags can be late but are never unsafe.

   Misconception

   "Send the binary pointer through two flops per bit."

   Several bits change at once, and each can land on a different read edge. In the twin, the step from 7 to 8 is read as 0.

   Run It

   A 4-bit pointer crossing with different wire delays per bit, binary then Gray.

   RUNIcarus Verilog · in your browser

   Edit the code, then run it

   OutputWaves

   RunReset codeExpected: first torn value: 7 -> 0 binary pointer: 215 changes seen, 32 jumped by more than one FAIL: a binary pointer with two flops per bit showed values that were neither the old nor the next pointer

   See the Fix

   `timescale 1ps/1ps
   // A 4-bit write pointer crosses into a faster read clock. Each bit reaches the reader with its
   // own wire delay (0, 700, 1400, 2100 ps). The reader samples at its clock and decodes the value.
   module tb;
     logic wclk = 0, rclk = 0;
     logic [3:0] wcount = 0, tx = 0, wire_d = 0, s1 = 0, s2 = 0, now, prev = 0;
     int torn = 0, steps = 0;
     always #5000 wclk = ~wclk;                     // write clock, 10 ns
     always #3650 rclk = ~rclk;                     // read clock, 7.3 ns
     logic [3:0] next;
     assign next = wcount + 4'd1;
     always @(posedge wclk) begin
       wcount <= next;
       tx <= next ^ (next >> 1);   // the pointer as sent: Gray code, registered
     end
     for (genvar i = 0; i < 4; i++) begin : wires
       always @(tx[i]) wire_d[i] <= #(i * 700) tx[i];
     end
     always @(posedge rclk) begin
       s1 <= wire_d;                                // two-flop synchronizer
       s2 <= s1;
     end
     always @(s2) begin
       now = s2 ^ (s2 >> 1) ^ (s2 >> 2) ^ (s2 >> 3);   // Gray to binary
       steps++;
       if (4'(now - prev) > 1) begin
         if (torn == 0) $display("first torn value: %0d -> %0d", prev, now);
         torn++;
       end
       prev = now;
     end
     initial begin
       #2000000;
       $display("Gray pointer: %0d changes seen, %0d jumped by more than one", steps, torn);
       if (torn == 0) $display("PASS: the Gray pointer only ever showed the old or the next value");
       $finish;
     end
   endmodule
   

   Prints: Gray pointer: 199 changes seen, 0 jumped by more than one PASS: the Gray pointer only ever showed the old or the next value

   Misconception

   "Full and empty are exact in an asynchronous FIFO."

   Each side sees the other pointer two or three cycles late. Full stays high a little after a read frees space. It is safe, and it costs some throughput.

   Source Mehta, ASIC/SoC Functional Design Verification (2018) ch. 8.3.5 Design of an asynchronous FIFO using Gray code counters

   Half-Truth

   "Gray code makes any counter safe to cross."

   Only if it steps by one between samples. The depth must be a power of two, so the wrap is also one step. Reset can also change many bits at once.

   Source Golson, Synchronization and Metastability (SNUG Silicon Valley 2014) §5.2

   • Lesson R6.4Gray Codes and the Asynchronous FIFO
   • Lesson R6.6Capstone: The Asynchronous FIFO with an Assertion Suite
   • Lesson R6.2The Two-Flop Synchronizer and What It Cannot Carry
   • Problem R6.4.1A Gray Pointer
   • Problem R6.4.2The Torn Pointer
   • Problem R6.6.1The Asynchronous FIFO
4. WhyWhy Async FIFO Flags Are Late but SafeL2 Mid-Level

   Why is it acceptable that the write side sees the read pointer a few cycles late?

   Reveal the Model Answer

   A late read pointer looks like fewer reads than really happened. So the write side thinks the FIFO is fuller than it is, and full may stay high a little too long. It never thinks there is space that is not there. The same reasoning makes empty late but safe on the read side.

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 A late read pointer looks like fewer reads than really happened. Key point 2 So the write side thinks the FIFO is fuller than it is, and full may stay high a little too long. Key point 3 It never thinks there is space that is not there. Key point 4 The same reasoning makes empty late but safe on the read side.

   Misconception

   "The delay can make the FIFO overflow."

   A stale read pointer can only make full assert early or release late. Overflow would need the write side to see reads that have not happened.

   Source Mehta, ASIC/SoC Functional Design Verification (2018) ch. 8.3.5 Design of an asynchronous FIFO using Gray code counters

   • Lesson R6.4Gray Codes and the Asynchronous FIFO
5. What IfSetting an Almost-Full ThresholdL2 Mid-LevelL3 Senior

   What if the source needs a warning before full, because it takes 3 cycles to stop?

   Reveal the Model Answer

   Raise almost-full when the free space drops to the number of words the source can still send after the warning. Here that is 3, plus any cycles the flag itself takes to reach the source. In an asynchronous FIFO, the flag is already pessimistic, which adds a little margin at no extra cost.

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 Raise almost-full when the free space drops to the number of words the source can still send after the warning. Key point 2 Here that is 3, plus any cycles the flag itself takes to reach the source. Key point 3 In an asynchronous FIFO, the flag is already pessimistic, which adds a little margin at no extra cost.

   Delivery

   "Almost-full at half depth is a good default."

   The threshold must come from the source's stopping delay. Half depth either wastes space or, for a slow-to-stop source, is not enough.

   • Lesson P1.6Flow Control: Backpressure, FIFO Depth and Credits
   • Lesson R5.3FIFO Depth from Burst Arithmetic
6. CompareGray-Code Pointers vs a Handshake for Multi-Bit CrossingsL2 Mid-Level

   Compare a Gray-coded value with a request/acknowledge handshake for carrying a multi-bit value across clock domains.

   Reveal the Model Answer

   Gray code changes one bit per step, so a value caught mid-change is either the old or the new one. It suits counters that move by one, such as FIFO pointers. A handshake holds any data stable while a synchronized request crosses and an acknowledge comes back. It carries any value, but takes several cycles per transfer. Choose Gray for streaming pointers, and a handshake or FIFO for occasional wide data.

   1. Cycle 1

      Edge 21: empty is 1 while the FIFO holds two words. The read side has not seen those writes yet.

   2. Cycle 2

      Edge 22: the pointer steps from 1000 to 0000, one bit, the Gray wrap from 15 to 0.

   3. Cycle 4

      Edge 24: read_level is 1 with two words held. Low is safe; the read side just waits a cycle.

   Edges 20 to 25 of the run: the level the read side sees never rises above the words held.

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 Gray code changes one bit per step, so a value caught mid-change is either the old or the new one. Key point 2 It suits counters that move by one, such as FIFO pointers. Key point 3 A handshake holds any data stable while a synchronized request crosses and an acknowledge comes back. Key point 4 It carries any value, but takes several cycles per transfer. Key point 5 Choose Gray for streaming pointers, and a handshake or FIFO for occasional wide data.

   Half-Truth

   "Gray-code any multi-bit bus and it crosses safely."

   Gray only helps when consecutive values differ by one step. Arbitrary data jumps change many bits at once.

   Source Cummings, CDC Design and Verification Techniques (SNUG Boston 2008) §5.7.2-5.7.4; Mehta, ASIC/SoC Functional Design Verification ch. 8.3.4 (p155-156)

   • Lesson R6.2The Two-Flop Synchronizer and What It Cannot Carry
   • Lesson R6.3Pulse, Toggle and Handshake Synchronizers
   • Lesson R6.4Gray Codes and the Asynchronous FIFO
   • Problem R6.4.1A Gray Pointer
   • Problem R6.4.2The Torn Pointer
7. Prove ItSolve R6.4.2: The Torn PointerSimulator-graded

   Show it, don't just say it: this Silicon Lab problem is graded by the simulator.

   Open Problem R6.4.2

8. Break ItBreaking a Gray Pointer CrossingL3 Senior

   The FIFO uses Gray pointers and two-flop synchronizers. How could it still fail in silicon?

   Reveal the Model Answer

   Gray code assumes the bits arrive close together. If the wires of one pointer differ by more than about a clock period, two steps can mix. Logic between the Gray register and the synchronizer can glitch. And a Gray pointer that is computed but not registered can show several bits changing.

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 Gray code assumes the bits arrive close together. Key point 2 If the wires of one pointer differ by more than about a clock period, two steps can mix. Key point 3 Logic between the Gray register and the synchronizer can glitch. Key point 4 And a Gray pointer that is computed but not registered can show several bits changing.

   Missed Corner

   "Put a false path on the pointer crossing; it is synchronized."

   A false path lets the bits of one pointer be routed with any skew. The crossing then needs a maximum-delay or skew constraint instead.

   Source Lesson L8.1, Constrain the asynchronous FIFO (set_max_delay on the pointer crossing, false path for hold only)

   • Lesson R6.4Gray Codes and the Asynchronous FIFO
   • Lesson L8.1Capstone: Constrain the Asynchronous FIFO
9. Scale ItCDC Sign-Off on a Many-Clock SoCL3 SeniorL4 Staff

   How do you sign off clock domain crossings on an SoC with dozens of clocks?

   Reveal the Model Answer

   Start with structural analysis: define the clocks and their relationships. Then let the tool find every crossing and check that each has the right synchronizer for its type. Next comes protocol checking: each scheme's rules, such as hold times and Gray steps, become assertions in formal and simulation. Add reconvergence checks and reviewed waivers. Use metastability injection in simulation to expose designs that assume exact timing.

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 Start with structural analysis: define the clocks and their relationships. Key point 2 Then let the tool find every crossing and check that each has the right synchronizer for its type. Key point 3 Next comes protocol checking: each scheme's rules, such as hold times and Gray steps, become assertions in formal and simulation. Key point 4 Add reconvergence checks and reviewed waivers. Key point 5 Use metastability injection in simulation to expose designs that assume exact timing.

   Tool as Truth

   "Our regressions pass with all clocks running, so CDC is covered."

   RTL simulation never goes metastable and rarely hits the bad clock phase. CDC needs structural and protocol checks, not only passing tests.

   Source Mehta, ASIC/SoC Functional Design Verification ch. 8.5 (PDF p186-188); Sutherland, RTL Modeling with SystemVerilog ch. 8.1.6

   Wrong Altitude

   A staff-level answer that stops at "run the CDC tool".

   The interviewer wants the flow: constraints, structure, protocol, reconvergence, waiver review and who owns each step.

   • Lesson F5.6CDC and RDC with Formal
   • Lesson R6.2The Two-Flop Synchronizer and What It Cannot Carry
10. Prove ItSolve R6.6.1: The Asynchronous FIFOSimulator-graded

    Show it, don't just say it: this Silicon Lab problem is graded by the simulator.

    Open Problem R6.6.1

11. WhyWhy FIFO Flags Are Often RegisteredL2 Mid-Level

    Why might you register full and empty instead of computing them from the pointers?

    Reveal the Model Answer

    Combinational flags sit after a pointer compare, and the other block uses them in its own logic in the same cycle. That makes a long path across two blocks. Registered flags start that path at a flop. The cost is that you compute next-cycle flags from the next pointer values, which is easy to get wrong at the boundaries.

    Self-Check

    Tick each key point you covered in your answer.

    Key point 1 Combinational flags sit after a pointer compare, and the other block uses them in its own logic in the same cycle. Key point 2 That makes a long path across two blocks. Key point 3 Registered flags start that path at a flop. Key point 4 The cost is that you compute next-cycle flags from the next pointer values, which is easy to get wrong at the boundaries.

    Missed Corner

    "Registering the flag just delays it by a cycle; that is harmless."

    A flag that is one cycle late lets one extra write in at full or one read at empty. Registered flags must be computed from the next pointers, not delayed.

    Source Lesson R5.2 and problem R5.2.2 brief: a write is accepted only when write_en is 1 and full is 0, a read only when read_en is 1 and empty is 0, both on the flags before the edge; a refused write changes nothing

    • Lesson R5.2The Synchronous FIFO: Pointers, Full, Empty, the Extra Bit
    • Lesson R4.2Latency, Throughput and Registered Outputs
12. Prove ItSolve R5.2.1: A FIFO of Any DepthSimulator-graded

    Show it, don't just say it: this Silicon Lab problem is graded by the simulator.

    Open Problem R5.2.1

13. What IfA FIFO Whose Depth Is Not a Power of TwoL2 Mid-Level

    Asked if they claim it works for any depth

    What if the FIFO must be 6 entries deep?

    Reveal the Model Answer

    The address bits no longer wrap by themselves at the end of the memory. Each pointer must wrap by compare: back to 0 after 5. Then track full with a lap bit that flips on each wrap, or keep a level counter. Many teams just round up to 8 when the area allows.

    Self-Check

    Tick each key point you covered in your answer.

    Key point 1 The address bits no longer wrap by themselves at the end of the memory. Key point 2 Each pointer must wrap by compare: back to 0 after 5. Key point 3 Then track full with a lap bit that flips on each wrap, or keep a level counter. Key point 4 Many teams just round up to 8 when the area allows.

    Missed Corner

    "Use a 3-bit pointer and let it run to 7; the last two slots just stay unused."

    Then the FIFO holds 8, not 6, and full arrives late. Any logic sized for 6 overflows.

    Source Lesson R5.3 (a FIFO of any depth) and problem R5.2.1 brief

    • Lesson R5.3FIFO Depth from Burst Arithmetic
    • Problem R5.2.1A FIFO of Any Depth