Difficulty: Easy · Puzzle 3 of 6 · Topic: CDC Basics Puzzles
A 4-bit counter value moves from 7 to 8 and every bit is synchronised separately; each bit may be captured in its old or its new state. How many different values can the receiver read for plain binary and for gray code? Does the gray scheme also work for the step 15 to 0?
Count the bits that change in each step.
1) Binary 7 = 0111 and 8 = 1000: all four bits change, so each bit can be old or new independently: 2^4 = 16 possible captured values, from 0 to 15.
2) Gray 7 = 0100 and 8 = 1100: only the top bit changes, so there are 2 possible values: 0100 or 1100, which are the gray codes of 7 and 8.
3) So with gray code a skewed or late capture gives either the old or the new count, never a wild value. (3 to 4 in binary: 011 to 100, all three bits change: 8 values.)
4) Gray code changes exactly one bit at every step including the wrap from 15 to 0 (1000 to 0000), so it works there too, but only for sequences that step by one (counters and FIFO pointers), not for arbitrary jumps.Answer: Binary 7 to 8: 16 possible captured values; gray: only 2 (the old or the new count). Gray also works for the wrap 15 to 0, but only for sequences that change by one at a time.
Checked by running a model of the rule in a Python model. A Python model enumerates every old/new combination of the changing bits.
Thinking gray code makes any bus safe. It guarantees a single-bit change per step, so it only works for values that move by one, like pointers; a bus that can jump from any value to any other still changes several bits at once and needs a handshake or FIFO.
What must also be true of the pointer for gray code to work in an asynchronous FIFO? Model answer: the pointer must step by exactly one per event and the number of states must be a power of two (so the wrap is also a one-bit change), which is why FIFO depths are powers of two.