Gray code

Let $ {\mathcal B} _ {n} $ denote the set of all $ N = 2 ^ {n} $ binary strings of length $ n $. A Gray code of order $ n $ is a sequence $ B _ {0} \dots B _ {N - 1 } $ of elements of $ {\mathcal B} _ {n} $ in which every successive pair ( $ B _ {i} , B _ {i + 1 } $) of bitstrings differs by one bit in some position; the bits in all other positions agree. A cyclic Gray code is one in which $ B _ {0} $ and $ B _ {N - 1 } $ also differ by one bit. These bitstrings can also be thought of as the characteristic vectors of subsets of $ \{ 1 \dots n \} $. The hypercube of order $ n $( or $ n $- cube) is the graph whose vertex set is $ {\mathcal B} _ {n} $ and whose edge set consists of those pairs of vertices that differ by one bit. Thus, a Gray code is a Hamilton path (cf. Graph circuit) on the $ n $- cube and a cyclic Gray code is a Hamilton cycle (cf. Graph circuit) on the $ n $- cube.

Origins and uses.

The term "Gray code" comes from F. Gray, who worked as an engineer at Bell Laboratories, and who, in 1953, obtained US patent 2,632,058 for "pulse code communication" . The patent contained a construction which has come be known as the binary reflected Gray code (BRG code), after the recursive construction rule given below for $ n > 0 $.

$$ \tag{a1 } {\mathcal C} ( n ) = {\mathcal C} ( n - 1 ) \cdot 0 \circ {\overline{ {{\mathcal C} ( n - 1 ) }}\; } \cdot 1 . $$

If $ n = 0 $, then $ {\mathcal C} ( n ) = \varepsilon $, the empty string. There are three operations. The dot operation $ {\mathcal L} \cdot x $, for a list $ {\mathcal L} $, gives the list consisting of every string in $ {\mathcal L} $ appended with the symbol $ x $. The concatenation operation $ {\mathcal L} _ {1} \circ {\mathcal L} _ {2} $ gives the list $ {\mathcal L} _ {1} $ followed by the list $ {\mathcal L} _ {2} $. By $ {\overline {\mathcal L} \; } $ one denotes the reversal of the list $ {\mathcal L} $. Thus $ {\mathcal C} ( 1 ) = 0,1 $, $ {\mathcal C} ( 2 ) = 00, 10, 11, 01 $ and $ {\mathcal C} ( 3 ) = 000, 100, 110, 010, 011,111, 101, 001 $.

There is a simple relation between the $ r $ th binary string (counting from $ 0 $) in the BRG code, call it $ g _ {n} \dots g _ {1} $, and the binary representation of $ r = ( b _ {n - 1 } \dots b _ {0} ) _ {2} $. For $ i = 1 \dots n $,

$$ b _ {i - 1 } = b _ {i} \oplus g _ {i} \textrm{ and } g _ {i} = b _ {i - 1 } \oplus b _ {i} , $$

where the $ \oplus $ is the exclusive-or operation.

Connections and variations.

The BRG code can be used in solving the Chinese rings puzzle and the towers of Hanoi puzzle, both of which predate Gray's patent [a1]. In practice, variants of the BRG code are often required. Uniform Gray codes refer to those that have, at least approximately, the same number of bit changes occurring in each position. A monotone Gray code has the property that all strings with $ k $ ones appear before any with $ k + 2 $ ones [a6].

Combinatorial Gray codes.

The Gray code concept has been extended from subsets to many other types of combinatorial objects. The concept of a combinatorial Gray code is not precisely defined, but the two crucial ideas are that each object is listed exactly once and successive objects differ in some small prescribed way. Combinatorial Gray codes are useful because they often lead to efficient algorithms for generating (i.e., listing) the objects. Some of the more important combinatorial Gray codes are as follows.

Combinations, partitions, permutations, and other objects.

Represent combinations (cf. Combination) by their characteristic vectors; i.e., the $ k $- combinations of an $ n $- set are represented by those strings in $ {\mathcal B} _ {n} $ that have exactly $ k $ ones. For combinations, a rule analogous to (a1) may be given, for $ 0 < k < n $. The result is a Gray code in which each string differs from its predecessor by transposition of two bits:

$$ {\mathcal C} ( n,k ) = {\mathcal C} ( n - 1,k ) \cdot 0 \circ {\overline{ {{\mathcal C} ( n - 1,k - 1 ) }}\; } \cdot 1 . $$

This list gives rise to what is known as a revolving door algorithm; one element leaves the set and another element enters the set [a2].

For permutations (cf. Permutation) a Gray code is known in which successive permutations differ only by transposition of two adjacent elements. It is a recursive construction in which $ n $ sweeps back and forth through the list of permutations of $ 1 \dots n - 1 $. This Gray code is usually attributed to S.M. Johnson and H.F. Trotter [a3], but was known much earlier by experts in campanology (which is the study of bells and bell ringing).

A Gray code is known for the linear extensions of partially ordered sets in which each extension differs by one or two transpositions of adjacent poset elements [a4].

For set partitions, Gray codes are known in which successive partitions differ only by an element moving from some block to some other block. For numerical partitions, a Gray code is known in which successive partitions differ by one part increasing by one and another part decreasing by one [a5].

Many combinatorial Gray codes can be viewed as Hamilton cycles in vertex-transitive graphs, particularly Cayley graphs (cf. also Graph; Graph circuit) [a7]. The Gray code for permutations gives a Hamilton cycle on a Cayley graph known as the permutohedron.

References

[a1]	F.G. Heath, "Origins of the binary code" Scientific Amer. , 227 (1972) pp. 76–83
[a2]	A. Nijenhuis, H.S. Wilf, "Combinatorial algorithms" , Acad. Press (1978) (Edition: Second)
[a3]	E.M. Reingold, J. Nievergelt, N. Deo, "Combinatorial algorithms: Theory and practice" , Prentice-Hall (1977)
[a4]	G. Pruesse, F. Ruskey, "Generating linear extensions fast" SIAM J. Computing , 23 (1994) pp. 373–386
[a5]	C.D. Savage, "Gray code sequences of partitions" J. Algorithms , 10 (1989) pp. 577–595
[a6]	C.D. Savage, P. Winkler, "Monotone Gray codes and the middle two levels problem" J. Combinatorial Th. A , 70 (1995)
[a7]	D. Witte, J.A. Gallian, "A survey: Hamiltonian cycles in Cayley graphs" Discrete Math. , 51 (1984) pp. 293–304