生成多项式与矩阵的关系及优化

(n,k)循环码码组集合中(全“0”码除外)幂次最低的多项式(n-k阶)称为生成多项式g(x)。它是能整除xn+1且常数项为1的多项式,具有唯一性。集合中其他码多项式,都是按模xn+1运算下g(x)的倍式,即可以由生成多项式g(x)产生循环码的全部码组。换句话说,循环码完全由其码组长度n及生成多项式g(x)所决定。阶数低于n并能被g(x)除尽的一组多项式就构成一个(n,k)循环码。也就是说,阶数小于或等于n-1能被g(x)除尽的每个多项式都是该循环码的许用码组。

(n,k)循环码有2k个码组,因为可以构成循环许用码组A(x)的信息码组m(x)有2k个。

式中,m(x)为不大于k-1阶的多项式。

例如,令n=7,g(x)=x4+x3+x2+1是x7+1的一个因式,共有8个阶次不大于6的多项式是g(x)的倍式,即

这8个多项式是一个(7,3)循环码。由于它有8个码组,k=3,因此n-k=7-3=4,这必定是生成多项式的阶次。

为了寻找生成多项式,必须对xn+1进行因式分解,这可以用计算机来完成。对于某些n值,xn+1只有很少几个因式,因而码长为这些n值的循环码很少。仅对于很少几个n值才有很多因式。

对于任意n值有

若取x+1为生成多项式,这样构成的循环码就是简单的偶监督码(n,n-1)。由于g(x)为一阶多项式,因此只有一位监督码。可以证明,x+1的任何倍式的码重(即码组中1的个数)必定保持偶数。这是一种最简单的循环码,dmin=2。

另一个最简单的循环码是以xn-1+xn-2+…+x+1为生成多项式,由于生成多项式是n-1阶,故信息码位数为1,只有两种码组即全0和全1,因此这种循环码是重复码(n,1),dmin=n。

任何(n,k)循环码的生成多项式g(x),乘上x+1后得到生成多项式g(x)·(x+1)所构造的循环码(n,k-1),其最小码距增加1。(n,k-1)码是(n,k)码的一个子集。

以因式分解中的本原多项式作为生成多项式,可以构造出纠正一个错误的循环汉明码。

考查表10.4.1,其中n-k=4阶的多项式只有编号为(2)的码组(0010111),所以表中所示(7,3)循环码组的生成多项式为g(x)=x4+x2+x+1,并且该码组集合中的任何码多项式A(x)都可由信息位乘以生成多项式得到

式中,(mk-1mk-2…m1m0)为信息码元。

对于(7,k)循环码,有

表10.4.1中所示(7,3)循环码组的g(x),是由式(10.4.9)中第1、3两项相乘得到的。

如果令式(10.4.9)中第1、2两项相乘,也得到一个4阶多项式,由它可以构成另一个(7,3)循环码组的集合。可见选择不同的因式组合会得到不同的生成多项式,从而构成不同的循环码组。(www.xing528.com)

由于g(x)为n-k阶多项式,以与此相对应的码组作为生成矩阵中的一行,可以证明g(x),xg(x),…,xk-1g(x)等多项式必定是线性无关的。把这k个多项式相对应的码组作为各行构成的矩阵即为生成矩阵,由各行的线性组合可以得到2k个循环码码组。这样循环码的生成矩阵多项式可以写成

以表10.4.1中的生成多项式g(x)构造G(x),相应的矩阵形式为

作线性变换,整理成典型形式的生成矩阵

信息码元与式(10.4.12)相乘,得到的就是系统循环码。

由式(10.4.10)生成矩阵得到的循环码并非系统码。在系统码中码组的左边k位是信息码元,随后是n-k位监督码元。这相当于码多项式为

式中,r(x)=rn-k-1xn-k-1+…+r0为监督码多项式,其相应的监督码元为(rn-k-1,…,r0)。由式(10.4.13)可知

可见,构造系统循环码时,只需将信息码多项式升n-k阶(即乘上xn-k),然后以g(x)为模,即除以g(x),所得余式r(x)即为监督码元。因此,系统循环码的编码过程就变成用除法求余的问题。

系统码的生成矩阵为典型形式G=(Ik Q),与单位矩阵Ik每行对应的信息多项式为

由式(10.4.15)可得相应的监督码多项式为

由此得到生成矩阵中每行的码多项式为

因此系统循环码生成矩阵多项式的一般表示为