信息论与编码7.ppt

第七章 线性分组码第七章第七章 线性分组码线性分组码内容提要线性分组码同时具有信息位分组和校验位与信息位呈线性关系两种特性。目前，几乎所有得到实际应用的纠错码都是线性的。本章首先介绍有关纠错码的基本概念，然后介绍抽象代数中与编码直接相关的基础知识，包括群及群的陪集分解，重点论述线性分组码的定义及其编译码理论，并介绍线性分组码的纠检错能力。最后介绍一种典型的线性分组码汉明码。7.1 7.1 纠错码纠错码的基本概念的基本概念 l信源编码的目的是压缩冗余度，提高信息的传输速率。l信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输的可靠性。香农第二定理指出，当信息传输速率低于信道容量时，通过某种编译码方法，就能使错误概率为任意小。目前已有了许多有效的编译码方法，并形成了一门新的技术纠错编码技术。这里所讲的纠错编码即信道编码，与信源编码一样都是一种编码，但两者的作用是完全不同的。7.1.1 信道纠错编码信道纠错编码 讨论码字序列c通过离散信道时发生的情况，信道分为无记忆信道和有记忆信道。l在无记忆信道中，噪声对传输码元的影响是相互独立的，即每一个差错的出现与其前后是否有错无关,如图8.1。在无记忆信道中，错误是随机产生的，因此被称作随机错误，无记忆信道也被称为随机信道（random channel）。图8.1 二进制对称信道 7.1.2 差错类型差错类型有记忆信道中，各种干扰所造成的错误往往不是单个地，而是成群、成串地出现，表现出错误之间有相关性。图8.2就是这种信道的一个模型。图8.2 有记忆信道模型 就实际信道而言，由于其干扰的复杂性，往往是两种错误并存。随机错误与突发错误并存的信道，称为组合信道或复合信道。为了方便研究，将信息传输系统模型简化成图7.3所示的简化模型图7.3 简化的信息传输系统模型 模型突出了以控制差错为目的的纠错码编码器和译码器，因此也称为差错控制系统。7.1.3 差错控制系统模型及分类差错控制系统模型及分类在差错控制系统中使用的码按其纠错能力的不同可分为两种：检错码检错码和纠错码纠错码。能发现错误但不能纠正错误的码称为检错码；不仅能发现错误而且还能纠正错误的码称为纠错码。（）前向纠错前向纠错(FEC)方式方式 FEC(Forward Error Control)方式是发端发送有纠错能力的码（纠错码），接收端收到这些码后，通过纠错译码器自动地纠正传输中的错误。差错控制系统大致可分为前向纠错、重传反馈和混合纠错等三种方式。优点是不需要反馈信道；能进行一个用户对多个用户的同时通信，特别适合于移动通信；译码实时性较好，控制电路也比较简单。缺点是译码设备较复杂；编码效率较低。（）重传反馈重传反馈(ARQ)方式方式:ARQ(Automatic Repeat Request)方式是：发端发出能够发现错误的码（检错码），收端译码器收到后，判断在传输中有无错误产生，并通过反馈信道把捡测结果告诉发端。发端把收端认为有错的消息再次传送，直到收端认为正确接收为止。l优点是译码设备简单，在多余度一定的情况下，码的检错能力比纠错能力要高得多，因而整个系统能获得极低的误码率。l应用ARQ方式必须有一条从收端至发端的反馈信道。并要求信源产生信息的速率可以进行控制，收、发两端必须互相配合，其控制电路比较复杂，传输信息的连贯性和实时性也较差。（）混合纠错混合纠错(HEC)方式方式 HEC(HybridErrorControl)方式是上述两种方式的结合。发端发送的码既能检错、又有一定的纠错能力。收端译码时若发现错误个数在码的纠错能力以内，则自动进行纠错；若错误个数超过了码的纠错能力，但能检测出来，则通过反馈信道告知发方重发。这种方式在一定程度上避免了FEC方式译码设备复杂和ARQ方式信息连贯性差的缺点。在设计差错控制系统时，选择何种实现方式，应综合考虑各方面的因素。主要有：满足用户对误码率的要求；有尽可能高的信息传输速率；(4)可接受的成本。有尽可能简单的编译码算法且易于实现；按信息位与校验位的关系，可将编码分成以下两大类：按信息位与校验位的关系，可将编码分成以下两大类：（1）线性码校验位与信息位呈线性关系（即可用一次方程描述）。（2）非线性码校验位与信息位不呈线性关系。按信息位与校验位之间的约束关系，可分为：按信息位与校验位之间的约束关系，可分为：（1）分组码将信息符号分成k位一组，每组增加r位校验位，这r位校验位仅与本组的k位信息位有关，与其他的信息位无关。循环码除全零码字外，其余码字都可由另一码字的码符循 环移位得到；非循环码某个码字的循环移位不一定还是该码的码字。（2）卷积码将信息符号分成k位一组，每组增加r位校验位，这r位校验位不仅与本组的k位信息位有关，还与前面m组的信息位有关。7.1.4 纠错码的分类纠错码的分类7.2 7.2 群与群的陪集分解群与群的陪集分解本节仅介绍与线性分组码的编码有直接关系的必要的代数基础，主要涉及群和群的陪集分解，本书涉及的其他代数知识将在相应的章节中予以介绍。7.2.1 7.2.1 群的概念群的概念定义定义7.1 群是一些元素的集合，在群中定义了一种代数运算（加法或乘法，运算符号都用*表示），且具有如下性质：（1）封闭性：对于任意元素和，如果，则恒有；（2）结合律：对于任意元素，恒有；（3）存在幺元；（4）对于任一元素，存在逆元。若*为加法运算，则称为加法群；若*为乘法运算，则称为乘法群。有关群的几个概念有关群的几个概念v交换群交换群：如果群中定义的*运算满足交换律，即如果，则称该群为交换群。v群的阶群的阶：群所含元素的个数称为群的阶。v有限群有限群：如果群的阶为有限值，则称该群为有限群，否则称为无限群。7.2.2 7.2.2 子群子群定义定义7.2 如果非空集合如果非空集合 本身也是一个群（与群本身也是一个群（与群G关于同一运算关于同一运算*），则），则 为为G 的子群。的子群。【例7.4】对整数定义加法运算构成加法群，偶数对加法就构成它的一个子群。如何构造一个子群（有限群）？设，则定义，记（幺元)，则，元素集合就构成G的一个子群，称g为子群的生成元，称s为生成元g的阶，s也就是子群的阶。【例7.5】对集合G=(1,2,3,4,5,6,7,8,9)定义模10加法运算，运算符号用*表示，模10加法运算结果如表7-1所示。可见，G是一个交换群，0为加法幺元。+012345678900123456789112345678902234567890133456789012445678901235567890123466789012345778901234588890123458999012345890表7-1模10加法运算（1）以2为生成元，对2进行*运算，得到2的方幂：则是G的一个子群。因为，所以生成元2的阶为5。（2）类似地，以5为生成元，是G的一个子群，生成元5的阶为2。（3）以3为生成元，也是G的一个子群，生成元3的阶为10。对G中的元素（生成元）进行*运算得到的方幂，则集合就构成G的子群，这样构成的子群称为循环群。定理7.1 有限群的子群的阶一定整除群的阶。例7.5中生成元5在模10加法运算下构成子群G=5,0。G 的阶2整除G 的阶10。7.2.3 7.2.3 群的陪集分解群的陪集分解若为G的子群，取元素，集合称为的G陪集，陪集具有如下特性：（1）若，则；（2）若，则（空集）。群的陪集分解:设群G的阶为，的阶为n，每次选取元素，与中的元素进行*运算，从而得到m个陪集。如下表所示元 素陪 集说 明h1g1 g2 gn子群h2 h2*g1 h2*g2 h2*gn(h2G)是第一行没出现过的元素h3h3*g1 h3*g2 h3*gn(h3G)是第一、二行没出现过的元素hmhm*g1 hm*g2 hm*gn(hmG)是前面（m-1）行没出现过的元素陪集分解的性质如下v（1）完备性：可将整个群分解为若干陪集，一个元素也不剩，因为子群的阶整除群的阶。v（2）正交性：若，则，。【例7.7】线性分组码：n=7，k=4，记为（7，4）码。信源符号4位一组：u=（u3，u2，u2，u0），ui0,1，i=0,1,2,3码符号7位一组：C=（c6,c5,c4,c3,c2,c1,c0），cj0,1，j=0,1,2,3,4,5,67.3 7.3 线线性分性分组码组码的的编码编码 码符号与信源符号的关系为（7-1）用矩阵表示式（7-1），得7.3.1 生成矩阵、校验矩阵生成矩阵、校验矩阵简记为c=uG 称为生成矩阵 表7-3列出了按c=uG 生成的16个码字。表7-3（7，4）线性分组码信 息 组码 字0 0 0 000000000 0 0 100001110 0 1 000110010 0 1 100111100 1 0 001010100 1 0 101011010 1 1 001100110 1 1 101101001 0 0 010010111 0 0 110011001 0 1 010100101 0 1 110101011 1 0 011000011 1 0 111001101 1 1 011110001 1 1 11111111定义矩阵,可以验算，矩阵H与G正交，即满足或,因此有 称H为校验矩阵,H由n=7维空间的nk=74=3维子空间中的3个线性无关行矢组成。计算 ,称s为y的伴随式伴随式，若s=0知道y是选用码矢，传输无误；若s 0，则y不是选用码矢，说明在传输过程中发生了误码 记e为错误图案，则 y=c+e 说明伴随式仅与错误图案有关 假设误码只有一位，则列矢e中只有一位为1，由式（8-4）可看出，观察列矢s与校验矩阵H中的哪一列相同，就可确定H中的哪一位出错。（7-4）定义定义7.5 （n，k）线性分组码C中一组基底所构成的kn阶矩阵称为码C的生成矩阵，用G表示。设此基底为g0，g1，gk1，g0=（g0,n1，g0,n2，g0,0）g1=（g1,n1，g1,n2，g1.0）gk1=（gk1,n1，gk1,n2，gk1,0）写成矩阵形式，为 一个线性空间的基底可以不只一组，因此作为码的生成矩阵G，也可以不止一种形式。可以从码集C中另取k个线性无关的码矢作为基底，它们也生成相同的线性空间，即生成同一个（n，k）线性分组码。7.3.2 系统码系统码 一个子空间的基底选用并不是唯一的，所以对应的生成矩阵G也不是唯一的。【例7.8】二元（6，3）线性分组码，下面给出的G1和G2都可以作为它的生成矩阵。表8-3给出了分别由G1和G2所生成的线性码。信息组由G1生成的（6，3）码由G2生成的（6，3）码000000000000000001111000001101010110101010011011001101011110100101011100110101010011101011110011110110101111100110111000表7-5 由不同生成矩阵生成的线性分组码 观察由G2所生成的线性码，由c=u G =（u2，u1，u0，u2+u0，u2+u1，u1+u0）=（c5，c4，c3，c2，c1，c0）得 码矢的前3位是信息位，后3位是校验位，将这样的码称为系统码。在一般情况下，生成矩阵G是kn矩阵，可通过初等变换将G变成如下形式。Ik是kk单位方阵，P P是k(nk)矩阵（nk），称这种形式的G G为标准生成矩阵标准生成矩阵，因为初等变换不改变矩阵的秩，因此 仍由k个线性无关的行矢组成。这样生成的码c=u G=uIk P=（cn1，cn2，c1，c0），前面k位cn1，cn2，cnk是信息位，后面nk位cnk1，cnk2，c1，c0是校验位，称这种码为线性系统分组码，简称系统码系统码。这时校验矩阵相应地变成 ，其中Ink是(nk)(nk)单位方阵，P PT是矩阵P P的逆元转置矩阵，对于模2加运算，0的逆原为1，1的逆元为0，故有PT=PT，。可以验证 称H H为一致校验矩阵，简称校验矩阵。7.3.3 对偶码对偶码 设原码有k位信息位，其生成矩阵为G，校验矩阵为H，对应线性码C。若用H作为生成矩阵，生成另一码C，则对应的校验矩阵为G，称C为C的对偶码对偶码，C有nk位信息位，k位校验位。因为c=uH，c=uG，c(c)T=uG(uH)T=u(G HT)uT=0，说明互为对偶的码矢内积为0，两码矢正交。7.3.4 编码的实现编码的实现 设码的G矩阵为当信息组m（mn-1mn-2 mn-k）时，相应的码字c是 c mG（cn-1 cn-2 c1 c0）cj mn-1 p1,j+mn-2 p2,j+mn-k pk,j 0 j nk cjmj nk j n1 其中图7.4 （n，k）线性分组码编码电路 编码实现电路如图8.4所示。电路由移位寄存器、模二加法器和模二乘法器组成根据图8.4的电路，可画出（7，3）线性分组码的编码器电路，如图8.5。图7.5 （7,3）线性分组码编码电路 7.4 7.4 线线性性码码的的纠检错纠检错能力能力 7.4.1 码的距离和重量码的距离和重量 定义定义7.6 两个码字之间，对应位取值不同的个数，称为它们之间的汉明距离，简称距离，用d（c1，c2）表示。定义定义7.7 码字中非零码元的个数，称为该码字的汉明重量，简称重量，用w（c）表示。定义定义7.8 一个码的最小距离dmin定义为(79)定理定理7.2 线性分组码的最小距离等于其非零码字的最小重量。根据定理，要得到码的最小距离，只要检查2k1个非零码字的重量即可。事实上，两个码字之间的距离表示了它们之间差别的大小。因此，一个线性分组码的最小距离是衡量码抗干扰能力的重要参数。码的最小距离愈大，其抗干扰能力愈强。7.4.2 线性码的纠检错能力线性码的纠检错能力 以上定理是纠错码理论中最重要的基本定理之一，它说明了一个距离为d的线性分组码，既可用来纠正个错误，又可用来检测e d1个错误。定定理理7.3 对于任一个（n，k）线性分组码，若要在码字内 检测e个错误，则要求码的最小距离d e1；纠正t个错误，则要求码的最小距离d 2t1；纠正t个错误同时检测e（t）个错误，则要求d te1。定理定理7.4 （n，k）线性分组码有最小距离为d的充要条件，是H矩阵中任意d1列线性无关。推论推论7.1 （n，k）线性分组码的最大的，可能的最小距离等于n k1。由此定理可知，所有列相同，但排列位置不同的各种H矩阵所对应的不同（n，k）线性分组码，都有相同的最小距离，即它们在纠错能力和码率上是完全等价的。线性分组码的n位码符号由k位信息位加上nk位校验位组成，这n位码符号取自符号集，在整个n维空间Vn共有qn个矢量。线性分组码对应k维子空间，在k维子空间中，共有qk个矢量，这qk个矢量就是选用码矢，其余qnqk个矢量称为禁用矢量。第三步：再选一个第一行、第二行没列出的禁用矢量y2，其余各列都用y2和第一行对应码矢相加（模2加）；第二步：选一个在第一行中没列出的禁用矢量y1写在第二行的第一列，其余各列都用y1和第一行对应码矢相加（模2加）；第一步：从全零码矢开始，把所有选用码矢依次写成一行；下面将qn个矢量排成标准阵列第四步：如此重复，直至把所有qn个矢量列完。7.5 7.5 标标准准阵阵列和列和译码译码7.5.1 标准阵列标准阵列把这样列出的表格称为标准阵列。取q=2，则2n个矢量列出的标准阵列如表7-9所示。【例7.12】二元（5,3）码，生成矩阵 ,信源有8个消息待发，对应信源编码器的8个输出序列，即000，001，010，011，100，101，110，111 根据c=u G编码，得到8个码矢，即00000，00111，01010，01101，10011，10100，11001，11110按上述方式将25=32个5重矢量排成标准阵列，如表7-10所示。表7-10将32个矢量排成标准阵列00000001110101001101100111010011001111100000100110010110110010010101011100011111000100010101000011111000110110110111110000100000110111001001101111000011101110107.5.2 陪集分解陪集分解由标准阵列的构成法，得到结论：（1）第一行是qk个选用码矢，以后每行都是第一行的陪集，每行的第一个元素称 为陪集首，分别记为 ；（2）陪集首是前面先列出的元素中没有出现过的，从而该陪集中的元素也是前面没有出现过的；（3）如果选的陪集首是该行中的另一个元素，则该行中的元素还是原来的qk个元素，只不过排列顺序变了，这说明该行中的每个元素都可以做陪集首；（4）根据（1）和（2），最后把所有qn个元素全列完了（qnk行qk列=qn个元素）；（5）同一陪集中所有元素的伴随式相同，不同陪集的伴随式不同。7.5.2 陪集分解陪集分解【例7.13】在表7-10所列的标准阵列中，每行的第一个元素为该行的陪集首，有由矩阵G 可得 ，根据式 计算出4个伴随式，即 从 来看，若e=0，则s=0；若e 0，则s 0，伴随式s只由错误图样e决定，。7.5.3 译码译码 接收到y后，到标准阵列中去找（因为qn个矢量全部列在其中，总可以找到），假设在某列中找到了y，则把它相应地译成该列的第一个矢量。【例7.15】仍考虑例7.12所述的二元（5，3）码，假设接收矢量为y=10110，在表7-10列出的标准阵列中，找到y位于第6列，相应地译成10100。错误图案是y=10110所在行的陪集首。！利用标准阵列译码，需要把2n个n重矢量全部储存在译码器中，译码器的复杂性将随n成指数增加，当n较大时难以使用。1 用标准阵列译码 2 用伴随式译码 在标准阵列中出现的qn个矢量都是可能的接收矢量，它们具有y=ej+cj的形式，将y看成是发送码矢cj时收到的矢量，则ej就是错误图案，根据最小错误译码准则，可译码如下：在标准阵列的每一行中选重量最轻的矢量作为陪集首（例8.6二元（5，3）码的标准阵列就是如此），接收到y后，计算伴随式s=HyT，再在s所对应的陪集中，找到陪集首e，译码输出 。用伴随式译码，译码正确的概率与陪集首的选择有关。根据最大后验概率译码准则，重量最轻的错误图样产生的可能性最大，所以应该优先选择重量小的n重作为陪集首。这样构造的译码表，使得e j+ci与ci之间的距离最小，从而使译码器能以更大的正确概率译码，这就是最小距离译码。可以将标准阵列简化成更为实用的译码表，表7-11所示就是表7-10所列（5，3）线性分组码标准阵列的译码表。！将表8-9所示的译码表存入译码器，只需要存储2nk个n重（陪集首）及2n-k个nk重（伴随式）矢量。表7-11 （5，3）线性分组码标准阵列的译码表伴随式s错误图样（陪集首）e0000000010000110000101100100 3 二元线性码的误码率 根据伴随式译码方法，选重量最轻的矢量作为陪集首，采用最小距离译码准则时，陪集首项的集合就是可纠正图案的集合，即错成 y=c+e时，可纠正为 ，则正确译码的概率就是陪集首出现的概率。设是第l个陪集首的重量，则对于二进制对称信道BSC，有式中，是重量为i的陪集首个数，则错误概率为 7.6 7.6 汉汉明明码码 7.6.1 汉明码的构造汉明码的构造 定义定义7.9若H矩阵的列是由非全零且互不相同的所有二进制r重组成，则由此得到的线性分组码，称为GF(2)上的（2r1，2r1r）汉明码。7.6.2 汉明限与完备码汉明限与完备码 一个二进制（n，k）线性分组码，若要纠正t个错误，则应使小于或等于t个错误所组成的所有错误图样，都必须有不同的伴随式与之对应，即以下不等式成立：(723)式(723)称为汉明限汉明限。如果某一（n，k）线性分组码能使(723)式等号成立，即错误图样总数正好等于伴随式数目，则称这种码为完备码完备码。如果一个（n，k）线性分组码，除了能将重量小于等于t的所有错误图样作为陪集首外，还有部分（但不是全部）重量大于t的错误图样作为陪集首，则称这种码为准完备码准完备码。本章的主要内容本本 章章 小小 结结（3）线性分组码的检纠错能力：汉明距离和汉明重量，码的最小距离，码的最小距离与检纠错能力的关系，距离为d的线性分组码的构造，MDS码。（2）线性分组码的编码：线性分组码的定义，生成矩阵和校验阵的构成，系统码的生成矩阵和校验矩阵，对偶码，编码实现电路。（1）纠错码的基本概念：信道纠错编码及其目的，差错控制系统的三种实现方式，检错码与纠错码，分组码与卷积码，随机错误与突发错误。（5）汉明码：汉明码的定义，构造一个汉明码，汉明限，完备码与准完备码。（4）伴随式与译码：错误图样，接收序列的伴随式，码的标准阵列的构成，选择陪集首，将标准阵列简化为译码表，线性分组码的译码步骤。