Gray Codes

# Gray Codes

 Definition: A Gray Code for \$k\$-bit words is an ordered list of \$2^k\$ many \$k\$-bit binary words (containing \$0\$'s and/or \$1\$'s) in which consecutive binary words differ by exactly one bit.

Recall Hamiltonian Graphs and Cube Graphs. The definition of a Cube graph is a graph \$G = (V(G), E(G))\$ is a graph that is obtained by taking all vertices denoted as binary words and joining the vertices with the edge whenever the binary words differ by \$1\$. While the definition of a Hamiltonian Graph is a graph \$G = (V(G), E(G))\$ is considered Hamiltonian if and only if the graph has a cycle containing all of the vertices of the graph

One property of cube graphs is that they are in fact Hamiltonian, and since each vertex in a cube graph is only joined to vertices with an edge whenever binary words differ by \$1\$ means that if we find what is known as a Hamiltonian Path for these \$Q_k\$ graphs, then we have successfully determined a gray code.

Let's recall \$Q_1\$, \$Q_2\$, and \$Q_3\$: \$Q_1\$ has a rather obvious Hamiltonian path as seen in blue: So a possible gray code for \$Q_1\$ is \$0 1\$

\$Q_2\$ also has a rather obvious Hamiltonian path, once again highlighted in blue: So a possible gray code for \$Q_2\$ is \$00 01 11 10\$

Now let's look at the more complex graph, \$Q_3\$. Here is a potential Hamiltonian path for \$Q_3\$ containing all vertices in \$Q_k\$: Hence we can obtain the gray code of \$000 010 110 100 101 111 011 001\$

Of course, drawing our graphs such as \$Q_4\$ and \$Q_5\$, …, will become ever more tedious. Here are some gray codes up to \$Q_5\$:

Number of Bits Gray Code
\$1\$-bit (\$Q_1\$) \$0 1\$
\$2\$-bit (\$Q_2\$) \$00 01 11 10\$
\$3\$-bit (\$Q_3\$) \$000 001 011 010 101 111 110 100\$
\$4\$-bit (\$Q_4\$) \$0000 0001 0011 0010 0101 0111 0110 0100 1001 1011 1111 1101 1010 1110 1100 1000\$
\$5\$-bit (\$Q_5\$) \$00000 00001 00011 00010 00101 00111 00110 00100 01001 01011 01111 01101 01010 01110 01100 01000 ...\$