binary Gray code

An n-bit binary Gray code is a non-repeating sequence of the integers from 0 to 2n-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 distanceMathworldPlanetmathPlanetmath 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:


There is a one-to-one correspondence between all possible n-bit Gray codes and all possible Hamiltonian cyclesMathworldPlanetmath 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