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:

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 following algorithms for incrementing a Gray-coded integer G. They both first convert G to binary, which is shown as index(G).

Figure 13-2 Incrementing a Gray-coded integer.

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

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.