格雷码

格雷码（循环二进制单位距离碼）是任意两个相邻数的代码只有一位二进制数不同的编码，它与奇偶校验码同属可靠性编码。

簡介
格雷碼（Gray code）是由貝爾實驗室的Frank Gray在1940年提出，用於在PCM（脈衝編碼調變）方法傳送訊號時防止出錯，並於1953年三月十七日取得美國專利。格雷碼是一個數列集合，相鄰兩數間只有一個位元改變，為無權數碼，且格雷碼的順序不是唯一的。

格雷碼能避免訊號傳送錯誤的原理
傳統的二進位系統例如數字3的表示法為011，要切換為鄰近的數字4，也就是100時，裝置中的三個位元都得要轉換，因此於未完全轉換的過程時裝置會經歷短暫的，010,001,101,110,111等其中數種狀態，也就是代表著2、1、5、6、7，因此此種數字編碼方法於鄰近數字轉換時有比較大的誤差可能範圍。格雷碼的發明即是用來將誤差之可能性縮減至最小，編碼的方式定義為每個鄰近數字都只相差一個位元，因此也稱為最小差異碼，可以使裝置做數字步進時只更動最少的位元數以提高穩定性。
數字0～7的編碼比較如下：

十進位 　 格雷碼　二進位
0 　　 000 000
1 　　 001 001
2 　　011 010
3 　　010 011
4 　　110 100
5 　　111 101
6 　　101 110
7 　　100 111

直接排列
以二進制為0值的格雷碼為第零項，第一項改變最右邊的位元，第二項改變右起第一個為1的位元的左邊位元，第三、四項方法同第一、二項，如此反覆，即可排列出n個位元的格雷碼。

鏡射排列
n位元的格雷碼可以從n-1位元的格雷碼以上下鏡射後加上新位元的方式快速的得到，如右圖所示一般。

下面詳述鏡射排列（binary-reflected Gray code）構造n位元的格雷碼的構造原理。在這個方法中，n位元的格雷碼是透過遞迴地鏡射n-1位元的格雷碼（也就是複製一份並翻轉順序，放在原列表下方），並在兩份列表最前面分別放上0和1，以產生格雷碼。比如說，對於n=4，我們有下面步驟：

4位元的格雷碼：0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000

鏡射後的格雷碼：1000, 1001, 1011, 1010, 1110, 1111, 1101, 1100, 0100, 0101, 0111, 0110, 0010, 0011, 0001, 0000

將原格雷碼加上0：00000, 00001, 00011, 00010, 00110, 00111, 00101, 00100, 01100, 01101, 01111, 01110, 01010, 01011, 01001, 01000

將鏡射後的格雷碼加上1：11000, 11001, 11011, 11010, 11110, 11111, 11101, 11100, 10100, 10101, 10111, 10110, 10010, 10011, 10001, 10000

最終產生的5位元格雷碼：00000, 00001, 00011, 00010, 00110, 00111, 00101, 00100, 01100, 01101, 01111, 01110, 01010, 01011, 01001, 01000, 11000, 11001, 11011, 11010, 11110, 11111, 11101, 11100, 10100, 10101, 10111, 10110, 10010, 10011, 10001, 10000

在這個遞迴行為中，我們使用了基底情況1位元的格雷碼，也就是G1 = (0, 1)。這也可以想成是0位元的格雷碼G0 = (Λ)（也就是空字串）所生成的結果。更進一步地，我們可以透過這個流程，看出這個標準格雷碼所給出的一些性質。下面使用Gn表示這樣生成出的n位元的格雷碼，則對於任何n\geq 0，我們有：

• Gn是數字0, 1, 2, ..., 2n-1在二進位中的某個排列，換言之，這些數字的二進位在n為元的格雷碼中都恰好出現一次。
• Gn可以看成是被鑲入在Gn+1的前半段之中的。
• 由上可看出這個編碼是穩定的，即，當某個二進位數出現在這個編碼當中之後，它都將佔據相同的位置，不論編碼的位數n變得多大。這也允許我們談論「編碼中第幾個號碼」，因為這是被良好定義的。
• 任兩個相鄰的號碼都相差恰好一個位元，即，他們的漢明距離為一。
• 最後一個號碼（必為2n-1的n位元二進位編碼）總是與第一個號碼（0的n位元二進位編碼）相差恰好一個位元。換言之，這個編碼是循環的。

二進位數轉格雷碼
（假設以二進制為0的值做為格雷碼的0）

G：格雷码 B：二进制码 n：正在计算的位

根据格雷码的定义可得：

G(n) = B(n+1) XOR B(n)

即

G(n) = B(n+1) + B(n)

自低位至高位运算即可，无需考虑进位，例略。

