簡單介紹

若循環碼的生成多項式具有如下形式\(g(x)=LCM[m_{1}(x),m_{3}(x)..m_{2t-1}(x)]\)

其中LCM表示最小公倍式，t為糾錯個數，\(m_{i}(x)\)為素多項式，則由此生成的循環碼稱為BCH碼，其最小碼距\(d\ge d_{0}=2t+1\)，其中\(d_{0}\)為設計碼距，則這個碼能糾正t個隨機獨立差錯。

舉個例子來有個先驗感知:BCH(15,5)碼，可糾正3個隨機獨立差錯(t=3)，求它的生成多項式。

碼距應該為\(d\ge d_{0}=2*3+1=7\)

n=15，根據\(n=2^{m}-1\)，得出m等于4；查下表不可約多項式可知:

階數編號多項式(二進制表示)

2	1	111
3	1	1101
4	1 3 5	010011 011111 000111
5	1 3 5	100101 111101 110111

于是就有了\(m_{1}(x)=x^{4}+x+1\),\(m_{3}(x)=x^{4}+x^{3}+x^{2}+x+1\),\(m_{5}(x)=x^{2}+x+1\)

這樣就得出：

\(g(x)=LCM[m_{1}(x),m_{3}(x),m_{5}(x)]=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1\)

基本知識

BCH?碼是用于校正多個隨機錯誤模式的多級、循環、錯誤校正、變長數字編碼，是迄今為止所發現的一類很好的線性糾錯碼類。它的糾錯能力很強，特別在短和中等碼長下，其性能接近于理論值，并且構造方便，編碼簡單。特別是它具有嚴格的代數結構，因此它在編碼理論中起著重要的作用。

BCH碼是循環碼的一個子類，他的糾錯能力是通過：先聲明期望碼能糾錯隨機錯誤的的個數，然后再構造這樣的碼生成多項式。

如果一個域F僅具有有限多個元素，比如僅有q個元素，這樣的域稱為有限域或稱之為伽羅瓦域，記為GF(q)。

\(GF(2^{m})\)的構成

可以將\(GF(p)\)延伸為一個含有\(p^{m}\)個元素的域，稱為GF(p)的擴展域，表示為\(GF(p^{m})\)

由這個我們就可以知道二進制域\(GF(2)\)是擴展域\(GF(2^{m})\)的一個子域，類似于實數域是復數域的一個子域一樣。除了數字0和1之外，在擴展域中還可以用a來表示特殊元素，\(GF(2^{m})\)中任何非0元素都可由a的冪次表示。這樣\(GF(2^{m})\)的元素可表示為\(GF(2^{m})={0,a^{0},a^{1},a^{2},.........a^{2^{m}-2}}\)

系數取自GF(2)上的(m-1)次多項式，即

\[a(\alpha)=a_{0}+a_{1}\alpha+...+a_{m-1}\alpha^{m-1}\]

其中\(a_{i}\in GF(2)，i=0,1,2...m-1\)。這些多項式的總數正好等于\(2^{m}\)。我們希望能將這些數據作為\(GF(2^{m})\)上的元素，這些元素可以通過多項式或者是m維二元矢量進行表示。

舉一個例子，m=4時，對于\(GF(2^{4})\)的16個元素可以如下表所示:

接下來引入\(GF(2^{m})\)中元素間的加法和乘法運算，系數之間的運算采用模2運算。

先來看加法

\(m(\alpha)=1+\alpha+\alpha^{3}\)---->1101

\(n(\alpha)=1+\alpha^{2}?\)----------->1010

則\(m(\alpha)+n(\alpha)=(+\alpha+\alpha^{3})+(1+\alpha^{2})=\alpha+\alpha^{2}+\alpha^{3}\)

------>0111

但是當我們在乘法的時候，就會有問題:

\(m(\alpha)*n(\alpha)=1+\alpha+\alpha^{2}+\alpha^{5}\)

超過了最高次數項，必須把它簡化為小于等于3的多項式。如何才能簡化？可以通過令\(\alpha\)是某個4次多項式\(\pi(x)\)的根。在上述的例子里，我們可以令\(\alpha\)為\(\pi(x)=1+x+x^{4}\)的根，即\(\alpha^{4}=1+\alpha\)

從而

\[\begin{eqnarray}m(\alpha)*n(\alpha)&=&1+\alpha+\alpha^{2}+\alpha^{5}\\&=&1+\alpha+\alpha^{2}+\alpha(1+\alpha)\\&=&1 \end{eqnarray}\]

即(1101)*(1010)=(1000).這樣用多項式表示\(GF(2^{4})\)元素對于多項式乘法是封閉的。

我們總結一下，如果需要生成有限域\(GF(2^{m})\)，則\(\pi(x)\)必須是m次多項式。這里的\(\pi(x)\)必須是\(GF(2)\)上的既約多項式(\(\pi(x)\)在\(GF(2)\)上不能進一步因式分解，或者說\(\pi(x)\)沒有次數小于m-1，系數在\(GF(2)\)上的多項式作為因式)

關于GF域有以下幾個定理:

1.如果\(\pi(x)\)是\(GF(2)\)上次數等于m的既約多項式，則對\(GF(2)\)上每個次數小于m的多項式c(a)存在唯一的逆元:\(c^{-1}(a)\in GF(2^{m})\)

2.令\(\lambda\)為\(\sum_{i=1}^{t}1=0\)成立的最小整數t(這里的1為單位元素)，該\(\lambda\)稱為有限域\(GF(q)\)的特征，該特征一定是質數。

循環碼的定義和多項式表示

一個二元n維矢量\(v=(v_{0},v_{!},...,v_{n-1})\)，若把它的分量循環向右一位，則得到另一個n維矢量\(v^{(1)}=(v_{n-1},v_{0},v_{1},.....v_{n-2})\)，這里把\(v^{(1)}\)稱為v的循環移位。

