讲义61线性分组码

1、信息论课程讲义（第六章）第六章 线性分组码纠错编码（FEC）主要分为分组码和卷积码两大类，这一章主要介绍 分组码。6-1 汉明码(Hamming Code)汉明码是一种基本的线性分组码。6-1-1线性分组码的定义分组码是一种代数编码，它的基本关系一个码字包括独立的信息 元和监督元，其监督元与信息元之间是一种代数关系， 如果这种代数关系为线性的则称为线性分组码。分组码的编码器的模型为:m= (mk,mk-i,mOderC=(C n-lG-Z,c)m为编码器的输入，称为信息码元（信息位），它由k位码元组成。C为编码器的输出，称为码字矢量，它由 n位码元组成，其中有k位信息元，r=n-k位监督元。对

2、于二元编码来说，k位信息码元 共有2k个不同组合，根据编码器为一一对应关系，输出的码字矢量 也应当有2k种码字。对于长度为n的二元序列来（n-重）说，共有2n 个可能的码字矢量，编码器只是在这2n个可能码矢中选择2k个码字, 被选中的2k个n-重称为许用码字，其余的2n-2k个码字称为禁用码字, 称这2k个码字矢量的集合为（n,k）分组码。信息元监督元线性分组码定义:长度为n,有2k个码字的分组码，当且仅当这2k个码字是GF(2)上n维矢量空间(所有n重)的一个k维子空 间时，称为(n,k)线性分组码，简称(n,k)码。二元分组码为线性分组码的充要条件为两个码字的模二加也 是一个码字。由于k维

3、子空间是在模2加法下运算的，构成了一个加法交换 群(阿贝尔群)，所以线性分组码也称为群码。线性分组码的一个重要参数为码率(Code rate): R=k/n;它实际上也就是编码效率或传输效率。如果(n ,k)码位信息位没有变化，与信息码元排列相同，并且与监督位分开，称为系统码，否则称为非系统码。6-1-2 基本监督矩阵(Parity check matrix)线性分组码可以用GF(2)上的矢量空间的矩阵和GF(2)上多项式来 描述，对于汉明码这一类分组码用矩阵描述更为方便。汉明码定义:对于任意正整数r3,存在有下列参数的线性分组码,码长：n=2r-1信息位：k=2r-1-r= n-r监督位：r

4、=n-k6-3最小码距：dmin=3这种码称为狭义汉明码,也称为完备汉明码。这种码的码字矢量为:C=C n-1,Cn-2, c, C0如果对于系统码，其前k位为信息位，后r位位监督位。信息位=mk-i,mk-2,n0|=Cn-i,Cn-2, Qk监督位=Cn-k-1,ccCo由于线性分组码的监督元与信息元之间的线性关系，可以用二元 域上的线性方程组描述。记为:Cn-k-1=hi ,n-1 Cn-1 + h1,n-2Cn-2 + +hi,n-kCn-kCn-k-2 = h2,n-1 Cn-1 + h2,n-2Cn-2 + +h2,n-kCn-kC0 = hr,n-1Cn-1 +hr,n-2Cn-

5、2 +在二元域上,hij：0,1整理这个方程组可得:h1,n-1h1,n-2h1,n-k10 0Cn-1h2,n-h2,n-h2,n-k01 0Cn-212hr,n-1hr,n-2hr,n-k00 1C0+ hr,n-kCn-k=0记为:（一致校验CT为C的转置，称矩阵H为分组码的基本监督矩阵矩阵，一致监督矩阵）P h1,n h1,n= -1 -2可见系统码的基本监督矩阵为:hi,n-kH=P I rIrh2,n-1h2,n-2h2,n-khr,n-1hr,n-2hr,n-kP为r X k矩阵,Ir为r X r单位阵。举例:(7,4)系统汉明码，n=7, k=4, r=3C二C6,C5,C4,

6、C3,C2,Cl,Co；其中C6,C5,C4,C3为信息位，C2,Cl,Co为监督位。H由HC T=0可知:监督方程为:C2=C5+C4+C3Cl=C6+C4+C3Co=C6+C5+C3根据这个方程组可以进行编码。例如信息码元m=1011,则有C2=C5+C4+C3=0+1+1=0C1 =C6+C4+C3=1+1+1=1C0=C6+C5+C3=1+0+1=0则汉明码字C二1011010。信息论课程讲义(第六章)6-1-3 生成矩阵(Generator matrix)(1) 生成矩阵的基本形式:由上面(7,4)汉明码的例子;可以将基本监督方程扩展写为:C6=C6C5=C564=04C3=C302

7、=05+64+03Cl=C6+C4+C300=06+05+03用矩阵表示:06,C5,04,03,02,01,0006,05,04,03.100001000010000101111011110106,05,04,03,02,01 ,0 m3,m2,m1,0= mo.10000100001000010111101111016-7可以写为:C=m3,m2,mi,mo.G汉明码字=信息码字生成矩阵G称为(7,4)汉明码的生成矩阵。例如：m=1100,C二1100G二1100110可以看出:(n,k)码的生成矩阵的基本形式为:Ggl,n-1g2,n-1g1,ng1,1-2g2,ng2,1-2gi,0g

8、2,0gk,n-1gk,n gk,1-2gk,0同样，利用生成矩阵的编码关系为C=mG而系统(n,k)码的生成矩阵的基本形式应当为10.0g1,n-k-1g1,001 0g2,n-k-1g2,0 0 001gk,n-k-1gk,0G这种系统码的生成矩阵也称为典型生成矩阵，其基本形式为;G=Ik,Q, Q为 kx r 矩阵，IJ为 kx k 单位阵。(2) 系统码基本监督矩阵与典型生成矩阵的关系:从生成矩阵与码字矢量的关系可以看出：G矩阵的每一行都是 个码字矢量，分别对应信息码字100,01000001的分组码 的码字。由于每一行都是码字，把每一行作为一个码字矢量，都应当满足 监督矩阵所规定的监

9、督关系，即应当有:HG T=0，同时有：GHt=0称H与G为正交矩阵，由P Ir Ik Q t=0信息论课程讲义（第六章）P+Qt=0p =Q t Q = PTP矩阵与Q矩阵互为转置矩阵。对于系统码，已知监督矩阵H就可以确定典型生成矩阵G，反 之，已知生成矩阵也就可以确定监督矩阵。（3）生成矩阵的一般性质:根据线性分组码的定义，（n,k）线性分组码C是二元n重矢量空间中的一个k维子空间，因此，在码字C的集合中（2k个码元的码组中），可以找到k个线性独立的码字,gi,g2,g使C中的所有码字6-9都是这k个码字的线性组合。g1=g1,n-1,g1,n-2, ,gog2 = g2,n-1,g2,n

10、-2, ,g0gk=gk,n-1 ,gk,n-2, ,g0C=mn-igi+mn-2g2+mh-kgk其中系数就是信息码字矢量的元素 ：mn-1,mn-2m n-k=m k-1 ,mk-2m 0根据线性矢量空间的知识，这k个码字矢量就可以张成（生成） 这个k维子空间，将这k个矢量组成的矩阵就是（n,k）分组码的 生成矩阵。所以生成矩阵是一个 k行n列的矩阵。确定（n ,k）码的生成矩阵的问题实际上就是确定n-重矢量空间中k维子空间的k个线性无关的码字矢量的问题。也就是寻找 基底的问题。(n,k)码的n-重矢量空间中的一个 k维子空间的基底可以有多个，因此可以有不同的生成矩阵G，但都产生相同的码

11、组。(n,k)码的n-重矢量空间中可以有多个k维子空间，产生不同的码组。(？)(4)非系统汉明码:可以证明非系统汉明码的一致监督矩阵可以用一种简单方法得到。例如:H(7,4)非系统汉明码的H为00 0 110110 010 10 1其每一例都是二进制数的1,2,3。利用HC T=0的基本关系,可以得到非系统形式的汉明码。通过H矩阵的列换位，可以将H变为系统码的形式。6-1-4 校验子与译码(Syndrome Matrix and Decoding)设发送码字为：C = (Cn-1,Cn-2,0)；由于信道干扰产生差错,反映到接收码字上可以用一个二元矢量E表示，称为错误图样(errorP att

12、er ns),E=(en-i,en-2,0)其中：ei=1表明相应位有错，e=0表明相应位无错。这时接收码 字可以表示为,R=C+E=(c n-1+en-1,Cn-2+en-2, C+G)译码器的作用就是从接收码字R中得到发送码字的估计值，或者说从接收码字中确定错误图样E,然后由C=R-E得到发送码字的估计值，如果估计正确则译码正确，否则译码错误。定义S为校验子（伴随式）：S=RH t=CH t+EH t=EH T 或ST=HR t=HC t+HE t=HE T（本教材的表示方法）S=sr,sr-1, s= Sn-k-k-l, S可以看出：如果校验子矢量S工0,接收码字一定有错误，如果 校验子

13、矢量S=0,译码器认为接收码字无错误。F面通过例子说明校验子的作用。（7,4）汉明码的基本监督矩阵H为已知,H0 1 11 1 0 01 0 1 1 0 1 01 1 0 1 0 0 1由其得到的汉明码字如下表：00000000100100100010001101100000001010110110000000101001011001100111011011111101010010010010010011011010101010111011100110001110100000100110110111101110111111111110011100010111假如接收码字为R=0100101可以

14、看到:ST=HR t=0这时表明无差错;如果接收码字有一位差错，R=0110101;即错误图样E=0010000;接收码字的第三位错。这时校验子矢量为:ST0 =信息论课程讲义（第六章）10 11110 01110 110 1001110 10 0 11001相当于:0 11110 01110 110 100=1110 10 0 1000000ST可见这时校验子ST不为0,译码器认为有错，且正好等于H的 第三列，表明接收码字的第三位码元错了。这时判断发送码字位0100101，译码正确。如果接收码字由两位差错，R=011_1101；即错误图样E=0011000;接收码字的第三、四位错。这时校验子

15、矢量为:0 11110 01010 110 101=0110 10 0 10100ST00可见这时，校验子矢量不为0,但是如果这时接收机按原来的译码方法，将认为第7位出错。但如果接收机设计为检错系统，当校验 子不为0，就认为有错。因为（7,4）汉明码的最小码距为3，其纠错检 错能力是正确的。注意：这里告诉我们一个问题，纠错码的选用要小心，要根据信 道条件来确定，如果信道较差，而使用的纠错码能力不够，可能使译码错误反而增加，不仅错误的码元没有纠正，原来正确的码元还被错 误的改变。错上加错。这种纠检错能力是由码组的最小码距决定的。可以验证：下面的（7,3）线性分组码的最小码距为 4,可以纠一位错，

16、同时检两位错，其基本监督矩阵为:00011 0 1 1 0 0H111 0 1 01 1 0 0 0 00 1 1 0 0 06-1-5分组码的纠检错能力已知（n ,k）分组码的最小码距，就可以知道其纠检错能力，例如,当最小码距为4时，可以纠一位错，同时检两位错，也可以用于检三 位错，这与上一章介绍的结论是一样的。这里将进一步介绍有关性质。定理1：任一个（n,k）线性分组码，若要纠正t位错误，其充要条件是一致监督矩阵H中的任何2t个列向量线性无关。或者说：若使一个（n,k）线性分组码的最小码距为d其一致监督矩阵H中的任何d-1个列向量线性无关。或者说：若使一个（n,k）线性分组码的最小码距d，

17、等于一致监督矩阵H中和为0的最小列数。推理1：改变一致监督矩阵的列的位置，不会影响列的相关性,也就不会影响其最小码距。但可能产生不同的码组，其纠错检错能力 是相同的。根据这个推理，非系统汉明码的一致监督矩阵，经过列换位，可以得到系统汉明码的一致监督矩阵。例如：（7,4）非系统汉明码的监督矩阵位,H将其进行列换位,H0可以得到:100由于前面1列的位置可以任意放置，编出的码字可以不同，但纠错能力是相同的。推理2： （n,k）线性分组码的最小码距dmin的最大值为n-k+1=r+1。dmin r+1这说明,要想提高纠检错能力，只能增加监督元的位数。例如:H这个监督矩阵的最小码距位dmin=4，因为

18、，它由d-1=3个列向量线性无关，任何两个列或三个列相加都不为0。这时最小码距达到其最大值。实际上这是一个n=4, k=1, r=3的简单重复码,0 00001 1111它可以纠一位，同时检两位，或检 4位。定理2:线性分组码的最小码距等于非 0码字的最小码重。分组码的检错能力:最小码距为dmin的分组码，能检出所有dmin-1位或更少位错误 的错误图样。它不能检测出所有的dmin位错误，但可以检出一些（大部分）dmin位或更多位的码元错误。事实上，（n,k）码能检出长度为n的2n-2k个错误图样。因为为禁 用码字的个数，收到禁用码字就等于检出错码。令一个（n,k）线性分组码，Ai为码组中重量

19、为i的码字的个数，码 字集合（码组）的重量分布为 Ao,Ai,An。这时码字在误码率（转移概率）为Pe的BSC信道上的漏检概率为:nPU =送 AiPe(1 - Pe)2i吕其中Pei（1-pyi为错误图样（环,編1,e中出现i个1, n-i个0的概率,Ai为此错误图样分布正好错成许用码字的数量。 也就是错误图样等于 许用码字的可能性就是漏检概率。4）汉明码的重量分布为AO=1,A1=A2=O,A3=A4=7,A5=A6=O,A7=1。Pu=7p3(1-p)4+7 p4(1- p)3+p7（根据公式A0 一项没用，所以只有三项）当Pe=10-2时，漏检概率为7X 10-6。可见其实际检错能力远

20、远高于最低检错能力。如果按照最小码距与检错能力的分析，其漏检概率为:n7Pu =2 cnp e（1-c7p e（1- p。）7i工十i =3但是对于短码可以这样计算，对于长码，这样计算是很困难的。t个或更少的错分组码的纠错能力:当(n ,k)分组码的最小码距为d=2t+1，它可以纠正误。但实际上，纠错能力为t的分组码还可以纠正一些t+1位或更多位错误的错误图样(在后面的译码原理分析中可以看出)，但较难精确计算，其错误译码概率的上限为:npe 3,码长和信息位长度分别为 n=2r-1和k=n-r。码长必须为奇数,信息位是受到限制的。因此人们通过进一步研究，发现了一些由汉明 码引出的线性分组码，它

21、们不属于狭义汉明码，但有时也称为汉明码, 可以理解为广义汉明码。例如（7,3）汉明码，不是狭义汉明码，因为这时r=4,如果按照狭义汉明码的定义，码长应当为n=2r-1=15。F面我们看一下引出码的例子。(4)对偶码:从线性空间的零化空间的概念可以知道，如果一个矢量空间的有 两个子空间，其中一个子空间的每一个矢量都与另一个子空间的每一 个矢量正交，则称这两个子空间互为正交空间，或互为零化空间，也 叫作对偶空间。由线性分组码的一致监督矩阵H和生成矩阵G的基本定义可知，生成矩阵的每一个行向量均为一个码字，因此有HGt=O，这 说明H与G互为零化空间，而且分别为n维线性空间Vn的r维和k 维子空间。如

22、果H和G分别是码字C的监督矩阵和生成矩阵，则将H d=G作为监督矩阵，G d=H作为生成矩阵，则可以产生一个(n,n-k)线性分组码Cd，称C和Cd互为对偶码。例如：(7,4)分组码的对偶码为一种(7,3)分组码。(2,1)(n,k)如果一种码的对偶码是它本身，贝帰此码为自对偶码。例如 重复码就是自对偶码。(5)缩短码:在实际使用中，为了得到希望的码长和信息位长度，有时将 汉明码的信息位减少若干个(i)码元，这时构成一种(n-i,k-i)分组码，这 种码称为原码的缩短码。例如：(7,4)汉明码的缩短码为(6,3)码，其一致监督矩阵由原来的H将第一列去掉而得到。Hs1 1 1 1 0 00 1 1 0 1 01 0 1 0 0 1(