Chapter 13. Gray Code

13–1 Gray Code

Is it possible to cycle through all 2ⁿ combinations of n bits by changing only one bit at a time? The answer is “yes,” and this is the defining property of Gray codes. That is, a Gray code is an encoding of the integers such that a Gray-coded integer and its successor differ in only one bit position. This concept can be generalized to apply to any base, such as decimal, but here we will discuss only binary Gray codes.

Although there are many binary Gray codes, we will discuss only one: the “reflected binary Gray code.” This code is what is usually meant in the literature by the unqualified term “Gray code.” We will show, usually without proof, how to do some basic operations in this representation of integers, and we will show a few surprising properties.

The reflected binary Gray code is constructed as follows. Start with the strings 0 and 1, representing the integers 0 and 1:

Reflect this about a horizontal axis at the bottom of the list, and place a 1 to the left of the new list entries and a 0 to the left of the original list entries:

This is the reflected binary Gray code for n = 2. To get the code for n = 3, reflect this and attach a 0 or 1 as before:

From this construction, it is easy to see by induction on n that (1) each of the 2ⁿ bit combinations appears once and only once in the list, (2) only one bit changes in going from one list entry to the next, and (3) only one bit changes when cycling around from the last entry to the first. Gray codes having this last property are called “cyclic,” and the reflected binary Gray code is necessarily cyclic.

If n > 2, there are non-cyclic codes that take on all 2ⁿ values once and only once. One such code is 000 001 011 010 110 100 101 111.

Figure 13–1 shows, for n = 4, the integers encoded in ordinary binary and in Gray code. The formulas show how to convert from one representation to the other at the bit-by-bit level (as it would be done in hardware).

FIGURE 13–1. 4-bit Gray code and conversion formulas.

As for the number of Gray codes on n bits, notice that one still has a cyclic binary Gray code after rotating the list (starting at any of the 2ⁿ positions and cycling around) or reordering the columns. Any combination of these operations results in a distinct code. Therefore, there are at least 2ⁿ · n! cyclic binary Gray codes on n bits. There are more than this for n ≥ 3.

The Gray code and binary representations have the following dual relationships, evident from the formulas given in Figure 13–1:

• Bit i of a Gray-coded integer is the parity of bit i and the bit to the left of i in the corresponding binary integer (using 0 if there is no bit to the left of i).

• Bit i of a binary integer is the parity of all the bits at and to the left of position i in the corresponding Gray-coded integer.

Converting to Gray from binary can be done in only two instructions:

The conversion to binary from Gray is harder. One method is given by

We have already seen this formula in “Computing the Parity of a Word” on page 96. As mentioned there, this formula can be evaluated as illustrated below for n = 32.

B = G ^ (G >> 1);
B = B ^ (B >> 2);
B = B ^ (B >> 4);
B = B ^ (B >> 8);
B = B ^ (B >> 16);

Thus, in general it requires instructions.

Because it is so easy to convert from binary to Gray, it is trivial to generate successive Gray-coded integers:

for (i = 0; i < n; i++) {
   G = i ^ (i >> 1);
   output G;
}

13-2 Incrementing a Gray-Coded Integer

The logic for incrementing a 4-bit binary integer abcd can be expressed as follows, using Boolean algebra notation:

Thus, one way to build a Gray-coded counter in hardware is to build a binary counter using the above logic and convert the outputs a′, b′, c′, d′ to Gray by forming the exclusive or of adjacent bits, as shown under “Gray from Binary” in Figure 13–1.

A way that might be slightly better is described by the following formulas:

That is, the general case is

Because the parity p alternates between 0 and 1, a counter circuit might maintain p in a separate 1-bit register and simply invert it on each count.

In software, the best way to find the successor G′ of a Gray-coded integer G is probably simply to convert G to binary, increment the binary word, and convert it back to Gray code. Another way that’s interesting and almost as good is to determine which bit to flip in G. The pattern goes like this, expressed as a word to be exclusive or’d to G:

1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16

The alert reader will recognize this as a mask that identifies the position of the leftmost bit that changes when incrementing the integer 0, 1, 2, 3, ..., corresponding to the positions in the above list. Thus, to increment a Gray-coded integer G, the bit position to invert is given by the leftmost bit that changes when 1 is added to the binary integer corresponding to G.

This leads to the algorithms for incrementing a Gray-coded integer G as shown in Figure 13–2. They both first convert G to binary, which is shown as index(G).

B = index(G);                     B = index(G);
B = B + 1;                        M = ~B & (B + 1);
Gp = B ^ (B >> 1);                Gp = G ^ M;

