How to generate Gray Codes for non-power-of-2 sequences

More recently, a reader posed an interesting question with regard to using Gray codes for FIFO counters. This question was: "Is it possible to generate a Gray code counter/sequence for any non-power-of-2 number (so long as it is an even number)? (Click Here to see the original question in more detail.)

Being up to my ears in alligators fighting fires (I never metaphor I didn't like), I posed this query to the readers of Programmable Logic DesignLine (www.pldesignline.com) and was soon deluged with responses. The thing that amazed me the most was that folks attacked this problem from so many angles and came up with so many different solutions.

What was the question again?
Just to make sure we're all tap-dancing to the same drum beat, let's quickly remind ourselves as to the original problem. Suppose we have a FIFO (First-In First-Out) memory for which we will require a read pointer and a write pointer.

As a starting point, let's 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. One way to implement our read and write pointers would be as binary counters, which means they are each going to be 4 bits wide. The problem here is that multiple bits may change when transitioning from one value to another. For example, four bits change when one of the pointers 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 as shown above, 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.

So, is it possible to create a Gray code sequence for any non-power-of-2 number (so long as it is an even number)? Let us see. . .

A sledgehammer approach
Actually, before we leap into the fray, I did receive one email that read as follows:

I'm sure someone will have a more formal proof, but logically you can think of the grey code counter as walking though a Karnaugh map of the counter bits. Given this, you can always extend the "walk" by two. For example, one step right becomes down, right, up. So, I'm confident you can conclude that the grey code sequence always exists.

Well, so long as we're all confident (grin). But I was hoping for a little more than this. Now, several readers took a "sledgehammer" approach whereby they hard-coded a solution without looking for an underlying structure. For example, one reader sent the following sequence with an accompanying one-line message saying: "Not an algorithm, but it appears to work."

2. A hard-coded sledgehammer approach.

As we shall see, this solution is unknowingly based on the "adjacent pairs" technique presented in the next topic. The snag here is that I simplified the problem for the purposes of my blog. In reality, the guy who posed the original question is looking to create a FIFO with a memory size of 1128, which means we really require some algorithmic way to do this rather than hammering it out by hand.

Throwing away adjacent pairs
Quite a few readers noted that – using our original gray code as the base code – wherever you have a pair of adjacent states where the least-significant bit does not change, then the states before and after such a pair always differ by exactly one bit.

3. Throwing away adjacent pairs.

For example, consider the first four codes in the left-hand table: 0000, 0001, 0011, 0010. If we remove the two shaded codes (0001 and 0011) we are left with 0000 and 0010, which differ by only one bit. So by removing one pair from the left-hand table we have a 14-count sequence, removing any two pairs gives us a 12-count sequence, and removing any three pairs gives us a 10-count sequence (it would be pointless to remove four pairs to give us an 8-count sequence, because we could achieve the same effect by dropping down to a 3-bit Gray code).

In fact, we can mix-and-match to some extent, because we could remove one pair of codes whose least-significant bit was 1 and another pair whose least-significant bit was 0 so long as these pairs are not themselves adjacent to each other.