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 fifth and final installment of our mini-series, we ponder the concept of "n-ary" (non-Boolean) Gray codes.

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 4 we took things one step further by contemplating the generation of sub-2ⁿ Gray code count sequences comprising consecutive values.

Introducing Non-Boolean Gray Codes
Thus far we've considered standard reflected binary Gray codes. As usual, of course, there's much more to the story; for example, there are a number of specialized versions of these codes, such as Balanced Gray codes, Beckett–Gray codes, Single-track Gray codes, and so forth (you might wish to check out the Wikipedia Gray Code entry for more details).

Of particular interest to us here are what we might call "n-ary Gray codes". These are also known as non-Boolean Gray codes because they use non-Boolean values in their encodings.

Let's start by considering a "4-ary" or quaternary (base-4) number system, in which each digit may carry one of four values: 0, 1, 2 and 3. Just to keep things simple, we'll restrict ourselves to playing with two-digit values. In this case, a standard quarterly count would follow the sequence 00, 01, 02, 03, 10, 11, 12, 13... as illustrated in Figure 5-1(a).

Figure 5-1. Standard versus Gray code quaternary count sequences.

The point is that we can also create gray-code equivalent as illustrated in Figure 5-1(b). As we expect, only a single digit changes between adjacent states in the Gray code version. And, as usual, observe that cycling back from the final value to the first also involves only a single digit transitioning.

All well-and-good, but what happens if we now decide to assign binary codes to each of these quaternary digits? Can we achieve a Gray code in both domains? For example, what happens if we we say that 0 in quaternary = 00 in binary, 1₄ = 01₂, 2₄ = 10₂, and 3₄ = 11₂? As illustrated in Figure 5-2, the result is not pretty.

Figure 5-2. Quaternary Gray code count with binary equivalent version #1.

As we see, although our quaternary Gray code is OK (only a single quaternary digit changes between states), the underlying binary values are not. For example, 01₄ to 02₄ in quaternary would equate to 0001₂ to 0010₂ in binary, and 30₄ to 00₄ in quaternary would equate to 1100₂ to 0000₂ in binary. In cases like these, two bits are changing, which is a "no-no".

Of course, we may simply not care, because we may never be using an underlying binary mapping. But suppose we are... is there a way around this? Actually there are a couple of things we can do. The first is to keep our existing quaternary-to-binary mapping but to modify the quaternary Gray code sequence as illustrated in Figure 5-3.

Figure 5-3. Quaternary Gray code count with binary equivalent version #2.

The alternative it to keep our original quaternary Gray code sequence, but to apply a different quaternary-to-binary mapping; for example, 0₄ in quaternary = 00₂ in binary, 1₄ = 01₂, 2₄ = 11₂, and 3₄ = 10₂ as illustrated in Figure 5-4. In this case, we've actually applied a Gray code mapping to the underlying binary assignments.

Figure 5-4. Quaternary Gray code count with binary equivalent version #3.

Not bad eh? But what happens if we wish to work in a base that's not a power of two? For example, consider a "3-ary" or ternary / trinary (base-3) system, in which each digit can adopt values of 0, 1, and 2. First of all, it's certainly possible to achieve a ternary Gray code sequence as illustrated in Figure 5-5.

Figure 5-5. Standard versus Gray code ternary count sequences.

But is it possible to implement a ternary-to-binary mapping such that we have a Gray code in both domains? Sadly, the answer is "No". And believe me, I've tried.

I started by assuming ternary 0₃ is mapped to binary 00₂, ternary 1₃ is binary 01₂, and ternary 2₃ is binary 10₂, but that didn’t work. Then I tried ternary 0₃ to binary 00₂, ternary 1₃ to binary 01₂, and ternary 2₃ to binary 11₂, to no avail. I even tried to make use of the "spare" binary code; for example mapping ternary 0₃ to both binary 00₂ and binary 10₂, while ternary 1₃ was mapped to binary 01₂, and ternary 2₃ was mapped to binary 11₂. No luck.

One thing we can do is to remove an odd number of ternary values. In this case, it is possible to achieve a Gray code on the binary side of the fence, but now we've lost the ability to make the ternary sequence Gray on every transition. Oh well... you can’t win them all (unless you can come up with something amazingly cunning, in which case I would be delighted to hear about it).

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