Gray code

Gray code is a binary numeral system in which the binary representations of any two adjacent numbers differ in exactly one bit. For example, the Gray code sequence for $3$-bit binary numbers is

$$000,001,011,010,110,111,101,100$$

Note that sequence indices start at $0$; that is, $G(0)=000,G(4)=110$.

Gray code was proposed by Frank Gray of Bell Labs in the 1940s and patented in 1953.

Constructing Gray code (transformation)

There are many ways to construct Gray code. We first introduce a manual construction, then give code and a correctness proof.

Manual construction

A $k$-bit Gray code can be constructed as follows. Start with the all-$0$ Gray code and use these rules:

1. Flip the least significant bit to obtain the next Gray code (for example, $000\to 001$);
2. Flip the bit to the left of the rightmost $1$ to obtain the next Gray code (for example, $001\to 011$).

Applying these rules alternately for $2^{k-1}$ steps produces the sequence of $k$-bit Gray codes.

Mirror construction

A $k$-bit Gray code can be obtained quickly from a $k-1$-bit Gray code by mirroring it vertically and then prefixing a new bit, as shown below:

$$\begin{matrix} k=1\\ 0\\ 1\\\\\\\\\\\\\\ \end{matrix} \to \begin{matrix}\\ \color{Red}0\\\color{Red}1\\\color{Blue}1\\\color{Blue}0\\\\\\\\\\ \end{matrix} \to \begin{matrix} k=2\\ {\color{Red}0}0\\{\color{Red}0}1\\{\color{Blue}1}1\\{\color{Blue}1}0\\\\\\\\\\ \end{matrix} \to \begin{matrix}\\ \color{Red}00\\\color{Red}01\\\color{Red}11\\\color{Red}10\\\color{Blue}10\\\color{Blue}11\\\color{Blue}01\\\color{Blue}00 \end{matrix} \to \begin{matrix} k=3\\ {\color{Red}0}00\\{\color{Red}0}01\\{\color{Red}0}11\\{\color{Red}0}10\\{\color{Blue}1}10\\{\color{Blue}1}11\\{\color{Blue}1}01\\{\color{Blue}1}00 \end{matrix}$$

Computing Gray code

Let us compare the binary representations of $n$ and $G(n)$. The binary representation of $G(n)$ has bit $i$ equal to $1$ exactly when $n$'s bit $i$ is $1$ and bit $i+1$ is $0$, or bit $i$ is $0$ and bit $i+1$ is $1$. Thus, this is an XOR operation:

$$G(n)=n\oplus \left\lfloor\frac{n}{2}\right\rfloor$$

int g(int n) { return n ^ (n >> 1); }

Correctness proof

We now prove that in the Gray code sequence generated by the formula above, the binary representations of every pair of adjacent Gray codes differ in exactly one bit.

Consider the difference between $n$ and $n+1$. Consider the operation on $n$ of adding $1$. This flips all of $n$'s consecutive $1$ bits at the end to zero, then changes the lowest $0$ to $1$. Write the binary representations of $n$ and $n+1$ as follows:

$$\begin{aligned} (n)_2 &= \cdots0\underbrace{11\cdots11}_{k\text{个}}\\ (n+1)_2 &= \cdots1\underbrace{00\cdots00}_{k\text{个}} \end{aligned}$$

When computing $g(n)$ and $g(n+1)$, the last $k$ bits both become the form $\displaystyle\underbrace{100\cdots00}_{k\text{个}}$, while bit $k+1$ is different. This is because $n$ and $n+1$ are identical except for their last $k+1$ bits, so bit $k+1$ is XORed with either $1$ in both cases or $0$ in both cases. In either case, bit $k+1$ is different. Apart from the last $k+1$ bits, the other bits are XORed in the same way, so their results are identical.

This proves the claim.

Constructing the original number from Gray code (inverse transformation)

Next, consider the inverse transformation of Gray code: given a Gray code $g$, find the original number $n$. Traverse the binary bits from the most significant bit to the least significant bit (the least significant bit has index $1$, namely the units bit; the most significant bit has index $k$). The relationship between $n$'s binary bit $i$ and $g$'s binary bit $i$, denoted $g_i$, is:

$$\begin{aligned} n_k &= g_k \\ n_{k-1} &= g_{k-1} \oplus n_k &&= g_k \oplus g_{k-1} \\ n_{k-2} &= g_{k-2} \oplus n_{k-1} &&= g_k \oplus g_{k-1} \oplus g_{k-2} \\ n_{k-3} &= g_{k-3} \oplus n_{k-2} &&= g_k \oplus g_{k-1} \oplus g_{k-2} \oplus g_{k-3} \\ &\vdots\\ n_{k-i} &=\displaystyle\bigoplus_{j=0}^ig_{k-j} \end{aligned}$$

int rev_g(int g) {
  int n = 0;
  for (; g; g >>= 1) n ^= g;
  return n;
}

Applications

Gray code has several useful applications, some of which are unexpected:

• The Gray code sequence of $k$-bit binary numbers can be viewed as a Hamiltonian cycle through the vertices of a $k$-dimensional hypercube (a square in two dimensions and a unit segment in one dimension), where each bit of the Gray code represents one coordinate dimension.

• Gray code is used to minimize errors in signal transmission in digital-to-analog converters (such as sensors), because only one bit changes at a time.

• Gray code can be used to solve the Tower of Hanoi problem.

  Let the number of disks be $n$. Start from the $n$-bit all-$0$ Gray code $G(0)$ and move to the next Gray code in sequence (move from $G(i)$ to $G(i+1)$). The $i$-th binary bit of the current Gray code represents the $i$-th disk, counting from smallest to largest.

  Since exactly one binary bit changes at each step, move disk $i$ whenever bit $i$ changes. During the disk moves, every disk other than the smallest has only one possible destination. When moving the first disk, there are always two possible destinations. Thus, use the following strategy:

  If $n$ is odd, the disk-movement path is $f\to t\to r\to f\to t\to r\to\cdots$, where $f$ is the starting peg, $t$ is the peg to which all disks are ultimately moved, and $r$ is the remaining peg.

  If $n$ is even: $f \to r \to t \to f \to r \to t \to \cdots$

• Gray code is also used in the theory of genetic algorithms.

Exercises

• CSP S2 2019 D1T1 Difficulty: easy

• SGU #249 Matrix Difficulty: medium

Some content on this page is translated from the blog post Код Грея and its English translation Gray code. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.