消防安全大排查大整治活动统计表.pptx

差错控制的任务是发现所产生的错误、并指出发生错误的信号或者校正错误，差错控制是采用可靠、有效的信道编码方法来实现的。信道编码器要对信源编码输出的符号进行变换，使其尽量少受噪声干扰的影响，减少传输差错，提高通信可靠性。本章要讨论的问题是在符号受到噪声干扰的影响后，如何从接收到的信号中恢复出原送入信道的信号、确定差错概率是多少等等。本章首先讨论信道编码的基本概念和分类，在此基础上再讨论两类主要的信道编、译码方法，即线性分组码与卷积码。第1页/共164页6.1 6.1 信道编码的概念信道编码的概念 进行信道编码是为了提高信号传输的可靠性，改善通信系统的传输质量，研究信道编码的目标是寻找具体构造编码的理论与方法。在理论上，香农第二定理已指出，只要实际信息传输率 (信道容量)，则无差错的信道编、译码方法是存在的。从原理上看，构造信道码的基本思路是根据一定的规律在待发送的信息码元中人为地加入一定的多余码元(称为监督码)，以引入最小的多余度为代价来换取最好的抗干扰性能。第2页/共164页6.1.1 信道编码的分类 由于实际信道存在噪声和干扰，使发送的码字与信道传输后所接收到的码字之间存在差错。在一般情况下，信道中噪声或干扰越大，码字产生差错的概率也就越大。有些实际信道既有独立随机差错也有突发性成串的差错，这种信道称混合差错信道，实际的移动信道属于此类信道。对不同的信道需要设计不同类型的信道编码方案，按照信道特性进行划分，信道编码可分为：以纠独立随机差错为主的信道编码、以纠突发差错为主的信道编码和纠混合差错的信道编码。从功能上看，信道编码可分为检错(可以发现错误)码与纠错(不仅能发现而且能自动纠正)码两类，纠错码一定能检错，检错码不一定能纠错，平常所说的纠错码是两者的统称。第3页/共164页 根据信息码元与监督码元之间的关系，纠错码分为线性码和非线性码。线性码信息码元与监督码元之间呈线性关系，它们的关系可用一组线性代数方程联系起来。非线性码信息码元与监督校元之间不存在线性关系。按照对信息码元处理的方法的不同，纠错码分为分组码和卷积码。分组码-把信息序列以每 个码元分组，然后把每组 个信息元按一定规律产生 个多余的监督码元，输出序列每组长为 ，则每一码字的 个校验元只与本码字的 个信息位有关，与别的码字的信息位无关，通常记分组码为 。第4页/共164页 其中分组码又可分循环码和非循环码：对循环码而言，其码书的特点是，若将其全部码字分成若干组，则每组中任一码字中码元循环移位后仍是这组的码字；对非循环码来说，任一码字中的码元循环移位后不一定再是该码书中的码字。卷积码-把信息序列以每 (通常较小)个码元分段，编码器输出该段的监督码元 不但与本段的 个信息元有关，而且还与其前面L段的信息码元有关，故记卷积码为 。按照每个码元的取值来分，可有二元码和多元码。由于目前的传输或存储系统大都采用二进制的数字系统，所以一般提到的纠错码都是指二元码。第5页/共164页综上所述，纠错码分类如图6.1.1所示。图6.1.1 纠错码的分类 第6页/共164页6.1.2 与纠错编码有关的基本概念 在通信系统的接收端，若接收到的消息序列 和发送的码符号序列 不一样，例如 ，而 ，与 中有两位不同，即出现两个错误，这种错误是由信道中的噪声干扰所引起的。为了说明如何描述这种错误及相应编码方法的性质，我们先介绍一些基本概念。(1)码长、码重和码距 码字中码元的个数称为码字的长度，简称码长，用 表示。码字中非“0”码元的个数称为码字的汉明重量(简称码重，记作 )。对二进制码来说，码重 就是码字中所含码元“1”的数目，例如码字“110000”，其码长 ，码重第7页/共164页两个等长码字之间对应码元不相同的数目称为这两个码组的汉明距离(简称码距)。例如码字“110000”与“100001”，它们的汉明距离 。在某一码书 中，任意两个码字之间汉明距离的最小值称为该码的最小距离 ，即：例如：码组 的最小码距 。从避免码字受干扰而出错的角度出发，总是希望码字间有尽可能大的距离，因为最小码距代表着一个码组中最不利的情况，从安全出发，应使用最小码距来分析码的检错、纠错能力。因此，最小码距是衡量该码纠错能力的依据，是非常重要的一个参数。第8页/共164页(2)错误图样在二元无记忆 次扩展信道中，差错的形式也可以用二元序列来描述。设发送码字为 ，接收码字为 ，两者的差别:称为错误图样。如错误图样中的第 位为“1”()，则表明传输过程中第 位发生了错误。例如：，而 ，则 ，可知接收的消息序列 中的第“2”位和第“6”位出现了错误。第9页/共164页(3)重复码和奇偶校验码 前面已述信道编码的任务是构造出以最小多余度的代价换取最大抗干扰性的“好“码。下面，从直观概念出发，说明多余度与抗干扰性能的关系，介绍两种极端情况：一是高可靠性，低有效性的重复码；二是高有效性，低可靠性的奇偶校验码。1)重复码 构成重复码的方法是当发送某个信源符号 时，不是只发一个，而是连续重发多个，连续重发的个数越多，重复码的抗干扰能力就越强，当然效率也越低。第10页/共164页不重复时为(1，1)重复码，如图6.1.2所示:图6.1.2 发送码元不重复 对这种情况可得结论：不重复，方法简单，但没有任何抗干扰能力，既不能发现，更不能纠正错误。重复一次时为(2，1)重复码，如图6.1.3所示:图6.1.3 发送码元重复一次 第11页/共164页 对这种情况可得结论：重发一次，效率降低一倍，可以换取在传输过程中允许产生一个错误(收端能发现它)，但不能纠正这个错误。重复二次时为(3，1)重复码，如图6.1.4所示：图6.1.4 发送码元重复二次 (3，1)重复码用“000”来代表信息“0”，用“111”来代表信息“1”，码本中共有两个码字。第12页/共164页 显然，所增加的两位码元并不会增加信息，是多余的，因而使信息传输率降低。此外，除了传送信息的“000”和“111”两种组合之外，还有六种组合001，010，011，100，101，110没有利用。当信道上信噪比足够大时，我们可以认为码字中产生的错误一般不多于一个码元，那么，如果接收到“001”、“010”、“100”，我们就可判定实际传输的是“000”；同样，如接收到“011”、“101”、“110”，则可判定为“111”。因此多余码元使我们可检出一个错，并且还可纠正这个错误，这样就提高了信息传输的可靠性。对这种情况可得结论：重发二次，效率降低二倍，但换取了可纠正一个差错或发现两个差错的性能改善。第13页/共164页2)奇偶检验码 奇偶校验是一种最基本的校验方法。构成奇偶检验码的方法是在每 个二进制信息位后加上一个奇(偶)监督位(或称校验位)，使码长 ，同时使码中“1”的个数恒为奇数(或偶数)，如图6.1.5所示。在奇偶校验码中，监督位 ，它是一种码重 为奇数(或偶数)的系统分组码。图6.1.5 奇偶校验码 第14页/共164页 奇偶校验又可以分为奇校验和偶校验。其规则如下：奇校验-如果信息码元中“1”值的个数为奇数个，则校验码元值为“0”；如果信息码元中“1”值的个数为偶数个，则校验码元值为“1”。即所有信息码元与校验码元的模二和等于“1”。偶校验-如果信息码元中“1”值的个数为偶数个，则校验码元值为“0”；如果信息码元中“1”值的个数为奇数个，则校验码元值为“1”。即所有信息码元与校验码元的模二和等于“0”。根据奇偶校验的规则，校验位值的确定方法如表6.1.1所示。第15页/共164页表6.1.1 奇偶校验规则表 校验方式信息位中“1”值的个数校验位值奇校验奇数个0偶数个1偶校验偶数个0奇数个1第16页/共164页例如，在七位信息码中，字符A的代码为1000001，其中有两位码元值为“1”。若采用奇校验编码，由于这个字符的七位代码中有偶数个“1”，所以校验位的值应为“l”，其8位组合代码为：10000011，前7位是信息位，最右边的1位是校验位。同理，若采用偶校验，可得奇偶校验位的值为“0”，其8位组合代码为：10000010。这样在接收端对码字中“1”的个数进行检验，如有不符，就可断定发生了差错。在接收端进行校验时，如采用奇校验编码，当接收到的字符经检测其八位代码“l”的个数为奇个数时，则被认为传输正确；否则就被认为传输中出现差错。然而，如果在传输中有偶数位出现差错，用此方法就检测不出来了。第17页/共164页所以，奇偶校验方式只能检测出位代码中出现的任意奇数个错误，如果代码中错码数为偶数个，则奇偶校验不能奏效。由于奇偶校验码容易实现，所以当信道干扰不太严重以及码长不很长时很有用，特别是在计算机通信网的数据传送中经常应用这种检错码。奇偶校验编码如果是在一维空间上进行，则是简单的“水平奇偶校验”或“垂直奇偶校验”码，如果是在二维空间上进行，则是“水平垂直奇偶校验码”。第18页/共164页垂直奇偶校验 在垂直奇偶校验编码中，先将整个要发送的信号序列划分成长度为的若干个组，然后对每组按码元中“1”的个数为奇数或偶数的规律，在其后附加上一位奇偶校验位，如表6.1.2所示。表6.1.2中将70个码元组成的信号序列划分成长度为7的10个组，每组按顺序一列一列地排列起来，然后对垂直方向的码元进行奇偶校验(假设采用偶校验)，得到一行校验位，附加在其他各行之后，然后按列的顺序进行传输。第19页/共164页码元位分组1234567891011000111001201101000113000101110041000100000500011011016011100100070110101001偶校验位0111101010表6.1.2 垂直奇偶校验 第20页/共164页在垂直奇偶校验编码和校验过程中，用硬件方法或软件方法来实现上述连续的奇偶校验运算都非常容易，而且在发送时可以边发送边产生校验位，并插入发送，在接收时边接收边进行校验后去掉校验位。垂直奇偶校验方法的编码效率为：这种奇偶校验方法能检测出每个分组中的所有奇数位的错，但检测不出偶数位的错。对于突发性错误，由于出错码元为奇数个或偶数个的概率各占一半，因而对差错的漏检率接近于1/2。第21页/共164页水平奇偶校验 为了降低对突发错误的漏检率，可以采用“水平奇偶校验”，它是以分组为单位，对一组中的相同位的码元进行奇偶校验。在水平奇偶校验中，把信号序列先以适当的长度划分成个组，每组位码元，并把每组按顺序一列一列地排列起来，如表6.1.3所示 然后对水平方向的码元进行奇偶校验，得到一列校验位，附加在其他各列之后，最后按列的顺序进行传输。表中的信号序列共分成10个组，每组有7个码元。传输时按列的顺序先传送第l组，再传送第2组，最后传送第11列即校验位列(本例采用偶校验)。因此，在信道中传送的二进制信号序列为：100100001000111101101。第22页/共164页码元位分组偶校验位12345678910110001110011201101000111300010111000410001000000500011011011601110010000701101010011表6.1.3 水平奇偶校验 第23页/共164页水平奇偶校验的编码效率是：水平奇偶校验不但可以检测各组同一位上的奇数位错，而且可以检测出突发长度小于或等于(每组的码元数)的所有突发性错误(突发性错误是指一连串的码元均出错)，因为传输时按组的顺序发送，发生长度小于或等于的突发性错误必然分布在不同行中，每行最多只有一位出错，所以可以检出差错。水平奇偶校验的漏检率比垂直奇偶校验码要低。但是，在实现水平奇偶校验时，不论采用硬件方法还是软件方法，都不能在发送过程中边产生边插入奇偶校验位，而必须等待要发送的完整数据信号序列到齐后，才能确定校验位，也就是要使用一定的存储空间。因此，其编码和检测的实现都要复杂一些。第24页/共164页水平垂直奇偶校验 同时进行水平奇偶校验和垂直奇偶校验就构成二维的“水平垂直奇偶校验码”，如表6.1.4所示。其具体实现过程是：先将整个欲发送的信号序列划分成长度为的若干个组；然后对每个组按码元中“1”的个数为奇或偶数的规律，在其后附加上一位奇偶校验位(表中采用偶校验)；再对每个字符的相同位按“1”的个数为奇或偶数的规律，增加一个校验位(表中采用偶校验)。第25页/共164页码元位分组偶校验位12345678910110001110011201101000111300010111000410001000000500011011011601110010000701101010011偶校验位01111010100表6.1.4 水平垂直奇偶校验 第26页/共164页水平垂直奇偶校验的编码效率为：这种方法能检测出所有3位或3位以下的错误，因为在这种情况下，至少会在某一行或某一列上出现一位错，这时错误就能被检测到；还能检测出奇数位错、突发长度小于或等于的突发性错以及很大一部分偶数位错。一些试验测量表明，这种方式的编码可使误码率降至原始误码率的百分之一到万分之一。另外，水平垂直奇偶校验不仅可检错，还可用来纠正部分差错。上述奇偶校验码中，水平奇偶校验码、垂直奇偶校验码是单纯检错码，而水平垂直奇偶校验码则还具有有限的纠错能力，但多数情况下只用于检错。第27页/共164页6.1.3 检错与纠错原理 检错、纠错的目的是要根据信道接收端接收到的信息序列 来判断 是否就是发送的序列，如果有错则尽可能纠正其中的错误。要纠正传输差错，首先必须检测出错误。而要检测出错误，常用的方法是将发送端要传送的信息序列(常为二进制序列)中截取出长度相等的码元进行分组，每组长度为k，组成k位码元信息序列 ，并根据某种编码算法以一定的规则在每个信息组的后面产生 个冗余码元，由冗余码元和信息码元一起形成“位编码序列”，即信号码字 ，位的码字比信息码长(有 个码元)，因而纠错编码是冗余编码，如图6.1.6所示。第28页/共164页图6.1.6 纠错编码 译码就是利用校验关系进行检错、纠错的，在接收端收到的位码字中，信息码元与冗余码元之间也应符合上述编码规则，并根据这一规则进行检验，从而确定是否有错误。这就是差错控制的基本思想。我们把这种将信息码元分组，为每组码附加若干校验码的编码称为分组码。在分组码中，校验码元仅校验本码组中的信息码元。分组码一般用符号 表示，其中 是每组二进制信息码元的数目，是编码组的长度(简称码长)，即编码组的总位数，为每码组中的校验码元(或称监督位)数目。第29页/共164页通常，将分组码规定为具有如图6.1.7所示的结构。图中前面 位()为信息位，后面附加 个()校验位。图6.1.7 分组码的结构 实现检纠错常用的基本方法除了前面介绍的 重复码方法和奇偶校验方法外，还有等重码(或定比码)方法：奇偶校验方法。增加偶(或奇)校验位使得对消息序列 而言校验方程成立，当校验位数增加时，可以检测到差错图样的种类数也增加，但同时码率减小。第30页/共164页 重复码方法。重复消息位使之可以检测出任意小于 个差错的错误图样。等重码方法。设计码字中的非“0”符号个数(若是二进制码则为“1”的个数)恒为常数，使码书 由全体重量恒等的 长矢量组成。表6.1.5所示为一种用于表示数字“0”到“9”的五中取三等重码(所有码字的码重都等于“3”)的例子。表6.1.5 五中取三等重码 显然五中取三等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错。123456789001011110011011011010001111010111100011101001101101第31页/共164页对于纠错码，其抗干扰能力完全取决于码书C中许用码字之间的距离。码的最小距离越大，则码字间的最小差别越大，抗干扰能力就越强，即受较强的干扰仍不会造成许用码字之间的混淆。差错控制编码是用增加码元数，利用“冗余”来提高抗干扰能力的，即是以降低信息传输速率为代价来减少错误的，或者说是用削弱有效性来增强可靠性的。第32页/共164页6.1.4 检错与纠错方式和能力(1)检错与纠错方式 自动请求重发方式-用于检错的纠错码在译码器输出端给出当前码字传输是否可能出错的指示，当有错时按某种协议通过一个反向信道请求发送端重传已发送的全部或部分码字，这种纠错码的应用方式称为自动请求重发方式(ARQ，Automatic-Repeat-reQuest)。前向纠错方式-用于纠错的纠错码在译码器输出端总要输出一个码字或是否出错的标志，这种纠错码的应用方式称为前向纠错方式(FEC，Forward-error control)。另外用于检错与纠错的方式还有混合纠错(HEC，Hybrid Error Correction)。图6.1.8所示为上述几种检错与纠错方式示意图，图中有斜线的方框表示在该端检出错误。第33页/共164页图6.1.8 差错控制的工作方式 ARQ方式：发送端用编码器对发送数据进行差错编码，通过正向信道送到接收端，而接收端经译码器处理后只是检测有无差错，不作自动纠正。如检测到差错，则利用反向信道反馈信号，请求发送端重发有错的数据单元，直到接收端检测不到差错为止。第34页/共164页FEC方式：发送端用编码器对发送数据进行差错编码，在接收端用译码器对接收到的数据进行译码后检测有无差错，通过按预定规则的运算，如检测到差错，则确定差错的具体位置和性质，自动加以纠正，故称为“前向纠错”。HEC方式：是检错重发和前向纠错两种方式的混合。发送端用编码器对发送数据进行便于检错和纠错的编码，通过正向信道送到接收端，接收端对少量的接收差错进行自动前向纠正，而对超出纠正能力的差错则通过反馈重发方式加以纠正，所以是一种纠检结合的混合方式。(2)检错与纠错能力 一个纠错码的每个码字都可以形成一个汉明球，因此要能够纠正所有不多于 位的差错，纠错码的所有汉明球均应不相交，判定纠错码的检、纠错能力可根据任意两个汉明球不相交的要求，由码的最小距离 来决定。第35页/共164页定理6.1.1 若纠错码的最小距离为 ，那么如下三个结论的任何一个结论独立成立：若要发现个独立差错，则要求最小码距 ；若要纠正个独立差错，则要求最小码距 ；若要求发现个同时又纠正个独立差错，则；这里说的“同时”是指在译码过程中，若错误个数 ，则能纠正；若错误个数 ，但 ，则能检测 这些错误，但不能纠正。或者说能检测个错误，其中 个错误可以纠正。其直观的关系如图6.1.9所示。第36页/共164页 (a)纠错能力的几何说明 (b)检错能力的几何说明 (c)区分纠错和检错的示意图(d)检错、纠错能力与最小码距的关系图6.1.9 最小码距与检错、纠错能力 第37页/共164页图6.1.9(c)中，粗线球面(圆)是纠正 个错误的球面，细线球面(圆)代表检出 个错误的球面。当接收码字 中不包含错误或错误 ，将落在粗线球内或球上，因而可把 纠正为原发送的码字，当接收码字 包含 个而 个错误时，不会落在任何码字的纠错球内，但此时代表纠错范围的粗线球面与另一码字的代表检错范围的细线球面没有相交或相切，于是可将纠错和检错区分开来。当码的最小码距为3或4时，可以纠正所有1位错。当码的最小码距为5时，可以纠正所有2位错。当码的最小码距为时，可以纠正所有 位错。第38页/共164页定理6.1.1说明，码的最小距离 越大，码的纠(检)错误的能力越强。但是，随着多余码元的增多，信息传输速率会降低得越多。通常用 来表示码字中信息码元所占的比例，称为编码效率，简称码率，它是衡量码性能的又一个重要参数。码率越高，信息传输率就越高，但此时纠错能力要降低，若 时就没有纠错能力了。可见，码率与纠错能力之间是有矛盾的。第39页/共164页6.2 6.2 线性分组码线性分组码 线性分组码是纠错码中非常重要的一类码，虽然对于同样码长的非线性码来说线性码可用码字较少，但由于线性码的编码和译码容易实现，而且是讨论其他各类码的基础，至今仍是广泛应用的一类码。第40页/共164页6.2.1 线性分组码的基本概念 定义6.2.1 对信源编码器输出的 进制序列进行分组，设分组长度为 ，相应的码字表示为：其中：每个码元 都是 进制的，显然这样的码字共有 个。信道编码(纠错编码)的目的是将信息码字 进行变换，使其成为以下形式：其中：，为 进制数，显然这样的码字共有 个。我们称全体码字 的集合为 元分组码。若由 到 之间的变换为线性变换，则称全体码字 的集合为 元线性分组码，常用 线性分组码 来表示全体码字 的集合。第41页/共164页例6.2.1 设将信源编码器输出的二进制序列进行分组，分组长度为 ，相应的码字表示为：，这里 是二进制的，即 。这样的码字共有两个，即“1”和“0”。现将 进行变换，变换规则为：因此，形成的纠错码具有以下形式：。由于 只取“0”或“l”，所以 的全体码字只有两个：长为 的全“0”或全“l”序列。即经过上述变换，得到了 重复码。第42页/共164页例6.2.2 设信源编码器输出的信息序列为 ，其中 ：是二进制数。信道编码器输出的码字为 ，其中 ：也是二进制数。若从 到 的变换规则为：由于从 到 的变换是一种线性变换，所以全体 的集合构成了种 线性分组码。第43页/共164页由本例可以看出，变换后码字集合中每一个码字的所有码元之和为：因为假设了码为二进制码，上述码元的和是模2和。因此，变换后将每一个码字的码元全部加起来，它的模2和为“0”，即每一个码字中“1”的个数为偶数个，所以这种码为偶校验码。第44页/共164页例6.2.3 分组码，按以下的规则(校验方程)可得到四个校验元：式中：是三个信息码元，方程中的加运算均为模2加。由此可得到 分组码的八个码字。八个信源序列与八个码字的对应关系列于表6.2.1中。由校验方程看到，信息码元与校验码元满足线性关系，因此该 码是线性码。第45页/共164页表6.2.1 例6.2.3编出的 线性码的码字与信息码元的对应关系 信息码元码字0 0 00 0 0 0 0 0 00 0 10 0 1 1 1 0 10 1 00 1 0 0 1 1 10 1 10 1 1 1 0 1 01 0 01 0 0 1 1 1 01 0 11 0 1 0 0 1 11 1 01 1 0 1 0 0 11 1 11 1 1 0 1 0 0第46页/共164页对于线性分组码有一个非常重要的结论：一个 线性分组码中非零码字的最小重量等于该码的最小距离 。证明 设有任意两个码字 。根据线性分组码的性质，有 。而 的码重等于 的码距 。即：而 是C中任意两个非全零码字，所以：证毕 由例6.2.3 线性码的八个码字可见，除全零码字外，其余七个码字最小重量 ，所以该 线性码的最小距离 。第47页/共164页6.2.2 生成矩阵和一致校验矩阵 从矢量空间的角度，形形色色的编码方法实质上是采用了不同的基底选择方法及矢量映射规则而形成的。基底的选择与映射规则均可用矩阵来表示，因此在线性分组码的讨论中就有了生成矩阵和一致校验矩阵的概念。(1)生成矩阵 在讨论生成矩阵之前，我们再看例6.2.3的 线性分组码。该码所满足的校验方程可写成矩阵形式：式中称线性分组码的生成矩阵。第48页/共164页定义6.2.2 若信息组以不变的形式，在码字的任意 位中出现，则该码称为系统码。否则，称为非系统码。目前常用的有两种形式的系统码：一种是把信息组排在码字 的最左边 位：，式(6.2.2)就是这种形式，若非特别说明，我们后面所说的系统码均指这种形式。另一种是把信息组安置在码字 的最右边 位：。第49页/共164页能够产生系统码的生成矩阵为典型矩阵(或称标准阵)，典型矩阵的最大优势是便于检查生成矩阵 的各行是否是线性无关。如果 不具有标准型，虽能产生线性码，但码字不具备系统码的结构，因而存在难以区分码字中信息码元和监督码元的缺点。由于系统码的编码与译码较非系统码简单，而且对分组码来说，系统码与非系统码的抗干扰能力是等价的，故若无特别声明，我们仅讨论系统码。如果生成矩阵 为非标准型的，可经过行初等变换变成标准型。第50页/共164页(2)一致校验矩阵 从前面的讨论我们知道，编码问题就是在给定的 下如何从已知的 个信息码元求得 个校验码元。一般可写成：或 式(6.2.3)表明，中各码元是满足由矩阵 所确定的个线性方程的解，故 是码书 中的一个码字，由 的全体就构成了码书 ；反之，若某码元序列满足由 所确定的 个线性方程，则该码元序列一定是码书 中的一个码字。第51页/共164页因此，一定，便可由信息码元求出校验码元，编码问题就迎刃而解；或者说，要解决编码问题，只要找到 即可。由于 码的所有码字均按所确定的规则求出，故称 为其一致校验矩阵。综上所述，我们将 矩阵的特点归纳如下：矩阵的每一行代表一个线性方程的系数，它对应求一 个校验码元的线性方程。矩阵每一列代表此码元与哪几个校验方程有关。由该 矩阵得到的 分组码的每一码字 都必须满足 由 矩阵的行所确定的线性方程，即式(6.2.3)或式 (6.2.4)。第52页/共164页 码需有 个校验码元，故需有 个独立的线性方程。因此，矩阵必须有 行，且各行之间线性无关，即 矩阵的秩为 。由于生成矩阵 中的每一行及其线性组合都是 码中的一个码字，故有：或 由例6.2.3不难看出，码的 矩阵右边为一个四阶单位矩阵。通常，系统型 线性分组码的 矩阵右边 列组成一个单位矩阵 ，故有：式中 是一个 阶矩阵。我们称这种形式的 矩阵为典型矩阵(或标准矩阵)，同样，采用典型矩阵形式的 矩阵更易于检查各行是否线性无关。第53页/共164页 由式(6.2.5)易得：由此关系可知 或 这说明，的第一行就是 的第一列，的第二行就是 的第二列，因此，矩阵一旦确定，则 矩阵也就确定，反之亦然。第54页/共164页(3)线性分组码的编码 线性分组码的编码就是根据一致校验矩阵 或生成矩阵 将长度为 的信息码元变换成长度为 的码字。这里以 线性分组码为例来说明构造编码电路的方法。例6.2.4 设二元码字为 ，码的一致校验矩阵 为：由 得：第55页/共164页 按照该线性方程组，可直接画出 线性分组码的并行编码电路和串行编码电路，如图6.2.1所示。(a)并行编码电路 (b)串行编码电路图6.2.1 线性分组码编码电路原理图 第56页/共164页(4)对偶码和缩短码 我们已经讨论了 线性分组码的生成矩阵 与其对应的一致校验矩阵 ，如果把 码的一致校验矩阵看成是 码的生成矩阵，将 码的生成矩阵看成是 码的一致校验矩阵，则称这两种码互为对偶码。例6.2.6 求例6.2.3所述 码的对偶码。显然，码的对偶码应是 码，由对偶码的定义得，码的 矩阵就是 码的 矩阵，将其化成标准形式后即可按式(6.2.1)得到 码的对偶码 码，如表6.2.2所示。第57页/共164页表6.2.2 例6.2.3线性码的对偶码 信息码元码字信息码元码字0 0 0 00 0 0 0 0 0 01 0 0 01 0 0 0 1 0 10 0 0 10 0 0 1 0 1 11 0 0 11 0 0 1 1 1 00 0 1 00 0 1 0 1 1 01 0 1 01 0 1 0 0 1 10 0 1 10 0 1 1 1 0 11 0 1 11 0 1 1 0 0 00 1 0 00 1 0 0 1 1 11 1 0 01 1 0 0 0 1 00 1 0 10 1 0 1 1 0 01 1 0 11 1 0 1 0 0 10 1 1 00 1 1 0 0 0 11 1 1 01 1 1 0 1 0 00 1 1 10 1 1 1 0 1 01 1 1 11 1 1 1 1 1 1第58页/共164页 在有些情况下，如果对某一给定长度的信息码元找不到合适码长的码，则可将某一 码缩短以满足要求。例如，在 线性分组码的码字集合中将最左边一位为“0”的消息和对应的码字选出来，并把消息中最左边的“0”去掉，则可构成 线性分组码，这种码称为缩短码。如表6.2.3所示。表6.2.3 例6.2.3线性码的缩短码 信息码元码字0 00 0 0 0 0 00 10 1 1 1 0 11 01 0 0 1 1 11 11 1 1 0 1 0第59页/共164页6.2.3 线性分组码的译码 只要找到 矩阵或 矩阵，便解决了编码问题。经编码后发送的码字，由于信道干扰可能出错，接收方怎样发现或纠正错误呢，这就是译码要解决的问题。定义6.2.3 设 码的一致校验矩阵为 ，是发送码字为 时的接收序列，则称：为接收序列 的伴随式或校正子。伴随式 是一致校验矩阵 的线性组合，如果错误图样中有一些分量不为“0”，则在 中正好就是 中不为“0”的那几列组合而成。由于 是 维的列向量，所以伴随式 也是一个 维向量。第60页/共164页由上面的分析，可得如下结论：从式(6.2.7)可知伴随式 仅与错误图样 有关，它充分反映了信道受干扰的情况，而与发送的是什么码字无关。伴随式是是否有错的判别式，若 ，则判没有出错；若 ，则判有错。不同的错误图样具有不同的伴随式，它们是一一对应的，对二元码来说，伴随式即为 矩阵中与错误图样对应的各列之和。注意，如果错误图样 本身就是一个码字，即 码，那么计算伴随式 得到的结果必为“”，此时的错误不能发现，也无法纠正，因而这样的错误图样称为不可检错误图样。第61页/共164页例6.2.7 计算例6.2.3所述 码接收 时的伴随式。解：码的一致校验矩阵为：当接收时，接收端译码器根据接收序列计算的伴随式为：第62页/共164页 因此，译码器判别接收序列无错，传输中没有发生错误。当接收时，接收端译码器根据接收序列计算的伴随式为:由于 ，所以译码器判别接收序列有错，传输中有错误发生。码是纠正单个错误的码，观察 即为 的第二行，因此可判定接收序列 的第二位发生了错误。由于接收序列中错误个数与码的纠错能力相符，所以可正确译码，即发送码字应为 。第63页/共164页当接收 时，接收端译码器根据接收序列计算的伴随式 为：，但与 的任何一列都不相同，无法判别错误发生在哪些位上，此时只能发现有错。伴随式的计算可用电路来实现，如前所述的 码，设接收序列 ，则伴随式为：第64页/共164页根据上式，可画出 码的伴随式计算电路，如图6.2.3所示。图6.2.3 码的伴随式计算电路 第65页/共164页6.2.4 线性分组码的纠错能力 由前面的介绍可知，线性分组码的纠错能力 和码字的最小距离 有关，一般 是在设计通信系统时提出的，那么寻找满足纠正 个错误码元的码字就是编码技术的任务，为此我们还需进一步研究 和码字结构的关系。线性分组码码字的结构是由生成矩阵(或一致校验矩阵)决定的，若巳知 矩阵，该码的结构也就知道了，实际上所谓校验就是利用 矩阵去鉴别接收矢量 的结构。那么从研究码的纠错能力角度来看 与 有什么关系呢？定理6.2.1 线性分组码最小码距等于 的充要条件是 矩阵中任何 列线性无关。第66页/共164页定理6.1.2是构造任何类型线性分组码的基础，由定理可得出以下三个结论：为了构造最小距离 (可检测 个错误)或 (可纠正 个错误)的线性分组码，其充要条件是要求 矩阵中任意 列线性无关。例如，要构造最小距离为3的码，则要求 矩阵中任意2列线性无关。对于二元码，即要求 矩阵满足无相同的列和无全“0”的列，就可纠正所有单个错误。因为交换 矩阵的各列不会影响码的最小距离，因此所有列向量相同但排列位置不同的 矩阵所对应的分组码，其纠错能力和码率是等价的。任一线性分组码的最小距离(或最小重量)均满足 。第67页/共164页满足 的线性分组码称为极大最小距离码。在同样的 之下，由于 最大，因此纠错能力更强，所以设计这种码，是编码理论中人们感兴趣的一个课题。根据定理6.2.1，我们可以由 矩阵的列的相关性直接知道码的纠错、检错能力。在巳知信息位 的条件下，如何去确定监督位 的位数(即确定码长)，才能满足对纠错能力 的要求？对此有下述结论：若 是 二元码，当巳知 时，要使 能纠正 个错，则必须有不少于 个校验位，并且使 满足：第68页/共164页式中的 为 中 取的组合。满足 时的码称为完备码，这种码的校验元得到了最充分的利用。式(6.2.9)又称为汉明不等式。第69页/共164页6.2.5 汉明码 汉明码是汉明(Hamming)于1950年提出的能纠正一位错的特殊的线性分组码。汉明码有许多很好的性质，是一种完备码，它可以用一种简洁有效的方法进行译码。由于它的编、译码较简单，且较容易实现，因此被广泛采用，尤其是在计算机存储与运算系统中被广泛应用。(1)汉明码的参数 对于任意正整数 ，存在具有下列参数的二进制汉明码：码 长：信息位数：监督位数：最小码距：第70页/共164页给定 后，即可构造出具体的 汉明码，这可以从建立致校验矩阵 入手。我们知道，矩阵的列数就是码长 ，行数等于 。例如 ，可算出 ，因而是(7，4)线性码。其 矩阵正是用 个非零三维列向量构成的。如：此时，矩阵的列所对应的十进制数正好是“1”“7”，对于纠一位差错来说，其伴随式的值就等于对应的 矩阵的列矢量，即错误位置。所以这种形式的 矩阵构成的码很便于纠错，但这是非系统的(7，4)汉明码的一致校验矩阵。如果要得到系统码，可调整各列次序来实现：第71页/共164页有了 ，就可得到系统码的校验位，其相应的生成矩阵为：设码字 ，根据 (或 )及关系式 ，有：(7，4)汉明码的编码电路原理图如图6.2.4所示。第72页/共164页汉明码的译码，可以采用计算伴随式，然后确定错误图样并加以纠正的方法。图6.2.5所示为(7，4)汉明码的译码电路原理图。需要注意的是(7，4)汉明码的矩阵并非只有以上两种。原则上讲，汉明码的一致校验矩阵有 列 行，它的 列由除了全“0”以外的 位码组构成，每个码组只在某列中出现一次，矩阵中各列的次序是可任意改变。另外，对照完备码的定义可知，汉明码实际上是 的完备码。第73页/共164页图6.2.5 (7，4)汉明译码器电路原理图 第74页/共164页6.3 6.3 循环码循环码循环码是一种特殊的线性分组码，属于线性分组码的一个重要子类，也是目前研究最为透彻的一类码，大多数有实用价值的纠错码都是循环码。循环码与一般的线性分组码相比具有以下优点：循环码的编码及译码易于用简单的具有反馈连接的移位寄存器来实现。定义6.3.1 设有 线性分组码 ，如果它的任意一个码字的每一次循环移位仍然是 中的一个码字，则称 为循环码。也即，如果 是循环码 的一个码字，那么 等也都是 的码字时，则所有这些具有循环特性的码字的全体便构成了循环码 。第75页/共164页例如在例6.2.3中的 线性分组码就是循环码，该码如表6.3.1所示。由表可以看到，在右边的码字栏内，任意一个码字将其循环移位后，其结果仍然是该栏内的一个码字。例如将第二行的码字循环右移一位后可得到第五行的码字，第五行的码字循环右移一位后得到第三行的码字等。实际上右移和左移具有同样的效果。循环码的主要特点是：理论成熟：可利用成熟的代数结构深入探讨其性质；实现简单：可利用循环移位特性在工程上进行编、译码；第76页/共164页 循环码的描述方式有很多，但在工程上最有用的是采用多 项式的描述方法。由于循环码的以上特点，可以将其用多项式来表示，从而可以借助代数的工具对循环码进行分析，这也是循环码能被广泛应用的原因之一。信息码元码字0 0 00 0 0 0 0 0 00 0 10 0 1 1 1 0 10 1 00 1 0 0 1 1 10 1 10 1 1 1 0 1 01 0 01 0 0 1 1 1 01 0 11 0 1 0 0 1 11 1 01 1 0 1 0 0 11 1 11 1 1 0 1 0 0第77页/共164页6.3.1 循环码的多项式描述 设有循环码字 ，则可以用一个次数不超过 的多项式惟一确定，其相应的多项式可表示为：(6.3.1)即码字 与码多项式 一一对应。由循环码的特性可知，若 是循环码 的一个码字，则 也是该循环码的一个码字，它的码多项式为：(6.3.2)比较式(6.3.1)和式(6.3