文档介绍：循环码和BCH码
简述
1957年开始研究
循环码的优点:
编码和校正子的计算容易实现
具有固定的代数结构,能找到很多实用的方法来译码
循环码定义
对一个n维码字向量v=(v0,v1,…,vn-1)做一次向右循环移位,得到v(1)=(vn-1,v0,…,vn-2),类似,向右做i次移位,得到v(i)=(vn-i,vn-i+1,…,vn-i-1),等价于向左移位n-i次
循环码:一个(n,k)线性码C,若每个码字的循环移位仍然是C的码字,则称其为循环码
为研究循环码的代数结构,将码字v的分量看做多项式的系数:v(x)=v0+v1X+v2X2+…+vn-1Xn-1
每个码字对应于一个次数等于或小于n-1的多项式
码字和多项式是一一对应的, v(x)叫做码多项式
码多项式
若v的码多项式为v(x)=v0+v1X+v2X2+…+vn-1Xn-1
则v(i)的码多项式为vn-i+vn-i+1X+…+vn-i-1Xn-1
计算xiv(x)-v(i)得到:
(1)
也就是说v(i)就是xiv(x)除Xn+1后的余式
循环码的性质
循环码中非零次数最低的多项式是唯一的
证明:(反证法)假设有两个最低次数一样的多项式,这这两个多项式之和的次数更低,而且应该是码多项式(线性,封闭性),矛盾。
循环码中非零次数最低多项式常数项为1
证明: (反证法)假设常数项为0,则码多项式可提取公因子X,另一个因子是次数更低的码多项式(循环左移1次),矛盾。
设g(X)=1+g1X+…+Xr是(n,k)循环码非零次数最低的多项式,次数小于或等于n-1的二进制多项式是码多项式当且仅当它是g(X)的整倍数。
循环码的性质
证明:1)若v(X)是g(X)的整倍数,即
v(X)=(1+u1X+...+uiXi)g(X),Xig(X)是g(X)向左循环移位i次的码多项式,故v(X)是码的线性组合;2)设v(X)是码多项式,有v(X)= a(X)g(X)+ b(X), b(X)次数小于g(X), b(X)可以写成b(X)= a(X)g(X)+v(X),故b(X)是码多项式或0,因g(X)是次数最低的非零多项式,故b(X)=0,即v(X)是g(X)的整倍数
循环码的性质
(n,k)循环码有且仅有一个n-k次的码多项式g(X)=1+…+Xn-k,这就是次数最小的码多项式,也称为码的生成多项式
循环码的性质
(n,k)循环码的生成多项式g(X)是Xn+1的一个因子
证明:由公式(1)显然。
若g(X)是次数为n-k,且是Xn+1的一个因子,则g(X)是生成多项式,生成一个(n,k)循环码
证明:略。
性质6说明Xn+1任何一个n-k次多项式都可以生成一个(n,k)循环码,当n很大时,可以构造很多的(n,k)循环码,有好有坏,如何选择?
例子: X7+1
X7+1=(1+ X)(1+X+X3)(1+X2+X3)
故有两个(7,4)循环码
循环码的系统形式
码字前n-k分量为校验位,后k分量是信息位
编码步骤:
用Xn-k乘信息序列u(X)
用生成多项式g(X)除Xn-ku(X),得余式b(X)为校验位
得到码多项式Xn-ku(X)+b(X)