IntroductionIn the not-so-distant past, I published a mini-series of four "Logic 101" articles encompassing
Assertion-Level Logic,
Positive-vs-Negative Logic,
Reed-Muller Logic, and
Gray Codes.
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.
Pruning the middleNow, the previous solution is easy to use by hand, but it's not great as the basis for an algorithmic approach, because it would require us to keep track as to which pairs of codes we've removed.
In fact, the solution is rather simple. Remember that we generated our original 4-bit Gray code using what I call the "mirroring method" (see my Original Article for more details) – a more correct name might be to call this a "recursive reverse-and-prefix" approach.
Well, several readers noted that is possible to simply remove pairs of entries from the center of the table around the "mirror line", although everyone expressed themselves in different ways. For example, one message simply said:
It's quite easy to build gray codes which other sequences numbers then 2,4,8,16 etc. Just use the mirror technique and stop the right position.
Other folks went into a little more detail, such as the contributor who noted:
Here's a method that works for any number that can be divided by two. Let's say your even number is 58, in which case the next highest power of two is 64. So, we begin by generating a Gray code sequence for 64, BUT we stop at 29 (halfway to 58). We then forget about the rest of the "64" Gray codes, replace the MSB with a 1 (just like normal Gray codes), and mirror our original 29 codes (down to 0).
Let's look at this in a little more detail. As shown in the following figure, if we desire a 14-count sequence, we simply remove two entries from the middle – the one immediately above the "mirror" line and one immediately below. Similarly, if we are looking for a 12-count sequence, we remove two entries above the "mirror" line and two below, and so forth.
4. Pruning the middle of the sequence. Pruning the ends
There's always another way of doing something. For example, quite a few folks came up with a logical counterpart to the previous solution. A typical suggestion was as follows:
I just read the article in which you asked how to create a non-power-of-2 modulo Gray code counter. I believe there are a lot of ways to achieve this, but I think that probably simplest one is to remove the same numbers of entries from the top and from the bottom of a traditional power-of-2 Gray code counter.
And of course, this is also perfectly correct. As shown in the following figure, if we desire a 14-count sequence, we simply remove one entry from the top of the table and one from the bottom; if we are looking for a 12-count sequence, we remove two entries from the top and two from the bottom, and so forth.
5. Pruning the ends of the sequence. And what about ring and twisted-ring counters? As discussed in the relevant Wikipedia Entry a Ring Counter (or Overbeck Counter) is formed from a circular shift register where the output from the last register element is fed back into the input to the first (this is classified as a "counter" because it cycles through a specific sequence of states). Such a counter is used to circulate a single one (or zero) around the ring. So if we wanted a 10-state count, we would require a 10-element shift register as illustrated below:
6. A 10-bit ring counter sequence. Of course, this does us absolutely no good at all because this isn't a Gray code sequence (two bits change for every transition). But suppose we use a Twisted Ring Counter (or Johnson Counter) in which the output from the last stage is inverted before being fed back to the input to the first stage. In this case, a 5-bit counter will provide us with the following 10-count sequence:
7. A 5-bit twisted ring counter sequence. In conclusion
Good Grief Charlie Brown. There's a lot more to this than meets the eye. Actually, I haven't even touched on the really interesting stuff yet, because I have some cunning ideas I'm mulling over in the back of my mind (there's just too much to do and too little time to do it all in).
But before we close, there are a couple of things you might be interested in reading and/or playing with. First of all, you may wish to check the fairly wide-ranging Wikipedia Entry on Gray codes. In addition to the Gray code sequence upon which we've based our discussions, there are also Beckett"Gray codes, Snake-in-the-Box codes, Single-Track Gray codes and n-ary Gray codes (there are also known as non-Boolean Gray codes).
5.assaultcube
6.nexuiz
8.alien arena
