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 fourth installment of our mini-series, we take a look at generating sub-2n Gray code count sequences comprising consecutive values.
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 5 we will take a leap into the unknown to wrestle with the concept of "n-ary" (non-Boolean) Gray codes.
Generating sub-2n gray code count sequences with consecutive values
With regard to the topic we introduced in Part 3 of the mini-series in which we generated non-power-of-2 sequences; the solutions we came up with will be perfectly OK for some applications, but there may be problems if we want to use them for certain tasks, such as pointers into memory arrays.
Let's suppose that – as opposed to a full 2n count (16 values in the case of the 4-bit examples we've been playing with) – we wish to use a reduced count sequence, such as 14, 12, or 10. Obviously this is easy-peasy when using pure binary addressing schemes as illustrated in Figure 4-1.
Figure 4-1. Implementing reduced binary count sequences.
As we see, all we have to do is to remove states from the end of the count sequence and to implement corresponding smaller arrays of memory locations.
But now let's now consider the case of the various Gray code implementations. As we discussed in Part 3
, there are several approaches we can use in order to generate a reduced-count Gray code sequence. One of these is to simply remove pairs of values from either side of the "mirror line" as illustrated in Figure 4-2.
Figure 4-2. One way to implement reduced Gray code sequences.
OK so far, but now let's consider what happens when we apply one of these reduced sequences to our addressing logic; for example, let's take our 10-count example. Basically we are going to end up with "holes" in our memory array as illustrated in Figure 4-3.
Figure 4-3. This approach leaves "holes" in our memory array.
As we see, the sequence (in hexadecimal) followed by this Gray code counter is: 0, 1, 3, 2, 6, E, A, B, 9, 8, and it then cycles back to 0 again; each step is a Gray code (single-bit) transition, including the wrap-around from 8 to 0. Meanwhile, the right-hand side of Figure 4-3 simply reflects which locations are hit in the memory array – not the order in which they are hit.
The end result is that it is no longer a trivial task to create a cut-down memory array, because these "holes" are going to mess everything up. So, the real question (the "Crux of the Biscuit"
as it were), is: "Is it possible to create a Gray code sequence to address a 10-word FIFO using sequential addresses of 0-to-9?"
As an aside, the full quote by American composer, guitarist, singer, film director, and satirist Frank Vincent Zappa is: "The crux of the biscuit is the apostrophe."
(I actually know what he meant by this, but that's a story for another day.)
Well, here's a technique that Mike Jarvis, a Design Engineer at Cray
, taught me. First of all we create an empty table with the number of entries we desire; ten in the case of this particular example. We set the least-significant bit to 0 for all of the entries in the upper half of the table, and to 1 for all of the entries in the lower half of the table as illustrated in Figure 4-4(a).
Figure 4-4. The process of sub-2n consecutive Gray code generation.
Next, we start with our highest two addresses (8 and 9, which equate to 10002
in the case of this example) straddling the "mirror line" as illustrated in Figure 4-4(b). And then we populate the rest of the table using smaller values working out from the center as illustrated in Figure 4-4(c). The result is a 10-sequence Gray code using consecutive addresses of 00002
(0 to 9 in decimal) as illustrated in Figure 4-5.
Figure 4-5. Hurray! No "holes" in the memory array.
Once again, the right-hand side of Figure 4-5 simply reflects which locations are hit in the memory array – not the order in which they are hit. I tell you, it amazes me that you can have a concept as simple as Gray codes, but every time you think you know it all, something new comes up that blows your socks off.
Of course the test case shown here is just a proof-of-concept. We populated the table by hand; we don't yet have an algorithm for this. Can we extrapolate this to a generic algorithm that allows us to do the same thing for any non-2n
Gray code sequence? In the case of a 1128-word memory array, for example, can we generate a Gray code sequence that ends up using sequential addresses of 0-to-1127 in the memory array?
Once again, I think we'll leave this 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 article that I could post under your name here on Programmable Logic Designline
Next time, in Part 5
, which will be the final installment of this mini-series, we will consider "n-ary" (or "non-Boolean") Gray codes.
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]).