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 first installment of a five-part mini-series, we consider the concept of Gray codes in general. In Part 2 we will take a look at generating Gray codes and also Binary-to-Gray and Gray-to-Binary conversions. In Part 3 we will ponder the generation of sub-2n Gray code count sequences. In Part 4 we will consider the generation of sub-2n 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.
Let's start at the very beginning…
In addition to being jolly interesting, Gray codes are fundamentally simple. Having said this, it can be a little tricky to wrap one's brain around the Gray code concept if you haven't seen it before, so let's take things one step at a time…
Suppose we have a flat panel/sheet/whatever that can move back and forth to the left and right as illustrated in Figure 1-1. (How does it move? Perhaps it's on rollers or something. Don't worry about it. That part isn't important.)
Now suppose that we want some way to determine the position of our panel… is it currently located to the left or is it on the right? How could we determine this? Well, one way would be to fabricate it as a printed circuit board (PCB) and to have one half of the top side of the board (the right-hand-side in this example) covered in copper as illustrated in Figure 1-2.
Let's assume that there's a via somewhere on the right-hand side of the board linking the copper on the top to a pad on the bottom. Let's also assume that we have a wire connected to the pad on the bottom of the board. We could collect this wire to one side of a battery; connect the other side of the battery to one side of a small incandescent light bulb; and connect the other side of the bulb to a probe resting on upper side of the board as illustrated in Figure 1-3.
As an aside – I created all of these images using Microsoft Visio. Over the years I must have spent hundreds and hundreds of hours working with Visio. If they awarded “belts” I bet I'd be a Black Belt of the highest order by now, but we digress…
Of course our probe would have to be designed so as not to scratch the copper or wear it away – perhaps as a conducting roller or a wire brush or something. Also the wire connected to the pad under the board would have to be flexible so as to accommodate the board's motion. But all of these points are just “nitty-gritty” details…
The main thing is that we can now determine the position of the board. If the board is slid over to the right, the circuit will be broken and the light will be off; if the board is slid over to the left, the circuit will be completed and the light will be on.
Now, this is all well-and-good … but it's a bit coarse. Suppose we wish to know the board's position to a little higher resolution… for example: “All the way to the left” , “Part way to the left” , “Part way to the right” , and “All the way to the right” . Well, in this case we could use multiple areas of copper and two light bulbs as illustrated in Figure 1-4.
The idea is that all of the copper areas on the top-side of the board are connected together somehow (possibly by vias and tracks under the board). As we see, if the board is slid all the way over to the right, both lights will be off. As we start to slide the board to the left, Light 0 will be illuminated (as shown in Figure 1-4). If we slide the board a little more to the left, Light 0 will turn Off and Light 1 will turn On. Finally, when the board has been slid all the way over to the left, both lights will be illuminated.
Of course we don't need to use lights. Instead, our probes could be connected to the inputs of a microprocessor, which we could be using to both monitor the current position of the board and to modify that position using servo motors, for example.
Now, we can imagine the board shown in Figure 1-4 as comprising two rows, each divided into four areas of blank or copper-filled board. We can further increase the resolution using more rows and more areas; for example, consider four rows each divided into sixteen areas as illustrated in Figure 1-5.
Are we having fun yet? Now, do you notice anything interesting about the ordering of the patterns of blank and copper-filled board? Well, supposing that we were to visualize the board as being rotated 90° degrees clockwise … YES! These patterns form a binary count sequence as illustrated in Figure 1-6.
Now, this may appear to be quite simple, but there is a problem… When moving between states in a standard binary sequence, multiple bits may change from 0 to 1 or vice versa; for example, two bits change value when moving from 00012 to 00102 .
Even though these two values are adjacent (next to each other) in a “binary count” sense, in the physical world there is no way to ensure that both bits will transition at exactly the same time. In the case of our board as illustrated in Figure 1-5, for example, the four probes may be fractionally out of alignment, thereby causing the system to pass through an intermediate state.
That is, an intended state change of 00012 to 00102 might actually result in the sequence 00012 to 00112 to 00102 … or possibly 00012 to 00002 to 00102 . And if more bits are changing (when transitioning from 00112 to 01002 , for example) we might bounce though a longer series of intermediate values. Imagine if you were tasked with writing the program for the microprocessor that is monitoring the position of the board and/or directing servo motors to move it to a new position… what a nightmare… you wouldn't know if you were coming or going!
In order to address this problem, the American physicist and Bell Labs researcher Frank Gray came up with a solution that we now commonly refer to as a Gray code. In fact, Frank Gray actually used the term “reflected binary code” in his 1947 patent application. He derived this name from the fact that: “It may be built up from the conventional binary code by a sort of reflection process.”
Note: As an aside, reflected binary codes were applied to mathematical puzzles before they became known to engineers. As far back as 1878, the French engineer Émile Baudot used Gray codes in telegraphy, and he ended up receiving the French Legion of Honor medal for his labors. But we digress…
The idea behind a Gray code is that only a single bit (copper/non-copper area in our example) changes when transitioning from one state to another as illustrated in Figure 1-7.
Isn't this cool? It means that even if our probes are slightly misaligned, we will only ever pass from one Gray code state to another without passing through any intermediate (potentially confusing) values.
Shaft-angle encoding
Of particular interest, observe the fact that the final Gray code value (at the bottom of the table) differs by only a single bit from the initial code (at the top of the table). Why is this important? Well, it means that we can regard the count as being “circular”, which is particularly advantageous when we apply these little scamps to a task like monitoring the position (angular rotation) of a shaft. For example, consider the circular “board” illustrated in Figure 1-8.
If you compare the ring patterns in Figure 1-8 with the Gray code columns in Figure 1-7, you'll see that the copper/non-copper areas are identical.
Imagine this being connected to a shaft that passes through the center of the board. By means of the four rings of copper/non-copper areas, we can determine the angular position of the shaft. The way this works is that the conducting/non-conducting areas are arranged in concentric circles, where each circle represents a binary digit. A set of electrical contacts, one for each of the circles, is used to detect the logic values represented by the presence or absence of the conducting areas.
A digital controller can use this information to determine the angle of the shaft. The precision of the measurement depends on the number of bits (circles). A 4-bit value representing 16 unique states allows the shaft's angle to be resolved to 22.5°, while a 10-bit value representing 1,024 unique states allows the shaft's angle to be resolved to 0.35°. Using a Gray code sequence to define the conducting and non-conducting areas ensures that no intermediate values are generated as the shaft rotates.
In addition to shaft angle encoding, Gray codes are of use for a variety of applications, such as facilitating error correction in digital communications and the ordering of the input variables on Karnaugh Maps.
In Part 2 of this mini-series we will take a look at generating Gray codes and also Binary-to-Gray and Gray-to-Binary conversions.
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.
Leave a Reply
You must Register or Login to post a comment.