第6章线性分组码ppt课件.ppt

第6章线性分组码,6.1线性分组码的基本原理 6.2线性分组码矩阵表述 6.3线性分组码的编码及译码 6.4汉明码及其它纠错码,纠错码的分类：,按功能分：检错码、纠错码按监督码元与信息码元的关系分：线性码、非线性码按对信息码元的处理方法分：分组码、卷积码 其中分组码又包括循环码和非循环码按信息码元编码后是否保持原形分为：系统码、非系统码按纠错类型分：纠正随机错误码、纠正突发错误码、纠正混合错误码、纠正同步错误码等按码元的取值分：二进制码、多进制码,(n，k)线性分组码：把信息序列按一定长度分成若干信息码组，每组由相继的k位信息数字组成；然后，编码器按照预定的线性运算规则(可由线性方程组来规定)把信息码组变换成n(nk)重码字，如图所示。,6.1.1基本概念,6.1线性分组码的基本原理,（1）如果(n，k)线性分组码的数域为GF(p)，即每一个码元 可能有p种取值，则信源可发出pk种不同的消息组；（2）线性码的校检位与信息位之间呈线性关系；（3）由pk个信息码组编成的码字集合称为(n,k)码许用码字, 由pn-pk个除了许用码字之外的码字集合称为禁用码字。,注：,码矢：一个n重的码字C可以用矢量C=cn-1cn-2c1c0来表示，所以码字又称为码矢。,码率：对(n，k)线性码，用Rkn表示码字中 信息位所占的比重，叫做编码效率或编码速率， 简称码率。它说明了信道利用效率，所以也叫做 传信率。注： R是衡量码性能的一个重要参数（1）R越小，冗余度就越大，检错和纠错的能力 越强，但也降低了传输信息的实际速率。（2）R越大，码的效率也就越高或传信率越高。,例如，信息分组长度k3，在每一信息组后加上4个监督元，构成(7，3)线性分组码。 设该码的码字为c6c5c4c3c2c1c0，其中c6、c5、c4为信息元；c3、c2、c1、c0为监督元，每个码元取值为“0”或“1”，即ciGF(2)。监督元按下面方程组计算：,（6）,监督方程（校验方程）：是线性方程组，它确定了由信息 元得到监督元的规则,式(61) 为监督方程或校验方程,利用监督方程或校验方程。每给出一个3位的信息组，就可编出一个码字，如表61所示。,表6-1（，）分组码编码表,1.汉明（Hamming)重量（码重）：码字中非零码元的数目 例如“010”码字的码重为1，“011”码字的码重为2。2.汉明距离（码距）：两个码字之间对应码位上具有不同 二元码元的位数。3.最小汉明距离，用dmin表示：在一种编码中，任意两个许 用码字间距离的最小值，即码字集合中任意两码字间的 最小距离；4.最小汉明重量：在非零码字中，重量最小者称为该码的 最小汉明重量。,6.1.2码的重量和码的距离,5. 通常用d(C1，C2)表示两个n重C1、C2之间的汉明距离;6. 汉明距离的性质：(1)对称性：d(C1，C2)d(C2，C1)；(2)非负性：d(C1，C2)0； (3)满足距离三角不等式： d(C1，C2)d(C1，C3)d(C3，C2)。,7. 最小距离dmin与码率R是码的两个最主要的参数， dmin表示 了码的纠错能力。 注 ：纠错码的基本任务之一就是构造出R一定且dmin尽可能 大的码，或dmin一定且R尽可能大的码。 8. MDS码：(n，k，d)线性分组码的最小距离dminnk1。 若系统码的最小距离dminnk1，则称此码为极大最小距 离可分码，简称MDS码。,若一个码组内能检测e个错码，则要求最小 码距为,dmine1,注：若一种编码的最小距离为dmin，则它最多能检 出dmin-1个错码。,6.1.3码的检错及纠错能力,图62码距与检错、纠错能力的关系,2. 若一个码组内能纠正t个错码，则要求最小 码距为,dmin2t1,(63),注：若一种编码的最小码距为dmin，则它最多能纠正（dmin1）/2个错码。,3. 若在一个码组内能纠正t个错码，同时也能检测e(et)个错码，则要求最小码距为,dminet1 (et),(-4),注：能纠正t个错码，同时能检测e个错码的含义是：当错码不超过t个时，码组能自动予以纠正；而当错码超过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，此码只能检错，不能纠错。,线性分组码具有下述性质： (1)两个属于该码组码字的和仍是一个属于该码组的码字。 (2)全零码字总是码组中的一个码字。 (3)一个线性码组中两个码字之间的最小距离等于任何非零 码字的最小重量。注：如果两个码字的和是另外一个码字，该两个码字的差也将仍然是一个合法码字。例如，若C1、C2和C3是码字，且C1+ C2 = C3，那么有C3 -C1=C2。所以，对一个线性分组码，全零码字必为一个合法码字。,6.1.4线性分组码的性质,【例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。,（1）设S为一个长度为n且分量在GF(p)上的向量集合。S中 所有向量的线性组合构成的集合称为S的线性扩张，记 为S。（2）线性扩张是由S生成的GF(pn)的一个子空间。（3）给定GF(pn)的任意子集S，可以得到一个由S生成的线 性码C=S，它恰好包含下列码字：全零码字;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。,在（n，k）线性分组码中，n表示码长，k表示信息位的维数，将n个码字位和k个信息位之间的关系写成矩阵形式,即,CUG,(66),6.2线性分组码矩阵表述,6.2.1生成矩阵,式中:,G为该线性分组码（n，k）码的生成矩阵，即,（67）,（1）G建立了消息与码矢间的一一对应关系，它起着编码器的变换作用。因此C的每一位数字都是消息数字的线性组合。（2）一个子空间的基底矢量的选择不是惟一的，所以生成矩阵G的选择也不是惟一的。,注：,【例64】已知(7，3)线性分组码，设该码的码字为C=c6 c5 c4 c3 c2 c1 c0，其中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+u1c0=u1+u0,又因为,C=c6 c5 c4 c3 c2 c1 co，U=u2 u1 u0,，由C=UG，所以,【例65】已知GF(2)中码生成矩阵分别为：,求：G1和G2分别对应的码字空间？,表62用不同的生成矩阵得到的线性码,在线性分组码（n，k）中，若设CT、0T及HT分别为C、0、H的转置矩阵，则每个码字中r个监督元和信息元之间的关系为,HCT0T 或 CHT0,（68）,H称为(n,k)线性码的一致监督矩阵，即,式中：,Ccn1 cn2 . cl c0。,6.2.2监督矩阵,【例66】已知(7，3)线性分组码，设该码的码字为C=c6 c5 c4 c3 c2 c1c0,其中c6、c5、c4为信息元; c3、c2、c1、c0为监督元，每个码元ciGF(2)。监督元可按式(61)方程组计算。求监督矩阵。,c6=u2c5=u1c4=u0,解：因为,则由监督方程得,c3u2u0c6c4c2u2u1u0c6c5c4c1u2u1c6c5c0u1u0c5c4,得：,1.等价码 如果一个线性P 元码可由另一个通过下面一种或两种运算得到，则称它们为等价码。该运算为：(1)用非零常量去乘它的分量；(2)对码的位置做置换。,6.2.3等价码及系统码,定理61两个kn矩阵，若一个可以由另一个通过一系列下述变换得到，则它们生成的GF(p)上的(n，k)线性码等价： （1）对行置换； （2）对行乘以一个非零常量； （3）把一行乘以一个常量然后加到另一行上； （4）对列置换； （5）对任意列乘以一个非零常量。,（1）编码后信息元保持不变的码为系统码。（2）例65中G2生成的码，因其前k位与消息完全相同，为系统码，该码的编码器仅需存储k(n-k)个数字(非系统码要存储kn个数字)，译码时仅需对前k个信息位纠错即可恢复消息。,2. 系统码,（1）系统码的生成矩阵可用分块矩阵表示,GIkP,(610),式中：Ikkk阶单位方阵；Pk(n-k)阶阵。由此G生成的码称为系统码，否则称为非系统码。 在系统码的码组 C(cn1，cn2，c0)中，前k位 (cnl，cnk)(u1，uk)是信息位，后nk位 (cnk，c)称为码字的校验位。,3. 生成矩阵与监督矩阵的关系,对一致监督矩阵H各行实行初等变换，并将后r列化为单位子阵，则得到监督矩阵H的标准形式,HQIr,(611),A): H阵的每一行都代表一个监督方程，它表示与该行中“1”相对应的码元的和为0，因而，H的标准形式还说明了相应的监督元是由哪些信息元决定的。B): r个监督方程(或H阵的r行)必须是线性独立的，这就要求H阵的秩为r。若要把H阵化成标准形式，只需检查单位子阵的秩，就能方便地确定H阵本身的秩。,（2）监督矩阵H的标准形式,注：,推导：由于生成矩阵G的每一行都是一个码字，所以G的每行都满足HCT0T，则有：,HGT0T 或 GHT0,(612),GHTIkpQIrTQTp0,（613）,（3）线性分组码的生成矩阵和监督矩阵的关系,因此，线性码的生成矩阵G和监督矩阵H的行矢量彼此正交。由式(610)、(611)及式(612)得：,所以 由此可得： GIkPIkQT HQIrpTIr 因而线性系统码的监督矩阵H和生成矩阵G之间可以相互直接转换。,PQT 或PTQ,（614）,（615）,例如，已知(7，4)线性系统码的监督矩阵为,可直接写出它的生成矩阵为,对一个(n，k)线性码CI，由于HGT0T，如果以G作监督矩阵，以H作生成矩阵，可构造另一个码CJ，码CJ是一个(n，nk)线性码，则称码CJ为原码CI的对偶码。注：对偶码是原码的生成矩阵和监督矩阵互换后所构成的码，所以对偶码的码字与原码的码字彼此正交，而它们的码字集合分别构成的两个子空间是互为零化空间。,6.2.4对偶码及缩短码,1. 对偶码,例如，(7，4)线性码的对偶码是(7，3)码，那么(7，3)码的监督矩阵H（7，3）是(7，4)码的生成矩阵G（7，4），即,H（7，3）G（7，4）,而（7，3)码的生成矩阵G（7，3)是(7，4)码的监督矩阵H（7，4）,H(7，4),G（7，3）,G（7，3）和H(7，4) 可以互相转化，它们是等价的。G(7，3)是(7，3)码生成矩阵的标准形式，H(7，4)是(7，4)码一致校验矩阵的标准形式，两者可以编出互为对偶码的(7，3)码和(7，4)码，如表63和表64所示。,表63G（7，3）编出的（7，3）码,表6-4 H（7，4）编出的（7，4）码,（2）线性分组码的性质完全由G 或H 决定。,注： （1）对偶码G与H的变换过程可简单地将单位子 阵由前移到后，或由后移到前来实现。,在(7，3)码的码字集合中，如果将最左面一位为0的消息和对应的码字挑选出来，并把最左面的0删去，则它们构成(6，2)线性分组码，如表65所示。这种码叫缩短码。,2. 缩短码,表63G（7，3）编出的（7，3）码,表65缩短的(6，2)码,求缩短码的生成矩阵和一致监督矩阵是很方便的，如(6，2)码的生成矩阵就是将(7，3)码的生成矩阵的最上面一行和最左面一列删去，将(7，3)码的一致校验矩阵的最左面一列删去就是(6，2)码的一致监督矩阵，即,注： 由线性分组码（n，k）生成缩短码（n-i，k-i），由于删掉的都是0码元，缩短码的纠错、检错能力与原码相同。,(n，k)线性码的编码是根据线性码的监督矩阵或生成矩阵将长为k的信息组变换成长为n(nk)的码字，即先求出信息元和码元之间的关系,再利用此关系构造编码电路。 由监督矩阵和生成矩阵求出的信息元和码元之间关系的结果是一致的，编码电路也相同。因为生成矩阵和监督矩阵只是以不同方式来描述同一码的结构而已。,6.3线性分组码的编码及译码,6.3.1线性分组码的编码,例如，利用监督矩阵来构造(7，3)线性分组码的编码电路。设二元码字为,Cc6 c5 c4 c3 c2 c1 c0,码的监督矩阵为,图63线性系统码编码电路,（1）设C是GF(p)上的一个(n，k)码，a是长为n的任意向量。则将集合,（616）,称为C的一个陪集(Coset)。当(a-b)C时，称a和b属于同一个陪集。,6.3.2标准阵列及译码,1. 陪集与陪集首,（2）一个陪集中具有最小重量的向量称为陪集首(Coset Leader)。如果有多余一个向量具有最小重量，则从中随机选择一个定为陪集首。,定理61假设C是GF(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。,【例67】设C为一个二元（3，2）码，其生成矩阵如下：,码字C=000，010，101，111。,C的陪集为:,所有的8个向量都被这两个陪集覆盖了。如果a+C是C的一个陪集而且b(a+C)，则有b+C=a+C。因此，上面已经列出了所有陪集。,由此可以看到所有陪集已经被覆盖了。,因为两个陪集或不相交或重合，所以GF(qn)上的所有向量可以写为,其中t=qn-k-1,2. 标准阵列,一个(n，k)码组C的标准阵列(Standard Array)是一个GF(pn)上全部向量的pn-kpk阵列，它的第一行由码组C构成(0码字在最左边)，其它行是陪集ai+C，都以相应次序排列，陪集首放在最左边。,（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重用完为止。,（2）构造标准阵列,表66(n，k)线性码的标准阵列,（3）标准阵列中的变量定理6-2 在标准阵列的同一行中没有相同的变量，而且2n个n重中任一个n重在阵列中必出现一次且仅出现一次。,证明： 因为阵列中任一行都是由所选出某一n重变量分别与2k个码字相加构成的，而2k码字互不相同，它们与所选变量的和也不可能相同，所以在同一行中没有相同的变量。在构造标准阵列时，是将全部n重码字用完为止，因而每个n重必出现一次。,另外， 假定某一n重X出现在第y行第i列，那么XEyCi，又假设X出现在第m行第j列，则有XEmCj，yy)的第一个元素，而按阵列构造规则：后面行的第一个元素是前面行中未曾出现过的元素，这就和阵列构造规则相矛盾。因而任何n重不可能在阵列中出现两次。,（4）标准阵列的结构 (n，k)线性码的标准阵列有2k列(和码字数相等)，2n2k2nk行，且任何两列和两行都没有相同的元素，即列和行都不相交。标准阵列的每一行叫做码的一个陪集， 每个陪集有相同的错误图样。每个陪集的第一个元素叫做陪集首，每一列包含2nk个元素，最上面的是一个码字，其它元素是陪集首和该码字之和，例如第 j 列即为：,DjCj，E2Cj，E3十Cj， ， E2n-kCj,(623),若发送码字为Cj，信道干扰的错误图样是陪集首，则接收字R必在Dj中，此时接收字R正确译为发送码字Cj；若错误图样不是陪集首，则接收字不在Dj中，则译成其它码字，造成错误译码。因而当且仅当错误图样为陪集首时，译码才是正确的。所以，这2nk个陪集首称为可纠正的错误图样。,（5）利用标准阵列来译码,选择重量最轻的元素作陪集首，按标准阵列译码就是按最小距离译码，所以，标准阵列译码法是最佳译码法。,【例68】已知二元(4，2)线性分组码生成矩阵为 求: (1)系统的标准阵列。(2)若接收码字R=1010,错误图样E=0100,求对应的码字,并判断译码有无错误。(3)若接收码字R=1010,错误图样E=0110,求对应的码字,并判断译码有无错误。,解：(1)由C=UG 得系统的码组为0000，0111，1001，1110,表67（4，2）线性码的标准阵列,所构造的标准阵列如表67所示：,(2)当接收字R1010时，在表67的第3行第4列中找到了它，于是就可以把R译成位于第4列的码字U1110。显然，位于第3行的陪集首0100是错误图样E，因此译码正确,表示信道第2位有错。,(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，它不在陪集首，属于错误译码。,当收到一个接收字R后，可用监督矩阵H来检验R是否满足监督方程，即HRT0T是否成立。若关系式成立，则认为R是一个码字，否则判为码字在传输中发生了错误。 把SRHT或STHRT，称为接收字R的伴随式(或监督子，或校验子)。,6.3.3 伴随式及错误检测,1. 伴随式,推导： 设发送码字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的第i列）代入得：,STh1en1h2en2.hne0,（628）,(1)伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定。(2)伴随式是错误的判别式为：若S0，则判没有出错，接收字是一个码字；若S0，则判有错。(3)不同的错误图样具有不同的伴随式，它们是一一对应的，二元码伴随式是H阵中与错误码元对应列之和。,2. 伴随式与错误图样,【例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）,3. 标准阵列与伴随式,(n，k)线性码的一般译码步骤：（1）计算接收码字R的伴随式STHRT。（2）若ST0，则认为接收到的R没有错误；否则认为有错，根据伴随式和错误图样一一对应的关系，利用伴随式译码表，由伴随式译出R的错误图样。（3）将接收码字减错误图样，得发送码字的估值。,4. 利用伴随式译码,【例611】二元(4，2)线性分组码生成矩阵为,求：(1)系统的伴随式译码表。(2)若接收码字R=1101,估算对应的码字。,表69(4，2)线性码译码表,解：(1)系统的标准阵列如表67所示。因为错误图样为陪集首，由S=EHT计算对应的伴随式，则得伴随式译码表如表69所示。,(2) 接收字R1110011，其伴随式为：,查译码表69，得错误图样,则码字估值。,【例612】设二元(6，3）码的生成矩阵为,解：线性码的标准阵列如表68所示，因为错误图样为陪集首，由S=EHT计算对应的伴随式，则得伴随式译码表如表610所示。,求伴随式译码表。,表610(6，3)线性码伴随式译码表,1.汉明码是一种特殊的(n，k，d)线性分组码；2.m元汉明码的参数n、k和d分别为：,6.4汉明码及其他纠错码,6.4.1汉明码,3.二进制汉明码的参数n、k和d分别为：,4.汉明码的最小距离是3，故汉明码能纠正一个随机错误或检测2个错误，且码的校验矩阵H中任意2列线性无关。,二进制汉明码的校验矩阵H由一切r(rnk)维非零二元向量排列而成，即的列为所有非零的r维向量组成，旦r 给定，就可构造出具体的(n，k)汉明码。,6.4.2汉明码的构造,1. 校验矩阵,【例613】构造一个二元的（7，4，3）汉明码，该码的校验矩阵为,（630）,2. 系统汉明码,如果H矩阵形如：,HQIr,式中：Irr 维单位方阵；Qr(2r-r-1)子矩阵。由此 H 生成的码称为系统汉明码,注：任意交换H矩阵的列，相当于码字各分量的次序作了相应变动，但并不会改变矩阵H中各列之间的相关性，因而也不会改变码的最小距离。,对式（6-30）矩阵进行列交换得：,（632）,有了H，按照HCT0就可得到系统码的校验位，表611就是按此方法编出的(7，4)汉明码。,表611(7，4)汉明码,相对应的系统汉明码的生成矩阵G为,GIkQT,（633）,例如，(7，4，3)系统汉明码的生成矩阵G为,3. 系统汉明码的生成矩阵,【例614】 求三元r3的汉明码的参数、H 矩阵及G 矩阵。根据汉明码的一般定义，得：,因为汉明码dmin3，只要任意两列线性无关，所以可以直接写出H 矩阵如下(不是惟一的):,生成矩阵为：,若从汉明码的校验矩阵H中截去任意x列，便可得到一个r(2rx1)阶的矩阵H。如果用H作为校验矩阵，那么就可以得到另一个线性码，此码称为截短汉明码，它的各参数分别为：,码长 n2rx1信息位数 k2rrx1校验位数 rnk最小距离 dmin3,6.4.3汉明码的变形,1. 截短汉明码,（1）如果对H进行适当的截除，就可以提高截短汉明码的最小距离。 例如，设HQ|Ir，从Q中截去所有重量为偶数的列，就得到一个r2r1阶矩阵： 式中：Q2r-1r个重量为奇数的列组成的矩阵。由于H中所有列的重量均为奇数，所以没有3列之和为0。但是对Q中重量为3的列hi，在Ir中有3列hp、hq、hr，使得hi+hphq+hr0。因此以该H为检验矩阵的截短汉明码的最小距离为4。,H Q Ir,(635),注：,（2）截短线性码的最小距离不一定大于原码的最小距离。 例如，要求构造码长n6的纠单个错误的截短汉明二进制码，这时可把（7，4，3）码缩短一位得到，即在（7，4，3）码的所有2k2416个码字中，挑出第一个码元都是0的码字，共有8个，然后把该0去掉，这样就得到了（6，3，3）缩短码，它的生成矩阵,汉明码的另一种变形是增长汉明码，即在汉明码的每个码字中的相同位置处增加一个比特，使新码的码长增加。,2. 增长汉明码,注： 增长码的最小汉明距离总是不会小于原码的最小距离,在码长为n2r1的汉明码的每个码字最后增加一个比特cn，使得： 于是新码的码长就增加为n+12r。这里新码称为扩展汉明码，新增加的比特cn称为全监督位。,1,(636),注：扩展汉明码,由于汉明码的最小距离dmin3，所以必有一个重量为3的码字Ci，那么按式(636)对应于此码字的全监督位就是比特“1”，从而使得增长后的码字重量由3变成4。如果原来码字重量为偶数则加上全校验位“”之后并不改变原码字的重量。由此可知，加上全校监督之后，汉明码中奇重量码字的重量增加1，而偶重量码字的重量保持不变，所以扩展汉明码的最小距离由3变为4。,设汉明码的校验矩阵为H，则按式(636)的方式增长后的扩展汉明码的校验矩阵变成: 即HG就是在H的最上面增加一个全“1”行，在H的最右列增加一个全“”列后的矩阵。,（637）,一旦r给定，就可构造出具体的(n，k)汉明码了，这可以从建立一致监督矩阵着手。从线性码的一致监督矩阵的介绍可知，矩阵的列数就是码长n，行数等于r。如r3，就可算出n8，k4，因而是(8，4)线性码。,（638）,例如,(7，4)汉明码按式(637)增长之后的扩展汉明码的校验矩阵为,（1）在纠正t个错误的(n，k)线性码中，凡小于或等于t 的所有信道错误图样数之和正好等于标准阵列陪集首数2n-k，那么这种码皆可称为完备码。（2）完备码是最佳码，完备码的监督位得到了充分的利用。,6.4.4完备码,（3）不论r为何值，汉明码都是纠1位错误的完备码。 对于纠1位差错来说，其伴随式等于错误位置对应的H的列变量。 汉明码的最小距离dmin为3，如果再增加1位校验位，可使dmin增至4，则它就是纠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变量在内，也就是说，把无错的情况也看成一个可纠的错误图样。,(639),式中右边加1就是考虑无错的情况。,（4）一个纠t个错误的(n，k)线性码必须满足：,纠一个错误的(n，k)线性码，满足：,同样，对纠两个错误的(n，k)线性码，必须满足：,(640),依次类推，一个纠t个错误的(n，k)线性码必须满足：,（641）,式（6-41）不仅表示了码的纠错能力和可纠的错误图样数2nk之间的关系，也说明了纠错能力为t的(n，k)码，码组中必须的监督元数目nk和纠错能力间的关系。,（5）当一个纠个错误的(n，k)线性码，其监督元个数nk仅能使式(641)中的相等关系成立，即,（642）,则称该码为完备码。这时由码的纠错能力所确定的伴随式数恰好等于可纠的错误图样数，所以完备码的n个监督码元得到了充分的利用。,