# Gray Code Fundamentals – Part 3

In this, the third installment of our mini-series, we take a look at generating sub-2^{n} 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^{n} 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 ^{n} 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

_{2}to 1000

_{2}. 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 1000

_{2}, the next count will return us to our initial value of 0000

_{2}, 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: 0000

_{2}, 0001

_{2}, 0011

_{2}, 0010

_{2}, 0110

_{2}, 0111

_{2}, 0101

_{2}, 0100

_{2}, 1100

_{2}, 1101

_{2}. The problem is that three bits will change value on the next transition, which will return us to our starting value of 0000

_{2}from our current value of 1101

_{2}.

**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: 0000

_{2}, 0001

_{2}, 0011

_{2}, and 0010

_{2}. If we remove the two shaded codes (0001

_{2}and 0011

_{2}) we are left with 0000

_{2}and 0010

_{2}, 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-2

^{n}Gray code count sequences

*comprising consecutive values*.

**Author's Note:**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**.

Author

Max The Magnificent 6/17/2011 6:40:23 PM