Over the last week I've been researching
Gray Codes and how to generate them. I understand the basic concept but I wanted a deeper understanding. Most of the explanations out there are a little dense so I'm going to try to make the available information a little bit more accessible to everyone. So let's start with a basic explanation of what a Gray code is.
A Gray Code is a special way of counting, where adjacent entries differ by only one digit. In practice this almost always refers to a binary counting sequence and more specifically a special code called the Binary Reflected Gray Code (BRGC). From here on, this is the Gray code that I'll be talking about.
These code have practical uses in many areas. The one that I'm most familiar with is in rotary encoders where it's advantageous that only one digit changes at a time. In a normal binary counting sequence you may have multiple bits change at once. For example from $$$0111$$$ to $$$1000$$$. The problem with this is that if all the bits don't change at exactly the same moment, the value $$$1010$$$ may be read from the sensor. If Gray codes are used, as you progress through the series only one bit changes at a time. This leaves no ambiguity as to what the value is.
Let's start with a formal definition of a Gray code and try to explain things in easier to understand terms.
$$G_0=\epsilon \\ G_{k+1}=0G_k,1G_k^R$$
The series for zero bits is shown as $$$G_0=\epsilon$$$ and indicates an empty series. The next equation, $$$G_{k+1}=0G_k,1G_k^R$$$ indicates that the series for a Gray code series of $$$k+1$$$ bits is created by taking the the Gray code of $$$k$$$ bits and joining a reversed copy to its end, with zeros added before entries in the first half of the series, and ones added before entries in the second half of the series. This is how the series ensures that consecutive entries only differ by one digit. This may be clearer in the diagram below.
 |
| Constructing $$$G_{k+1}$$$ from $$$G_{k}$$$ |
If $$$G_k$$$ is a Gray code where consecutive entries differ by one digit, then appending a mirror of itself to its end won't change that, except for where the two series join, as those two entries will be the same. Adding zero to the first half of the new series and one to the second half of the new series won't change it either but it does mean that the entries where the series join now differ by one digit. This means that the new series $$$G_{k+1}$$$ is now also a Gray code. It also proves that the entries in the output are unique. Starting with $$$G_0$$$, we know that all its entries are unique. If we then assume that all the elements of $$$G_k$$$ are unique, then the elements of $$$G_{k+1}$$$ must also be unique as $$$G_k$$$ with zeros added before it and a reverse copy of $$$G_k$$$ with ones added before it create a new unique series. It's then provable by induction that the each entry in a Gray code is unique.
This gives us the instructions needed to construct a Gray code of any length. Start with the minimal Gray Code that contains one empty element and keep doubling its length when adding a new digit.
 |
| Constructing $$$G_3$$$ from $$$G_2$$$ |
Getting a picture in your mind of what a Gray code looks like will be helpful for the next step. For some situations the above representation can help, but in others, the vertical table representation with the index $$$n$$$ of each element is better.
 |
