信道容量和编码.ppt

9.1分组码
9.1.1分组码简介
1.线性分组码
（1）基本概念
对于（n,k）线性分组码，生成矩阵是一个k×n的矩阵。设输入的信息为m=[m1,m2,…,mk]，生成的码字为v=[v1,v2,…,vn]，则v=mG，其中G为生成矩阵。生成矩阵的各行向量为码字空间的基底，由于一个子空间的基底选择不是唯一的，所以生成矩阵G的选择也不是唯一的。对于生成码字中前k位与信息完全相同的码称为系统码。这样，对于系统码其生成矩阵可以表示为：
G=[IkP]

式中：Ik表示k×k的单位矩阵；P表示一个k×(n-k)的矩阵。

由于（n,k）码的生成矩阵G，表示的是n维空间中的一个k维的子空间，那么一定存在一个n-k维的子空间与G表示的子空间正交，称为G行空间的零化空间。我们用一个(n-k)×n的矩阵H的行向量来表示这个零化空间。则有如下关系：
GHT=0或HGT=0
矩阵H称为(n,k)码的一致校验矩阵。对于系统码的生成矩阵G=[Ik,P]，一致校验矩阵H有如下形式：
H=[PTIn-k]（2）伴随式与纠错
设发送的码字为V=[v1,v2,…,vn]，接收的码字为R=[r1,r2,…,rn]，则传输中的错误图样为E=[e1,e2,…,en]，R=V+E。若E≠0，则表明传输中出现错误，因此通过在接收端检测RHT是否为零来检查是否出错，定义：
S=RHT
为伴随式，它是一个n重序列。
S=RHT=(V+E)HT=VHT+EHT=EHT
可见伴随式只与错误图样有关，而与发送的码字无关。若E=0，则S=0表明没有错误；否则S≠0，伴随式与错误图样E有一个对应关系，通过这个对应关系，由伴随式S得到错误图样E，再将接收的码字R与错误图样E相加，就可得到纠错后的正确码字。（3）汉明距离与汉明码
线性码的纠错能力与码的最小距离有关。定义一个码字的非零分量数为汉明重量。两码字间的不同符号数定义为两码字的汉明距离。一线性码两两互异的码字构成的汉明距离中，数值最小的称为该码的最小汉明距离dmin；非零码字中，重量最小的称为该码的最小汉明重量。对于线性分组码，它的最小汉明距离等于最小汉明重量。
对于一个二进制(n,k)线性分组码，当它的最小汉明距离为d时，用于检错时它最多可以发现d-1个错误；用于纠错时它最多可以纠正(d-1)/2位错误。若d≥t+t’+1，其中t’>t，这时该线性码可以在纠t个错的同时发现t’个错误。
汉明码的参数为：
码长：n=2m-1
信息位数：k=2m-m-1
其中，m为任意不小于2的整数。
一旦m给定，就可以构造出具体的(n,k)汉明码。
2.循环码
循环码是具有以下特点的线性分组码：任意码组的每一次循环移位（左移或右移）得到的是码中的另一码组。即若(vn-1vn-2…v0)为(n,k)码的码字，则（vn-2vn-3…v0vn-1）也是(n,k)码的码字。通常用多项式来表示循环码，如用
V(x)=vn-1xn-1+vn-2xn-2+…+v1x+v0
来表示码组(vn-1vn-2…v0)，称V(x)为码多项式。对于循环码，xV(x)，x2V(x)，…，以及循环移位的线性组合均为循环码，且这些码多项式都是模xn-1的余式。
（1）生成多项式与编码电路
从(n,k)循环码的2k个码字中，挑出一个前面k-1位均为0的n-k次码多项式g(x)=xn-k+gn-k-1xn-k-1+…+g1x+1
则xg(x)，x2g(x)，…，xk-1g(x)都是码字，且这k个码字线性无关，称g(x)为码的生成多项式。它是2k个码字集合中唯一的一个次数为n-k次的多项式。
用上述k个码字作为循环码的基底，并以该基底作为构成一个矩阵G(x)，即

则称G(x)为生成矩阵G的多项式，而矩阵G为生成矩阵。对于循环码，有以下关系：(n,k)循环码的每个码多项式都是生成多项式g(x)的倍式；能被g(x)除尽的次数不大于n-1次的的多项式必然是码多项式。此外，g(x)一定是xn-1的因子，即
xn-1=g(x)h(x)
式中，h(x)称为码的校验（监督）多项式，它由g(x)惟一决定。
循环码的编码可以用反馈移位寄存器来实现，如图所示。（2）伴随式与译码电路
设V(x)与R(x)分别是发送和接收的码多项式，E(x)为错误多项式，则
R(x)=V(x)+E(x)
用生成多项式g(x)除R(x)，得商式为q(x)，余式为S(x)，即：
R(x)=q(x)g(x)+S(x)
式中的S(x)即为伴随式。

3.BCH码
BCH码是一类纠正多个随机错误的循环码，其定义如下所述。二进制或q进制循环码的生成多项式g(x)，若含有以下δ-1个连续根：α，α2，α3，…，αδ-1，则由该g(x)生成的(n,k)循环码称为二进制或q进制BCH码。码的生成多项式为
g(x)=LCM{m1