Gray CodesWhat can we learn from a mathematical point of view from the kinds of examples we are considering, listing mathematical objects in a list in such a way that adjacent objects in the list are close to each other?...
How many ways are there to take three letters a, b, c and arrange them in different ordered strings?
However, there is a different point of view about this list of strings. We can ask if there is some way to measure how much alike or different the two strings are. We can try to determine a distance between strings. If two strings have the same length, we can find the Hamming distance between the two strings. The name for this distance honors the American mathematician Richard Hamming.
We can get a different insight here by using some graph theory, a geometric tool involving drawing pictures with dots and lines. We will represent each string of length 3 by a vertex (dot) of the graph and join two vertices by a line segment (edge) if and only if the strings differ in exactly two positions.
(William Rowan Hamilton)
(Thomas Penyngton Kirkman)
Returning to the issue of listing all the triples on three symbols from the point of view of ordering triples so as to minimize the total Hamming distance when moving cyclically from one trip to the next, I have drawn in Figures 2, 3, and 4 some Hamiltonian circuits of the graph which appears in Figure 1. These Hamiltonian circuits use different edges of the graph in Figure 1 but it is natural to ask if there is a symmetry of the graph in Figure 1 which will transform one of these Hamiltonian circuits into another.
What can we learn from a mathematical point of view from the kinds of examples we have been considering, listing mathematical objects in a list in such a way that adjacent objects in the list are close to each other?
Gray in fact obtained a patent (granted in 1953 but applied for considerably earlier) for ideas involving his code which minimized the number of changes for a cyclic listing of the binary strings of length n. The code that he developed is often now referred to as the reflected Gray code.
Barnes, T. and C. Savage, Efficient generation of graphical partitions, Discrete Applied Math., 78 (1997) 17-26.
Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal , which also provides bibliographic services.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance