格雷碼

典型的二進制格雷碼（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、葛萊碼、葛蘭碼、格萊碼、戈萊碼、循環碼、二進制反射碼、最小差錯碼等名字，它們有的是錯誤的，有的易與其它名稱混淆，建議不再使用它們。

基本介紹

• 中文名：格雷碼
• 外文名：Binary Gray Code
• 全稱：二進制格雷碼
• 提出者：弗蘭克·格雷
• 提出時間：1940年

概述

在一組數的編碼中，若任意兩個相鄰的代碼只有一位二進制數不同，則稱這種編碼為格雷碼（Gray Code），另外由於最大數與最小數之間也僅一位數不同，即“首尾相連”，因此又稱循環碼或反射碼。在數字系統中，常要求代碼按一定順序變化。例如，按自然數遞增計數，若採用8421碼，則數0111變到1000時四位均要變化，而在實際電路中，4位的變化不可能絕對同時發生，則計數中可能出現短暫的其它代碼（1100、1111等）。在特定情況下可能導致電路狀態錯誤或輸入錯誤。使用格雷碼可以避免這種錯誤。格雷碼有多種編碼形式。

格雷碼（Gray Code）曾用過Grey Code、葛萊碼、格萊碼、戈萊碼、循環碼、反射二進制碼、最小差錯碼等名字，它們有的不對，有的易與其它名稱混淆，建議不要再使用這些曾用名。

碼錶

格雷碼有多種編碼形式

十進制數	4位自然二進制碼	4位典型格雷碼	十進制餘三格雷碼	十進制空六格雷碼	十進制跳六格雷碼	步進碼
0	0000	0000	0010	0000	0000	00000
1	0001	0001	0110	0001	0001	00001
2	0010	0011	0111	0011	0011	00011
3	0011	0010	0101	0010	0010	00111
4	0100	0110	0100	0110	0110	01111
5	0101	0111	1100	1110	0111	11111
6	0110	0101	1101	1010	0101	11110
7	0111	0100	1111	1011	0100	11100
8	1000	1100	1110	1001	1100	11000
9	1001	1101	1010	1000	1000	10000
10	1010	1111	----	----	----	----
11	1011	1110	----	----	----	----
12	1100	1010	----	----	----	----
13	1101	1011	----	----	----	----
14	1110	1001	----	----	----	----
15	1111	1000	----	----	----	----

表中典型格雷碼具有代表性。若不作特別說明，格雷碼就是指典型格雷碼，它可從自然二進制碼轉換而來。

特點

• 格雷碼屬於可靠性編碼，是一種錯誤最小化的編碼方式。因為，雖然自然二進制碼可以直接由數/模轉換器轉換成模擬信號，但在某些情況，例如從十進制的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. 1位格雷碼有兩個碼字
2. (n+1)位格雷碼中的前2ⁿ個碼字等於n位格雷碼的碼字，按順序書寫，加前綴0
3. (n+1)位格雷碼中的後2ⁿ個碼字等於n位格雷碼的碼字，按逆序書寫，加前綴1
4. n+1位格雷碼的集合 = n位格雷碼集合(順序)加前綴0 + n位格雷碼集合(逆序)加前綴1

2位格雷碼	3位格雷碼	4位格雷碼	4位自然二進制碼
00	000	0000	0000
01	001	0001	0001
11	011	0011	0010
10	010	0010	0011
	110	0110	0100
	111	0111	0101
	101	0101	0110
	100	0100	0111
		1100	1000
		1101	1001
		1111	1010
		1110	1011
		1010	1100
		1011	1101
		1001	1110
		1000	1111

異或轉換

二進制碼→格雷碼（編碼）：

此方法從對應的n位二進制碼字中直接得到n位格雷碼碼字，步驟如下：

1. 對n位二進制的碼字，從右到左，以0到n-1編號
2. 如果二進制碼字的第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]，

解碼：

利用卡諾圖

利用卡諾圖相鄰兩格只有一位變化以及卡諾圖的變數取值以低階格雷碼的順序排布的特徵，可以遞歸得到高階格雷碼。由於此方法相對繁瑣，使用較少。生成格雷碼的步驟如下：

1. 將卡諾圖變數分為兩組，變數數目相近（最好相等）
2. 以邏輯變數高位在左低位在右建立卡諾圖
3. 從卡諾圖的左上角以之字形到右上角最後到左下角遍歷卡諾圖，依次經過格子的變數取值即為典型格雷碼的順序

三位格雷碼（三位格雷碼由建立在二位基礎上）

AB╲ C	0	1
00	0→	1↓
01	↓2	←3
11	6→	7↓
10	4	←5

格雷碼次序：000起點→001→011→010→110→111→101→100終點

四位格雷碼

AB╲CD	00	01	11	10
00	0→	1→	3→	2↓
01	↓4	←5	←7	←6
11	12→	13→	15→	14↓
10	8	←9	←11	←10

格雷碼次序：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實現，運行結果如右圖所示：

#include<stdio.h>voidmain(){    intm,n,i,j,b,p,bound;    intgr[14];//輸入n,m並判斷m是否合法    bound=1;    printf("Pleaseinputtwonumber:n,m\n");    scanf("%d,%d",&n,&m);    for(i=1;i<=n;i++)        bound*=2;    if(m<0||m>=bound)    {        printf("Dataerror!");        exit(0);    }    b=1;    for(i=0;i<n;i++)    {        p=0;        b*=2;        for(j=0;j<=m;j++)        {            if(j%b-b/2==0)                p=1-p;        }        gr[i]=p;    }    printf("m=");    for(i=n-1;i>=0;i--)    {        printf("%d",gr[i]);    }    printf("\n");}

格雷碼解碼的Pascal 程式：

var    x,y,i:longint;begin    readln(x);    fori:=30downto0do    begin        y:=(xand(1shli))xor((xand(1shl(i+1)))shr1);        x:=xandnot(1shli)ory;    end;    writeln(x);end.2var    x,i,n:longint;begin    readln(n);    x:=n;    fori:=1to31do    begin        x:=xshr1;        n:=nxorx;    end;    writeln(n);end.