简单介绍
若循环码的生成多项式具有如下形式(g(x)=LCM[m_{1}(x),m_{3}(x)..m_{2t-1}(x)])
其中LCM表示最小公倍式，t为纠错个数，(m_{i}(x))为素多项式，则由此生成的循环码称为BCH码，其最小码距(dge d_{0}=2t+1)，其中(d_{0})为设计码距，则这个码能纠正t个随机独立差错。
举个例子来有个先验感知:BCH(15,5)码，可纠正3个随机独立差错(t=3)，求它的生成多项式。
码距应该为(dge 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_{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)
从而
即(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_{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}))上有根(eta _{j})的最小次数多项式称为(eta_{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个错误的码的生成多项式为:
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]^freeback
else:
bb[j]=bb[j+1]
bb[bch_c-1]=g[bch_c-1]&freeback
else:
for j in range(bch_c-1):
bb[j]=bb[j+1]
bb[bch_c-1]=0
return bb
def 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()