格雷碼
格雷碼(循環二進制單位距離碼)是任意兩個相鄰數的代碼只有一位二進制數不同的編碼,它與奇偶校驗碼同屬可靠性編碼。
簡介
[編輯]格雷碼(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的玩具也是運用相同的數學模式。
參考來源
[編輯]文獻
[編輯]- 柯利弗德·皮寇弗; 陳以禮(翻譯). 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 (中文(繁體)).