跳转至

格雷碼

格雷碼是一個二進制數系，其中兩個相鄰數的二進制位只有一位不同。舉個例子，\(3\) 位二進制數的格雷碼序列為

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

注意序列的下標我們以 \(0\) 為起點，也就是説 \(G(0)=000,G(4)=110\)。

格雷碼由貝爾實驗室的 Frank Gray 於 1940 年代提出，並於 1953 年獲得專利。

構造格雷碼（變換）

格雷碼的構造方法很多。我們首先介紹手動構造方法，然後會給出構造的代碼以及正確性證明。

手動構造

\(k\) 位的格雷碼可以通過以下方法構造。我們從全 \(0\) 格雷碼開始，按照下面策略：

  1. 翻轉最低位得到下一個格雷碼，（例如 \(000\to 001\)）；
  2. 把最右邊的 \(1\) 的左邊的位翻轉得到下一個格雷碼，（例如 \(001\to 011\)）；

交替按照上述策略生成 \(2^{k-1}\) 次，可得到 \(k\) 位的格雷碼序列。

鏡像構造

\(k\) 位的格雷碼可以從 \(k-1\) 位的格雷碼以上下鏡射後加上新位的方式快速得到，如下圖：

\[ \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} \]

計算方法

我們觀察一下 \(n\) 的二進制和 \(G(n)\)。可以發現，如果 \(G(n)\) 的二進制第 \(i\) 位為 \(1\)，僅當 \(n\) 的二進制第 \(i\) 位為 \(1\)，第 \(i+1\) 位為 \(0\) 或者第 \(i\) 位為 \(0\)，第 \(i+1\) 位為 \(1\)。於是我們可以當成一個異或的運算，即

\[ G(n)=n\oplus \left\lfloor\frac{n}{2}\right\rfloor \]
1
int g(int n) { return n ^ (n >> 1); }

正確性證明

接下來我們證明一下，按照上述公式生成的格雷碼序列，相鄰兩個格雷碼的二進制位有且僅有一位不同。

我們考慮 \(n\) 和 \(n+1\) 的區別。把 \(n\) 加 \(1\)，相當於把 \(n\) 的二進制下末位的連續的 \(1\) 全部變成取反，然後把最低位的 \(0\) 變成 \(1\)。我們這樣表示 \(n\) 和 \(n+1\) 的二進制位：

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

於是我們在計算 \(g(n)\) 和 \(g(n+1)\) 的時侯，後 \(k\) 位都會變成 \(\displaystyle\underbrace{100\cdots00}_{k\text{個}}\) 的形式，而第 \(k+1\) 位是不同的，因為 \(n\) 和 \(n+1\) 除了後 \(k+1\) 位，其他位都是相同的。因此第 \(k+1\) 位要麼同時異或 \(1\)，要麼同時異或 \(0\)。兩種情況，第 \(k+1\) 位都是不同的。而除了後 \(k+1\) 位以外的二進制位也是做相同的異或運算，結果是相同的。

證畢。

通過格雷碼構造原數（逆變換）

接下來我們考慮格雷碼的逆變換，即給你一個格雷碼 \(g\)，要求你找到原數 \(n\)。我們考慮從二進制最高位遍歷到最低位（最低位下標為 \(1\)，即個位；最高位下標為 \(k\)）。則 \(n\) 的二進制第 \(i\) 位與 \(g\) 的二進制第 \(i\) 位 \(g_i\) 的關係如下：

\[ \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;
}

實際應用

格雷碼有一些十分有用的應用，有些應用讓人意想不到：

  • \(k\) 位二進制數的格雷碼序列可以當作 \(k\) 維空間中的一個超立方體（二維裏的正方形，一維裏的單位向量）頂點的哈密爾頓迴路，其中格雷碼的每一位代表一個維度的座標。

  • 格雷碼被用於最小化數字模擬轉換器（比如傳感器）的信號傳輸中出現的錯誤，因為它每次只改變一個位。

  • 格雷碼可以用來解決漢諾塔的問題。

    設盤的數量為 \(n\)。我們從 \(n\) 位全 \(0\) 的格雷碼 \(G(0)\) 開始，依次移向下一個格雷碼（\(G(i)\) 移向 \(G(i+1)\)）。當前格雷碼的二進制第 \(i\) 位表示從小到大第 \(i\) 個盤子。

    由於每一次只有一個二進制位會改變，因此當第 \(i\) 位改變時，我們移動第 \(i\) 個盤子。在移動盤子的過程中，除了最小的盤子，其他任意一個盤子在移動的時侯，只能有一個放置選擇。在移動第一個盤子的時侯，我們總是有兩個放置選擇。於是我們的策略如下：

    如果 \(n\) 是一個奇數，那麼盤子的移動路徑為 \(f\to t\to r\to f\to t\to r\to\cdots\)，其中 \(f\) 是最開始的柱子，\(t\) 是最終我們把所有盤子放到的柱子，\(r\) 是中間的柱子。

    如果 \(n\) 是偶數：\(f \to r \to t \to f \to r \to t \to \cdots\)

  • 格雷碼也在遺傳算法理論中得到應用。

習題

本頁面部分內容譯自博文 Код Грея 與其英文翻譯版 Gray code。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

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