Math 455  •  4 May 2009

Reflective binary Gray code

Copyright © 2009 by Murray Eisenberg.  All rights reserved.

Introduction

A binary Gray code of order n is a walk in the (hyper)cube (Subscript[Q, n]) that becomes a Hamiltonian cycle in (Subscript[Q, n]) when the initial vertex of the walk is appended at the end so as to close the walk. Thus a binary Gray code is a list of all the n-bit binary words in which each two consecutive words differ in exactly one bit and the final word differs from the initial word in exactly one bit.
The reflective binary Gray code of order n is the particular binary Gray code constructed by the algorithm indicated below.

A utility to convert binary words to text strings

It will be convenient to represent each binary word as a Mathematica list consisting of 0s and 1s. If you wish, you can convert such a list of 0s and 1s to a text string by using the following function.

toBinaryWord[lis_List]:=StringJoin[lis/.{0->"0",1->"1"}]

For example:

toBinaryWord[{0,1,1,0,1}]

Then to convert an entire binary Gray code c to the corresponding list of text strings, use:
	 Map[toBinaryWord, c]

Creating the reflective binary Gray code step-by-step

The reflective binary Gray code of order 1

By definition, the reflective binary Gray code of order 1 is:

c={0,1};

The number of binary words here is (2^1), which is given by:

k=Length[c]

The reflective binary Gray code of order 2

To construct the reflective binary Gray code of order 2 from the code c of order 1, first reverse the bits of c and join the result to the original c:

Reverse[c]

r=Join[c,Reverse[c]]

Next, prepend 0 to each entry in the first half of this new list and prepend 1 to each entry in the second half of that list.

Here is the entire list of what needs to be prepended:

z=Join[Table[0,{k}],Table[1,{k}]]

You can accomplish the prepending in this case as follows:

{z,r}

c=Transpose[{z,r}]

That is the reflective binary Gray code of order 2. Here it is again, displayed as a table of length 2 lists of bits:

c//TableForm

And here is the same thing but shown as a table of text words:

Map[toBinaryWord,c]//TableForm

The number of binary words here is (2^2), which is given by:

k=Length[c]

The reflective binary Gray code of order 3

To construct the reflective binary Gray code of order 3 from the code c of order 2, first reverse the bits of c and join the result to the original c:

r=Join[c,Reverse[c]]

Next, append 0 to each entry in the first half of this new list and append 1 to each entry in the second half of that list. As before, first form the list of what needs to be appended:

z=Join[Table[0,{Length[c]}],Table[1,{Length[c]}]]

The method eariler to carry out the prepending does not work here, since each entry in r is already a list:

{z,r}

Transpose[{z,r}]

The desired list has to have first entry {0,0,0}, second entry {0,0,1}, etc. Here is one way to obtain the desired list:

Partition[Flatten[Transpose[{z,r}],2],3]

However, there is no need to do quite that much work: the built-in function MapThread accomplishes doing the same thing:

MapThread[Prepend,{r,z}]

Map[toBinaryWord,%]//TableForm

For an animation that explains visually what MapThread does, see the Animated Mathematica Functions page at the on-line Wolfram Documentation Center.

Generalizing the MapThread[Prepend,{r,z}] method

The expression MapThread[Prepend,{r,z}] does not work as is if you start with the original reflective binary Gray code of order 1:

c={0, 1};
k=Length[c];
r=Join[c, Reverse[c]];
z=Join[Table[0,{k}],Table[1,{k}]];
MapThread[Prepend,{r,z}]

Why didn't that work?  Look at one of the attempted Prepend operations:

Prepend[0,0]

The first argument to Append must be a list!  So the following does work:

Prepend[{0},0]

Hence to make the MapThread[Prepend,{r,z}] method work even in this case, start instead with c = {{0},{1}}:

c={ {0},{1} };
k=Length[c];
r=Join[c,Reverse[c]];
z=Join[Table[0,{k}],Table[1,{k}]];
MapThread[Prepend,{r,z}]

A program for creating the reflective binary Gray code

The individual steps to go from the reflective binary Gray code of order k to the reflective binary Gray code of order k+1may be combined into the following function grayStep:

grayStep[c_]:=Module[{r,z,k=Length[c]},
r=Join[c,Reverse[c]];
z=Join[Table[0,{k}],Table[1,{k}]];
MapThread[Prepend,{r,z}]
]

For example:

grayStep[{{0},{1}}]

grayStep[%]

grayStep[grayStep[{{0},{1}}]]

Then the reflective binary Gray code of an arbitrary order may be obtained by iterating the function grayStep an appropriate number of times. The simplest way to carry out the iteration is to use the built-in Mathematica function Nest:

Nest[grayStep,{{0},{1}},2]

For an animation that explains visually what Nest does, see the Animated Mathematica Functions page at the on-line Wolfram Documentation Center.

Here, finally, is a function to create the reflective Gray code of arbitrary order:

reflectiveGrayCode[n_]:=Nest[grayStep,{{0},{1}},n-1]

reflectiveGrayCode[3]

Map[toBinaryWord,%]//TableForm