格雷碼是什麼？

反射二進位制碼或格雷碼是對二進位制數系統的一種排序，使得兩個連續的值僅在一個位元（二進位制數字）上不同。格雷碼在硬體生成的二進位制數的正常序列中非常有用，因為從一個數字到下一個數字的轉換可能會導致錯誤或歧義。因此，格雷碼可以輕鬆地消除此問題，因為在兩個數字之間的任何轉換期間，只有一個位元改變其值。

格雷碼不是加權的，這意味著它不依賴於數字的位置值。這是一種迴圈變數碼，這意味著從一個值到下一個值的每次轉換都只涉及一個位元的變化。

格雷碼也稱為反射二進位制碼，因為前 (n/2) 個值與後 (n/2) 個值相同，但順序相反。

構造一個 n 位格雷碼

n 位格雷碼可以使用反射和字首方法遞迴生成，如下所述。

  • 生成 n=1 的程式碼：0 和 1 程式碼。
  • 按順序取之前的程式碼：0 和 1。
  • 在以下列表中新增反轉的程式碼：0、1、1 和 0。
  • 現在為原始的先前程式碼新增字首 0，為新生成的程式碼新增字首 1：00、01、11 和 10。

因此，格雷碼 0 和 1 分別對應於二進位制數 0 和 1。格雷碼：00、01、11 和 10 分別對應於二進位制數：00、01、10 和 11。類似地，您可以為 3 位二進位制數構造格雷碼

因此，格雷碼如下所示：

對於 n = 1 位
對於 n = 2 位
對於 n = 3 位
二進位制
格雷碼
二進位制
格雷碼
二進位制
格雷碼
0
0
00
00
000
000
1
1
01
01
001
001
 
10
11
010
011
11
10
011
010
 
100
110
101
111
110
101
111
100

從 Gn 生成 G(n+1) 的迭代方法如下所示。這是一種更簡單的構造 n 位二進位制數的格雷碼的方法。如果輸入值的下一個較高位設定為 1，則每個位都被反轉。第 n 個格雷碼是透過計算 n⊕(floor(n/2)) 獲得的。

  • Gn 是從 0 到 (2n-1) 的排列的唯一數字。
  • Gn 嵌入到 G(n+1) 的前半部分，後半部分為 G(n+1) 的反序。
  • 在前一半的每個數字中新增字首 0，在後一半的每個數字中新增字首 1。

兩個相鄰格雷碼的漢明距離始終為 1，並且第一個格雷碼和最後一個格雷碼的漢明距離也始終為 1，因此它也稱為 迴圈碼。

您可以使用其他方法構造格雷碼，但它們可能無法像上面給出的方法那樣並行執行。例如，可以使用 K 對映構造 3 位格雷碼，如下所示

十進位制
二進位制
格雷碼
0
000
000
1
001
001
2
010
011
3
011
010
4
100
110
5
101
111
6
110
101
7
111
100

格雷碼的型別

還有其他型別的格雷碼，例如貝克特-格雷碼、單軌格雷碼等。

  • N 進位制格雷碼，其中包含非布林值，例如 1、2、3 的序列。
  • 二維 (n,k) 格雷碼用於糾錯。
  • 平衡格雷碼具有相等的轉換計數。

格雷碼的用途

格雷碼用於旋轉和光學編碼器、卡諾圖和錯誤檢測。

更新時間： 2023年11月1日

41K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告