BCH碼的基本原理參考了此處
【舉例子詳細(xì)分析】BCH碼(BCH code)

文章目錄

• 模二多項(xiàng)式環(huán)
• • 代碼實(shí)現(xiàn)
• BCH碼
• • 對(duì)信息編碼

模二多項(xiàng)式環(huán)

模二多項(xiàng)式環(huán)中的一個(gè)多項(xiàng)式，和二進(jìn)制數(shù) 是有一個(gè)由多項(xiàng)式的系數(shù)決定的，一一對(duì)應(yīng)的關(guān)系的。
比如，有一個(gè)多項(xiàng)式
$F(x)=x^4+x+1$
將其系數(shù)為0的項(xiàng)補(bǔ)全后，可以得到
$F(x)=1?x^4+0?x^3+0?x^2+1?x+1$，
按順序取出系數(shù)為10011

模二多項(xiàng)式環(huán)中的運(yùn)算有關(guān)特性不再贅述

代碼實(shí)現(xiàn)

class Polynomial2():'''模二多項(xiàng)式環(huán)，定義方式有三種一是>>> Polynomial2([1,1,0,1])x^3 + x^2 + 1二是>>> Polynomial2('1101')x^3 + x^2 + 1三是>>> Poly([3,1,4]) # 直接給出系數(shù)為1的項(xiàng)的階x^4 + x^3 + x>>> Poly([])0'''def __init__(self,ll):if type(ll) == str:ll = list(map(int,ll))self.param = ll[::-1]self.ones = [i for i in range(len(self.param)) if self.param[i] == 1] # 系數(shù)為1的項(xiàng)的階數(shù)列表self.Latex = self.latex()self.b = ''.join([str(i) for i in ll]) # 二進(jìn)制形式打印系數(shù)self.order = 0 # 最高階try:self.order = max(self.ones)except:passdef format(self,reverse = True):'''格式化打印字符串reverse = False時(shí)，可以低位在左但是注意定義多項(xiàng)式時(shí)只能高位在右'''r = ''if len(self.ones) == 0:return '0'if reverse:return ((' + '.join(f'x^{i}' for i in self.ones[::-1])+' ').replace('x^0','1').replace('x^1 ','x ')).strip()return ((' + '.join(f'x^{i}' for i in self.ones)+' ').replace('x^0','1').replace('x^1 ','x ')).strip()def __call__(self,x):# 懶得寫(xiě)print(f'call({x})')def __add__(self,other):a,b = self.param[::-1],other.param[::-1]if len(a) < len(b):a,b = b,afor i in range(len(a)):try:a[-1-i] = (b[-1-i] + a[-1-i]) % 2except:breakreturn Polynomial2(a)def __mul__(self,other):a,b = self.param[::-1],other.param[::-1]r = [0 for i in range(len(a) + len(b) - 1)]for i in range(len(b)):if b[-i-1] == 1:if i != 0:sa = a+[0]*ielse:sa = asa = [0] * (len(r)-len(sa)) + sa#r += np.array(sa)#r %= 2r = [(r[t] + sa[t])%2 for t in range(len(r))]return Polynomial2(r)def __sub__(self,oo):# 在模二多項(xiàng)式環(huán)下，加減相同return self + oodef div(self,other):r,b = self.param[::-1],other.param[::-1]if len(r) < len(b):return Polynomial2([0]),selfq=[0] * (len(r) - len(b) + 1)for i in range(len(q)):if len(r)>=len(b):index = len(r) - len(b) + 1 # 確定所得商是商式的第index位q[-index] = int(r[0] / b[0])# 更新被除多項(xiàng)式b_=b.copy()b_.extend([0] * (len(r) - len(b)))b_ = [t*q[i] for t in b_] r = [(r[t] - b_[t])%2 for t in range(len(r))]for j in range(len(r)): #除去列表最左端無(wú)意義的0if r[0]==0:r.remove(0)else:breakelse:breakreturn Polynomial2(q),Polynomial2(r)def __floordiv__(self,other): # 只重載了整除，即//return self.div(other)[0]def __mod__(self,other):return self.div(other)[1]def __repr__(self) -> str:return self.format()def __str__(self) -> str:return self.format()def __pow__(self,a):# 沒(méi)有大數(shù)階乘的需求，就沒(méi)寫(xiě)快速冪t = Polynomial2([1])for i in range(a):t *= selfreturn tdef latex(self,reverse=True):# Latex格式打印...其實(shí)就是給大于一位長(zhǎng)度的數(shù)字加個(gè)括號(hào){}def latex_pow(x):if len(str(x)) <= 1:return str(x)return '{'+str(x)+'}'r = ''if len(self.ones) == 0:return '0'if reverse:return (' + '.join(f'x^{latex_pow(i)}' for i in self.ones[::-1])+' ').replace('x^0','1').replace(' x^1 ',' x ').strip()return (' + '.join(f'x^{latex_pow(i)}' for i in self.ones)+' ').replace('x^0','1').replace(' x^1 ',' x ').strip()def __eq__(self,other):return self.ones == other.onesdef Poly(ones):if len(ones) == 0:return Polynomial2('0')ll = [0 for i in range(max(ones)+1)]for i in ones:ll[i] = 1return Polynomial2(ll[::-1])from tqdm import trange from number import *PP = Polynomial2 P = Poly # 簡(jiǎn)化名稱,按長(zhǎng)度區(qū)分 P 和 PP ''' 定義方式可改為 PP('11010') 或者 P([5,6,7]) '''

