信息论与编码第6.ppt

第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)线性分组码的数域为GF(p)，即每一个码元可能有p种取值，则信源可发出pk种不同的消息组。为使接收端对码字惟一可译,即当从n位长的码字中译出k位的消息时，消息组与码字之间应有一一对应的关系，因此编码器至少要存储pk个码字才能实现消息到码字的变换(当k比较大时，这种编码器就显得有些不切实际)。为了压缩编码器的存储容量，通常对编码器附加一个线性约束条件，使得线性码的校检位与信息位之间呈线性关系。对于二进制码，(n，k)线性分组码(以后简称为(n，k)码)共有2k个码字，它们构成k维子空间的主要特征是：在加法运算下满足封闭性；在2k个码字中只有k个是线性独立的。,(n，k)码除具有封闭性外，还满足加法交换律和加法结合律。因为(n，k)码的pk个码字集合构成可交换的加法群，所以线性码又称为群码。对(n,k)码通过预定的线性运算，可将长为k位的信息码组变换成n(nk)重的码字。由pk个信息码组编成的码字集合称为(n,k)码许用码字,由pn-pk个除了许用码字之外的码字集合称为禁用码字。,码组是所有码字的集合。一个n重的码字C可以用矢量C=cn-1cn-2c1c0来表示，所以码字又称为码矢。对(n，k)线性码，用Rkn表示码字中信息位所占的比重，叫做编码效率或编码速率，简称码率。它说明了信道利用效率，所以也叫做传信率。R越小，冗余度就越大,即在一个码字中添加给每个信息符号的冗余符号越多。一个码组的冗余符合越多，检错和纠错的能力越强，但也降低了传输信息的实际速率。R越大，码的效率也就越高或传信率越高。R是衡量码性能的一个重要参数。,如上所述，信道编码就是给已知信息组按预定规则添加监督码元，以构成码字。在k个信息元之后附加r(rnk)个监督码元，使每个监督元是其中某些信息元的和。例如，信息分组长度k3，在每一信息组后加上4个监督元，构成(7，3)线性分组码。设该码的码字为c6c5c4c3c2c1c0，其中c6、c5、c4为信息元;c3、c2、c1、c0为监督元，每个码元取值为“0”或“1”，即ciGF(2)。监督元可按下面方程组计算：,（6）,式(61)为一线性方程组，它确定了由信息元得到监督元的规则，所以称为监督方程或校验方程。由于所有码字都按同一规则确定，因此式(61)称为一致监督方程或一致校验方程，所得到的监督元称为一致监督元或一致校验元，这种编码方法称为一致监督编码或一致校验编码。因为一致监督方程是线性的，亦即监督元和信息元之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。利用式(61),每给出一个3位的信息组，就可编出一个码字，如表61所示。,表61（，）分组码编码表,6.1.2码的重量和码的距离在信道编码中，定义码字中非零码元的数目为码字的汉明（Hamming)重量，简称码重。例如“010”码字的码重为1，“011”码字的码重为2。把两个码字之间对应码位上具有不同二元码元的位数定义为两码字的汉明距离，简称码距。在一种编码中，任意两个许用码字间距离的最小值，即码字集合中任意两码字间的最小距离，称为这一编码的最小汉明距离，以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，dmin）表示最小距离为dmin，码率为Rkn的线性分组码。纠错码的基本任务之一就是构造出R一定且dmin尽可能大的码，或dmin一定且R尽可能大的码。在3位二元码字中，如8种码字都作为许用码字时，任两组码间的最小距离为1，称这种编码的最小码距为1，记作dmin1。已知(n，k，d)线性分组码的最小距离dminnk1。若系统码的最小距离dminnk1，则称此码为极大最小距离可分码，简称MDS码。,6.1.3码的检错及纠错能力下面讨论码的检错、纠错能力与最小码距的数量关系。在一般情况下，对于分组码有以下结论：(1)若一个码组内能检测e个错码，则要求最小码距为,dmine1,(62),或者说，若一种编码的最小距离为dmin，则它最多能检出dmin-1个错码。式（62）可以通过图62（a)来说明。图中C表示某码组，当误码不超过e个时，该码组的位置将不超出以C为圆心、e为半径的圆(实际上是多维的球)。只要其他任何许用码组都不落入此圆内，则C码组发生e个误码时就不可能与其他许用码组相混。这就证明了其他许用码组必须位于以C为圆心，以e1为半径的圆上或圆外，所以，该码的最小码距dmin为e1。,图62码距与检错、纠错能力的关系,(2)若一个码组内能纠正t个错码，则要求最小码距为,dmin2t1,(63),或者说，若一种编码的最小码距为dmin，则它最多能纠正（dmin1）/2个错码。式（63）可以用图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个时，则不可能纠正错误，但仍可检测e个错码，这正是混合检错、纠错的控制方式。可以用图62(c)来说明式(64)。图中C1和C2分别为两个许用码字，在最不利情况下，C1发生e个错码而C2发生t个错码，为了保证这时两码字不发生相混，则要求以C1为圆心、e为半径的圆必须与以C2为圆心、t为半径的圆不发生交叠，即要求最小码距dminet1。同时，还可以看到当错码超过t个时，两圆也有可能相交，因而码组不再有纠错的能力，但仍可检测e个错码。,(4)若一个码组内能纠正t个错误和P个删除，则要求最小码距为,(65),这里所说的删除是指已知错误产生的位置，但不知错误值的大小。,【例61】已知GF(2)中一个码组的全部码字为 如果将此码用于检错,能检出几位错码?如果将此码用于纠错,能纠出几位错码?如果将此码同时用于检错和纠错,能检出几位错码?纠出几位错码?,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，此码只能检错，不能纠错。,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=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)的一个子空间。给定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表示信息位的维数，也就是子空间的维数，将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)方程组计算。求生成矩阵。解因为信息位分别为u2、u1、u0，则码元为:,c6=u2c5=u1c4=u0c3=u2+u0c2=u2+u1+u0c1=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）个监督元和信息元之间的关系为,HCT0T 或 CHT0,（68）,H称为(n,k)线性码的一致监督矩阵，即,式中：,Ccn1 cn2.cl c0。,【例66】已知(7，3)线性分组码，设该码的码字为C=c6c5c4c3c2c1c0,其中c6c5c4为信息元;c3c2c1c0为监督元，每个码元ciGF(2)。监督元可按式(61)方程组计算。求监督矩阵。解因为,c6=u2c5=u1 c4=u0,则由监督方程得,c3u2u0c6c4c2u2u1u0c6c5c4c1u2u1c6c5 c0u1u0c5c4,因为,6.2.3等价码及系统码如果一个线性P元码可由另一个通过下面一种或两种运算得到，则称它们为等价码。该运算为：(1)用非零常量去乘它的分量；(2)对码的位置做置换。,定理61两个kn矩阵,若一个可以由另一个通过一系列下述变换得到，则它们生成的GF(p)上的(n，k)线性码等价：（1）对行置换；(2)对行乘以一个非零常量；(3)把一行乘以一个常量然后加到另一行上；（4）对列置换；（5）对任意列乘以一个非零常量。,前三种运算（只是行变换）保留了生成矩阵的行的线性独立性，变换只是改变了基。最后两种运算（列变换）把矩阵变成能生成等价码的一个矩阵。由例65中G2生成的码，因其前k位与消息完全相同，则称这种码为系统码。系统码的编码器仅需存储k(n-k)个数字(非系统码要存储kn个数字)，译码时仅需对前k个信息位纠错即可恢复消息。由于系统码的编码和译码都比较简单，而且性能也与非系统码一样，因此系统码得到了十分广泛的应用。,系统码的生成矩阵可用分块矩阵表示为,GIkP,(610),式中：Ikkk阶单位方阵；Pk(n-k)阶阵。由此G生成的码称为系统码，否则称为非系统码。显然,在系统码的码组 C(cn1，cn2，c0)中，前k位(cnl，cnk)(u1，uk)是信息位，后nk位(cnk，c)称为码字的校验位。,对上节所讲的一致监督矩阵H各行实行初等变换，并将后r列化为单位子阵，则,HQIr,(611),把变换所得的后面r列是一单位子阵的监督矩阵H称为监督矩阵H的标准形式。H阵的一般形式可通过行的线性变换化成标准形式。利用标准形式的H阵进行编、译码很方便，所以H阵的标准形式是一种常用形式。显然，H阵的每一行都代表一个监督方程，它表示与该行中“1”相对应的码元的和为0，因而,H的标准形式还说明了相应的监督元是由哪些信息元决定的。H阵的r行代表了r个监督方程，也表示由H所确定的码的码字有r个监督元，那么为了得到确定的码，r个监督方程(或H阵的r行)必须是线性独立的，这就要求H阵的秩为r。若要把H阵化成标准形式，只需检查单位子阵的秩，就能方便地确定H阵本身的秩。,在前面我们讨论了线性分组码的生成矩阵和监督矩阵，它们二者之间有无联系呢？回答是肯定的。(n，k)线性码的G和H之间有非常密切的关系。由于生成矩阵G的每一行都是一个码字，所以G的每行都满足HCT0T，则有：因此，线性码的生成矩阵G和监督矩阵H的行矢量彼此正交。那么，由生成矩阵的行矢量张成的k维子空间和由监督矩阵行矢量张成的nk维子空间互为零空间。由式(610)、(611)及式(612)得：,HGT0T 或 GHT0,(612),GHTIkpQIrTQTp0,（613）,所以 由此可得：GIkPIkQT 或 HQIrpTIr因而线性系统码的监督矩阵H和生成矩阵G之间可以相互直接转换。例如，已知(7，4)线性系统码的监督矩阵为,PQT 或PTQ,（614）,（615）,可直接写出它的生成矩阵为,6.2.4对偶码及缩短码对一个(n，k)线性码CI，由于HGT0T，如果以G作监督矩阵，以H作生成矩阵，可构造另一个码CJ，码CJ是一个(n,nk)线性码，则称码CJ为原码CI的对偶码。显然，由于对偶码是原码的生成矩阵和监督矩阵互换后所构成的码，所以对偶码的码字与原码的码字彼此正交，而它们的码字集合分别构成的两个子空间是互为零化空间。例如，(7，4)线性码的对偶码是(7，3)码，那么(7，3)码的监督矩阵H（7，3）是(7，4)码的生成矩阵G（7，4），即,而（7，3)码的生成矩阵G（7，3)是(7，4)码的监督矩阵H（7，4），即,H（7，3）G（7，4）,H(7，4),G（7，3）,为了将由原码的监督矩阵和生成矩阵交换后所得对偶码的生成矩阵和监督矩阵化成标准形式，需在交换后对矩阵的行作初等变换，此变换过程可简单地将单位子阵由前移到后，或由后移到前，无需作繁琐的运算。由前面的讨论可知，若已知消息U，可从G求出监督元，也可从H求得同样的监督元。因此线性分组码的性质完全由G或H决定。对于一个具体的矩阵来说，它既可以作为生成矩阵将消息变换成码字，也可作为一致校验矩阵将消息变换成另一种码字，这样所得的两种码称为对偶码，前者如果是(n，k)码，那么后者一定是(n，n-k)码。,G（7，3）和H(7，4)这两个矩阵利用初等交换可以互相转化，根据矩阵代数理论可知它们是等价的。G(7,3)是(7,3)码生成矩阵的标准形式，H(7,4)是(7，4)码一致校验矩阵的标准形式，两者可以编出互为对偶码的(7，3)码和(7，4)码，如表63和表64所示。在(7，3)码的码字集合中，如果将最左面一位为0的消息和对应的码字挑选出来，并把最左面的0删去，则它们构成(6，2)线性分组码，如表65所示。这种码叫缩短码。,表63G（7，3）编出的（7，3）码,表6-4 H（7，4）编出的（7，4）码,表65缩短的(6，2)码,求缩短码的生成矩阵和一致监督矩阵是很方便的，如(6，2)码的生成矩阵就是将(7，3)码的生成矩阵的最上面一行和最左面一列删去，将(7，3)码的一致校验矩阵的最左面一列删去就是(6，2)码的一致监督矩阵，即,6.3线性分组码的编码及译码 6.3.1线性分组码的编码(n，k)线性码的编码就是根据线性码的监督矩阵或生成矩阵将长为k的信息组变换成长为n(nk)的码字,即先求出信息元和码元之间的关系,再利用此关系构造编码电路。若由监督矩阵和生成矩阵求出的信息元和码元之间关系的结果是一致的，则编码电路也相同。因为生成矩阵和监督矩阵只是以不同方式来描述同一码的结构而已。,下面利用监督矩阵来构造(7，3)线性分组码的编码电路。设二元码字为,Cc6c5c4c3c2c1c0,码的监督矩阵为,图63线性系统码编码电路,6.3.2标准阵列及译码设C是GF(p)上的一个(n，k)码，a是长为n的任意向量。则将集合,（616）,称为C的一个陪集(Coset)。当(a-b)C时，称a和b属于同一个陪集。,定理61假设C是(p)上的一个(n，k)码，则(1)任意长为n的向量b都属于C的某个陪集；(2)每个陪集恰好包含pk个向量；(3)两个陪集或者不相交或者完全重合(不可能部分相交)；(4)若a+C是C的一个陪集，且b(a+C)，则b+C=a+C。证明(1)b=b+0b+C。(2)注意到xa+x是Ca+C上的一一映射，因此a+C含有的元素个数与C相同，即等于pk。,(3)假设a+C与b+C相交，即它们至少有一个公共向量。设v(a+C)(b+C)。则必存在x,yC使,（617）,（618）,其中,zC（因为两个码字的差也是一个码字）。固有,（619）,类似地，可以证明(a+C)(b+C)。由此可得（b+C）=（a+C）。,（4）因为b(a+C)，这表明对某个xC有b=a+x。对任意(b+y)(b+C)有b+y=(a+x)+y=a+(x+y)(a+C)（620）因此(b+C)(a+C)。另一方面，对任意(a+z)(a+C)，有a+z=(b-x)+z=b+(z-x)(b+C)（621）因此(a+C)(b+C),从而b+C=a+C。证毕一个陪集中具有最小重量的向量称为陪集首(CosetLeader)。如果有多余一个向量具有最小重量，则从中随机选择一个定为陪集首。,【例67】设C为一个二元（3，2）码，其生成矩阵如下：,码字C=000,010,101,111。C的陪集为:,所有的8个向量都被这两个陪集覆盖了。如果a+C是C的一个陪集而且b(a+C)，则有b+C=a+C。因此，上面已经列出了所有陪集。为了方便演示，以下写出全部的可能情况：,由此可以看到所有陪集已经被覆盖了。,因为两个陪集或不相交或重合，所以GF(qn)上的所有向量可以写为 一个(n,k)码组C的标准阵列(Standard Array)是一个GF(pn)上全部向量的pn-kpk阵列,它的第一行由码组C构成(0码字在最左边),其它行是陪集ai+C,都以相应次序排列,陪集首放在最左边。,t=qn-k-1,设二元(n，k)线性码用来纠错，发送码字取自于2k个码字集合Ci。码字经信道传输后，接收码字R可以是2n个n重矢量中的任一个。任何译码方法，都是把2n个n重矢量划分为2k个互不相交的子集D1，D2，D2k，使得在每个子集中仅含一个码字。根据码字和子集间一一对应关系，若接收字Rx落在子集Dx中，就把Rx译为子集Dx含有的码字Cx。所以，当接收字R与实际发送码字在同一子集中时，译码就是正确的。,对给定的（n，k）线性码，将2n个n重划分为2k个子集的一种方法是构造所谓的“标准阵列”。其方法如下：先将2k个码字排成一行，作为“标准阵列”的第一行，并将全0码字C1000放在最左面的位置上；然后在剩下的2n2k个n重中选取一个重量最轻的n重E2放在全0码字C1的下面，再将E2分别和码字C2，C3，相加，放在对应码字下面构成阵列第二行，在第二次剩下的n重中，选取重量最轻的n重E3，放在E2下面，并将E3分别加到第一行各码字上，得到第三行；，继续这样做下去，直到全部n重用完为止，按上述方法所构造的标准阵列如表6-6所示：,表66(n，k)线性码的标准阵列,定理6-2 在标准阵列的同一行中没有相同的变量，而且2n个n重中任一个n重在阵列中必出现一次且仅出现一次。证明 因为阵列中任一行都是由所选出某一n重变量分别与2k个码字相加构成的，而2k码字互不相同，它们与所选变量的和也不可能相同，所以在同一行中没有相同的变量。在构造标准阵列时，是用完全部n重为止，因而每个n重必出现一次。另外，假定某一n重X出现在第y行第i列，那么XEyCi，又假设X出现在第m行第j列，则有XEmCj，yy)的第一个元素，而按阵列构造规则：后面行的第一个元素是前面行中未曾出现过的元素，这就和阵列构造规则相矛盾。因而任何n重不可能在阵列中出现两次。证毕,由上可知，(n，k)线性码的标准阵列有2k列(和码字数相等)，2n2k2nk行，且任何两列和两行都没有相同的元素，即列和行都不相交。标准阵列的每一行叫做码的一个陪集，每个陪集有相同的错误图样。每个陪集的第一个元素叫做陪集首，每一列包含2nk个元素，最上面的是一个码字，其它元素是陪集首和该码字之和，例如第j列即为：若发送码字为Cj，信道干扰的错误图样是陪集首，则接收字R必在Dj中，此时接收字R正确译为发送码字Cj；若错误图样不是陪集首，则接收字不在Dj中，则译成其它码字，造成错误译码。因而当且仅当错误图样为陪集首时，译码才是正确的。所以，这2nk个陪集首称为可纠正的错误图样。,DjCj，E2Cj，E3十Cj，Cj,(623),由于陪集首是可纠的错误图样，为了使译码错误概率最小，应选取出现概率最大的错误图样作陪集首。已知重量较轻的错误图样出现概率较大，所以在构造标准阵列时是选取重量最轻的n重码字作陪集首。这样，当错误图样为陪集首(可纠的错误图样)时，接收码字与发送码字间的距离(等于陪集首)最小。因此，选择重量最轻的元素作陪集首，按标准阵列译码就是按最小距离译码，所以，标准阵列译码法也是最佳译码法。,【例68】已知二元(4,2)线性分组码生成矩阵为 求:(1)系统的标准阵列。(2)若接收码字R=1010,错误图样E=0100,求对应的码字,并判断译码有无错误。(3)若接收码字R=1010,错误图样E=0110,求对应的码字,并判断译码有无错误。,解(1)由C=UG得系统的码组为0000,0111,1001,1110所构造的标准阵列如表67所示。,表67（4，2）线性码的标准阵列,标准阵列中的第一行是4个码字，其中码字0排在左边，然后在剩下的12个码字中，挑选一个重量最小的码字(例如1000)作为第二行的陪集首。将1000与第一行中所有的码字相加，就得到第二行。接着，在剩下的8个矢量中选取0100为第三行的陪集首，等等。在这个例子中，陪集首的重量皆为1，但对于其他的码，陪集首的的重量可能为2，3，4，。,(2)当接收字R1010时，在表67的第3行第4列中找到了它，于是就可以把R译成位于第4列的码字U1110。显然，位于第3行的陪集首0100是错误图样E，因此译码正确,表示信道第2位有错。由此可见，译码正确与否的关键在于信道错误向量是否是陪集首。因为将R译为与它最接近的码向量U，所以符合最大似然译码准则。(3)当接收字R1010时，在表67的第3行第4列中找到了它，于是就可以把R译成位于第4列的码字U1110。显然，位于第3行的陪集首0100不是错误图样E=0110，因此译码不正确。由此可见，译码正确与否的关键在于信道错误向量是否是陪集首。因为将R译为与它最接近的码向量U，所以符合最大似然译码准则。,【例69】设二元(6，3）码的生成矩阵为,表68（6，3）线性码的标准阵列,求：(1)若接收码字R=111011,错误图样E=010000,求对应的码字,并判断译码有无错误。(2)若接收码字R=100111,错误图样E=001100,求对应的码字,并判断译码有无错误。解（1）若接收字R111011，查表68可知它所在子集的估值101011，错误图样E010000和陪集首相同，因此译码正确。,（2）由于R100111，与此R对应的100110，但它的错误图样为E001100，它不在陪集首，属于错误译码。当n很大时，用标准阵列译码要存储2n个n重码字是不实际的。如当C为码长是100的二元码时，则C的标准阵列由2100个阵元组成，译码器必须存储它们，译码时还必须从中搜索接收码字R，这在工程实践上是很难实现的。然而利用伴随式译码可以使标准阵列译码过程得到简化。,6.3.3 伴随式及错误检测用监督矩阵编码，当然也用监督矩阵译码。当收到一个接收字R后，可用监督矩阵H来检验R是否满足监督方程，即HRT0T是否成立。若关系式成立，则认为R是一个码字，否则判为码字在传输中发生了错误。因此，HRT的值是否为0是检验码字出错与否的依据。把SRHT或STHRT，称为接收字R的伴随式(或监督子，或校验子)。设发送码字Ccn1 cn2 c0信道的错误图样为：,Eenl en2 eo,(624),式中：若ei0，表示第i位无错；若ei1，则表示第i位有错(in1，n2，0)。,那么，接收字R为,Rrn1 rn2.r0CE,cn1e n1 cn2十en2.coeo,（625）,将接收码字用监督矩阵进行检验，即可得接收码字的伴随式：,STHRTH(CE)THCTHET,（626）,由于HCT0T，所以,STHET,(627),将Hh1 h2 hn（hi表示H的列，i1，2，n。）代入式(6-27)得：,STh1en1h2en2.hne0,（628）,由上面分析得到如下结论：(1)伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定。(2)伴随式是错误的判别式为：若S0，则判没有出错，接收字是一个码字；若S0，则判有错。(3)不同的错误图样具有不同的伴随式，它们是一一对应的，二元码伴随式是H阵中与错误码元对应列之和。,【例610】二元(7，3)码的监督矩阵为,求：(1)若接收码字R1010011，计算接收码字伴随式,并判断传输中有没有发生错误。(2)若接收码字R1110011，计算接收码字伴随式,并判断传输中有没有发生错误。(3)若接收码字R0011011，计算接收码字伴随式,并判断传输中有没有发生错误。,解(1)若接收码字R1010011，接收端译码器根据接收码字R的计算伴随式为,因此，译码器判接收码字无错，即传输中没有发生错误。,(2)若接收码字R1110011，其伴随式为,由于ST0，译码器判为有错，即传输中有错误发生。(7，3)码是纠单个错误的码，且ST等于H的第二列，因此判定接收字R的第二位是错的。由于接收码字中错误码元数与码的纠错能力相符，所以译码正确。,(3)若接收码字R0011011，其伴随式为,ST不等于0，它既是H阵第一列和第四列之和，也是第二列和第七列之和，但与H阵的任何一列都不相同。当码元错误多于1个时，则无法判定错误出在哪些位上，只能发现有错。,伴随式的计算可用电路来实现，仍以(7，3)码为例，设接收码字Rr6r5r4r3r2r1r0，那么伴随式为,ST,图64(7，3)码伴随式计算电路,定理63在标准阵列中，一个陪集的所有2k个n重码字有相同的伴随式，不同陪集的伴随式互不相同。证明设H为给定(n，k)线性码的监督矩阵，在陪集首为Ey的陪集中的任意接收码字R为 其伴随式为,REyCi，i1，2，2k,SRHT(EyCi)HTEyHTCiHTEyHT,(629）,译码器存储该表后，在译码时就可以通过查表实现从伴随式到错误图样的转换，从而得到(n，k)线性码的一般译码步骤：（1）计算接收码字R的伴随式STHRT。（2）若ST0，则认为接收到的R没有错误；否则认为有错，根据伴随式和错误图样一一对应的关系，利用伴随式译码表，由伴随式译出R的错误图样。（3）将接收码字减错误图样，得发送码字的估值。,【例611】二元(4,2)线性分组码生成矩阵为,求：(1)系统的伴随式译码表。(2)若接收码字R=1101,估算对应的码字。解(1)系统的标准阵列如表67所示。因为错误图样为陪集首，由S=EHT计算对应的伴随式，则得伴随式译码表如表69所示。,表69(4,2)线性码译码表,(2)接收字R1110011，其伴随式为：,查译码表69，得错误图样,则码字估值。,【例612】设二元(6，3）码的生成矩阵为,求伴随式译码表。解线性码的标准阵列如表68所示，因为错误图样为陪集首，由S=EHT计算对应的伴随式，则得伴随式译码表如表610所示。,表610(6,3)线性码伴随式译码表,6.4汉明码及其他纠错码 6.4.1汉明码汉明码是一种特殊的(n，k，d)线性分组码，它的m元汉明码的参数n、k和d分别为：,二进制汉明码的参数n、k和d分别为：,由于汉明码的最小距离是3,故汉明码能纠正一个随机错误或检测2个错误,且码的校验矩阵H中任意2列线性无关。,6.4.2汉明码的构造汉明码的校验矩阵H由一切r(rnk)维非零二元向量排列而成，即的列为所有非零的r维向量组成，所以H的各列在并元和之下是封闭的，旦r给定，就可构造出具体的(n，k)汉明码。【例613】构造一个二元的（7，4，3）汉明码。这时rnk3，则有238个元素，除全0以外的其余7个元素，均可作为矩阵的列，所以该码的校验矩阵为,（630）,如果H矩阵形如：,（632）,有了H，按照HCT0就可得到系统码的校验位，表611就是按此方法编出的(7，4)汉明码。,表611(7，4)汉明码,一般地，相对应的系统汉明码的生成矩阵G为,GIkQT,（633）,所以(7，4，3)系统汉明码的生成矩阵G为,前面所举的分组码的例子都是二元的，下面我们举一个三元的汉明码，以示它们之间没有本质的差别。,【例614】求三元r3的汉明码的参数、H矩阵及G矩阵。根据汉明码的一般定义，得：,因为汉明码dmin3,只要任意两列线性无关，所以可以直接写出H矩阵如下(不是惟一的):,6.4.3汉明码的变形汉明码还有多种可能的变形，例如有截短汉明码和增长汉明码等等。若从汉明码的校验矩阵H中截去任意x列，便可得到一个r(2rx1)阶的矩阵H。如果用H作为校验矩阵，那么就可以得到另一个线性码，此码称为截短汉明码，它的各参数分别为：,码长 n2rx1信息位数 k2rrx1校验位数 rnk最小距离 dmin3,如果对H进行适当的截除，就可以提高截短汉明码的最小距离。如设HQ|Ir，从Q中截去所有重量为偶数的列，就得到一个r2r1阶矩阵：式中：Q2r-1r个重量为奇数的列组成的矩阵。由于H中所有列的重量均为奇数，所以没有3列之和为0。但是对Q中重量为3的列hi，在Ir中有3列hp、hq、hr，使得hi+hphq+hr0。因此以该H为检验矩阵的截短汉明码的最小距离为4。,H QIr,(635),截短汉明码实际上还可以看做截去原码中每个码字的某些相同比特后得到的另一个新的线性码。于是截短线性码的最小距离并不一定大于原码的最小距离，甚至还有可能出现截短码的最小距离小于原码的最小距离的情况。如要求构造码长n6的纠单个错误的截短汉明二进制码，这时可把（7，4，3）码缩短一位得到，即在（7，4，3）码的所有2k2416个码字中，挑出第一个码元都是0的码字，共有8个，然后把该0去掉，这样就得到了（6，3，3）缩短码，它的生成矩阵,就是（7，4，3）码矩阵G中的后三行去掉第一个0码元得到的。通常，对于任意的（n，k，d）码，均可用同样方法得到（n-i，k-i，d）缩短码，ik。显然，缩短码是原码字中去掉一些0码元得到的，因此缩短码的dmin至少与原码相同。与截短相反，汉明码的另一种变形是增长汉明码，即在汉明码的每个码字中的相同位置处增加一个比特，使新码的码长增加。比如，在码长为n2r1的汉明码的每个码字最后增加一个比特cn，使得：于是新码的码长就增加为n+12r。这里新码称为扩展汉明码，新增加的比特cn称为全监督位。,1,(636),由于汉明码的最小距离dmin3，所以必有一个重量为3的码字Ci，那么按式(636)对应于此码字的全监督位就是比特“1”，从而使得增长后的码字重量由3变成4。如果原来码字重量为偶数则加上全校验位“”之后并不改变原码字的重量。由此可知，加上全校监督之后，汉明码中奇重量码字的重量增加1，而偶重量码字的重量保持不变，所以扩展汉明码的最小距离由3变为4。与截短码不同的是，增长码的最小汉明距离总是不会小于原码的最小距离。,设汉明码的校验矩阵为H，则按式(636)的方式增长后的扩展汉明码的校验矩阵变成:即HG就是在H的最上面增加一个全“1”行，在H的最右列增加一个全“”列后的矩阵。例如,(7，4)汉明码按式(637)增长之后的扩展汉明码的校验矩阵为,（637）,一旦r给定，就可构造出具体的(n，k)汉明码了，这可以从建立一致监督矩阵着手。从线性码的一致监督矩阵的介绍可知，矩阵的列数就是码长n，行数等于r。如r3，就可算出n7，k4，因而是(7，4)线性码。,（638）,6.4.4完备码在纠正t个错误的(n，k)线性码中，凡小于或等于t的所有信道错误图样数之和正好等于标准阵列陪集首数2n-k，那么这种码皆可称为完备码。完备码的监督位得到了充分的利用，因而完备码是最佳码。对于汉明码，正好是t1的完备码，因为不论r为何值，汉明码都是纠1位错误的完备码。对于纠1位差错来说，其伴随式等于错误位置对应的H的列变量。汉明码的最小距离dmin为3，如果再增加1位校验位，可使dmin增至4，则它就是能纠正1位错误同时能检测2位错误的码，简称纠1检2错码。,例如(7，4)汉明码可变成(8，4)码，(8，4)码的H矩阵如式（638）所示。它的第一行为全1行，最后一列为1000T，其作用是使第8位成为偶校验位，而前7位码元同(7，4)码。这种H矩阵中，任何3列都是线性独立的，而只有4列才能线性相关，则dmin4，因此可实现纠1检2错。,定理6-4 二元(n，k)线性码能纠2nk个错误图样。这2nk个可纠的错误图样，包括0变量在内，也就是说，把无错的情况也看成一个可纠的错误图样。由定理6-4可以推出，一个(n，k)线性码的纠错能力t和所需的监督元数目间的关系：纠一个错误的(n，k)线性码，必须能纠正+个错误图样，因此：,(639),式中右边加1就是考虑无错的情况。,同样，对纠两个错误的(n，k)线性码，必须能纠个错误图样，所以,(640),依次类推，一个纠t个错误的(n，k)线性码必须满足：,（641）,式（6-41）不仅表示了码的纠错能力和可纠的错误图样数2nk之间的关系，也说明了纠错能力为t的(n，k)码，码组中必须的监督元数目nk和纠错能力间的关系。,当一个纠个错误的(n，k)线性码，其监督元个数nk仅能使式(641)中的相等关系成立，即,（642）,则称该码为完备码。这时由码的纠错能力所确定的伴随式数恰好等于可纠的错误图样数，所以完备码的n个监督码元得到了充分的利用。,