Mathematics 357 – Combinatorics Discussion 2 – Gray codes February 9, 2005

Background

Last time we discussed one way to list all the combinations of elements of a finite set X = {x_{1}, …, x_{n}} (equivalently, all subsets). It went like this: If n = |X|, then we represent each subset C by a binary vector of length n saying which elements of X are in C:

v_{C} = (v_{1}, …, v_{n}) where v_{i} = \{ \begin{matrix}1 & if x_{i} ∈ C \\ 0 & if x_{i} ∉ C \end{matrix}

We then interpret each such vector as a binary expansion of an integer in the range 0 ≤ x ≤ 2^{n} − 1. Listing those integers in some order, we get a listing of the combinations, or subsets. We discussed using the usual numerical order last time, but there are other orders that are also commonly used too. For instance, a different way to list the binary vectors of length n is called the “reflected” Gray code. To describe this method, we say how to build up the Gray codes for the integers in 0 ≤ x ≤ 2^{n} − 1 recursively:

• (The base case). The Gray codes for 0, 1 with n = 1 are 0, 1 respectively.

• (The recursion, or inductive step) To get the n = k + 1 Gray codes for the integers in 0 ≤ x ≤ 2^{k+1} −1, first list the n = k Gray codes for the integers in 0 ≤ x ≤ 2^{k} −1 with 0’s appended at the left, then list the Gray codes for the integers in 0 ≤ x ≤ 2^{k} − 1 with 1’s appended at the left, but in reverse order – this is the “reflection” in the name.

For example, for n = 2, we get the sequence of Gray codes 00, 01, 11, 10. (This means: 0 is coded as 00, 1 is 01, 2 is 11, and 3 is 10. Note that this is already different from the binary encoding we did before!) Similarly for n = 3, we get

(1)  000, 001, 011, 010, 110, 111, 101, 100.

The goal of today’s discussion is to understand some of the interesting properties of this method.

Discussion Questions

A) To make sure you have “the hang of” the construction, list out the Gray codes for integers in the correct order for n = 4 and n = 5.

B) One of the best ways to understand what the reflected Gray code is “really doing” is to think of a geometric picture. For instance with n = 3, we can draw a cube with vertices (corners) labeled with the binary vectors of length 3 in the following way:

The rationale for this labeling is that the vertices represent the subsets of {x_{1}, x_{2}, x_{3}} as above, and we have a edge between two vertices if and only if we can get from one subset to the other by either putting in or removing a single element.

1) In this picture, what are we doing if we visit the vertices in the order given in (1) above? Draw the corresponding path in the cube. How is this different from the “tour” of the vertices corresponding to the usual numerical ordering:

000, 001, 010, 011, 100, 101, 110, 111?

2) Draw a similar picture for n = 4. (It will probably be slightly messy the first time you try. Try to figure out a good way to represent it visually using the observation that it is really “two copies” of the picture for n = 3, joined by other edges. Do you see why?) Draw the path here corresponding to the Gray codes in the case n = 4. You should note that something similar to the case n = 3 is happening. Also compare with the path corresponding to the listing of the binary expansions of 0, 1, 2, …, 15 in numerical order.

C) What is the special property of the Gray code ordering (for some particular, fixed n). More specifically, what is always true about Gray codes of consecutive numbers (in the usual order)? Prove your assertion in general (i.e. for all n). Why might this be an interesting or valuable property for an encoding scheme for integers? (Hint: Think about transmitting numerical data over a communication system that might introduce an error in the data every once in a while, “flipping a bit” from a 0 to a 1 or vice versa.)

D) The reflected Gray code above is not the only way to code integers that has the special property from question C. Find at least two other ways to encode integers in the range 0 ≤ x ≤ 7 = 2^{3} − 1 with the same property. (Hint: Think about what you did in question B.)

E) All of the orders with the property from questions C and D are usually called Gray codes. (The reflected Gray code is one particular example.)

1) How many different Gray codes are there for the integers in the range 0 ≤ x ≤ 3? Find them all.

2) (Extra Credit) Same question as part 1 for the integers in 0 ≤ x ≤ 7 = 2^{3} − 1?

Assignment

Group write-ups due on Monday, February 14.