An interesting Gray code FIFO counter question

Here is the gist of the problem. Suppose we have a FIFO for which we have a read and a write pointer. As a starting point, assume that the size of the FIFO (the number of words it contains) is a power of 2 – let's say 2^4 = 16 words – which means that our read and write pointers are each going to be 4 bits wide.

One way to implement these pointers would be as binary counters. The problem here is that multiple bits may change when transitioning from one value to another. For example, four bits change when when the pointer transitions from 7 to 8 (0111 to 1000 in binary).

As an alternative, we can use a Gray Code counter, in which only one bit changes as we transition from one value to another.

1. Binary code versus 4-bit Gray code.

Observe that when we reach the final (maximum) Gray code value of 1000, the next "count" will return us to our initial value of 0000, which means that – as we expect – only a single bit changes for this transition also.

But now suppose that – instead of having 16 words – we wish our FIFO to contain only 10 words. If we use our original Gray code, the sequence will now be as follows: 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101. The problem is that three bits will change value on the next transition, which will return us to our starting value of 0000 from our current value of 1101.

Our friend says that he believes that it is possible to create a Gray code sequence for any non-power-of-2 number (so long as it is an even number), but that he has not been able to track down any methods on how to generate such a sequence.

I replied that if anyone knew how to do this, it would be the readers of Programmable Logic DesignLine (hint hint).

Questions? Comments? Feel free to email me – Clive "Max" Maxfield – at max@techbites.com). And, of course, if you haven't already done so, don't forget to Sign Up for our weekly Programmable Logic DesignLine Newsletter.