Gray Code

Date: 02/16/2001 at 16:51:50
From: Hooman
Subject: Gray theory

Hi,

What is Gray theory?

Thanks a lot. Sincerely yours,
Hooman

Date: 02/16/2001 at 18:39:30
From: Doctor Anthony
Subject: Re: Gray theory

Generating n-Tuples of 0's and 1's
-----------------------------------
Consider a list of n-tuples of 0's and 1's that has the property 
that every element differs from its predecessor in only one place. 
Such a list corresponds to a walk along the edges of an 'n-cube' 
that visits every CORNER exactly once. Any such walk is called a 
Gray code of order n.

Example:  If n = 2, the 'n-cube' will be a square with vertices at 
(0,0), (0,1), (1,1), and (0,1).
    
     (0,1)      (1,1)
       |----------|
       |          |
       |          |
       |          |
       |          |
       |----------| 
     (0,0)      (1,0) 

A Gray code is (0,0), (1,0), (1,1), (0,1).

Note that you could reverse the order of the n-tuples and the list 
above would still be Gray code. However, you could not swap (0,0) and 
(1,0), because then successive terms would differ in more than one 
place and you would not be traversing an edge but jumping across open 
space.

If the terminal corner and initial corner of the walk are separated 
by one edge (i.e. the last element and the first element in the Gray 
code differ in only one place), then the Gray code is called 'cyclic'.
The Gray code for the 2-cube is cyclic.

If n = 3, the 'n-cube' is be an ordinary cube with vertices (0,0,0), 
(0,0,1), (1,0,1), (1,0,0), (1,1,0), (0,1,0), (0,1,1), and (1,1,1). 
This list of vertices is also a Gray code for the 3-cube. You should 
notice that every pair of adjacent terms differs in only 1 place. 
This means that one of the edges of the cube lies between any two 
adjacent terms.

There are algorithms that allow you to generate the Gray codes 
(n-tuples of 0's and 1's) for any given n.

The topic is related to methods used in generating permutations and 
combinations - as opposed to just calculating how many there are.
 
- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/