Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search