Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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 
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/   
    
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/