另外，在sagemath中有更強(qiáng)大的更完備的多項(xiàng)式整數(shù)環(huán)

sage: P.<x> = PolynomialRing(Zmod(2))sage: p = x^4 + x + 1sage: p(x^3) x^12 + x^3 + 1sage: factor(p) # 分解多項(xiàng)式 x^4 + x + 1sage: factor(x^4+x^2+1) # 分解多項(xiàng)式 (x^2 + x + 1)^2

對(duì)這個(gè)不太熟悉，但功能沒(méi)問(wèn)題，主要用來(lái)檢驗(yàn)結(jié)果

BCH碼

原理大概是，根據(jù)編碼糾錯(cuò)個(gè)數(shù)，$Q(x)$ 有如下形式
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-FT2gSQOi-1659454509052)(Untitled%202.assets/9c2418c5823d42d89f917cb668638fa4.png)]
$p(x)$ 是本原多項(xiàng)式primitive polynomial
選定 $p(x)=x^4+x+1$
$p_3(x)$ 滿足 $p_3(x^3)\equiv 0\mathrm{mod}p$
選定 $p_3(x)=x^4+x^3+x^2+x+1$
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-7Tg8CO4k-1659454509053)(Untitled%202.assets/9669eadfe0fc4983a64329cccd80c540.png)]
$p_5(x)$ 滿足 $p_5(x^5)\equiv 0\mathrm{mod}p$
選定 $p_5(x)=x^2+x+1$
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-Nm5xHjrq-1659454509054)(Untitled%202.assets/d3bdf9ab65e84ffebd58f2e5a4d03f36.png)]
假設(shè)需要糾錯(cuò)3位，則
$$Q(x)=p(x)?p_3(x)?p_5(x)$$

要發(fā)送的信息$m(x)$，對(duì)其進(jìn)行編碼操作，得到的發(fā)送的信息S為
$$S(x)=Q(x)?m(x)$$
若發(fā)送過(guò)程不出錯(cuò)，則直接除以$Q(x)$即可得到原文$m(x)$

但若發(fā)送信息的過(guò)程中收到干擾，某幾位比特出現(xiàn)錯(cuò)誤，即接受到的信息R為
$$R(x)=Q(x)?m(x)+x^{e_1}+x^{e_2}+x^{e_3}$$

由于之前$p_3(x)$和$p_5(x)$的性質(zhì)，$Q(x)$也滿足
$$\begin{gathered} Q(x^3)\equiv 0\mathrm{mod}p \\ Q(x^5)\equiv 0\mathrm{mod}p \end{gathered}$$
所以
$$\begin{gathered} R(x)\equiv x^{e_1}+x^{e_2}+x^{e_3}\mathrm{mod}p \\ R(x^3)\equiv x^{3?e_1}+x^{3?e_2}+x^{3?e_3}\mathrm{mod}p \\ R(x^5)\equiv x^{5?e_1}+x^{5?e_2}+x^{5?e_3}\mathrm{mod}p \end{gathered}$$
這三個(gè)值都是已知的(可以求出的)，根據(jù)這三個(gè)值，通過(guò)某些方法解出 $e_1,e_2,e_3$ 的值，即可找出錯(cuò)誤位置并糾正，得到 $S(x)$，除以$Q(x)$即可得到原文 $m(x)$

對(duì)信息編碼

假設(shè)要發(fā)送的信息 m = 11010

這里原paper里面是低位在左邊
這里需要反序生成多項(xiàng)式

