Gray codes

by David Joyner and Jim McShea, Math Dept, USNA

Gray codes have several applications:

solving puzzles such as the Tower of Hanoi and the Brain [G],
analog-digital-converters (goniometers) [S],
Hamiltonian circuits in hypercubes [Gil] and Cayley graphs of Coxeter groups [CSW],
capanology (the study of bell-ringing) [W],
continuous space-filling curves [Gi],
classification of Venn diagrams [R],
design of communication codes,
increase the resolution of the CODACON spectrometer being constructed at L.A.S.P., Univ. of Colorado for a satellite application.

This worksheet and the text file gray.mpl contains four algorithms for generating a binary Gray code (essentially the "reflected" binary Gray code) of length n. One is the binary-to-reflected Gray code conversion [G]. Another takes advantage of the periodicity of the reflected Gray code in each coordinate. The third uses a relationship between the i-th codeword and the 2i-th codeword, which as far as we know is new. The third one is perhaps the fastest of these three but requires that the table of previous codewords be placed in memory. This package also contains some plotting commands for visualizing the "size" of each codeword in the code.

The fourth algorithm to produce Gray codes will actually produce an m-ary (not just binary) Gray code of length n. It is compact and relatively fast. Though discovered independently, this appears to be the same as the first algorithm of M. C. Er [E].

The gray package contains routines to

solve the Brain puzzle:
For example, the coordinate (x,2^y+1) of the plot below signifies that the y-th peg should be moved at the x-th step of the Brain puzzle:
give the binary representation and then the reflected binary Gray codeword associated to the decimal number,
An m-ary Gray code of length n.

There is a example worksheet which may be downloaded as well.

REFERENCES

[CSW] J. Conway, N. Sloane, and A. Wilks, "Gray codes and reflection groups", Graphs and combinatorics 5(1989)315-325

[E] M. C. Er, "On generating the N-ary reflected Gray codes", IEEE transactions on computers, 33(1984)739-741

[G] M. Gardner, "The binary Gray code", in Knotted donuts and other mathematical entertainments, F. H. Freeman and Co., NY, 1986

[Gi] W. Gilbert, "A cube-filling Hilbert curve", Math Intell 6 (1984)78

[Gil] E. Gilbert, "Gray codes and paths on the n-cube", Bell System Technical Journal 37 (1958)815-826

[R] F. Ruskey, "A Survey of Venn Diagrams", Elec. J. of Comb.(1997)

[S] Web page of T. Sillke

[W] A. White, "Ringing the cosets", Amer. Math. Monthly 94(1987)721-746

Last updated 2008-10-27.