The term Gray code is typically used to refer to a binary sequence in which only a single bit changes value when transitioning between adjacent states. In this, the third installment of our mini-series, we take a look at generating sub-2ⁿ Gray code count sequences.

Just to remind ourselves, in Part 1 we considered the concept of Gray codes in general; in Part 2 we pondered generating Gray codes and also Binary-to-Gray and Gray-to-Binary conversions; in Part 4 we will consider the generation of sub-2ⁿ Gray code count sequences comprising consecutive values; and in Part 5 we will take a leap into the unknown to wrestle with the concept of "n-ary" (non-Boolean) Gray codes.

Generating Sub-2ⁿ Gray Code Count Sequences
Just to make sure we're all tap-dancing to the same drum beat, let's briefly set the scene. Consider a 4-bit binary counter. As we've already discussed, multiple bits may change when transitioning from one value to another. For example, four bits change when one of the pointers transitions from 0111₂ to 1000₂. If multiple bits transitioning will cause us problems, we may decide to use a Gray code counter, in which only one bit changes as we transition from one value to another as illustrated in Figure 3-1.

Figure 3-1. Binary versus Gray codes.

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. Also observe that we've shown the hexadecimal values associated with each binary pattern in bold (we'll return to consider our interest in these values in Part 4 of this mini-series).

Now, suppose that – instead of sequencing through all 16 values – for some reason we actually wish to cycle through only 10 words. If we use our original Gray code as shown in Figure 3-1, 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...

Throwing Away Adjacent Pairs
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 as illustrated in Figure 3-2.

Figure 3-2. Throwing away adjacent pairs in the Gray code sequence.

For example, consider the first four codes in the left-hand table: 0000₂, 0001₂, 0011₂, and 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 any such 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 Middle
Our 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, in Part 2 of this mini-series, we generated our original 4-bit Gray code using what I call the "mirroring method"? Well, it's possible to simply remove pairs of entries from the center of the table around the "mirror line" as illustrated in Figure 3-3.

Figure 3-3. Pruning the middle of the Gray code sequence.

If we desire a 14-count sequence, for example, 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.

Pruning the Ends
The funny thing about digital logic is that there are almost always multiple ways of doing anything. For example, the logical counterpart to the previous solution is to remove the same numbers of entries from the top and from the bottom of a Gray code sequence as illustrated in Figure 3-4.

Figure 3-4. Pruning the ends of the Gray code sequence.

In this case, 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.

Now this is all-well-and-good, but there is a slight issue with all of the above techniques that might cause problems in certain applications. We will discuss this more in Part 4 when we come to consider the techniques we might use to generate sub-2ⁿ Gray code count sequences comprising consecutive values.

Author's Note: This mini-series of articles was abstracted from my book Bebop to the Boolean Boogie (An Unconventional Guide to Electronics) 3rd Edition, with the kind permission of my publisher, Newnes (an imprint of Elsevier).

Author's Note: My friend Jay Dowling is an absolute expert with regard to all aspects of Gray codes. In fact, Jay leads the Gray Code Community here at TechBites.com. So if you're interested in learning more, bounce over to the Gray Code Community where you'll discover all sorts of "stuff" (including some cunning Gray-code related generator programs that Jay has created).