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 fourth installment of our mini-series, we take a look at generating sub-2ⁿ Gray code count sequences comprising consecutive values.

Just to refresh our memories, 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 3 we considered the generation of sub-2ⁿ Gray code count sequences; 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 with Consecutive Values
With regard to the topic we introduced in Part 3 of the mini-series in which we generated non-power-of-2 sequences; the solutions we came up with will be perfectly OK for some applications, but there may be problems if we want to use them for certain tasks, such as pointers into memory arrays.

Let's suppose that – as opposed to a full 2ⁿ count (16 values in the case of the 4-bit examples we've been playing with) – we wish to use a reduced count sequence, such as 14, 12, or 10. Obviously this is easy-peasy when using pure binary addressing schemes as illustrated in Figure 4-1.

Figure 4-1. Implementing reduced binary count sequences.

As we see, all we have to do is to remove states from the end of the count sequence and to implement corresponding smaller arrays of memory locations.

But now let's now consider the case of the various Gray code implementations. As we discussed in Part 3, there are several approaches we can use in order to generate a reduced-count Gray code sequence. One of these is to simply remove pairs of values from either side of the "mirror line" as illustrated in Figure 4-2.

Figure 4-2. One way to implement reduced Gray code sequences.

OK so far, but now let's consider what happens when we apply one of these reduced sequences to our addressing logic; for example, let's take our 10-count example. Basically we are going to end up with "holes" in our memory array as illustrated in Figure 4-3.

Figure 4-3. This approach leaves "holes" in our memory array.

As we see, the sequence followed by this Gray code counter is: 0, 1, 3, 2, 6, E, A, B, 9, 8, and it then cycles back to 0 again; each step is a Gray code (single-bit) transition, including the wrap-around from 8 to 0. Meanwhile, the right-hand side of Figure 4-3 simply reflects which locations are hit in the memory array – not the order in which they are hit.

The end result is that it is no longer a trivial task to create a cut-down memory array, because these "holes" are going to mess everything up. So, the real question (the "Crux of the Biscuit" as it were), is: "Is it possible to create a Gray code sequence to address a 10-word FIFO using sequential addresses of 0-to-9?"

Note: As an aside, the full quote by American composer, guitarist, singer, film director, and satirist Frank Vincent Zappa is: "The crux of the biscuit is the apostrophe." (I actually know what he meant by this, but that's a story for another day.)

Well, here's a technique that Mike Jarvis, a Design Engineer at Cray, taught me. First of all we create an empty table with the number of entries we desire; ten in the case of this particular example. We set the least-significant bit to 0 for all of the entries in the upper half of the table, and to 1 for all of the entries in the lower half of the table as illustrated in Figure 4-4(a).

Figure 4-4. The process of sub-2ⁿ consecutive Gray code generation.

Next, we start with our highest two addresses (8 and 9, which equate to 1000₂ and 1001₂ in the case of this example) straddling the "mirror line" as illustrated in Figure 4-4(b). And then we populate the rest of the table using smaller values working out from the center as illustrated in Figure 4-4(c). The result is a 10-sequence Gray code using consecutive addresses of 0000₂ to 1001₂ (0 to 9 in decimal) as illustrated in Figure 4-5.

Figure 4-5. Hurray! No "holes" in the memory array.

I tell you, it amazes me that you can have a concept as simple as Gray codes, but every time you think you know it all, something new comes up that blows your socks off. Of course the test case shown here is just a proof-of-concept. We populated the table by hand; we don't yet have an algorithm for this. Can we extrapolate this to a generic algorithm that allows us to do the same thing for any non-2ⁿ Gray code sequence? In the case of a 1128-word memory array, for example, can we generate a Gray code sequence that ends up using sequential addresses of 0-to-1127 in the memory array?

Once again, I think we'll leave this as an exercise for the reader (grin). Of course, if you do work all of this out, it would make the basis for a great article that you could post here on www.TechBites.com.

OK, without any further dilly-dallying or shilly-shallying, let's head onwards and upwards to Part 5 in this mini-series, in which we consider "n-ary" (or "non-Boolean") Gray codes.

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).