跳至內容

格雷碼

維基百科,自由的百科全書

格雷碼(循環二進制單位距離碼)是任意兩個相鄰數的代碼只有一位二進制數不同的編碼,它與奇偶校驗碼同屬可靠性編碼

簡介

格雷碼(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位元的格雷碼以上下鏡射後加上新位元的方式快速的得到,如右圖所示一般。

二進位數轉格雷碼

(假設以二進制為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

格雷碼轉二進位數

由於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

應用

  • 格雷碼與相位移在三維曲面量測:利用格雷碼投射在微型曲面做量測 一個非接觸式、投影的方法光學測量。
  • 在化簡邏輯函數時,可以通過按格雷碼排列的卡諾圖來完成。

和格雷碼有相同數學模式的玩具

中國的古老益智玩具九連環有著和格雷碼完全相同的數學模式,外國一款名為spin out的玩具也是運用相同的數學模式。

參考來源

文獻

引用