Part 1 – Assertion-Level Logic
Part 2 – Positive vs Negative Logic
Part 3 – Reed-Müller Logic
Part 4 – Gray Codes
Editor's Note: See also the Follow-on Article that describes how to generate Gray Codes for non-power-of-2 sequences.
When moving between states in a standard binary sequence, multiple bits may change from 0 to 1 or vice versa; for example, three bits change value when moving from %0011 to %0100 (where the % character is used to indicate a binary number). In the physical world, there is no way to ensure that all the bits will transition at exactly the same time, so a system may actually pass through a sequence of intermediate states. For example, an intended state change of %0011 to %0100 could actually result in the sequence %0011 to %0111 to %0100.
Note that the correct grammar and spelling for Gray codes is "Gray" (not "gray", "Grey", or "grey"). This is because Gray codes are named after Frank Gray, who patented their use for shaft encoders in 1953. You can find a really Interesting Paper on this at www.faqs.org.
One way to avoid this problem is to use a Gray code, in which only a single bit changes when moving between states (Fig 1).
1. 4-bit binary code versus 4-bit Gray code.
Gray codes are of use for a variety of applications, such as the ordering of the input variables on Karnaugh Maps (you can see examples of this in Fig 4 and Fig 5). Another use is encoding the angle of a mechanical shaft (possibly in an industrial control application), where a disc attached to the shaft is patterned with areas of conducting material (Fig 2).
2. Gray code used for shaft-angle encoding.
The conducting (golden) areas are arranged in concentric circles, where each circle represents a binary digit (the inner circle represents bit 3 and the outer circle represents bit 0 in this example). 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 degrees, while a 10-bit value representing 1,024 unique states allows the shaft's angle to be resolved to 0.35 degrees. Using a Gray code sequence to define the conducting and non-conducting areas ensures that no intermediate values are generated as the shaft rotates.
Commencing with a state of all zeros, a Gray code can be generated by always changing the least significant bit that results in a new state. An alternative method which may be easier 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 used to generate a 4-bit Gray code is shown in Fig 3.
3. Using the mirroring technique to generate a 4-bit Gray code.
It is often required to convert a binary sequence into a Gray code or vice versa. Such converters are easy to create and are primarily of interest here due to their affinity to the Part 3 – Reed-Müller implementations that were introduced earlier in this mini-series. Consider a Binary-to-Gray converter (Fig 4). The checkerboard patterns of 0s and 1s in the Karnaugh Maps immediately indicate the potential for Reed-Müller implementations.
4. Binary-to-Gray converter.
Similar checkerboard patterns are also seen in the case of a Gray-to-Binary converter (Fig 5). Once again, the checkerboard patterns of 0s and 1s in the Karnaugh Maps immediately indicate the potential for Reed-Müller implementations.
5. Gray-to-Binary converter.
But wait, there's more, because Gray code counters are also of interest when it comes to applications such as representing the state variables in state machines or acting as pointers in First-In First-Out (FIFO) memories. This is because only one output bit is ever toggling at a time in a Gray code "counter", as opposed to possibly multiple bits in a binary counter.
The result is that Gray code counters consume only half the power of an equivalent binary counter and they generate correspondingly less noise. Actually, while the power (and average noise) difference between a Gray and a binary counter asymptotically approaches two, the peak noise difference is equal to the number of bits, since a Gray counter toggles only one bit at a time while a binary counter toggles all of its bits simultaneously two times over the course of a full-count cycle with fewer bits toggling proportionally more times.
Reader Jay Dowling, co-owner of StereoImaging Corporation, uses Gray code counters in many of his designs. Jay has compiled a Very Interesting Report (presented in the form of an Excel spreadsheet) that compares a variety of counter implementations in this context, including binary, Gray code, and two different types of Linear Feedback Shift-Register (LFSR) counter. (Jay also has a Yahoo Group from whence he provides Verilog design files and links.)
Clive "Max" Maxfield is president of TechBites Interactive, a marketing consultancy firm specializing in high technology. Max is the author and co-author of a number of books, including Bebop to the Boolean Boogie (An Unconventional Guide to Electronics), The Design Warrior's Guide to FPGAs (Devices, Tools, and Flows), and How Computers Do Math featuring the pedagogical and phantasmagorical virtual DIY Calculator.
Widely regarded as being an expert in all aspects of computing and electronics (at least by his mother), Max was once referred to as "an industry notable" and a "semiconductor design expert" by someone famous who wasn't prompted, coerced, or remunerated in any way. Max can be reached at [email protected].