上述簡單且快速的方法可以從格雷碼的刻畫中看出，以將任意的2進位數值轉換為其對應的格雷碼。這裡給出一個更詳盡的解釋。要得到該數值，對於所有1 \leq k \leq n，如果第k位元是1，則將第k-1位元反轉，否則不修改第k-1位。如此製造的數值即為所求。事實上，我們可以使用異或的布林邏輯來描述，我們得到g_m = m \oplus \left\lfloor \frac{m}{2}\right\rfloor，其中，gm是數字m對應到的格雷碼。下面給出兩個範例：

當m = 13時，其4位元的二進位表示法為1101，因此，其對應的格雷碼即為1011。

當m = 8320123時，其23位元的二進位表示法為11111101111010001111011，因此，其對應的格雷碼為10000011000111001000110。

有趣的是，這個演算法的每個位元可以平行計算，因此理想上所需的時間是固定的。我們接下來證明這個方法的正確性。我們使用數學歸納法。在n=1時此方法成立。而當nk個編碼（即0 \leq m 時）是被鑲入的，並且格雷碼是穩定的，從而n=k的計算在n=k+1也成立。接下來，我們僅須證明用此方法計算的a = g_m與b = g_{2^{k+1}-1-m}恰好相差2k即可。注意到2^{k+1}-1-m其實就是m的反轉，並且因為異或運算的性質兩輸入反轉並不影響結果，因此除了最大的位元，a, b兩者其餘位元的運算結果必相同。然而，顯然最大的位元（第k位）必為1，因此，兩者恰好相差2k，證明完畢。

下面給出一段程式碼轉換任意位數的二進位數值與其格雷碼：

在這段 python 程式碼中，函式BinaryToGray將一個二進位數字m轉換成其對應的格雷碼。該格雷碼的長度和m的二進位表示法的長度相等。def BinaryToGray(m: int):
return m ^ (m >> 1)

格雷碼轉二進位數
由于G(n) = B(n+1) + B(n)

故而B(n) = B(n+1)-G(n)

自高位至低位运算即可，无需考虑借位。

例：
格雷碼0111，為4位數，故设二进制数自第5位至第1位分别为：0 b3 b2 b1 b0。

b3= 0-0 =0

b2=b3-1=0-1=1

b1=b2-1=1-1=0

b0=b1-1=0-1=1

因此所轉換為之二進位碼為0101

下面給出一段程式碼轉換任意位數的格雷碼與其二進位數值：

這段 python 程式碼將一個格雷碼 g 轉換成其對應的二進位數 。
def GrayToBinary(g: int):
mask = g
while(mask):
mask >>= 1
g ^= mask
return g

超立方體圖與格雷碼
一個n維超立方體圖(Hypercube graph)是指由點集\{0, 1\}^n構成的圖Qn，其中的邊集為數對漢明距離為一的點對。顯然的，一個n為元的格雷碼與一個n維超立方體圖上的一個哈密爾頓循環（或路徑）之間有一一對應。因此，我們可以轉為研究超立方體圖。

這邊利用超立方體圖給出一個證明格雷碼存在的證明：

使用數學歸納法。注意到n=2時圖為循環圖，因此必有哈密爾頓循環。假設n=k時圖Qn有哈密爾頓循環，則當n=k+1時，因為圖Qn為圖Qk與圖K2的笛卡爾乘積，因此其也有哈密爾頓循環，證明完畢。

格雷等距同構
注意到格雷碼誘導了一個在兩個賦距空間上的等距同構，分別是有限體\mathbb{Z}_2^{2m}（其上的距離由漢明距離給出）以及有限環\mathbb{Z}_4^m（其上的距離由李距離給出）。

舉例而言，考慮m=1，我們有同構0\mapsto 00, 1 \mapsto 01, 2\mapsto 11, 3\mapsto 10。

其他種類的格雷碼
在實際使用時，格雷碼幾乎都是指二進位的鏡射排列格雷碼（BRGC），然而，數學家們也發現了其他不同種類的格雷碼。如同鏡射排列格雷碼一樣，他們兩兩相鄰的編碼漢明距離都恰好是一。

長度不足2n的n位元格雷碼
事實上我們可以構造出n位元但長度不足2的n次方的格雷碼，前提是長度必須是偶數。比如，從一個平衡格雷碼開始，移出一對頭尾或中間的值，以獲得想要的格雷碼。

n進位格雷碼
除了採用二進位的格雷碼，我們也可以考慮使用n進位的格雷碼，也稱非布林格雷碼。恰如其名，它允許使用除了0和1以外的數字做為運算。

舉例而言，3進位的格雷碼使用了0、1、2三種數字。更廣義的來說，一個(n, k)格雷碼使用n進位以及k個位元來建立編碼。比如(3, 2)格雷碼有一個例子是：00, 01, 02, 12, 11, 10, 20, 21, 22。

這樣的格雷碼也能夠使用遞迴構造出來。這裡提供一個遞迴構造(n, k)格雷碼的程式碼範例：

