binary Gray code

An $n$-bit binary Gray code is a non-repeating sequence of the integers from $0$ to $2^n-1$ inclusive such that the binary representation of each number in the sequence differs by exactly one bit from the binary representation of the previous number: that is, the Hamming distance between consecutive elements is $1$. In addition, we also define a cyclic Gray code to be a Gray code where an extra condition is imposed: The last number in the sequence must differ by exactly one bit from the first number in the sequence.

For example, one $3$-bit cyclic Gray code is:

$${000}_2$$

$${010}_2$$

$${011}_2$$

$${001}_2$$

$${101}_2$$

$${111}_2$$

$${110}_2$$

$${100}_2$$

There is a one-to-one correspondence between all possible $n$-bit Gray codes and all possible Hamiltonian cycles on an $n$-dimensional hypercube. (To see why this is so, imagine assigning a binary number to each vertex of a hypercube where an edge joins each pair of vertices that differ by exactly one bit.)

Title	binary Gray code
Canonical name	BinaryGrayCode
Date of creation	2013-03-22 12:30:09
Last modified on	2013-03-22 12:30:09
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	9
Author	mathcam (2727)
Entry type	Definition
Classification	msc 68P30
Classification	msc 05C45
Synonym	Gray code
Defines	cyclic Gray code