目錄
1. 概要
1.1 格雷碼的定義[1]
1.2 格雷碼的特點[1]
2. 二進制格雷碼生成方法
2.1 鏡像法
2.2 異或轉換[1]
2.3 奇偶項
2.4 低位優先更新法
2.6 驗證
3. 後記
2021-10-06
1. 概要
本文介紹幾種常用的二進制格雷碼生成方法及并給出幾種python實作代碼。
進一步，将二進制格雷碼的基本定義擴充到任意M進制的格雷碼，并給出任意M進制的格雷碼的一種編碼算法及其python代碼實作。
1.1 格雷碼的定義[1]
典型的二進制格雷碼（Binary Gray Code）簡稱格雷碼，因1953年公開的弗蘭克·格雷（Frank Gray，18870913-19690523）專利“Pulse Code Communication”而得名，當初是為了通信，現在則常用于模拟－數字轉換和位置－數字轉換中。法國電訊工程師波特（Jean-Maurice-Émile Baudot，18450911-19030328）在1880年曾用過的波特碼相當于它的一種變形。1941年George Stibitz設計的一種8元二進制機械計數器正好符合格雷碼計數器的計數規律。
我們通常所說的格雷碼一般是指二進制格雷碼，其（通俗非嚴謹）定義為：在一個固定長度的二進制編碼中，若任意兩個相鄰的代碼（包括首尾，即最大值與最小值之間）隻有一位二進制數不同，則稱這種編碼為格雷碼（Gray Code）。由于最大數與最小數之間也僅一位數不同，即“首尾相連”，是以又稱循環碼或反射碼（reflected binary code (RBC)）。
在數字系統中，計數器的設計要求數位按一定順序變化。例如，4比特二進制數按自然數遞增計數，若采用8421碼，則數0111變到1000時四位均要變化，而在實際電路中，4位的變化不可能絕對同時發生，則計數中可能出現短暫的其它代碼（1100、1111等）。在特定情況下可能導緻電路狀态錯誤或輸入錯誤。使用格雷碼可以避免這種錯誤。
格雷碼在很多場合都有應用，比如通信系統中的編碼，比如數字設計中的狀态機的編碼，比如數字系統中異步FIFO設計中的計數器的編碼,機電開關系統中格雷碼被用來防止産生錯誤的輸出等等。
1.2 格雷碼的特點[1]
- 格雷碼屬于可靠性編碼，是一種錯誤最小化的編碼方式。因為，雖然自然二進制碼可以直接由數/模轉換器轉換成模拟信号，但在某些情況，例如從十進制的3轉換為4時二進制碼的每一位都要變，能使數字電路産生很大的尖峰電流脈沖。而格雷碼則沒有這一缺點，它在相鄰位間轉換時，隻有一位産生變化。它大大地減少了由一個狀态到下一個狀态時邏輯的混淆。由于這種編碼相鄰的兩個碼組之間隻有一位不同，因而在用于方向的轉角位移量－數字量的轉換中，當方向的轉角位移量發生微小變化（而可能引起數字量發生變化時，格雷碼僅改變一位，這樣與其它編碼同時改變兩位或多位的情況相比更為可靠，即可減少出錯的可能性。
- 格雷碼是一種絕對編碼方式，典型格雷碼是一種具有反射特性和循環特性的單步自補碼，它的循環、單步特性消除了随機取數時出現重大誤差的可能，它的反射、自補特性使得求反非常友善。
- 由于格雷碼是一種變權碼，每一位碼沒有固定的大小，很難直接進行比較大小和算術運算，也不能直接轉換成十進制數，要經過一次碼變換，變成自然二進制碼，再由上位機讀取。 [3]
- 典型格雷碼是一種采用絕對編碼方式的準權碼，其權的絕對值為2^i-1(設最低位i=1)。
- 格雷碼的十進制數奇偶性與其碼字中1的個數的奇偶性相同。
2. 二進制格雷碼生成方法
2.1 鏡像法
如上圖所示，(n+1)比特格雷碼可以基于n比特格雷碼進行構造，方法如下：
- 将n比特格雷碼沿縱向翻轉得到它的“鏡像”
- 上半部分（即原n比特格雷碼）左邊添加一個0，下半部分（即鏡像部分）左邊添加一個1
實作代碼如下：
def bin_gray1_2(N: int):
#print('bin_gray1_2...')
grayList = []
grayList.append('0')
grayList.append('1')
# print(grayList)
for k in range(2,N+1):
for m in range(2**(k-1),2**k):
grayList.append('1' + grayList[2**k - m - 1])
for m in range(2**(k-1)):
grayList[m] = '0' + grayList[m]
return grayList
2.2 異或轉換[1]
二進制碼→格雷碼（編碼）：
此方法從對應的n位二進制碼字中直接得到n位格雷碼碼字，步驟如下：
- 對n位二進制的碼字，從右(LSB)到左(MSB)，以0(LSB)到n-1(MSB)編号
- 如果二進制碼字的第i位和i+1位相同，則對應的格雷碼的第i位為0，否則為1（當i+1=n時，二進制碼字的第n位被預設認為是0—可以視為為計算友善的權宜，是以第n-1位不變）
公式表示（G：格雷碼，B：二進制碼）：
如下圖所示為4比特2進制的格雷碼編碼過程示意圖([1])。
實作代碼如下：
def bin_gray2(N: int):
grayList = []
for i in range(2**N):
i_gray = i ^ (i>>1)
grayList.append(i_gray)
return grayList
格雷碼→二進制碼（解碼）：
從左邊第二位起，将每位與左邊一位解碼後的值異或，作為該位解碼後的值（最左邊一位依然不變）。依次異或，直到最低位。依次異或轉換後的值（二進制數）就是格雷碼轉換後二進制碼的值。
公式表示：（G：格雷碼，B：二進制碼）：
實作代碼待補充。
2.3 奇偶項
從0對應N比特的全零格雷碼開始：
- 當k為奇數時，在前一個偶數的格雷碼的基礎上翻轉最右邊位元（LSB）即得k的格雷碼編碼
- 當k為偶數時，在前一個偶數的格雷碼的基礎上，搜尋它從右到左的第一個為1的位元，然後翻轉該位元的左邊的位元k的格雷碼編碼
實作代碼如下：
def bin_gray3(N: int):
grayList = []
grayList.append(0)
prev = 0
for k in range(1,2**N):
if k%2 == 1: # odd number
grayList.append(prev^1)
prev = prev^1
else: # even number
pstr = bin(prev)[2:]
# print(pstr)
i = len(pstr)-1
while i>=0:
# print(i)
if pstr[i] == '1':
break
else:
i -= 1
cur = prev ^ (1<<(len(pstr)-i))
grayList.append(cur)
prev = cur
return grayList
2.4 低位優先更新法
自己杜撰的方法和名詞，不知道有無雷同^-^
由于格雷碼的定義要求每兩個相鄰數字的格雷碼最多隻能有一個比特不同，是以以下基于深度優先搜尋（DFS）的思路來給出二進制格雷碼編碼方法。
假定0~(k-1)的n比特格雷碼已經生成好，接下來考慮k的格雷碼的生成：以(k-1)的格雷碼為基礎，嘗試從最右邊碼元（LSB）開始尋找第一個滿足條件的可以翻轉的比特。算法流程如下：
實作代碼如下：
def bin_gray4(N: int):
grayList = []
grayList.append(0)
prevGray = 0
for k in range(1,2**N):
cnt = 0
while 1:
curGray = prevGray ^ (1<<cnt)
if curGray not in grayList:
grayList.append(curGray)
prevGray = curGray
break
else:
cnt += 1
return grayList
這個算法因為是從最根本的角度來考慮的，是以它具有普适性，即可以适用于任意M進制的格雷碼生成。而上面幾種生成方法都是隻能适用于二進制格雷碼的生成方法。當然從實際生成結果來看，可以看出以上幾種特定的二進制格雷碼的生成方法與本算法的生成結果是一緻的。從這個算法出發修改搜尋政策的話，可以很容易的地生成其它形式的二進制格雷碼編碼。
2.6 驗證
以下以4比特二進制格雷碼為例運作以上各函數看看生成結果：
# -*- coding: utf-8 -*-
"""
Created on Fri Oct 1 08:11:24 2021
@author: chenxy
"""
import sys
import time
import datetime
import math
# import random
from typing import List
# from queue import Queue
from collections import deque
import itertools as it
import numpy as np
# Each function's definition
if __name__ == '__main__':
print('bin_gray1_2...')
grayList = bin_gray1_2(N)
print(grayList, '\n')
grayList = bin_gray2(N)
print('bin_gray2...')
print([format(grayList[k],'#06b')[2:] for k in range(len(grayList))])
print('\n')
grayList = bin_gray3(4)
print('bin_gray3...')
print([format(grayList[k],'#06b')[2:] for k in range(len(grayList))])
print('\n')
grayList = bin_gray4(4)
print('bin_gray4...')
print([format(grayList[k],'#06b')[2:] for k in range(len(grayList))])
print('\n')
運作結果：
3. 後記
本篇中給出了4種二進制格雷碼的生成方式，但是實際上，前三種都是利用了二進制格雷碼的已知碼結構特征的特殊的生成方法。這些生成方法沒有通用性，因為它們是屬于事後諸葛亮式，是先設計出了格雷碼，然後再根據碼的結構特征寫出各種技巧性的代碼。而且它們也僅僅代表了很多種可能的二進制格雷碼中的特殊的一種（當然也是最常用的一種）而已。
隻有最後一種方法是從基本定義（the first principle）出發的生成方法，是具有通用性的。而且，即便是二進制的格雷碼，也有很多種設計方式，以上各種生成方法隻代表了其中一個特定的方法（當然也是最常用的一種）。
下一篇我們将格雷碼推廣到任意M進制，并給出任意M進制的格雷碼的生成方式。任意M進制格雷碼可能因為缺乏（最常用的）二進制格雷碼那種明顯的結構特征，是以二進制格雷碼的特定的生成方法就無法适用。但是從基本定義（the first principle）出發的生成方法則是可以通用的。參見下一篇：從二進制格雷碼到任意進制格雷碼(2)https://blog.csdn.net/chenxy_bwave/article/details/120622134
https://blog.csdn.net/chenxy_bwave/article/details/120622134
2021-10-06
Hann Yang在評論區提供了一個很簡潔緊湊的二進制的自然碼與格雷碼互相轉換的程式，列舉如下供大家參考：
# Hann Yang
def N2G(n,m=1):
return bin(n^n>>1)[2:].rjust(m,'0')
def G2N(G):
for i in range(2**len(G)):
if G==bin(i^i>>1)[2:]:break
return i
[1] https://baike.baidu.com/item/格雷碼/6510858
[2] Gray code - Wikipedia