FIGURE 13–2. Incrementing a Gray-coded integer.

A pencil-and-paper method of incrementing a Gray-coded integer is as follows:

Starting from the right, find the first place at which the parity of bits at and to the left of the position is even. Invert the bit at this position.

Or, equivalently:

Let p be the parity of the word G. If p is even, invert the rightmost bit.

If p is odd, invert the bit to the left of the rightmost 1-bit.

The latter rule is directly expressed in the Boolean equations given above.

13–3 Negabinary Gray Code

If you write the integers in order in base –2 and convert them using the “shift and exclusive or” that converts to Gray from straight binary, you get a Gray code. The 3-bit Gray code has indexes that range over the 3-bit base –2 numbers, namely –2 to 5. Similarly, the 4-bit Gray code corresponding to 4-bit base –2 numbers has indexes ranging from –10 to 5. It is not a reflected Gray code, but it almost is. The 4-bit negabinary Gray code can be generated by starting with 0 and 1, reflecting this about a horizontal axis at the top of the list, and then reflecting it about a horizontal axis at the bottom of the list, and so on. It is cyclic.

To convert back to base –2 from this Gray code, the rules are, of course, the same as they are for converting to straight binary from ordinary reflected binary Gray code (because these operations are inverses, no matter what the interpretation of the bit strings is).

13–4 Brief History and Applications

Gray codes are named after Frank Gray, a physicist at Bell Telephone Laboratories, who in the 1930s invented the method we now use for broadcasting color TV in a way that’s compatible with the black-and-white transmission and reception methods then in existence; that is, when the color signal is received by a black-and-white set, the picture appears in shades of gray.

Martin Gardner [Gard] discusses applications of Gray codes involving the Chinese ring puzzle, the Tower of Hanoi puzzle, and Hamiltonian paths through graphs that represent hypercubes. He also shows how to convert from the decimal representation of an integer to a decimal Gray code representation.

Gray codes are used in position sensors. A strip of material is made with conducting and nonconducting areas, corresponding to the 1’s and 0’s of a Gray-coded integer. Each column has a conducting wire brush positioned to read it out. If a brush is positioned on the dividing line between two of the quantized positions so that its reading is ambiguous, then it doesn’t matter which way the ambiguity is resolved. There can be only one ambiguous brush, and interpreting it as a 0 or 1 gives a position adjacent to the dividing line.

The strip can instead be a series of concentric circular tracks, giving a rotational position sensor. For this application, the Gray code must be cyclic. Such a sensor is shown in Figure 13–3, where the four dots represent the brushes.

FIGURE 13–3. Rotational position sensor.

It is possible to construct cyclic Gray codes for rotational sensors that require only one ring of conducting and nonconducting areas, although at some expense in resolution for a given number of brushes. The brushes are spaced around the ring rather than on a radial line. These codes are called single track Gray codes, or STGCs.

The idea is to find a code for which, when written out as in Figure 13–1, every column is a rotation of the first column (and that is cyclic, assuming the code is for a rotational device). The reflected Gray code for n = 2 is trivially an STGC. STGCs for n = 2 through 4 are shown here.

STGCs allow the construction of more compact rotational position sensors. A rotational STGC device for n = 3 is shown in Figure 13–4.

FIGURE 13–4. Single track rotational position sensor.

These are all very similar, simple, and rather uninteresting patterns. Following these patterns, an STGC for the case n = 5 would have ten code words, giving a resolution of 36 degrees. It is possible to do much better. Figure 13–5 shows an STGC for n = 5 with 30 code words, giving a resolution of 12 degrees. It is close to the optimum of 32 code words.

FIGURE 13–5. An STGC for n = 5.

All the STGCs in this section above are the best possible, in the sense that for n = 2 through 5, the largest number of code words possible is 4, 6, 8, and 30.

An STGC has been constructed with exactly 360 code words, with n = 9 (the smallest possible value of n, because any code for n = 8 has at most 256 code words) [HilPat].

Exercises

1. Show that if an integer x is even, then G(x) (the reflected binary Gray code of x) has an even number of 1-bits, and if x is odd, G(x) has an odd number of 1-bits.

2. A balanced Gray code is a cyclic Gray code in which the number of bit changes is the same in all columns, as one cycles around the code.

(a) Show that an STGC is necessarily balanced.

(b) Can you find a balanced Gray code for n = 3 that has eight code words?

3. Devise a cyclic Gray code that encodes the integers from 0 to 9.

4. [Knu6] Given a number in prime decomposed form, show how to list all its divisors in such a way that each divisor in the list is derived from the previous divisor by a single multiplication or division by a prime.