p = Polynomial2('10011') p3 = Polynomial2('11111') p5 = Polynomial2('111') Q = p * p3 * p5print('p =',p.b) print('p =',p) print('p3 =',p3.b) print('p5 =',p5.b)m = PP('01011')send = Q*m print('send =',send.b)

p = 10011
p = x^4 + x + 1
p3 = 11111
p5 = 111
send = 010011011100001

ei1 = 2 ei2 = 5 e1 = Poly([ei1]) e2 = Poly([ei2])r = send + e1 + e2# r.ones是r中系數(shù)為1的項(xiàng)的階數(shù) # [3*i for i in r.ones]就是把所有階數(shù)乘了3 r3 = Poly([3*i for i in r.ones]) # R(x^3) r5 = Poly([5*i for i in r.ones]) # R(x^5)rx1 = r%p rx3 = r3%p rx5 = r5%pprint('rx1 =',rx1) print('rx3 =',rx3) print('rx5 =',rx5)

rx1 = x
rx3 = x^3 + x^2 + 1
rx5 = 0

原文中 $R(x^3)\mathrm{mod}p=x^{13}$
此處 $x^3+x^2+1$ 和 $x^{13}$ 在$\mathrm{mod}p$下是相同的

全部代碼

from random import randintDEBUG = 0 # 如果開(kāi)啟DEBUG模式，則會(huì)打印中間值信息，并且按enter才會(huì)進(jìn)入下一次恢復(fù) # 不開(kāi)啟DEBUG，則while 1不斷運(yùn)行，捕捉到Ctrl+C中斷時(shí)打印當(dāng)前統(tǒng)計(jì)的成功率class Polynomial2():'''模二多項(xiàng)式環(huán)，定義方式有三種一是>>> Polynomial2([1,1,0,1])x^3 + x^2 + 1二是>>> Polynomial2('1101')x^3 + x^2 + 1三是>>> Poly([3,1,4]) # 直接給出系數(shù)為1的項(xiàng)的階x^4 + x^3 + x>>> Poly([])0'''def __init__(self,ll):if type(ll) == str:ll = list(map(int,ll))self.param = ll[::-1]self.ones = [i for i in range(len(self.param)) if self.param[i] == 1] # 系數(shù)為1的項(xiàng)的階數(shù)列表self.Latex = self.latex()self.b = ''.join([str(i) for i in ll]) # 二進(jìn)制形式打印系數(shù)self.order = 0 # 最高階try:self.order = max(self.ones)except:passdef format(self,reverse = True):'''格式化打印字符串reverse = False時(shí)，可以低位在左但是注意定義多項(xiàng)式時(shí)只能高位在右'''r = ''if len(self.ones) == 0:return '0'if reverse:return ((' + '.join(f'x^{i}' for i in self.ones[::-1])+' ').replace('x^0','1').replace('x^1 ','x ')).strip()return ((' + '.join(f'x^{i}' for i in self.ones)+' ').replace('x^0','1').replace('x^1 ','x ')).strip()def __call__(self,x):# 懶得寫(xiě)print(f'call({x})')def __add__(self,other):a,b = self.param[::-1],other.param[::-1]if len(a) < len(b):a,b = b,afor i in range(len(a)):try:a[-1-i] = (b[-1-i] + a[-1-i]) % 2except:breakreturn Polynomial2(a)def __mul__(self,other):a,b = self.param[::-1],other.param[::-1]r = [0 for i in range(len(a) + len(b) - 1)]for i in range(len(b)):if b[-i-1] == 1:if i != 0:sa = a+[0]*ielse:sa = asa = [0] * (len(r)-len(sa)) + sa#r += np.array(sa)#r %= 2r = [(r[t] + sa[t])%2 for t in range(len(r))]return Polynomial2(r)def __sub__(self,oo):# 在模二多項(xiàng)式環(huán)下，加減相同return self + oodef div(self,other):r,b = self.param[::-1],other.param[::-1]if len(r) < len(b):return Polynomial2([0]),selfq=[0] * (len(r) - len(b) + 1)for i in range(len(q)):if len(r)>=len(b):index = len(r) - len(b) + 1 # 確定所得商是商式的第index位q[-index] = int(r[0] / b[0])# 更新被除多項(xiàng)式b_=b.copy()b_.extend([0] * (len(r) - len(b)))b_ = [t*q[i] for t in b_] r = [(r[t] - b_[t])%2 for t in range(len(r))]for j in range(len(r)): #除去列表最左端無(wú)意義的0if r[0]==0:r.remove(0)else:breakelse:breakreturn Polynomial2(q),Polynomial2(r)def __floordiv__(self,other): # 只重載了整除，即//return self.div(other)[0]def __mod__(self,other):return self.div(other)[1]def __repr__(self) -> str:return self.format()def __str__(self) -> str:return self.format()def __pow__(self,a):# 沒(méi)有大數(shù)階乘的需求，就沒(méi)寫(xiě)快速冪t = Polynomial2([1])for i in range(a):t *= selfreturn tdef latex(self,reverse=True):# Latex格式打印...其實(shí)就是給大于一位長(zhǎng)度的數(shù)字加個(gè)括號(hào){}def latex_pow(x):if len(str(x)) <= 1:return str(x)return '{'+str(x)+'}'r = ''if len(self.ones) == 0:return '0'if reverse:return (' + '.join(f'x^{latex_pow(i)}' for i in self.ones[::-1])+' ').replace('x^0','1').replace(' x^1 ',' x ').strip()return (' + '.join(f'x^{latex_pow(i)}' for i in self.ones)+' ').replace('x^0','1').replace(' x^1 ',' x ').strip()def __eq__(self,other):return self.ones == other.onesdef Poly(ones):if len(ones) == 0:return Polynomial2('0')ll = [0 for i in range(max(ones)+1)]for i in ones:ll[i] = 1return Polynomial2(ll[::-1])from tqdm import trange from number import *PP = Polynomial2 P = Poly # 簡(jiǎn)化名稱,按長(zhǎng)度區(qū)分 P 和 PPp = Polynomial2('10011') p3 = Polynomial2('11111') Q = p*p3def getMorder(r,e1e2):return ((r+Poly(e1e2))//Q).orderdef main(mm):m = Polynomial2(bin(mm)[2:])send = Q*m # 發(fā)送的Send多項(xiàng)式ie1 = randint(0,send.order) # 隨機(jī)選兩個(gè)不相同的出錯(cuò)位置ie2 = randint(0,send.order)while ie1 == ie2:ie2 = randint(0,send.order)e1 = Poly([ie1])e2 = Poly([ie2])recv = send + e1 + e2 # 接收到的出錯(cuò)多項(xiàng)式rx = Poly([i for i in recv.ones])rx3 = Poly([3*i for i in recv.ones])if DEBUG:ff = max(len(recv.b),len(send.b))print('mm =',bin(mm)[2:])print('m =',m)print('p =',p)print('p3 =',p3)print()print('send:\t',send.b.zfill(ff))print('recv:\t',recv.b.zfill(ff))print('e:\t',(e1+e2).b.zfill(ff))print('e1,e2 =',ie1,ie2)print()print('R(x) =',rx)print('R(x) =',rx%p)print('R(x^3) =',rx3)print('R(x^3) =',rx3%p)ans = []for i in range(17):_e1 = Poly([i])for j in range(i,17):if i == j:continue_e2 = Poly([j])t1 = (_e1+_e2)%pt3 = (Poly([3*i])+Poly([3*j]))%pif DEBUG and i == ie1 and j == ie2:print('t1: ',t1)print('t3: ',t3)print(t1 == rx%p,t3 == rx3%p)if t1 == rx%p and t3 == rx3%p:#print('find',int(_e1.b,2),int(_e2.b,2),i,j)ans.append((i,j))if DEBUG:print('過(guò)濾前ans:',ans)if len(ans) > 1:# 若找到多組 e1e2，則判斷(R-e1-e2)//p 的階數(shù)是否小于8# 因?yàn)?m 的階數(shù)不會(huì)超過(guò)8 res = [i for i in ans if getMorder(rx,i)<=7]else:res = ansif DEBUG:print('過(guò)濾后ans:',res,'出錯(cuò)位置:',(ie1,ie2))input()return resif __name__ == '__main__':cnt = [0,0,0,0,0]while 1:try:# 隨機(jī)生成一個(gè)8bit明文cnt[len(main(randint(0,255)))] += 1# 返回值是結(jié)果列表 如果列表里只有一個(gè)元素則恢復(fù)成功# cnt 記錄的是返回的列表的長(zhǎng)度except:print('\n',cnt)if sum(cnt) != 0:sucP = (cnt[1]+cnt[2]/2+cnt[4]/4)/sum(cnt)print(f'p : {sucP},p^25:{sucP**25}')

總結(jié)

以上是生活随笔為你收集整理的模二多项式环 及 BCH码 的纯python实现和一些问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。