| Gray code indices in decimal |
Now that I've explained the basics of what a Gray code is, I want to detail a proof of a well known formula to generate them with an xor operation.
$$H[n] = n \oplus (n>>1)$$
Where $$$H[n]$$$ is the $$$n$$$th element of the Gray code. $$$H$$$ is used at the moment as it's a hypothesis that this formula is equivalent to $$$G[n]$$$ described above.
I found a well thought out explanation of this proof in a
Quora post but it could do with some further explanation. So I'll repeat the proof here with some commentary to help those new to the subject. To be clear all of these operations are performed on the binary representation of the numbers involved.
First, let's define a helper function.
$$F[n,k]=(2^k-1) \oplus n$$
$$$F[n,k]$$$ is a function that inverts all the bits of a binary string $$$n$$$ of length $$$k$$$. $$$2^k$$$ is a binary string of length $$$k+1$$$ that is all zeros except for the most significant bit. Subtracting one from this will create a binary string of length $k$ that is all ones. When the string $n$ is xored with this all of the bits are inverted. This is a function that essentially reverses the direction of a binary count. For example, when $$$k=3$$$, and for a value of $$$n=001$$$, $$$F[001,3] = 110$$$. Where $$$001$$$ is the second entry when counting in binary, $$$110$$$ is the second last. It's a mathematical representation of reflecting/mirroring a binary count.
Now we have that out of the way we will prove the following
$$H[x] \oplus H[F[x,k]]=2^{k-1}$$
What does that mean? It's saying that the output of the hypothesis function xored with the hypothesis function with the input ordering reversed will give a string of length $$$k$$$ that is all zeros except for the most significant bit. This is a fancy way of saying that the output of $$$H$$$ is symmetrically except for the most significant bit. This is a property of the Gray code that we are trying to prove. From the beginning of the series each element of a Gray code is equal to the element the same distance from the end except for the most significant bit.
As $$$F[x,k]$$$ is an inverted version of $$$x$$$ the most significant bit of one or the other, but not both, will be equal to one. Let's assume that it's $$$x$$$. It doesn't matter which one is chosen, the proof works either way. We can now write
$$x=2^{k-1} \oplus y \quad where \quad y<2^{k-1}$$
It then follows that $$$F[x,k] = F[y,k-1]$$$. This says that inverting $$$x$$$ which we have defined to start with one, will now start with zero and is equal to the inverted value of the new shorter bit string $$$y$$$. For example if $$$x=1100101$$$ then $$$y = 100101$$$. So $$$F[1100101,7]=0011010$$$ and $$$F[100101,6]=011010$$$.
Now onto the proof. It's all maths at this point, you can ignore conceptual ideas here and just work through the process.
\begin{align}H[x] \oplus H[F[x,k]]&=(2^{k-1} \oplus y) \oplus (2^{k-2} \oplus (y>>1)) \oplus H[F[y,k-1]] \\ &=2^{k-1} \oplus 2^{k-2} \oplus H[y] \oplus H[F[y,k-1]] \\ &= 2^{k-1} \oplus 2^{k-2} \oplus 2^{k-2} \\ &= 2^{k-1}\end{align}
Now we've proven this, for strings of length $$$k$$$ using strings of length $$$k-1$$$ it just needs to be proved for strings of length 1 ie $$$k=1$$$ for the inductive proof to be complete.
\begin{align} H[0] \oplus H[1] &= 0 \oplus 0 \oplus 1 \oplus 0 \\&=1\end{align}
All of that above just proves that $$$H[n] = n \oplus (n>>1)$$$ results in an output series that is mirrored with the most significant bit inverted. Now we need to prove the following
$$H[2^k \oplus x] = 2^k \oplus H[F[x,k]] \quad where \quad x<2^k$$
This states that if we add a one to the input to the hypothesis function, it's equivalent to inverting the input and then adding a one to the output. It's hard to see, but this describes the process of going from a Gray code of $$$k-1$$$ bits to a Gray code of $$$k$$$ bits.
\begin{align} H[2^k \oplus x] &= 2^k \oplus x \oplus 2^{k-1} \oplus (x>>1) \\ &= 2^k \oplus 2^{k-1} \oplus H[x] \\ &=2^k \oplus H[F[x,k]]\end{align}
As we did before, this needs to be proved for $$$k=1$$$ for the induction proof to work.
\begin{align}H[10 \oplus 1] &= 10 \oplus H[0] \\H[11] &= 10 \oplus 0 \oplus 0 \\ 11 \oplus 01 &= 10 \\ 10=10 \end{align}
OK, that was a confusing rabbit hole we just fell down, but it proves that $$$H[n]=G[n]$$$ for all $$$n$$$. I'm not entirely sure we need both parts of that proof, but it can't hurt to prove it twice. 😅
We can now be sure that $$$G[n] = n \oplus (n>>1)$$$ How simple is that! A Gray code can be generated by xoring its index with itself but right shifted by one. This means that each digit of the Gray code is the xor of two consecutive digits in the input.
 |
| Generating a Gray code from an index - input in green output in purple |
In the image above it's kind of like differentiating the bit stream. If two consecutive bits are different it generates a one in the output. So if we go from index to Gray code with something like a differentiation you might think we can go the other way with integration. You sure can. I won't prove it but you can look it up.
Now all this seems a little simple and useless apart from the use case I gave at the start, but this goes into some deep concepts. We're looking at mathematics over a
finite field, in this case $$$GF(2)$$$. Now here's the really cool part. If you use each digit of a Gray code as a coordinate and plot it, you visit each vertex of a square for a two bit Gray code. For a three bit Gray code you visit each vertex of a cube travelling along the edges. More generally for a k bit code you travel along the edges of a k-dimensional hypercube visiting all vertices. This is called a Hamilton cycle.
Sorry if I'm ranting but I find all this fascinating, but it hasn't solidified in my mind yet.
If you've made it this far you deserve a joke.
Q. What's the best way to visit all the vertices of a hypercube?
A. On a Hamilton bicycle.
