格雷碼

格雷碼

典型的二進位格雷碼（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簡要介紹 2編碼形式 3基本特點
4發展歷史 5轉換方法 6基本應用
7程序實現

簡要介紹

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

編碼形式

格雷碼有多種編碼形式
十進位數4位自然二進位碼4位典型格雷碼十進位餘三格雷碼十進位空六格雷碼十進位跳六格雷碼步進碼
0000000000100000000000000
10001000101100001000100001
20010001101110011001100011
30011001001010010001000111
40100011001000110011001111
50101011111001110011111111
60110010111011010010111110
70111010011111011010011100
81000110011101001110011000
91001110110101000100010000
1010101111----------------
1110111110----------------
1211001010----------------
1311011011----------------
1411101001----------------
1511111000----------------
表中典型格雷碼具有代表性。若不作特別說明，格雷碼就是指典型格雷碼，它可從自然二進位碼轉換而來。

基本特點

● 格雷碼屬於可靠性編碼，是一種錯誤最小化的編碼方式。因為，雖然自然二進位碼可以直接由數/模轉換器轉換成模擬信號，但在某些情況，例如從十進位的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
2位格雷碼3位格雷碼4位格雷碼4位自然二進位碼
00
01
11
10
000
001
011
010
110
111
101
100
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
異或轉換
二進位碼→格雷碼（編碼）：
此方法從對應的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，編解碼也按此順序進行
舉例：
如果採集器器採到了格雷碼：1010
就要將它變為自然二進位：
0 與第四位 1 進行異或結果為 1
上面結果1與第三位0異或結果為 1
上面結果1與第二位1異或結果為 0
上面結果0與第一位0異或結果為 0
因此最終結果為：1100 這就是二進位碼即十進位 12
當然人看時只需對照表1一下子就知道是12
...................c[n]=p[n]，
解碼：
利用卡諾圖
利用卡諾圖相鄰兩格只有一位變化以及卡諾圖的變數取值以低階格雷碼的順序排布的特徵，可以遞歸得到高階格雷碼。由於此方法相對繁瑣，使用較少。生成格雷碼的步驟如下：
● ● 將卡諾圖變數分為兩組，變數數目相近（最好相等）
● ● 以邏輯變數高位在左低位在右建立卡諾圖
● ● 從卡諾圖的左上角以之字形到右上角最後到左下角遍歷卡諾圖，依次經過格子的變數取值即為典型格雷碼的順序
三位格雷碼（三位格雷碼由建立在二位基礎上）
AB╲ C1
000→1↓
01↓2←3
116→7↓
104←5
格雷碼次序：000起點→001→011→010→110→111→101→100終點
四位格雷碼
AB╲CD00011110
000→1→3→2↓
01↓4←5←7←6
1112→13→15→14↓
108←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實現，運行結果如右圖所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include
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
{
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 程序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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.
2
var
x,i,n:longint;
begin
readln(n);
x:=n;
fori:=1to31do
begin
x:=xshr1;
n:=nxorx;
end;
writeln(n);
end.

基本信息

中文名
格雷碼
外文名
Binary Gray Code
別名
二進位格雷碼
提出者
提出時間
1940年