《编码理论 第二版 教学课件 ppt 作者 田丽华 第6-11章 第6章》由会员分享，可在线阅读，更多相关《编码理论 第二版 教学课件 ppt 作者 田丽华 第6-11章 第6章（107页珍藏版）》请在金锄头文库上搜索。
1、第6章 线性分组码,6.1 线性分组码的基本原理 6.2 线性分组码矩阵表述 6.3 线性分组码的编码及译码 6.4 汉明码及其他纠错码,6.1 线性分组码的基本原理 6.1.1 基本概念 在通信系统中，为了能在接收端发现和纠正信息传输中产生的错误，发送端需要对所传输的数字信息序列进行编码。首先，把信息序列按一定长度分成若干信息码组，每组由相继的k位信息数字组成；然后，编码器按照预定的线性运算规则(可由线性方程组来规定)把信息码组变换成n(nk)重码字，如图61所示。,图61 线性分组码编码器,n-k个附加码元是由信息码元的线性运算产生的,此码叫做（n,k）线性分组码。如果一个(n，k)线性分
2、组码的数域为GF(p)，即每一个码元可能有p种取值，则信源可发出pk种不同的消息组。为使接收端对码字惟一可译,即当从n位长的码字中译出k位的消息时，消息组与码字之间应有一一对应的关系，因此编码器至少要存储pk个码字才能实现消息到码字的变换(当k比较大时，这种编码器就显得有些不切实际)。为了压缩编码器的存储容量，通常对编码器附加一个线性约束条件，使得线性码的校检位与信息位之间呈线性关系。对于二进制码，(n，k)线性分组码(以后简称为(n，k)码)共有2k个码字，它们构成k维子空间的主要特征是：在加法运算下满足封闭性；在2k个码字中只有k个是线性独立的。,(n，k)码除具有封闭性外，还满足加法交换
3、律和加法结合律。因为(n，k)码的pk个码字集合构成可交换的加法群，所以线性码又称为群码。 对(n,k)码通过预定的线性运算，可将长为k位的信息码组变换成n(nk)重的码字。由pk个信息码组编成的码字集合称为(n,k)码许用码字,由pn-pk个除了许用码字之外的码字集合称为禁用码字。,码组是所有码字的集合。一个n重的码字C可以用矢量C=cn-1cn-2c1c0来表示，所以码字又称为码矢。 对(n，k)线性码，用Rkn表示码字中信息位所占的比重，叫做编码效率或编码速率，简称码率。它说明了信道利用效率，所以也叫做传信率。R越小，冗余度就越大,即在一个码字中添加给每个信息符号的冗余符号越多。一个码组
4、的冗余符合越多，检错和纠错的能力越强，但也降低了传输信息的实际速率。R越大，码的效率也就越高或传信率越高。R是衡量码性能的一个重要参数。,如上所述，信道编码就是给已知信息组按预定规则添加监督码元，以构成码字。在k个信息元之后附加r(rnk)个监督码元，使每个监督元是其中某些信息元的和。例如，信息分组长度k3，在每一信息组后加上4个监督元，构成(7，3)线性分组码。设该码的码字为c6c5c4c3c2c1c0，其中c6、c5、c4为信息元;c3、c2、c1、c0为监督元，每个码元取值为“0”或“1”，即ciGF(2)。监督元可按下面方程组计算：,（6）,式(61)为一线性方程组，它确定了由信息元得
5、到监督元的规则，所以称为监督方程或校验方程。由于所有码字都按同一规则确定，因此式(61)称为一致监督方程或一致校验方程，所得到的监督元称为一致监督元或一致校验元，这种编码方法称为一致监督编码或一致校验编码。因为一致监督方程是线性的，亦即监督元和信息元之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。利用式(61),每给出一个3位的信息组，就可编出一个码字，如表61所示。,表61 （，）分组码编码表,6.1.2 码的重量和码的距离 在信道编码中，定义码字中非零码元的数目为码字的汉明（Hamming)重量，简称码重。例如“010”码字的码重为1，“011”码字的码重为2。把两个码字
6、之间对应码位上具有不同二元码元的位数定义为两码字的汉明距离，简称码距。在一种编码中，任意两个许用码字间距离的最小值，即码字集合中任意两码字间的最小距离，称为这一编码的最小汉明距离，以dmin表示；在非零码字中，重量最小者称为该码的最小汉明重量。,通常，用d(C1，C2)表示两个n重C1、C2之间的汉明距离，则汉明距离有以下三个性质： (1)对称性：d(C1，C2)d(C2，C1)； (2)非负性：d(C1，C2)0； (3)满足距离三角不等式：d(C1，C2)d(C1，C3)d(C3，C2)。,最小距离dmin与码率R是码的两个最主要的参数， dmin表示了码的纠错能力。以后用（n，k，dmi
7、n）表示最小距离为dmin，码率为Rkn的线性分组码。纠错码的基本任务之一就是构造出R一定且dmin尽可能大的码，或dmin一定且R尽可能大的码。在3位二元码字中，如8种码字都作为许用码字时，任两组码间的最小距离为1，称这种编码的最小码距为1，记作dmin1。 已知(n，k，d)线性分组码的最小距离dminnk1。若系统码的最小距离dminnk1，则称此码为极大最小距离可分码，简称MDS码。,6.1.3 码的检错及纠错能力 下面讨论码的检错、纠错能力与最小码距的数量关系。在一般情况下，对于分组码有以下结论： (1)若一个码组内能检测e个错码，则要求最小码距为,dmine1,(62),或者说，若
8、一种编码的最小距离为dmin，则它最多能检出dmin-1个错码。式（62）可以通过图62（a)来说明。图中C表示某码组，当误码不超过e个时，该码组的位置将不超出以C为圆心、e为半径的圆(实际上是多维的球)。只要其他任何许用码组都不落入此圆内，则C码组发生e个误码时就不可能与其他许用码组相混。这就证明了其他许用码组必须位于以C为圆心，以e1为半径的圆上或圆外，所以，该码的最小码距dmin为e1。,图62 码距与检错、纠错能力的关系,(2) 若一个码组内能纠正t个错码，则要求最小码距为,dmin2t1,(63),或者说，若一种编码的最小码距为dmin，则它最多能纠正（dmin1）/2个错码。式（6
9、3）可以用图62(b)来说明。图中C1和C2分别表示任意两个许用码字，当各自错码不超过t个时，发生错码后两个许用码字的位置移动将分别不会超出以C1和C2为圆心、t为半径的圆。只要这两个圆不相交，则当错码小于t个时，可以根据它们落在哪个圆内而正确判断为C1或C2码字，即可以纠正错误。而以C1和C2为圆心的两个圆不相交的最近圆心距2t1就是纠正t个错误的最小码距了。,(3)若在一个码组内能纠正t个错码，同时也能检测e(et)个错码，则要求最小码距为,dminet1 (et),(-4),这里所说的能纠正t个错码，同时能检测e个错码的含义是：当错码不超过t个时，码组能自动予以纠正；而当错码超过t个时，
10、则不可能纠正错误，但仍可检测e个错码，这正是混合检错、纠错的控制方式。可以用图62(c)来说明式(64)。图中C1和C2分别为两个许用码字，在最不利情况下，C1发生e个错码而C2发生t个错码，为了保证这时两码字不发生相混，则要求以C1为圆心、e为半径的圆必须与以C2为圆心、t为半径的圆不发生交叠，即要求最小码距dminet1。同时，还可以看到当错码超过t个时，两圆也有可能相交，因而码组不再有纠错的能力，但仍可检测e个错码。,(4)若一个码组内能纠正t个错误和P个删除，则要求最小码距为,(65),这里所说的删除是指已知错误产生的位置，但不知错误值的大小。,【例61】 已知GF(2)中一个码组的全
11、部码字为 如果将此码用于检错,能检出几位错码?如果将此码用于纠错,能纠出几位错码?如果将此码同时用于检错和纠错,能检出几位错码?纠出几位错码?,000 000,001 110 ,010 101,011 011,100 011,101 101,110 110,解 由8个码字可得码组的最小汉明距离dmin=3。 若检测e个错码，则要求最小码距：dmine1，则e2，此码最多可以检出2位错码； 若纠正t个错码，则要求最小码距：dmin2t1，则t1，此码最多可以纠出1位错码； 若既能纠正t个错码，同时又能检测e(et)个错码，则要求最小码距：dminet1(et)，则e=2，t=0，此码只能检错，不
12、能纠错。,6.1.4 线性分组码的性质 一个线性分组码具有下述性质： (1)两个属于该码组码字的和仍是一个属于该码组的码字。 (2)全零码字总是码组中的一个码字。 (3)一个线性码组中两个码字之间的最小距离等于任何非零码字的最小重量。 如果两个码字的和是另外一个码字，该两个码字的差也将仍然是一个合法码字。例如，若C1、C2和C3是码字，且C1+ C2 = C3，那么有C3 -C1=C2。所以，对一个线性分组码，全零码字必为一个合法码字。,【例62】 已知GF(2)中码组C=0000,1010,0101,1111是一个分组长度n=4的线性分组码。观察码字之间所有十种可能的和：,0000+0000
13、=0000,0000+1010=1010,0000+0101=0101, 0000+1111=1111,1010+1010=0000,1010+0101=1111, 1010+1111=0101,0101+0101=0000,0101+1111=1010, 1111+1111=0000,它们都在C中，全零码字也在C中。该码组的最小距离为dmin=2。为了验证这个线性码的最小距离，可计算所有码字对（共6对）之间的距离:,显然这个码组的最小距离为2。,设S为一个长度为n且分量在GF(p)上的向量集合。S中所有向量的线性组合构成的集合称为S的线性扩张，记为S。因此线性扩张是由S生成的GF(pn)的一
14、个子空间。给定GF(pn)的任意子集S，可以得到一个由S生成的线性码C=S，它恰好包含下列码字：全零码字;S中所有的字;S中两个或两个以上的字的所有线性组合。,【例63】 设GF(2)中S=1100,0100,0011，S的所有可能线性组合为:1100+0100=1000，1100+0011=1111，0100+0011=0111，1100+0100+0011=1011。因此，C=S=0000，1100，0100，0011，1000，1111，0111，1011。可得该码组的最小距离dmin=1。,6.2 线性分组码矩阵表述 6.2.1 生成矩阵 在（n，k）线性分组码中，n表示码长，k表示信
15、息位的维数，也就是子空间的维数，将n个码字位和k个信息位之间的关系写成矩阵形式,即,CUG,(66),式中:,G为该线性分组码（n，k）码的生成矩阵，即,（67）,可见G建立了消息与码矢间的一一对应关系，它起着编码器的变换作用。因此C的每一位数字都是消息数字的线性组合。应该指出，一个子空间的基底矢量的选择不是惟一的，所以生成矩阵G的选择也不是惟一的。,【例64】 已知(7，3)线性分组码，设该码的码字为C=c6c5c4c3c2c1c0，其中c6、c5、c4为信息元;c3、c2、c1、c0为监督元，每个码元取值为“0”或“1”，即ciGF(2)。监督元可按式(61)方程组计算。求生成矩阵。 解
16、因为信息位分别为u2、u1、u0，则码元为:,c6=u2 c5=u1 c4=u0 c3=u2+u0 c2=u2+u1+u0 c1=u2+u1 c0=u1+u0,又因为,C=c6 c5 c4 c3 c2 c1 co，U=u2 u1 u0,，由C=UG，所以,这种形式不同的生成矩阵仅表示消息与码字之间不同的一一对应关系，但2k个消息的集合却对应着同一个（n，k）码的码字空间。,【例65】 已知GF(2)中码生成矩阵分别为：,求：G1和G2分别对应的码字空间？,表62 用不同的生成矩阵得到的线性码,6.2.2 监督矩阵 在线性分组码（n，k）中，因为监督元和信息元间是线性关系，若设CT、0T及HT分别为C、0、H的转置矩阵，所以每个码字中r（rnk）个监督元和信息元之间