一個(n,k)線性碼l，若它的每個碼字矢量的循環移位也是該碼的碼字，則稱l為循環碼。我們可以把碼字矢量\(v=(v_{0},v_{!},...,v_{n-1})\)看成是如下的多項式:

\[v(x)=v_{0}+v_{1}x+v_{2}x^{2}+....+v_{n-1}x^{n-1}=\sum_{j=0}^{n-1}v_{j}x^{j}\]

其中系數\(v_{j}\in {0,1}\)，\(v_{j}x^{j}\)實際上只是表示這個矢量v的第j+1位分量是\(v_{j}\)，因此\(x^{j}\)是位置算子。

每個碼字矢量與一個不高于n-1次的多項式對應，于是與\(v^{1}\)對應的多項式為:\(v^{1}(x)=v_{n-1}+v_{0}x+....+v_{n-2}x^{n-1}\)

觀察\(v(x)\)與\(v^{1}(x)\)的關系可得:\(x*v(x)=v^{1}(x)+v_{n-1}(x^{n}+1)\)(二元計算中+1和-1是等價的，所以將-1換成了+1)；進一步我們可以總結出:\(v^{1}(x)\equiv x*v(x)mod(x^{n}+1)\)

意思是說\(v^{i}(x)\)等于x與v(x)的乘積后再除以\(x^{n}+1\)以后的余式。

假如我們現在有一個n-k循環碼的生成多項式:\(g(x)=1+x^{2}+x^{4}\),則生成的(6,2)循環碼的碼字矢量和碼字多項式如下:

消息矢量碼字矢量碼字多項式

\((u_{0}，u_{1})\)	\((v_{0},v_{1},v_{2},v_{3},v_{4},v_{5})\)
(0,0)	(0,0,0,0,0,0)	\(v_{0}(x)=0*g(x)=0\)
(0,1)	(1,0,1,0,1,0)	\(v_{1}(x)=1*g(x)=g(x)\)
(1,0)	(0,1,0,1,0,1)	\(v_{2}(x)=x*g(x)=x+x^{3}+x^{5}\)
(1,1)	(1,1,1,1,1,1)	\(v_{3}(x)=(x+1)*g(x)=1+x+x^{2}+x^{3}+x^{4}+x^{5}\)

根據循環碼的定義(循環移位后仍然是在這個循環碼內的碼字)知道，((000000),(01010101),(10101010),(111111))是循環碼。消息矢量可以看成是代表的k位消息數據比特，在這個例子里是2.

給出一個定理:若g(x)是n-k次多項式，而且是\(x^{n}+1\)的因式，則g(x)生成一個(n,k)循環碼。

有限域的本原多項式

一個多項式是本原多項式的充要條件:一個m階的不可約多項式f(x)，如果f(x)整除\(x^{n}+1\)的最小正整數n滿足\(n=2^{m}-1\)，則該多項式是本原的。

例如用本原多項式\(p(x)=1+x+x^{3}\)來構造GF(8)，設GF(8)上的本原元為a，通過將a的冪模p(a)得到GF(8)上的所有元素:

極小多項式

系數定義在基域\(GF(q)\)上且在擴展域\(GF(q^{m})\)上有根\(\beta _{j}\)的最小次數多項式稱為\(\beta_{j}\)的極小多項式。

設\(b_{1},b_{2}...b_{p-1}\)為GF(p)上的非零域元素，則\(x^{p-1}+1=(x+b_{1})(x+b_{2})...(x+b_{p-1})\)

從上面的循環碼知識我們知道，為了找到分組長度為n的循環碼的生成多項式，首先分解\(x^{n}+1\)，因此\(x^{n}+1\)可以表示為多個因子的乘積，即\(x^{n}+1=f_{1}(x)f_{2}(x)....f_{w}(x)\)

在擴展域\(GF(p^{m})\)中，\(n=p^{m}-1\)

編碼

對于一個分組長度\(n=p^{m}-1\)、確定可糾正t個錯誤的BCH碼的生成多項式的步驟如下:

1.選取一個次數為m的素多項式并構造\(GF(p^{m})\)

2.求\(a^{i},i=0,1,2...n-2\)的極小多項式\(f_{i}(x)\)

3.可糾正t個錯誤的碼的生成多項式為:

\[g(x)=LCM[(f_{1}(x),f_{2}(x),f_{3}(x).....f_{2t}(x)]\]

d=2t+1稱為碼的設計距離，一旦確定了n和t，我們便可以確定BCH碼的生成多項式。

表中第2列是第3列多項式的根。

然后用生成多項式，按照生成循環碼的方式生成的就為BCH碼。

實現

bch_n=15 # (n,k)中的n bch_k=5 # (n,k)中的k bch_c=bch_n-bch_k g=[1,0,1,0,0,1,1,0,1,1,1] # 這個要自己計算 def encode(origin_data):zero=[0]bb=[]bb.extend((bch_c)*zero)for i in range(bch_k):freeback=origin_data[i]^bb[0]if freeback!=0:for j in range(bch_c-1):if g[j]!=0:bb[j]=bb[j+1]^freebackelse:bb[j]=bb[j+1]bb[bch_c-1]=g[bch_c-1]&freebackelse:for j in range(bch_c-1):bb[j]=bb[j+1]bb[bch_c-1]=0return bbdef main():origin_data=[1,0,0,1,1]print("Word to be encoded:")print(origin_data)data=[]data=encode(origin_data)print("Encoded it is:")print(data)main()

轉載于:https://www.cnblogs.com/yunlambert/p/10284455.html

總結

以上是生活随笔為你收集整理的BCH code的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。