\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Discussion 2 -- Gray codes}
\centerline{\it February 9, 2005}
\bigskip
\noindent
{\it Background}
\bigskip
Last time we discussed one way to list all the combinations
of elements of a finite set  $X = \{x_1,\ldots,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,\dots, v_n)\ {\rm where}\ v_i = \cases{1 & if $x_i \in C$\cr
                                                    0 & if $x_i \notin C$\cr}$$
We then interpret each such vector as a binary expansion of 
an integer in the range $0 \le x \le 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 {\it other orders} that are also commonly used too.  For instance, 
a different way to list the binary vectors of length $n$ is called the 
{\it ``reflected'' Gray code}.  To describe this method, we say how
to build up the Gray codes for the integers in $0 \le x \le 2^n - 1$
{\it recursively}:
\bigskip
\item{$\bullet$}  (The base case).  The Gray codes for $0,1$ 
with $n = 1$ are $0,1$ respectively.  
\item{$\bullet$}  (The recursion, or inductive step)
To get the $n = k+1$ Gray codes for the integers in 
$0 \le x \le 2^{k+1} - 1$, first list the $n = k$ Gray codes for the 
integers in $0 \le x \le 2^k - 1$ with $0$'s appended at the left,
then list the Gray codes for the 
integers in $0 \le x \le 2^k - 1$ with $1$'s appended at the left,
{\it but in reverse order} -- this is the ``reflection'' in the name.
\bigskip
\noindent
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
$$000, 001, 011, 010, 110, 111, 101, 100.\leqno(1)$$
The goal of today's discussion is to understand some of the interesting
properties of this method.
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\noindent
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$.  
\bigskip
\noindent
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 {\it cube} with vertices (corners)
labeled with the binary vectors of length 3 in the following way:
\vglue 1.0truein
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 {\it a single element}.  
\bigskip
\item{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?$$
\item{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,\ldots, 15$ in numerical order.
\bigskip
\noindent
C)  What is the {\it 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 {\it error} in the data every once in a while,
``flipping a bit'' from a $0$ to a $1$ or vice versa.)
\bigskip
\noindent
D)  The reflected Gray code above is not the {\it 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 \le x \le 7 = 2^3 - 1$
with the same property.   (Hint: Think about what you did in question B.)
\bigskip
\noindent
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.) 
\item{1)} {\it How many different} Gray codes
are there for the integers in the range $0 \le x \le 3$?  Find them all.
\item{2)}  ({\bf Extra Credit})  Same question as part 1 for
the integers in $0 \le x \le 7 = 2^3 - 1$?
\bigskip
\noindent
{\it Assignment}
\bigskip
Group write-ups due on Monday, February 14.
\bye




