Python資料結構格雷碼
- 前言
- 格雷碼
-
- 自然二進制碼轉二進制格雷碼
- 二進制格雷碼轉自然二進制碼
- Python實作
- 作者說
前言
格雷碼是由貝爾實驗室的Frank Gray與1940年提出,用于在PCM(脈沖編碼調變)方法傳送訊号,防止訊号出錯。其特點是任何兩個相鄰數的代碼隻有一位二進制數不同的編碼。時至今日,格雷碼有了更廣泛的作用,比如在遺傳算法中,使用自然二進制碼來表示基因會造成漢明懸崖問題;而采用格雷碼則能夠很好的避免這個問題的出現。
格雷碼
自然二進制碼轉二進制格雷碼
自然二進制碼轉換成二進制格雷碼,其法則是保留自然二進制碼的最高位作為格雷碼的最高位,而次高位格雷碼為二進制碼的高位與次高位相異或,而格雷碼其餘各位與次高位的求法相類似。
二進制格雷碼轉自然二進制碼
二進制碼轉換成格雷碼的做法是,保留二進制碼的最高位,而次高位格雷碼為二進制高位與此高位相異或
Python實作
# -*- coding: utf-8 -*-
import numpy as np
#實作二進制數組
class BinArray:
def __init__(self,n ):
self.n = n
self.array= np.zeros([self.n])
self.gray = np.zeros([self.n])
def bin2int(self):
ret = 0
for i in range(self.n):
if(self.array[i])==1:
ret+= int(2**i)
return ret
def bin2gray(self):
#二進制轉格雷碼
#第一位不變
self.gray[0] =self.array[0]
for i in range(1,self.n):
#python的xor運算不支援整形
if self.gray[i-1]==self.array[i]:
self.gray[i]=0
else:
self.gray[i]=1
def setbinarray(self,a):
if(len(a))>self.n:
return
for i in range(len(a)):
self.array[i]=a[i]
def show(self):
print("自然二進制")
print(self.array)
self.bin2gray()
print("格雷碼")
print(self.gray)
if __name__ == "__main__":
ba = BinArray(4)
a = [1,1,0,1]
ba.setbinarray(a)
ba.show()
作者說
本文是繼Python資料結構最小生成樹的序章,以簡單的方法實作了格雷碼。寫本文的另一個目的,在于為Python遺傳算法提供優化的方案。
資料結構雖然是特别基礎的理論,但是很多高深的算法和第三方庫都需要程式員又較好的資料結構的功底,Tensorflow更是很好的展示了這個理念。
Python資料結構格雷碼是這個系列的第二篇文章,如果您有任何寶貴的意見,歡迎你将意見發送至我的郵箱[email protected]。如果你想要擷取更多學習資料,歡迎加入Python學習QQ群,916372346。或者購買我們的課程https://www.jianshu.com/p/da4d714d49b9