从二进制格雷码到任意进制格雷码(1)
目錄
1. 概要
1.1 格雷碼的定義[1]
1.2 格雷碼的特點[1]
2. 二進制格雷碼生成方法
2.1 鏡像法
2.2 異或轉(zhuǎn)換[1]
2.3 奇偶項
2.4 低位優(yōu)先更新法
2.6?驗證
3. 后記
2021-10-06
1. 概要
????????本文介紹幾種常用的二進制格雷碼生成方法及并給出幾種python實現(xiàn)代碼。
????????進一步，將二進制格雷碼的基本定義擴展到任意M進制的格雷碼，并給出任意M進制的格雷碼的一種編碼算法及其python代碼實現(xiàn)。
1.1 格雷碼的定義[1]
????????典型的二進制格雷碼（Binary Gray Code）簡稱格雷碼，因1953年公開的弗蘭克·格雷（Frank Gray，18870913-19690523）專利“Pulse Code Communication”而得名，當初是為了通信，現(xiàn)在則常用于模擬－數(shù)字轉(zhuǎn)換和位置－數(shù)字轉(zhuǎn)換中。法國電訊工程師波特（Jean-Maurice-émile Baudot，18450911-19030328）在1880年曾用過的波特碼相當于它的一種變形。1941年George Stibitz設(shè)計的一種8元二進制機械計數(shù)器正好符合格雷碼計數(shù)器的計數(shù)規(guī)律。
????????我們通常所說的格雷碼一般是指二進制格雷碼，其（通俗非嚴謹）定義為：在一個固定長度的二進制編碼中，若任意兩個相鄰的代碼（包括首尾，即最大值與最小值之間）只有一位二進制數(shù)不同，則稱這種編碼為格雷碼（Gray Code）。由于最大數(shù)與最小數(shù)之間也僅一位數(shù)不同，即“首尾相連”，因此又稱循環(huán)碼或反射碼（reflected binary code?(RBC)）。
????????在數(shù)字系統(tǒng)中，計數(shù)器的設(shè)計要求數(shù)碼按一定順序變化。例如，4比特二進制數(shù)按自然數(shù)遞增計數(shù)，若采用8421碼，則數(shù)0111變到1000時四位均要變化，而在實際電路中，4位的變化不可能絕對同時發(fā)生，則計數(shù)中可能出現(xiàn)短暫的其它代碼（1100、1111等）。在特定情況下可能導(dǎo)致電路狀態(tài)錯誤或輸入錯誤。使用格雷碼可以避免這種錯誤。
????????格雷碼在很多場合都有應(yīng)用，比如通信系統(tǒng)中的編碼，比如數(shù)字設(shè)計中的狀態(tài)機的編碼，比如數(shù)字系統(tǒng)中異步FIFO設(shè)計中的計數(shù)器的編碼,機電開關(guān)系統(tǒng)中格雷碼被用來防止產(chǎn)生錯誤的輸出等等。
1.2 格雷碼的特點[1]
2. 二進制格雷碼生成方法
2.1 鏡像法
????????如上圖所示，(n+1)比特格雷碼可以基于n比特格雷碼進行構(gòu)造，方法如下：
????????實現(xiàn)代碼如下：
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 grayList2.2 異或轉(zhuǎn)換[1]
????????二進制碼→格雷碼（編碼）：
????????此方法從對應(yīng)的n位二進制碼字中直接得到n位格雷碼碼字，步驟如下：
????????公式表示（G：格雷碼，B：二進制碼）：
????????如下圖所示為4比特2進制的格雷碼編碼過程示意圖([1])。
?????????實現(xiàn)代碼如下：
def bin_gray2(N: int):grayList = []for i in range(2**N):i_gray = i ^ (i>>1)grayList.append(i_gray) return grayList?????????格雷碼→二進制碼（解碼）：
????????從左邊第二位起，將每位與左邊一位解碼后的值異或，作為該位解碼后的值（最左邊一位依然不變）。依次異或，直到最低位。依次異或轉(zhuǎn)換后的值（二進制數(shù)）就是格雷碼轉(zhuǎn)換后二進制碼的值。
????????公式表示：（G：格雷碼，B：二進制碼）：
????????實現(xiàn)代碼待補充。
??
2.3 奇偶項
????????從0對應(yīng)N比特的全零格雷碼開始：
? ? ? ? 實現(xiàn)代碼如下：
def bin_gray3(N: int):grayList = []grayList.append(0)prev = 0for k in range(1,2**N):if k%2 == 1: # odd numbergrayList.append(prev^1)prev = prev^1else: # even numberpstr = bin(prev)[2:]# print(pstr)i = len(pstr)-1while i>=0:# print(i)if pstr[i] == '1':breakelse:i -= 1cur = prev ^ (1<<(len(pstr)-i))grayList.append(cur)prev = cur return grayList2.4 低位優(yōu)先更新法
????????自己杜撰的方法和名詞，不知道有無雷同^-^
????????由于格雷碼的定義要求每兩個相鄰數(shù)字的格雷碼最多只能有一個比特不同，因此以下基于深度優(yōu)先搜索（DFS）的思路來給出二進制格雷碼編碼方法。
????????假定0~(k-1)的n比特格雷碼已經(jīng)生成好，接下來考慮k的格雷碼的生成：以(k-1)的格雷碼為基礎(chǔ)，嘗試從最右邊碼元（LSB）開始尋找第一個滿足條件的可以翻轉(zhuǎn)的比特。算法流程如下：
????????實現(xiàn)代碼如下：
def bin_gray4(N: int):grayList = []grayList.append(0)prevGray = 0for k in range(1,2**N):cnt = 0while 1:curGray = prevGray ^ (1<<cnt)if curGray not in grayList:grayList.append(curGray)prevGray = curGraybreakelse: cnt += 1return grayList????????這個算法因為是從最根本的角度來考慮的，因此它具有普適性，即可以適用于任意M進制的格雷碼生成。而上面幾種生成方法都是只能適用于二進制格雷碼的生成方法。當然從實際生成結(jié)果來看，可以看出以上幾種特定的二進制格雷碼的生成方法與本算法的生成結(jié)果是一致的。從這個算法出發(fā)修改搜索策略的話，可以很容易的地生成其它形式的二進制格雷碼編碼。
2.6?驗證
????????以下以4比特二進制格雷碼為例運行以上各函數(shù)看看生成結(jié)果：
# -*- 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 definitionif __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')?運行結(jié)果：
3. 后記
? ? ? ? 本篇中給出了4種二進制格雷碼的生成方式，但是實際上，前三種都是利用了二進制格雷碼的已知碼結(jié)構(gòu)特征的特殊的生成方法。這些生成方法沒有通用性，因為它們是屬于事后諸葛亮式，是先設(shè)計出了格雷碼，然后再根據(jù)碼的結(jié)構(gòu)特征寫出各種技巧性的代碼。而且它們也僅僅代表了很多種可能的二進制格雷碼中的特殊的一種（當然也是最常用的一種）而已。
????????只有最后一種方法是從基本定義（the first principle）出發(fā)的生成方法，是具有通用性的。而且，即便是二進制的格雷碼，也有很多種設(shè)計方式，以上各種生成方法只代表了其中一個特定的方法（當然也是最常用的一種）。??????
? ? ? ? 下一篇我們將格雷碼推廣到任意M進制，并給出任意M進制的格雷碼的生成方式。任意M進制格雷碼可能因為缺乏（最常用的）二進制格雷碼那種明顯的結(jié)構(gòu)特征，因此二進制格雷碼的特定的生成方法就無法適用。但是從基本定義（the first principle）出發(fā)的生成方法則是可以通用的。參見下一篇：從二進制格雷碼到任意進制格雷碼(2)https://blog.csdn.net/chenxy_bwave/article/details/120622134https://blog.csdn.net/chenxy_bwave/article/details/120622134
2021-10-06
?????????Hann Yang在評論區(qū)提供了一個很簡潔緊湊的二進制的自然碼與格雷碼相互轉(zhuǎn)換的程序，列舉如下供大家參考：
# 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:]:breakreturn i[1] https://baike.baidu.com/item/格雷碼/6510858
[2] Gray code - Wikipedia
總結(jié)
以上是生活随笔為你收集整理的从二进制格雷码到任意进制格雷码(1)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Ajax相关介绍
- 下一篇： angular使用动态组件后属性值_An