## 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?...Joseph Malkevitch
## Counting permutationsHow many ways are there to take three letters a, b, c and arrange them in different ordered strings? ## Distance between stringsHowever, 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 (Richard Hamming)
## Hamiltonian circuitsWe 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. Figure 1
(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. Figure 2 Figure 3 Figure 4
Figure 5 Figure 6 Figure 7 ## Gray codesWhat 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? Figure 8
Figure 9
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 Figure 10
Figure 11
Figure 12
n-cube. However, many Gray code problems "live" in a more subtle environment.For example, let us consider another fascinating circle of ideas, this time from the domain of number theory. Suppose we are given a positive integer n, say for example 4. What are the ways of writing 4 as the sum of one or more positive integers? For 4, a list of such choices appears below: 4 3, 1 2, 2 2, 1, 1 1, 1, 1, 1 Note that we are not interested in considering different arrangements of the terms making up the "list" as different, and hence, 2, 1, 1 is considered the same as 1, 2, 1. The numbers such as 3 and 1 are known as a partition of 4, and the list above enumerates all of the partitions of 4. These partitions are listed with largest part first down to the smallest part. Note that if one regards this as a cyclic sequence there is a "large distance" between the number of parts in row 1 and the number of parts in row 5. Note also that we cannot use Hamming distance here to find the distance between two rows because the strings in the different rows need not have the same length and Hamming distance can only be used for strings that have the same length. (However, there is a way to enumerate the partitions of n in a way that makes the listing into a Gray code problem.) Using ideas related to the partitions of the number 4, the geometer Branko Grünbaum was able to find a novel way of classifying convex plane quadrilaterals which has led to a variety of new directions for problems in elementary geometry.Innovative mathematical ideas have a life of their own. Frank Gray's ideas about how to code binary sequences is but one of many examples. ## References:Barnes, T. and C. Savage, Efficient generation of graphical partitions, Discrete Applied Math., 78 (1997) 17-26. Joseph Malkevitch 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 |