Skip to content

Gray Code

Gray code is a binary numeral system where two successive values differ in only one bit. For example, the Gray code sequence for 3-bit binary numbers is

\[ 000,001,011,010,110,111,101,100 \]

Note that the sequence indices start from \(0\), meaning \(G(0)=000\) and \(G(4)=110\).

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

Constructing Gray Code (Transformation)

There are many methods to construct Gray code. We first introduce manual construction methods, then provide code for construction and proof of correctness.

Manual Construction

A \(k\)-bit Gray code can be constructed as follows. Starting from the all-zero Gray code, follow this strategy:

  1. Flip the lowest bit to obtain the next Gray code (e.g., \(000\to 001\));
  2. Flip the bit to the left of the rightmost \(1\) to obtain the next Gray code (e.g., \(001\to 011\));

Alternate between the above strategies for \(2^{k-1}\) times to obtain the \(k\)-bit Gray code sequence.

Mirror Construction

A \(k\)-bit Gray code can be quickly obtained from the \((k-1)\)-bit Gray code by mirroring it and adding 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} \]

Calculation Method

Observe the binary representations of \(n\) and \(G(n)\). It can be seen that the \(i\)-th bit of \(G(n)\) is \(1\) if and only if the \(i\)-th bit of \(n\) is \(1\) and the \((i+1)\)-th bit is \(0\), or the \(i\)-th bit is \(0\) and the \((i+1)\)-th bit is \(1\). This can be treated as an XOR operation:

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

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

Proof of Correctness

Next, we prove that in the Gray code sequence generated by the above formula, two successive Gray codes differ in exactly one bit.

Consider the difference between \(n\) and \(n+1\). Adding \(1\) to \(n\) is equivalent to inverting all consecutive \(1\)s at the end of \(n\)'s binary representation and changing the lowest \(0\) to \(1\). We represent the binary digits of \(n\) and \(n+1\) as:

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

When computing \(g(n)\) and \(g(n+1)\), the last \(k\) bits will become \(\displaystyle\underbrace{100\cdots00}_{k\text{ bits}}\), while the \((k+1)\)-th bit differs because \(n\) and \(n+1\) are identical except for the last \(k+1\) bits. Therefore, the \((k+1)\)-th bit is either XORed with \(1\) or with \(0\) in both cases. In either scenario, the \((k+1)\)-th bit differs. The bits beyond the last \(k+1\) bits undergo the same XOR operation, so they remain identical.

Q.E.D.

Reconstructing the Original Number from Gray Code (Inverse Transformation)

Now consider the inverse transformation of Gray code: given a Gray code \(g\), find the original number \(n\). We traverse from the highest binary bit to the lowest (lowest bit index is \(1\), i.e., the units place; highest bit index is \(k\)). The relationship between the \(i\)-th bit of \(n\) and the \(i\)-th bit \(g_i\) of \(g\) 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} \]

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

Practical Applications

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

  • The Gray code sequence of \(k\)-bit binary numbers can be seen as a Hamiltonian cycle on the vertices of a hypercube in \(k\)-dimensional space (a square in 2D, a unit vector in 1D), where each bit of the Gray code represents a coordinate in one dimension.

  • Gray code is used to minimize errors in signal transmission in digital-to-analog converters (e.g., 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 all-zero \(n\)-bit Gray code \(G(0)\) and move to the next Gray code sequentially (\(G(i)\) to \(G(i+1)\)). The \(i\)-th bit of the current Gray code represents the \(i\)-th smallest disk.

    Since only one bit changes at a time, when the \(i\)-th bit changes, we move the \(i\)-th disk. During the disk movement, except for the smallest disk, any other disk has only one placement choice when moving. For the smallest disk, there are always two placement choices. Thus, our strategy is as follows:

    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 initial rod, \(t\) is the rod where all disks are finally placed, and \(r\) is the intermediate rod.

    If \(n\) is even: \(f \to r \to t \to f \to r \to t \to \cdots\)

  • Gray code is also used in genetic algorithm theory.

Exercises

This page is partially 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.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用