格雷码

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

簡介

格雷碼（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個位元的格雷碼。

4位元的格雷碼排列

鏡射排列

二進位格雷碼鏡射建構法

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位元的格雷碼，也就是G₁ = (0, 1)。這也可以想成是0位元的格雷碼G₀ = (Λ)（也就是空字串）所生成的結果。更進一步地，我們可以透過這個流程，看出這個標準格雷碼所給出的一些性質。下面使用G_n表示這樣生成出的n位元的格雷碼，則對於任何$n\geq 0$，我們有：

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

3位元格雷码 000 001 011 010 110 111 101 100

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

4位元2进制原始码 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

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

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

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

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

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

在這段 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

四維超立方體圖與4位元格雷碼

超立方體圖與格雷碼

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

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

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

格雷等距同構

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

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

其他種類的格雷碼

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

長度不足2ⁿ的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<0\lor j\geq n$

$P_{n+1,j}=1P_{n,j-1}^{\pi _{n}},0P_{n,j}\forall 0\leq j<n$

其中$\pi _{n}$是某一個$S_{n}$中的排列，而$P^{\pi }$為$P$的座標被$\pi$作用的結果。從這裡我們有

$G_{n}^{(1)}:=P_{n,0}P_{m,1}^{R}P_{n,2}P_{n,3}^{R}\dots ,\quad G_{n}^{(2)}=P_{n,0}^{R}P_{n,1}P_{n,2}^{R}P_{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或1876年改進了他的印字电报机的編碼，將6位編碼改為5位編碼，使用鏡射建構法的格雷碼，被稱為博多碼。波特率的名稱Baud也是從他而來。

其中，所有母音以字母順序放在鏡射格雷碼中第四和第五位元為零的區域，剩下的子音也以字母順序放在剩下的區域。這個編碼方式是設計給五個鋼琴鍵的鍵盤使用的，左手輸入第四和第五位元，右手則是剩下的三個位元。博多碼於1932年被用作國際電報電碼表第一號 (International Telegraph Alphabet No.1, ITA1)。

類比數位轉換器

法蘭克·格雷發明了一個使用真空管將類比訊號轉換為鏡射建構法二進位碼的方式，於1953年取得專利。此編碼因而被稱為「格雷」。

格雷構想的脈衝編碼調變真空管被貝爾實驗室的Raymond W. Sears製作出來。

格雷的專利封面部分內容，圖中15號為以鏡射格雷碼的編碼片

格雷使用的這種編碼方式能最小化類比轉數位產生的錯誤。直到今日，他的編碼仍然被廣泛用在這種應用。

位置編碼器

用於偵測旋轉角度的絕對型旋轉編碼器，使用3位元的鏡射式格雷碼

使用13位元格雷碼的光學旋轉編碼器，頂蓋（上）包含著光源和光柵，基板（下）灰色部分為光線感測器

格雷碼被廣泛用在線性和旋轉編碼器。若要將類比的位置資訊轉換為數位訊號，一個簡單的作法是將輸出的每個位元各作為一個軌道，每個軌道有不同的圖樣，表示該位元在對應的位置為0或1。

最直接的做法是將二進制數字依序排列一周，每個位元為一個軌道，分別讀取每個軌道在對應位置的數值，就可以得到轉換為數位的位置資訊。然而，在進位的時候我們將會遇到問題。位置3 (011)和位置4 (100)之間看似沒有其他數值了，但實際上，我們無法讓所有位元變化發生在同一個時間。假如第一個位元先變為1了，則我們會在兩數之間短暫讀到7 (111)；又或者假如第二個位元先變為0，則我們會短暫讀到1 (001)。

這會使得編碼器讀取到的位置不連續且難以預估，也讓讀取到的位置和實際位置相差巨大，或在距離很遠的位置之間跳動。只要一個位元的變化和其他不完全同步，就可以造成顯著的數值偏差。對於絕對型編碼器，這會造成位置測量錯誤，而對於增量型編碼器，這會破壞位置追蹤。

格雷碼相鄰的兩個編碼只相差一個位元，因此位置之間的轉換僅有一個位元有變化，完全解決了兩個位置之間轉換過程的問題。反觀二進制編碼在進位時會有多個位元產生變化，基本上無可避免讀取到錯誤的數值，而這個錯誤可以高達全部行程的一半。

單軌格雷碼編碼器

單軌格雷碼編碼器

另外一種格雷碼是「單軌格雷碼」（Single-track Gray code, STGC），由Norman B. Spedding提出，由Hiltgen, Paterson和Brandestini在Single-track Gray Codes (1996).中被精煉。

用作旋轉編碼器時，編碼條只需要一個軌道，且各位元的感測器可以分開放置在一周，可以做得比多軌的編碼器小。比如前述的13位元光學旋轉編碼器將光線偵測器排列在一起，可以想見若製造工藝較差，無法把感測器擺放得很靠近而不互相干擾，則編碼盤直徑就必須增加，來容納全部的軌道。若將光線感測器錯開，排列到圓形的一周，並相對應的改變編碼盤，則可能可以把整體裝置做得更小，或減少製造精度要求。

有很多年，數學家們認為沒有辦法透過調整編碼，將編碼盤縮減到一軌並透過不同擺放位置的偵測器，讓所有偵測器共用一個編碼盤，實現格雷碼旋轉編碼器。因此若需要高解析度的編碼器，常見的做法是改用增量型編碼器，即可在低至兩個位元（兩個位元的編碼器又稱作正交編碼器，Quadrature encoder）辨別角度改變。缺點是若轉速過快，無法正確讀取或記錄到每一個位元的改變，則位置資料將會永久錯誤，直到重新校正回零。

然而Etzion和Paterson推論沒有辦法用$n$個偵測器，用一個共用的軌道區分$2^{n}$個位置，但可以做到接近。若$n$是2的冪，則可以區分$2^{n}-2n$個位置；若$n$是質數，則可以區分$2^{n}-2$個位置。

9位元格雷碼編碼、1度解析度的單軌編碼器

5個位元可以區分30個位置，而Gary Williams於2008年找到9位元、1度解析度（360個位置）的解法。

布林代數精簡化

卡诺图範例。

卡诺图 (Karnaugh map) 被用作一個精簡化布林代數的方式，由莫里斯·卡诺於1953年發明。其軸以格雷碼標記，方便以圖形的方式視覺地找出可以消去的變數，比如圖中藍色區塊，在C=0, D=0下，AB變數以格雷碼順序排列時，產生了相鄰的1。若可以圈出大小為$2^{n}$的方格皆為1，則$n$個變數就可以被削去。比如原本藍色區塊內的方格為A'BC'D' + ABC'D'，因為AB軸以格雷碼標記，相鄰的兩格只相差一個位置，藍色區塊對應到的是A變化，因此可以化簡為BC'D'。

以最小努力在狀態之間移動

若一個系統會需要依序地在一些二元控制項的所有狀態中循環，且改變一個控制項會花費非零的努力（金錢、時間、壽命、勞力等等），則格雷碼可以最小化改變控制項的花費，低到切換狀態都只需改變一個控制項。測試管路系統的所有閥門開關排列組合就是一個例子，切換位於管路不同位置的閥門需要時間、勞力，甚至閥門壽命，因此最小化改變閥門狀態的次數是理想的。

平衡格雷碼相較鏡射格雷碼，每個位元位置的變化次數都盡可能相同。在一個完整的4位元格雷碼編碼中（4個位元就是16種組合，因此也共會有16個位元改變），平衡格雷碼將把16個位元變化分配到四個位元，也就是每個控制項需要開關兩次。

由於開關有使用壽命，使用機械開關的格雷碼編碼器可以使用平衡格雷碼讓各個位元的開關損耗更均勻，延長壽命。

格雷碼定址

若將記憶體或匯流排的定址編碼使用格雷碼編排，則在序列讀取時（比如依序讀取記憶體內容）可以減少定址電晶體開關次數，從而減少電路功率和發熱。

格雷碼計數器和算數

在兩個時脈不同步的系統之間以序列的方式傳遞計數器數值，格雷碼是理想的編碼方式。因為相鄰兩個計數只相差一個位元，儘管計數器在以序列方式傳遞過程中被更改了，也不會產生錯誤的數值。只要整個傳遞過程中計數器最多改變1，則接收到的數值只有可能是改變前的或改變後的數值。

又或者計數器是以並列的方式傳輸，但每條線路可能有不同的傳播延遲，儘管時脈不同步，或者傳播延遲過大導致部分線路的數值無法在取樣時間內抵達，收到的數值也只可能是改變前或改變後的數值。

前者利用格雷碼相鄰的編碼只相差一個位置，因此若將兩相鄰數字各取前後綴後相接，則結果必然會是兩數其中之一。後者利用格雷碼相鄰的編碼只相差一位，無論各個位元有沒有及時接收，也只會有一個位元位置是有影響的，其他的位置都沒有變化，因此是否收到更新後的數值只跟該位元是否有及時接收到有關，且不會產生其他數值。

無論如何，這都解決了使用一般二進制編碼，若沒有正確得接收到每一個位元的更新值，則數值將完全錯亂的問題。使用格雷碼最多只會錯誤地接收到舊的值，這在某些應用中是可以接受的。

參考來源

文献

• 柯利弗德·皮寇弗; 陳以禮（翻譯）. The Math Book:From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics [數學之書]. 時報文化. 2013-04-16. ISBN 978-957-135-699-0 （中文（繁體））. 

{{reflist|refs=