Gray Code

Author

Eric W. Weisstein
March 31, 2005

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/GrayCode.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/GrayCode.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Additional Authors

GrayCode and FromGrayCode by
Richard Phillips
Oct. 11, 2004

Code

GrayCodeList[k_]:=Module[{b=IntegerDigits[k,2],i},
Do[
If[b[[i-1]]==1,b[[i]]=1-b[[i]]],
{i,Length[b],2,-1}
];
b
]

FromGrayCodeList[d_]:=Module[{b=d,i,j},
Do[
If[Mod[Sum[b[[j]],{j,i-1}],2]==1,
b[[i]]=1-b[[i]]],
{i,n=Length[d],2,-1}
];
FromDigits[b,2]
]

GrayCode[i_,n_]:=FromDigits[BitXor@@@Partition[Prepend[IntegerDigits[i,2,n],0],2,1],2]
FromGrayCode[i_,n_]:=FromDigits[BitXor[IntegerDigits[i,2,n],FoldList[BitXor,0,Most[IntegerDigits[i,2,n]]]],2]

Examples

FromDigits[#,2]&/@(GrayCodeList/@Range[0,15])

(GrayCode[#,4]&/@Range[0,15])

BaseForm[#,2]&/@(FromDigits[#,2]&/@(MyGrayCode/@Range[0,15]))

DisplayForm[GridBox[
Flatten/@Transpose@Partition[Table[{i,BaseForm[FromDigits[MyGrayCode[i],2],2]},{i,0,59}],20],
GridFrame->True,RowLines->True,ColumnLines->True,ColumnAlignments->Right]]

Table[FromGrayCode[MyGrayCode[i]],{i,20}]

Figure

<<Utilities`Plot`

Show[PixelPerfect[BasePlot[FromDigits[#,2]&/@MyGrayCode/@Range[255]],BlockSize->2]]

Show[PixelPerfect[BasePlot[FromDigits[#,2]&/@MyGrayCode/@Range[511]],BlockSize->1]]

By Reflection

GrayReflections[n_]:=Nest[Function[d,Flatten/@Join[Prepend[{#},0]&/@d,Prepend[{#},1]&/@Reverse[d]]],{0,1},n]

GrayReflections[1]

GrayReflections[2]

GrayCodeList/@Range[0,7]