Gray codes

by David Joyner and Jim McShea, Math Dept, USNA

Gray codes have several applications:

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

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), and updated versions

[S] Web page of T. Sillke

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


Last updated 2008-10-27.