For example (000, 001, 011, 010, 110, 111, 101, 100) is a Gray code of dimension 3. A Gray code can also be considered as a Hamiltonian path on the n-cube, that is a sequence of adjacent edges that visits each corner exactly once. Gray codes are important in analog-to-digital conversion systems.
Note that the group of rigid motions of an n-cube (orthogonal linear transformations of determinant 1) acts on the set of Gray codes of dimension n. A pattern of Gray codes is an orbit of this action. For example, there is exactly one pattern of Gray codes of dimension 3 shaped something like a toast rack. There are 5 patterns in dimension 4 and 9 in dimension 5. The number of patterns of Gray codes of dimension n is unknown for n > 5.
A proof of the given results for n = 4 and 5 will earn you an A for this course. The solution for n = 6 will get you first class Honours next year (provided you satisfy the other requirements). A solution, even partial, for general n would be close to a PhD.
To return to Page 1, click here .
Last update January 11, 2000
Author: Phill Schultz, schultz@maths.uwa.edu.au