The Gray Code

2026, Kenneth Levasseur
Mathematics & Statistics
UMass Lowell
Kenneth_Levasseur@uml.edu

v=Tuples[{0,1},4];
e=Map[UndirectedEdge@@#&,Select[Subsets[v,{2}],(Total[Mod[#[[1]]+#[[2]],2]]==1)&]];
Graph[e,VertexLabels->"Name",PlotLabel->"The 4-Cube"]

The Gray Code is a Hamiltonian cycle through the n-Cube.  It is a list of the (2^n) bit strings of length n with the property that each string differs from its predecessor in exactly one position.  The last string is understood to be connected to the first.

Here is the Gray Code for the 4-cube with each string converted to a base 10 integer.

{GrayCode[4],Map[FromDigits[#,2]&,GrayCode[4]]}//Transpose

This isn’t the usual ordering of the integers from 0 to 15 but there are reasons why it’s a better ordering such as in many electronics applications.  So it’s of interest to know how to convert back and forth between the usual sequence of integers from 0 to (2^n)-1 to the Gray code ordering of the same integers.

By the way, the Gray Code isn't the only Hamiltonian cycle on the 4-cube but it’s one of the simplest one to construct.

If we consider the entries in the Gray Code to be integers in base 2, the numbers are as follows for the 4-cube.

Map[FromDigits[#,2]&,GrayCode[4]]

This is a permutation of the integers from 0 to 15.  The next output is the “matrix representation” of this as a function on {0,1,2,...,13,14,15}.

{Range[0,15],Map[FromDigits[#,2]&,GrayCode[4]]}

There are two related questions we might ask:
1.  If 0≤k≤(2^n)-1, what number is in position k?
2. If 0≤k≤(2^n)-1, where is k in the list?

Note: In answering these questions, keep in mind that positions are indexed starting at 0, not 1.

For example, the number position 7 of the Gray Code for the 4-cube is 4. We say that the conversion to the Gray Code of 7  is 4.

If we look for 7 in the in the Gray Code for the 4-cube, we find it in position 5. We say that the conversion from the Gray Code of 7 is 5

A function to answer the first question, what number is in a given position?

The function is designed to take two modes of input, but the output is always a sting of bits that we can easily convert to an integer using FromDigits.  The code for this and other functions used in this Notebook is in the Initializations Section.

?ToGray

ToGray[7,4]

ToGray[{0,1,1,1}]

FromDigits[ToGray[{0,1,1,1}],2]

A function to answer the second question, where is a given number?:

FromGray has the same basic design as ToGray.

?FromGray

FromGray[{0,1,1,1}]

FromGray[7,4]

FromDigits[FromGray[{0,1,1,1}],2]

Interesting Visuals

ListPlot[Map[{#,FromDigits[FromGray[#,6],2]}&,Range[0,(2^6)-1]]]

ListPlot[Map[{#,FromDigits[ToGray[#,6],2]}&,Range[0,(2^6)-1]]]

Here is a composition of the ToGray function with itself.

Map[{#,FromDigits[ToGray[ToGray[#,6]],2]}&,Range[0,63]]//ListPlot

Manipulate[Map[{#,FromDigits[Nest[FromGray,FromGray[#,n],k-1],2]}&,Range[0,2^n-1]]//ListPlot[#,Ticks->{Range[0,2^n-1,Max[1,2^(n-3)]],Range[0,2^n-1,Max[1,2^(n-3)]]}]&,{k,1,32,1},{n,2,10,1}]

Manipulate[Map[{#,FromDigits[Nest[ToGray,ToGray[#,n],k-1],2]}&,Range[0,2^n-1]]//ListPlot[#,Ticks->{Range[0,2^n-1,Max[1,2^(n-3)]],Range[0,2^n-1,Max[1,2^(n-3)]]}]&,{k,1,32,1},{n,2,10,1}]

Timing of the functions on the 512-Cube.

n=512;s=RandomInteger[{0,1},n-1]//Prepend[#,1]&;k=FromDigits[s,2];
{Timing[FromGray[k,n];],Timing[FromGray[s];]}

n=512;s=RandomInteger[{0,1},n-1]//Prepend[#,1]&;k=FromDigits[s,2];
{Timing[ToGray[k,n];],Timing[ToGray[s];]}

The order of the Gray Code as a permutation,

The GrayOrder function determines the order of the Gray Code function on the n-Cube.

GrayOrder[6]

Conjecture:  The order of the (n^th)Gray Code is  (2^(Ceiling[(Subscript[log, 2])(n)])), which implies that the order  on the (2^m)-cube is (2^m).

Map[{#,GrayOrder[#],2^Ceiling[Log[2,#]]}&,Range[1,17]]

Gray Code Decoder

An exercise in Chapter 14 of Applied Discrete Structures introduces the Gray Code Decoder, which is the same as the function FromGray.  Starting in Copy state, if the bits in a string are used as input from left to right, the output will be the location of that string in the Gray Code.

The state machine for the Gray Code decoder.

Import["http://faculty.uml.edu/klevasseur/ads/images/fig-gray-code-decoder.png"]

GrayDecoder::usage="GrayDecoder[bitlist] returns the location of bitlist on the Gray Code on n bits, where n is the length of bitlist."

GrayDecoder[seq_List]:=Module[{state},state=0;Map[If[state==0,state=#;#,state=1-#;1-#]&,seq]]

GrayDecoder[{1,0,1,1,0}]

FromGray[{1,0,1,1,0}]

Initializations

GrayCode::usage="GrayCode[n] returns the Gray Code on n bits in the form of lists of bits.";

GrayCode[1]={{0},{1}};
GrayCode[n_]:=GrayCode[n]=Join[Map[Prepend[#,0]&,GrayCode[n-1]],Map[Prepend[#,1]&,Reverse[GrayCode[n-1]]]]

FromGray::usage="FromGray[k,n] returns the k'th entry in the Gray code on n bits.  Caution: numbering starts with 0.\nFromGray[bitlist] returns the location of bitlist on the Gray Code on n bits, where n is the length of bitlist.";

GrayOrder::usage="GrayOrder[n] returns the order of the Gray Code function on the n-Cube."

FromGray[0,1]={0};
FromGray[1,1]={1};
FromGray[k_,n_]:=FromGray[{k,n}]
FromGray[{k_,n_}/;(k≥0) &&( k<2^n)]:=If[k<2^(n-1),Prepend[FromGray[k,n-1],0],Prepend[FromGray[2^n-1-k,n-1],1]]

The following function realizes the Gray Code Decoder.

FromGray[seq_List]:=Module[{state},state=0;Map[If[state==0,state=#;#,state=1-#;1-#]&,seq]]

FromGray[k_?NumberQ,n_]:=FromGray[PadLeft[IntegerDigits[k,2],n]]

ToGray::usage="ToGray[bitlist] returns the bit string that is in position bitlist of the Gray Code on n bits, where n is the length of bitlist.\n ToGray[k,n] returns the bitstring that is in position k in the Gray code on n bits. ";

ToGray[pos_List]:=Mod[pos+(pos//Drop[#,-1]&//Prepend[#,0]&),2]

ToGray[k_,n_]:=ToGray[PadLeft[IntegerDigits[k,2],n]]

GrayOrder[n_]:=Module[{id,k=1},id=Map[PadLeft[IntegerDigits[#,2],n]&,Range[0,2^n-1]];
NestWhile[(k+=1;Map[ToGray[#]&,#])&,Map[ToGray,id],(#!=id)&];
k]

GrayCycles[k_]:=Map[#-1&,PermutationCycles[1+Map[FromDigits[#,2]&,GrayCode[k]]],{2}]

Tests and further experiments

GrayOrder[5]

GrayCycles[k_]:=PermutationCycles[1+Map[FromDigits[#,2]&,GrayCode[k]]]

GrayCycles[3]

GrayCycles[4]

GrayCycles[5]

{#,Tally[Length/@First[GrayCycles[#]]]}&/@Range[2,18]

PowerOfTwoQ[k_]:=FixedPoint[If[EvenQ[#1],((#1)/2),#1]&,k]==1

?PowerOfTwoQ

Select[Range[600144],PowerOfTwoQ[({2,1,3,30,4080,#}.(2^Range[0,5]))]&]

FactorInteger/@%

(({2,1,3,30,4080,#}.(2^Range[0,5])))&[

Map[FactorInteger,%]

{Range[16,31],Map[FromDigits[#,2]&,GrayCode[5]]//Take[#,-16]&}-16

GrayCode[4]

s=RandomInteger[{0,1},100]

FromGray[s]//FromDigits[#,2]&

FromGray[FromDigits[s,2],100]//FromDigits[#,2]&

{ToGray[6,5],ToGray[{0,0,1,1,0}]}

n=40;
num=RandomInteger[{0,2^n-1}];
string=IntegerDigits[num,2];
{Timing[FromGray[num,n];],Timing[FromGray[string];]}

n=40;
num=RandomInteger[{0,2^n-1}];
string=IntegerDigits[num,2];
{Timing[ToGray[num,n];],Timing[ToGray[string];]}

Map[GC[3,#]&,Range[0,7]]

Map[GC[3,#]&,Range[0,7]]==Map[ToGray,Map[PadLeft[IntegerDigits[#,2],3]&,Range[0,7]]]

Map[GC[4,#]&,Range[0,15]]==Map[ToGray,Map[PadLeft[IntegerDigits[#,2],4]&,Range[0,15]]]

Timing[ToGray[string]]

ToGray[{1,0,0}]

GrayCode[3]

FromDigits[FromGray[#,4],2]&/@Range[0,2^4-1]//ListPlot

Map[GC[4,#]&,Map[FromDigits[#,2]&,GrayCode[4]]]

GC[3,2]

GrayCode[3]

The state machine for the Gray Code decoder.

Import["http://faculty.uml.edu/klevasseur/ads/images/fig-gray-code-decoder.png"]

FromGray[{1,1,0}]

FromGray[{0,0,0,1,0,1}]

ToGray[{0,1,0}]

Map[FromDigits[GrayDecoder[#],2]&,GrayCode[6]]

Timing[GrayDecoder[Table[RandomInteger[],{50}]]]

Timing[ToGray[Table[RandomInteger[],{50}]]]

nums=Map[PadLeft[IntegerDigits[#,2],5]&,Range[0,31]]

{Map[Nest[GrayDecoder,#,3]&,nums],GrayCode[5]}//Transpose