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 second installment of our mini-series, we take a look at generating Gray codes and also Binary-to-Gray and Gray-to-Binary conversions.
Just to refresh our memories, in Part 1 we considered the concept of Gray codes in general; 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 with 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.
Generating a Gray code
Before we start, let’s briefly remind ourselves as to the difference between a standard binary count and one of the many possible Gray code equivalents as illustrated in Figure 2-1 (we’ll use 4-bit sequences for the purpose of these examples).
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 Figure 2-2 (it might be more correct to call this a “recursive reverse-and-prefix” technique).
Binary-to-Gray and Gray-to-Binary conversions
It is often required to convert a binary sequence into a Gray code or vice versa. Such converters are easy to create and are of especial interest here due to their affinity to Reed-Müller implementations (I’ll do an article on Reed-Müller Logic after I’ve finished this mini-series on Gray codes). First let’s consider a Binary-to-Gray converter as illustrated in Figure 2-3.
The checkerboard patterns of 0s and 1s in the Karnaugh Maps immediately indicate the potential for Reed-Müller implementations. Similar checkerboard patterns are also seen in the case of a Gray-to-Binary converter as illustrated in Figure 2-4.
It’s very quiet in here!
Gray code counters are of interest for a variety of 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.
In addition to preventing intermediate states, 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.
Actually implementing a Gray code counter
Before we proceed, let’s briefly ponder the process of actually implementing a Gray code counter. Just to give us something to play with, let’s suppose we wish to generate a Gray code that can be used to index into a memory array. For example, suppose we’re implementing something sort-of like a FIFO, and that (for the purposes of this example), we simply wish to keep on cycling through all of the memory locations. The point is that we aren’t particularly concerned as to the order in which we address the locations, just that we sequence our way through them visiting each one a single time before returning to the first location to do it all over again.
Assuming that we’re dealing with a 16-word memory array, one scenario [as illustrated in Figure 2-5 (a)] starts with a standard 4-bit binary counter, in which the current count value is passed through a chunk of feedback logic to generate the next count value. Also, the current count value is passed through a Binary-to-Gray converter (as introduced in Figure 2-3) to generate a corresponding Gray code.
The alternative technique [as illustrated in Figure 2-5(b)] is to simply create a Gray code counter from the ground up. Now, if we were to compare the binary counter (including binary-to-Gray converter) with the Gray code counter, there are several things I don’t know off the top of my head:
- How many logic gates are required for each implementation?
- How many levels of logic gates are there in the two feedback paths?
- What’s the (relative) maximum frequency of each type of counter?
- What’s the (relative) switching activity, noise, and power consumption of each type of counter?
I tell you, I’m constantly amazed by the number of things I don’t know. Now, we could work this out, but I’m a tad busy at the moment, so we’ll leave the pondering of these posers as an exercise for the reader (grin). Of course, if you do work all of this out, it would make the basis for a great follow-up article that I could post under your name here on Programmable Logic Designline.
But we digress… in Part 3 we will take a look at generating sub-2n Gray code count sequences.
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.
Hi Clive for yours interesting posts. I hope it would be in a better position to help. I am a final year engineering student and I am to design a sequential circuit which converts BCD to Gray code. Hope you will be able to help.