In this, the third installment of our mini-series, we take a look at generating sub-2n 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-2n 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-2n 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 01112 to 10002. 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.
Observe that when we reach the final (maximum) Gray code value of 10002, the next count will return us to our initial value of 00002,
which means that – as we expect – only a single bit changes for this
transition. 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: 00002, 00012, 00112, 00102, 01102, 01112, 01012, 01002, 11002, 11012. The problem is that three bits will change value on the next transition, which will return us to our starting value of 00002 from our current value of 11012.
Figure 3-1. Binary versus Gray codes.
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: 00002
, and 00102
. If we remove the two shaded codes (00012
) we are left with 00002
, 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 of this miniseries when we come to consider the techniques we might use to generate sub-2n
Gray code count sequences comprising consecutive values
The material presented here 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).
About the Author
Clive “Max” Maxfield is president of Maxfield High-Tech Consulting
and editor of the EE Times Programmable Logic Designline
. After receiving his B.Sc. in Control Engineering in 1980 from Sheffield Hallam University, Sheffield, England, Max began his career as a designer of central processing units for mainframe computers. Over the years, he has designed and built all sorts of interesting "stuff" from silicon chips to circuit boards and brainwave amplifiers to Steampunk “Display-O-Meters”. Max has also been at the forefront of Electronic Design Automation (EDA) for more than 20 years.
Max is the author and co-author of a number of books, including Bebop To The Boolean Boogie (An Unconventional Guide to Electronics)
, FPGAs: Instant Access
, and How Computers Do Math