It's funny how some things stick in your mind, isn't it? A few days ago I posted a blog on "n-ary" (non-Boolean) Gray codes, and this rascally rapscallion of a topic has been bouncing back and forth like a Super Ball in my brain ever since.
Here's where I'm at so far. Let's start with the binary number system because that's the way I tend to think by default. In the case of binary, we can say that a Gray code is one in which only a single bit (binary digit) changes when transitioning from one state to another. A quick-and-easy technique for generating binary Gray codes that's easy to remember and use is as follows:
- Commence with the simplest gray code possible; that is, for a single bit.
- Create a mirror image of the existing gray code below the original values.
- Prefix the original values with 0s and the mirrored values with 1s.
- Repeat steps (2) and (3) until the desired width is achieved.
An example of this mirroring process (which is more correctly referred to as a "reflected binary code") used to generate a 3-bit gray code is as follows:
In particular, observe that performing one more step from 100 back to 000 also involves only a single bit transitioning.
Another technique is to commence with a state of all zeros, and to then generate a Gray code by always changing the least significant bit that results in a new state. Alternatively, we can just "throw one together" by hand as follows:
So, why am I waffling on about this here? Well, until a reader posted a question in the blog referenced earlier, I hadn't really thought about "n-ary Gray codes" (these are also known as a "non-Boolean Gray codes" because they use non-Boolean values in their encodings).
Purely for the sake of discussion, let's start by playing with a "4-ary" or quaternary (base-4) number system, in which each digit may carry one of four values: 0, 1, 2 and 3. Now consider a standard quaternary count versus a Gray code quaternary equivalent (for the sake of simplicity we will experiment with 2-digit values):
As we would expect, only one digit changes between adjacent states in the Gray code version. And, as usual, observe that performing one more step from 30 back to 00 also involves only a single digit transitioning.
Now, this is where it starts to get interesting, because I started thinking (don't laugh, it happens sometimes when I least expect it) ... "what happens if we subsequently assign binary codes to each of these quaternary digits?"
For example, if we say that 0 in quaternary = 00 in binary, 1 = 01, 2 = 10, and 3 = 11, then 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, which means that 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... Well, we could get around this by applying a different assignment, such as 0 in quaternary = 00 in binary, 1 = 01, 2 = 11, and 3 = 10. That is, we've applied a Gray code mapping to the underlying binary assignments.
Are we having fun yet? Well, how about if we wish to work in a base that's not a power of two. For example, what about a "3-ary" or ternary / trinary (base-3) system, in which each digit can adopt values of 0, 1, and 2? Is it even possible to get a full Gray code here? Consider the following sequence (again, we'll play with 2-digit values for the sake of simplicity):
Although the right-hand table may look like a Gray code at first glance, it fails at the final fence, because the transition from 22 back to 00 involves two digits changing at the same time.
Now, this isn't to say that it isn't possible to come up with some sequence that passes through all nine combinations and returns to 00 with only a single digit change each time. But I'm a bit busy at the moment, so I'll hand this over to you... can you come up with such a sequence? And, if so, can you map binary values onto the ternary digits such that we have Gray codes in both bases?
What? You want more? Well, assuming that it is possible to solve the previous problem... then how about starting by creating a 3-digit base-11 Gray code, and then mapping each of these base-11 digits onto two base-7 digits, and then mapping each base-7 digit onto two base-3 digits, and then mapping each base-3 digit into two binary digits such that the entire sequence is a Gray code in all of these bases...
Questions? Comments? Feel free to email me – Clive "Max" Maxfield – at firstname.lastname@example.org). And, of course, if you haven't already done so, don't forget to Sign Up for our weekly Programmable Logic DesignLine Newsletter.