程式中的n與k分別為格雷碼使用的底數與位數，x為輸入待轉換的數值。
def toGray(n: int, k:int , x:int):
temp = []
for i in range(k):
ans.append(0)
temp.append(x%n)
x /= n
shift = 0
for i in range(k-1, -1, -1)
ans[i] = (temp[i] + shift) % n
shift += n - ans[i]
return ans
這裡完整地將所有0~26的3進位格雷碼都列出來：

000, 001, 002, 012, 011, 010, 020, 021, 022, 122, 121, 120, 110, 111, 112, 102, 101, 100, 200, 201, 202, 212, 211, 210, 220, 221, 222

平衡格雷碼
平衡格雷碼相較鏡射格雷碼，將各個位元位置在整個格雷碼編碼週期的變化次數平衡，將之間的差異降到最小。若一個格雷碼是「均勻的」，則所有位元位置的變化次數相等。在n為2的冪次時，共有n=2^k個編碼，2^k個位元改變（因為每次編碼增加，會有一個位元位置發生改變），則必然可以分配在k個位元，每個位元在一個周期裡發生\frac{2^k}{k}次改變。其應用可以參考格雷码#以最小努力在狀態之間移動

長游程格雷碼
長游程格雷碼最大化最小「相鄰兩次同一個位元位置被更改」距離。比如n位元的鏡射格雷碼的最後兩個位元在整個週期中更新了兩次，距離皆為2^{n-1}。我們想要最大化最小的這個數字。

盒中蛇編碼
在n維超立方體圖中的誘導路徑會形成格雷碼，稱作盒中蛇編碼（snake-in-the-box codes）因為稱立方體的每條邊皆平行於座標軸，因此沿著其邊移動，每次只會有一個座標分量被改變。

若為超立方體圖中的誘導循環，則稱為盒中線圈（coil-in-the-box）。

給定一個超立方體的維度，可以容納的最大的格雷碼編碼數量成為多個研究的內容。

單調格雷碼
單調編碼在互聯網結構中特別有用，尤其是在最小化處理器的線性陣列的擴張的時候。我們不妨定義一個二進位字串的權重為其含有的一的個數。那麼，顯然格雷碼是不可能擁有嚴格遞增的權重的。然而，我們可以透過放寬要求來逼近這個要求。以白話文解釋而言，我們轉而要求在使用權重w的邊之後，就不能再使用權種小於w-1的邊了。

下面我們具體的來描述單調格雷碼。考慮一個n維超立方體圖Q_n = (V_n, E_n)，我們可以將其依照權種大小來分割成n+1個點集，也就是說，對於0 \leq i \leq n我們可以定義

V_n(i) = \{v \in V_n \mid v\text{ has weight} i\}

那麼我們就有\left|V_n(i)\right| = \binom{n}{i}。令Q_n(i)為被V_n(i) \cup V_n(i+1)所誘導的子圖，以及令E_n(i)為Q_n(i)之中的邊，那麼我們定義一個單調格雷碼為在Q_n中的一個哈密爾頓路徑，使得其滿足對於所有\delta_1 \in E_n(i), \delta_2 \in E_n(j)，其中在該路徑中\delta_1比\delta_2先出現，都有i\leq j。

我們考察一個優雅的構造單調n位元格雷碼的方法。定義

P_{1, 0} = (0, 1)

P_{m, j} = \emptyset\ \forall j

P_{n+1, j} = 1P^{\pi_n}_{n, j-1}, 0P_{n, j}\forall 0\leq j

其中\pi_n是某一個S_n中的排列，而P^\pi為P的座標被\pi作用的結果。從這裡我們有

G_n^{(1)} := P_{n, 0}P_{m, 1}^RP_{n, 2}P_{n, 3}^R\dots, \quad G_{n}^{(2)} = P_{n, 0}^RP_{n, 1}P_{n, 2}^RP_{n, 3}\dots

其中P^R表示其逆路徑。

單軌格雷碼
此編碼方式使用一個共用的長編碼，各個位元的數值為取共用編碼的某個位置的值，以下是以5個位元表達30個格雷碼數值的例子。

track = "111111001111011100000110000000"
for i in range(30):
a = [
track[(0 + i) % 30],
track[(6 + i) % 30],
track[(12 + i) % 30],
track[(18 + i) % 30],
track[(24 + i) % 30],
]
print(a)

由於此類型的格雷碼主要用在旋轉編碼器上，且對該編碼器結構有了解後比較容易理解，因此更多解釋和應用請參考格雷碼#單軌格雷碼編碼器。

應用
和格雷碼有相同數學模式的玩具
中國的古老益智玩具九連環有著和格雷碼完全相同的數學模式，美國一款名為Spinout的玩具也運用了与之相同的數學模式。

電報編碼
法國工程師Émile Baudot於1875

引用