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-2n Gray code count sequences; and in Part 4 we took things one step further by contemplating the generation of sub-2n Gray code count sequences comprising consecutive values.
In this, the fifth and final installment of our mini-series, we ponder the concept of "n-ary" (non-Boolean) Gray codes.
Introducing non-Boolean Gray codes
Thus far we've considered only standard reflected binary Gray codes. As is usual in electronics, 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 simply say that 04
(that is, 0 in quaternary = 00 in binary), 14
, and 34
? In fact, as is 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, 014
in quaternary would equate to 00012
in binary, and 304
in quaternary would equate to 11002
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, 04
in quaternary = 002
in binary, 14
, and 34
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 03
is mapped to binary 002
, ternary 13
is binary 012
, and ternary 23
is binary 102
, but that didn’t work. Then I tried ternary 03
to binary 002
, ternary 13
to binary 012
, and ternary 23
to binary 112
, to no avail. I even tried to make use of the "spare" binary code; for example mapping ternary 03
to both binary 002 and
, while ternary 13
was mapped to binary 012
, and ternary 23
was mapped to binary 112
. 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).
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
If you found this article to be of interest, visit Programmable Logic Designline
where you will find the latest and greatest design, technology, product, and news articles with regard to programmable logic devices of every flavor and size (FPGAs, CPLDs, CSSPs, PSoCs...).
Also, you can obtain a highlights update delivered directly to your inbox by signing up for my weekly newsletter – just Click Here
to request this newsletter using the Manage Newsletters tab (if you aren't already a member you'll be asked to register, but it's free and painless so don't let that stop you [grin]).