格雷碼
| 格雷碼 |
|
中文名: 格雷碼 外文名: Binary Gray Code 全 稱: 二進制格雷碼 提出者: 弗蘭克·格雷 提出時間: 1940年 |
典型的二進制格雷碼（Binary Gray Code）簡稱格雷碼，因1953年公開的弗蘭克·格雷（Frank Gray，18870913-19690523）專利「Pulse Code Communication」而得名，當初是為了通信，現在則常用於模擬－數字轉換和位置－數字轉換中。法國電訊工程師波特（Jean-Maurice-Émile Baudot，18450911-19030328）在1880年曾用過的波特碼相當於它的一種變形。1941年George Stibitz設計的一種8元二進制機械計數器正好符合格雷碼計數器的計數規律。 格雷碼（Gray code）曾用過Grey Code、葛萊碼、葛蘭碼、格萊碼、戈萊碼、循環碼、二進制反射碼、最小差錯碼等名字，它們有的是錯誤的，有的易與其它名稱混淆，建議不再使用它們。[1]
目錄
概述
在一組數的編碼中，若任意兩個相鄰的代碼只有一位二進制數不同，則稱這種編碼為格雷碼（Gray Code），另外由於最大數與最小數之間也僅一位數不同，即「首尾相連」，因此又稱循環碼或反射碼。 在數字系統中，常要求代碼按一定順序變化。例如，按自然數遞增計數，若採用8421碼，則數0111變到1000時四位均要變化，而在實際電路中，4位的變化不可能絕對同時發生，則計數中可能出現短暫的其它代碼（1100、1111等）。在特定情況下可能導致電路狀態錯誤或輸入錯誤。使用格雷碼可以避免這種錯誤。格雷碼有多種編碼形式。 格雷碼（Gray Code）曾用過Grey Code、葛萊碼、格萊碼、戈萊碼、循環碼、反射二進制碼、最小差錯碼等名字，它們有的不對，有的易與其它名稱混淆，建議不要再使用這些曾用名。
碼錶
格雷碼有多種編碼形式 表中典型格雷碼具有代表性。若不作特別說明，格雷碼就是指典型格雷碼，它可從自然二進制碼轉換而來。
特點
格雷碼屬於可靠性編碼，是一種錯誤最小化的編碼方式。因為，雖然自然二進制碼可以直接由數/模轉換器轉換成模擬信號，但在某些情況，例如從十進制的3轉換為4時二進制碼的每一位都要變，能使數字電路產生很大的尖峰電流脈衝。而格雷碼則沒有這一缺點，它在相鄰位間轉換時，只有一位產生變化。它大大地減少了由一個狀態到下一個狀態時邏輯的混淆。由於這種編碼相鄰的兩個碼組之間只有一位不同，因而在用於方向的轉角位移量－數字量的轉換中，當方向的轉角位移量發生微小變化（而可能引起數字量發生變化時，格雷碼僅改變一位，這樣與其它編碼同時改變兩位或多位的情況相比更為可靠，即可減少出錯的可能性。 格雷碼是一種絕對編碼方式，典型格雷碼是一種具有反射特性和循環特性的單步自補碼，它的循環、單步特性消除了隨機取數時出現重大誤差的可能，它的反射、自補特性使得求反非常方便。 由于格雷碼是一種變權碼，每一位碼沒有固定的大小，很難直接進行比較大小和算術運算，也不能直接轉換成液位信號，要經過一次碼變換，變成自然二進制碼，再由上位機讀取。 典型格雷碼是一種採用絕對編碼方式的准權碼，其權的絕對值為2^i-1(設最低位i=1)。 格雷碼的十進制數奇偶性與其碼字中1的個數的奇偶性相同。
發展歷史
法國工程師Jean-Maurice-Émlle Baudot在1880年曾用過的波特碼是典型格雷碼的一種變形。 Gray Code是由貝爾實驗室的Frank Gray在1940年代提出的，用來在使用PCM（Pusle Code Modulation）方法傳送訊號時避免出錯。 Frank Gray於1947年申請、1953年獲得批准的專利「Pulse Code Communication」，當初是為了通信，後來則常用於模擬－數字轉換中。 1941年George Stibitz設計過一種8元格雷碼計數器。 這種方法基于格雷碼是反射碼的事實，利用遞歸的如下規則來構造： 1位格雷碼有兩個碼字 (n+1)位格雷碼中的前2n個碼字等於n位格雷碼的碼字，按順序書寫，加前綴0 (n+1)位格雷碼中的後2n個碼字等於n位格雷碼的碼字，按逆序書寫，加前綴1 n+1位格雷碼的集合 = n位格雷碼集合(順序)加前綴0 + n位格雷碼集合(逆序)加前綴1
異或轉換
二進制碼→格雷碼（編碼）： 此方法從對應的n位二進制碼字中直接得到n位格雷碼碼字，步驟如下： 對n位二進制的碼字，從右到左，以0到n-1編號 如果二進制碼字的第i位和i+1位相同，則對應的格雷碼的第i位為0，否則為1（當i+1=n時，二進制碼字的第n位被認為是0，即第n-1位不變）
（G：格雷码，B：二进制码）
例如：二進制碼0101，為4位數，所以其所轉為之格雷碼也必為4位數，因此可取轉成之二進位碼第五位為0，即0 b3 b2 b1 b0。 0 xor 0=0，所以g3=0 0 xor 1=1，所以g2=1 1 xor 0=1，所以g1=1 0 xor 1=1，所以g0=1 因此所轉換為之格雷碼為0111 格雷碼→二進制碼（解碼）： 從左邊第二位起，將每位與左邊一位解碼後的值異或，作為該位解碼後的值（最左邊一位依然不變）。依次異或，直到最低位。依次異或轉換後的值（二進制數）就是格雷碼轉換後二進制碼的值。 公式表示：
（G：格雷码，B：二进制码）
原碼：p[n:0]；格雷碼：c[n:0](n∈N）；編碼：c=G(p）；解碼：p=F(c）； 書寫時按從左向右標號依次減小，即MSB->LSB，編解碼也按此順序進行 ...................c[n]=p[n]， 解碼：
利用卡諾圖
利用卡諾圖相鄰兩格只有一位變化以及卡諾圖的變量取值以低階格雷碼的順序排布的特徵，可以遞歸得到高階格雷碼。由於此方法相對繁瑣，使用較少。生成格雷碼的步驟如下： 將卡諾圖變量分為兩組，變量數目相近（最好相等） 以邏輯變量高位在左低位在右建立卡諾圖 從卡諾圖的左上角以之字形到右上角最後到左下角遍歷卡諾圖，依次經過格子的變量取值即為典型格雷碼的順序 三位格雷碼（三位格雷碼由建立在二位基礎上） 格雷碼次序：000起點→001→011→010→110→111→101→100終點 四位格雷碼 格雷碼次序：0000起點→0001→0011→0010→0110→0111→0101→0100→1100→1101→ 1111→1110→1010→1011→1001→1000終點
使用異或乘除
用異或代替加減進行二進制豎式乘除，稱為異或乘除，它的特點是無進退位。 如：10101除以11將變成1100餘1。 二進制轉格雷碼： 只要異或乘以二分之三，即二進制的1.1，然後忽略小數部分；也可以理解成異或乘以三（即11），再右移一位。 格雷碼轉二進制： 異或乘以三分之二，即除以1.1，忽略餘數；或者左移一位，再異或除以三，忽略餘數。 機械工具，汽車制動系統有時需要傳感器產生的數字值來指示機械位置。如圖是編碼盤和一些觸點的概念圖，根據盤轉的位置，觸點產生一個3位二進制編碼，共有8個這樣的編碼。盤中暗的區域與對應的邏輯1的信號源相連；亮的區域沒有連接，觸點將其解釋為邏輯0。使用格雷碼對編碼盤上的亮暗區域編碼，使得其連續的碼字之間只有一個數位變化。這樣就不會因為器件製造的精確度有限，而使得觸點轉到邊界位置而出現錯誤編碼。
格雷碼
在化簡邏輯函數時，可以通過按格雷碼排列的卡諾圖來完成。
九連環問題
智力玩具九連環的狀態 變化符合格雷碼的編碼規律，漢諾塔的解法也與格雷碼有關。 九連環中的每個環都有上下兩種狀態，如果把這兩種狀態用0/1來表示的話，這個狀態序列就會形成一種循環二進制編碼（格雷碼）的序列。所以解決九連環問題所需要的狀態變化數就是格雷碼111111111所對應的十進制數341。
程序實現
根據格雷碼的特點，即：對於兩個相鄰的十進制數，對應的兩個格雷碼只有一個二進制位不同。另外，最大數與最小數間也僅有一個二進制位不同。以下給出用長度n的二進制數來表示十進制數m的格雷碼c實現，運行結果如右圖所示： 格雷碼解碼的Pascal 程序：