Difficulty: Hard · Puzzle 5 of 6 · Topic: CDC Basics Puzzles
An 8-deep asynchronous FIFO uses 4-bit pointers (one extra wrap bit) kept in gray code. In the write domain the binary write pointer is 9 and the synchronised read pointer is the gray code of 1. Is the FIFO full, and what exact comparison do you write? If the read side has meanwhile moved to 2, is the flag wrong?
Full means the pointers differ by 8: the two top gray bits are inverted and the rest are equal.
1) Gray of 9 (1001) is 1101; gray of 1 (0001) is 0001.
2) Full means write is exactly one lap ahead: (w - r) mod 16 = 8. In gray code that is: wgray equals rgray with the top two bits inverted.
3) rgray = 0001: inverting the top two bits gives 1101, which equals wgray. So the FIFO looks full: 9 - 1 = 8 entries.
4) Empty is simply wgray == rgray (compared in the read domain with the synchronised write pointer).
5) If the read pointer has really moved to 2, the true occupancy is 7: not full. But the write side only sees the old pointer, so its full flag stays on a little too long. That is conservative (a later write, never an overwrite), and it is the correct direction of error; the empty flag is conservative in the same way.Answer: Yes, full: wgray 1101 equals rgray 0001 with its top two bits inverted. The compare holds for every one of the 256 pointer pairs (it matches (w - r) mod 16 == 8). If the read pointer has already moved to 2 the true occupancy is 7, so the flag is stale but safe: it can only delay a write, never allow an overflow.
Checked by running a model of the rule in a Python model. A Python model checks the gray-code full and empty tests against binary occupancy for every pointer pair.
Comparing the gray pointers for plain equality to detect full (that is the empty test) or decoding them in the other domain. The one extra wrap bit is what tells full from empty; the top-two-bits-inverted compare is the gray-code form of 'one lap ahead'. Stale pointers err on the safe side by design.
Why can the FIFO depth not be 6? Model answer: gray code only changes one bit per step if the number of states is a power of two; with six states the wrap from the last state to the first changes several bits, so the pointer crossing is no longer safe.