差错控制编码(传媒05级).ppt

第8章 差错控制编码 第第8章章  差错控制编码差错控制编码 8.1  差错控制编码的基本概念差错控制编码的基本概念 8.2  差错控制方式差错控制方式 8.3  差错控制编码分类差错控制编码分类 8.4  检错和纠错原理检错和纠错原理 8.5  几种常用的检错码几种常用的检错码 8.6  线性分组码线性分组码 8.7  循环码循环码 9/13/20241第8章 差错控制编码 8.1  差错控制编码的基本概念差错控制编码的基本概念     不管是模拟通信系统还是数字通信系统，都存在不管是模拟通信系统还是数字通信系统，都存在因干扰和信道传输特性不好对信号造成的不良影因干扰和信道传输特性不好对信号造成的不良影响      它使模拟信号波形会发生畸变，一旦失真很难它使模拟信号波形会发生畸变，一旦失真很难纠正因此，在模拟系统中只能采取抗干扰、纠正因此，在模拟系统中只能采取抗干扰、防干防干扰措施扰措施,尽量将干扰降到最低程度以保证通信质量尽量将干扰降到最低程度以保证通信质量 9/13/20242第8章 差错控制编码 在数字系统中，干扰也会使信号产生变在数字系统中，干扰也会使信号产生变形，但一定程度的信号畸变不会影响接收，因形，但一定程度的信号畸变不会影响接收，因为我们只关心数字信号的电平状态（是高电平为我们只关心数字信号的电平状态（是高电平还是低电平），而不太在乎其波形的失真。

也还是低电平），而不太在乎其波形的失真也就是说，数字系统对干扰或信道特性不良的宽就是说，数字系统对干扰或信道特性不良的宽容度比模拟系统大容度比模拟系统大9/13/20243第8章 差错控制编码 数字通信系统除了可采取与模拟系统同样的措数字通信系统除了可采取与模拟系统同样的措施抗干扰外，还可对所传数字信息进行特殊的处施抗干扰外，还可对所传数字信息进行特殊的处理（即差错控制编码），对误码进行检错和纠理（即差错控制编码），对误码进行检错和纠错，进一步降低误码率错，进一步降低误码率      因此，数字通信系统可从硬件上采用抗干扰措因此，数字通信系统可从硬件上采用抗干扰措施，软件上采用信道编码对信息传输中出现的错施，软件上采用信道编码对信息传输中出现的错误进行控制和纠正误进行控制和纠正9/13/20244第8章 差错控制编码 图图8―1    两种通信系统干扰示意图两种通信系统干扰示意图 9/13/20245第8章 差错控制编码 香农提出了有扰信道中信息传输的重要理香农提出了有扰信道中信息传输的重要理论论——香香农农第第二二定定理理：：对对于于一一个个给给定定的的有有扰扰信信道，若该信道容量为道，若该信道容量为C，，则只要信道中的则只要信道中的R小小于于C，，就一定存在一种编码方式，使编码后就一定存在一种编码方式，使编码后的误码率随着码长的误码率随着码长n的增加按指数下降到任意的增加按指数下降到任意小的值。

或者说只要小的值或者说只要R

频分量、去除直流分量等等）9/13/20248第8章 差错控制编码 8.2  差错控制方式差错控制方式  差错控制方式可分为：前向纠错（差错控制方式可分为：前向纠错（FEC）、）、检错重发（检错重发（ARQ））和混合纠错（和混合纠错（HEC）三）三种图8―2是这三种方式构成的差错控制系是这三种方式构成的差错控制系统原理框图统原理框图 9/13/20249第8章 差错控制编码 图图8―2   三种差错控制方式示意图三种差错控制方式示意图 9/13/202410第8章 差错控制编码 前向纠错前向纠错(FEC)：发端将信息码经信道编码后：发端将信息码经信道编码后变成能够纠正错误的码，收端通过译码能自动发现变成能够纠正错误的码，收端通过译码能自动发现并纠正因传输带来的数据错误并纠正因传输带来的数据错误    优点：只要求单向信道，适合于只能提供单向信优点：只要求单向信道，适合于只能提供单向信道的场合，或广播传输方式接收信号的延时小、道的场合，或广播传输方式接收信号的延时小、实时性好实时性好   缺点：设备复杂、成本高，且缺点：设备复杂、成本高，且纠错能力愈强，设备纠错能力愈强，设备就愈复杂。

就愈复杂 9/13/202411第8章 差错控制编码 检错重发检错重发(ARQ)：发端将信息码编成能够检错：发端将信息码编成能够检错的码，收端收到后进行检验，将检验结果（有误码的码，收端收到后进行检验，将检验结果（有误码或者无误码）通过反向信道反馈给发端作为应答信或者无误码）通过反向信道反馈给发端作为应答信号发端根据收到的应答信号做出是继续发送新的号发端根据收到的应答信号做出是继续发送新的数据还是把出错的数据重发的判断数据还是把出错的数据重发的判断        检错重发系统可分为三种，停发等候重发系检错重发系统可分为三种，停发等候重发系统、返回重发系统和选择重发系统统、返回重发系统和选择重发系统9/13/202412第8章 差错控制编码       收端收到该码组并检验后，将应答信号收端收到该码组并检验后，将应答信号ACK发回发端，发端确认码组发回发端，发端确认码组1无错，就将无错，就将码组码组2发送出来；收端判断该码组有错并以发送出来；收端判断该码组有错并以NAK信号告知发端，发端将码组信号告知发端，发端将码组1重新发送重新发送一次9/13/202413第8章 差错控制编码 图图8―3  检错重发的三种工作方式检错重发的三种工作方式 9/13/202414第8章 差错控制编码 返回重发系统如图返回重发系统如图8―3（（b）所示，发端不停）所示，发端不停顿地发送信息码组，不再等候顿地发送信息码组，不再等候ACK信号，如果收信号，如果收端发现错误并发回端发现错误并发回NAK信号，则发端从下一个码信号，则发端从下一个码组开始重发前一段组开始重发前一段N个码组，图中个码组，图中N=5。

收端收到收端收到码组码组2有错发端在码组有错发端在码组6后重发码组后重发码组2、、3、、4、、5、、6，这种返回重发系统的传输效率比停发等候系统，这种返回重发系统的传输效率比停发等候系统有很大改进，在很多数据传输系统中得到应用有很大改进，在很多数据传输系统中得到应用9/13/202415第8章 差错控制编码 图图8―3（（c）：系统也是连续不断地发送码）：系统也是连续不断地发送码组，收端检测到错误后发回组，收端检测到错误后发回NAK信号，但是发端不信号，但是发端不是重发前是重发前N个码组，而是只重发有错误的那一组个码组，而是只重发有错误的那一组如只重发收端检出有错的码组如只重发收端检出有错的码组2      收端对已认可的码组，从缓冲存储器读出时重收端对已认可的码组，从缓冲存储器读出时重新排序，恢复出正常的码组序列新排序，恢复出正常的码组序列      系统传输效率最高，但价格也最贵系统传输效率最高，但价格也最贵9/13/202416第8章 差错控制编码 混合纠错方式是前向纠错方式和检错重发方式混合纠错方式是前向纠错方式和检错重发方式的结合如图的结合。

如图8―2（（c））所示      其内层采用其内层采用FEC方式，纠正部分差错；外层采方式，纠正部分差错；外层采用用ARQ方式，重传那些虽已检出但未纠正的差方式，重传那些虽已检出但未纠正的差错混合纠错方式在实时性和译码复杂性方面是前错混合纠错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷，较适合于环路延迟向纠错和检错重发方式的折衷，较适合于环路延迟大的大的高速数据传输系统高速数据传输系统 9/13/202417第8章 差错控制编码 8.3  差错控制编码分类差错控制编码分类   介绍几种主要分类介绍几种主要分类1)根据编码功能可分为检错码、纠错码和纠根据编码功能可分为检错码、纠错码和纠删码三种类型，只能完成检错功能的叫检错删码三种类型，只能完成检错功能的叫检错码；具有纠错能力的叫纠错码；而纠删码既码；具有纠错能力的叫纠错码；而纠删码既可检错也可纠错可检错也可纠错9/13/202418第8章 差错控制编码 (2) 按照信息码元和附加的监督码元之间的按照信息码元和附加的监督码元之间的检验关系可以分为线性码和非线性码检验关系可以分为线性码和非线性码线性码：信息码元与监督码元之间的关系为线性码：信息码元与监督码元之间的关系为线性关系，即监督码元是信息码元的线性组线性关系，即监督码元是信息码元的线性组合合，则称为线性码。

则称为线性码非线性码：两者不存性关系，称为非线非线性码：两者不存性关系，称为非线性码 9/13/202419第8章 差错控制编码 (3) 按按照照信信息息码码元元和和监监督督码码元元之之间间的的约约束束方方式式可可分分为分组码和卷积码为分组码和卷积码分组码：把信息序列分为分组码：把信息序列分为k位一组，附加位一组，附加m位监督码位监督码元，形成元，形成n=k+m位的码组监督码元仅与本码组的位的码组监督码元仅与本码组的信息码元有关，而与其它码组无关信息码元有关，而与其它码组无关卷积码：码组中的监督码元不但与本组信息码元有卷积码：码组中的监督码元不但与本组信息码元有关，而且与前面码组的信息码元也有约束关系，卷关，而且与前面码组的信息码元也有约束关系，卷积码又称连环码或链码积码又称连环码或链码9/13/202420第8章 差错控制编码 (4)  系系统统码码与与非非系系统统码码在线性性分分组组码码中中所所有有码码组组的的k位信息码元在编码前后保持原来形式的码叫系位信息码元在编码前后保持原来形式的码叫系统码，反之就是非系统码系统码的编、译码都相统码，反之就是非系统码系统码的编、译码都相对比较简单，因此得到广泛应用。

对比较简单，因此得到广泛应用 (5)  纠正随机错误码和纠正突发错误码前者用于纠正随机错误码和纠正突发错误码前者用于纠正因信道中出现的随机独立干扰引起的误码，后纠正因信道中出现的随机独立干扰引起的误码，后者主要对付信道中出现的突发错误者主要对付信道中出现的突发错误9/13/202421第8章 差错控制编码 8.4   检错和纠错原理检错和纠错原理   数字通信中码元的两种错误形式：随机错误和突发数字通信中码元的两种错误形式：随机错误和突发错误 (1)  随机错误由随机噪声引起的码元错误，其特随机错误由随机噪声引起的码元错误，其特点是码元中任意一位或几位发生从点是码元中任意一位或几位发生从0变变1或从或从1变变0的的错误是相互独立的，彼此之间没有联系，一般不会错误是相互独立的，彼此之间没有联系，一般不会引起成片的码元错误引起成片的码元错误9/13/202422第8章 差错控制编码 (2) 突发错误由突发噪声引起的码元错误，突发错误由突发噪声引起的码元错误，比如，闪电、电器开关的瞬态、磁带缺陷等比如，闪电、电器开关的瞬态、磁带缺陷等都属于突发噪声该错误的特点是各错误码都属于突发噪声。

该错误的特点是各错误码元之间存在相关性，因此是成片出现，错误元之间存在相关性，因此是成片出现，错误序列的长度（包括首和尾在内的错误所波及序列的长度（包括首和尾在内的错误所波及的段落长度）称为突发长度的段落长度）称为突发长度9/13/202423第8章 差错控制编码 简单例子：介绍检错和纠错的基本原理简单例子：介绍检错和纠错的基本原理   假设要发送一组具有四个状态的数据信息假设要发送一组具有四个状态的数据信息（比如，一个电压信号的四个值，（比如，一个电压信号的四个值，1V、、2V、、3V、、4V））首先要用二进制码对数据信息进首先要用二进制码对数据信息进行编码，显然，用行编码，显然，用2位二进制码就可完成，编位二进制码就可完成，编码表如表码表如表8―1所示9/13/202424第8章 差错控制编码 表表8―1    2位编码表位编码表 9/13/202425第8章 差错控制编码 假设不经信道编码，在信道中直接传输假设不经信道编码，在信道中直接传输按表中编码规则得到的按表中编码规则得到的0、、1数字序列，则在数字序列，则在理想情况下，收端收到理想情况下，收端收到00就认为是就认为是1V，收到，收到10就是就是3V。

而在实际通信中由于干扰（噪而在实际通信中由于干扰（噪声）的影响，会使信息码元发生错误从而出声）的影响，会使信息码元发生错误从而出现误码（比如码组现误码（比如码组00变成变成10、、01或或11）从从而引起信息传输错误而引起信息传输错误 9/13/202426第8章 差错控制编码 因此，以这种编码得到的数字信号在传输因此，以这种编码得到的数字信号在传输中不具备检错和纠错的能力问题的关键是中不具备检错和纠错的能力问题的关键是2位二进制码的全部组合都是信息码组或称许位二进制码的全部组合都是信息码组或称许用码组，任何一位（或两位）发生错误都会用码组，任何一位（或两位）发生错误都会引起歧义为了克服这一缺点，在每组码后引起歧义为了克服这一缺点，在每组码后面再加面再加1位码元，使位码元，使2位码组变成位码组变成3位码组9/13/202427第8章 差错控制编码 表表8―2   3位编码表位编码表 9/13/202428第8章 差错控制编码 在许用码组在许用码组000、、011、、101、、110中，右中，右边加上的边加上的1位码元就是监督码元，它的加入位码元就是监督码元，它的加入原则是使码组中原则是使码组中1的个数为偶数。

现在我们的个数为偶数现在我们再看一下出现误码的情况，假设许用码组再看一下出现误码的情况，假设许用码组000出现出现1位误码，即变成位误码，即变成001、、010或或100三三个码组中的一个，可见这三个码组中个码组中的一个，可见这三个码组中1的个的个数都是奇数，是禁数都是奇数，是禁用码组 9/13/202429第8章 差错控制编码 因此，当收端收到这三个码组中的任何一因此，当收端收到这三个码组中的任何一个时，就知道是误码，用这种方法可以发现个时，就知道是误码，用这种方法可以发现1位或位或3位出现错误的码组，而无法检出位出现错误的码组，而无法检出2位错位错误，通过增加误，通过增加1位监督码元，我们可以检出位监督码元，我们可以检出1位或位或3位错误（位错误（3位出错的概率极小），但无位出错的概率极小），但无法纠正错误法纠正错误9/13/202430第8章 差错控制编码 能否通过增加监督码元的位数来增加检错能否通过增加监督码元的位数来增加检错位数或实现纠错功能呢？比如我们在表位数或实现纠错功能呢？比如我们在表8-2中中再加再加1位监督码元变成位监督码元变成4位编码（表位编码（表8―3）。

表表8―3   4位编码表位编码表 9/13/202431第8章 差错控制编码 编码原则仍然是偶校验显然，检错编码原则仍然是偶校验显然，检错1位位和和3位没问题，但检错位没问题，但检错2位还不行（比如位还不行（比如0000变成变成1100，而，而1100是许用码组）设误码为是许用码组）设误码为1110，则可能的原码为，则可能的原码为0110、、1010、、1100、、1111四个（还按四个（还按1位误码考虑），而位误码考虑），而0110、、1010、、1100都是许用码组，所以无法纠错都是许用码组，所以无法纠错9/13/202432第8章 差错控制编码 可见，简单地增加可见，简单地增加1位监督码元并没有提位监督码元并没有提高检错与纠错能力，那么，检错与纠错能力高检错与纠错能力，那么，检错与纠错能力到底与什么有关呢？在回答这个问题之前，到底与什么有关呢？在回答这个问题之前，我我们们先先介介绍绍两两个个新新概概念念——码码元元距距离离和和码码元元重重量9/13/202433第8章 差错控制编码 码距（也称汉明距）：两个码组中对应码位上码距（也称汉明距）：两个码组中对应码位上码元不同的个数。

码元不同的个数      码距反映的是码组之间的差异程度，比如，码距反映的是码组之间的差异程度，比如，00和和01两组码的码距为两组码的码距为1；；011和和100的码距为的码距为3多个码组之间相互比较，可能会有不同的码距，其中的码组之间相互比较，可能会有不同的码距，其中的最小值被称为最小码距（用最小值被称为最小码距（用dmin表示）比如，表示）比如，000、、001、、110三个码组相比较，码距有三个码组相比较，码距有1和和2两个两个值，则最小码距为值，则最小码距为1；；9/13/202434第8章 差错控制编码 分析表明，一种编码方式的检错、纠错能力与分析表明，一种编码方式的检错、纠错能力与许用码组中的最小码距有关比如，表许用码组中的最小码距有关比如，表8―2中中8个个码组的最小码距为码组的最小码距为1，若这，若这8个码组都作为许用码个码组都作为许用码组，则没有检错能力，更不用说纠错了；组，则没有检错能力，更不用说纠错了；    若只选其中四个作为许用码组，则最小码距为若只选其中四个作为许用码组，则最小码距为2，可检，可检1位或位或3位错误；若只选位错误；若只选000和和111为许用码为许用码组时，其最小码距为组时，其最小码距为3，那么就可发现所有，那么就可发现所有2位位以下以下的错误，若用来纠错，则可纠正的错误，若用来纠错，则可纠正1位错误。

位错误 9/13/202435第8章 差错控制编码 根据理论推导，可以得出以下结论：根据理论推导，可以得出以下结论：(1) 在一个码组内要检出在一个码组内要检出e位误码，要求最小码距为：位误码，要求最小码距为：                              dmin≥e+1                         (8.4―1)(2) 在一个码组内要纠正在一个码组内要纠正t位误码，要求最小码距为：位误码，要求最小码距为：                        dmin≥2t+1                        (8.4―2) (3)  在一个码组内要纠正在一个码组内要纠正t位误码，同时检测出位误码，同时检测出e 位误码（位误码（e≥t））,要求最小码距为：要求最小码距为：                       dmin≥t+e+1                       (8.4―3) 9/13/202436第8章 差错控制编码 要提高编码的纠、检错能力，方法是：要提高编码的纠、检错能力，方法是：①①  增加监督码元位数（即冗余度）；增加监督码元位数（即冗余度）；②② 加大最小码距，最小码距增大，码元的冗余度就加大最小码距，最小码距增大，码元的冗余度就增大。

冗余度增大，最小码距不一定增大冗余度增大，最小码距不一定增大      编码方式具有检错和纠错能力的必要条件是信编码方式具有检错和纠错能力的必要条件是信息编码必须有冗余，而充分条件是码元之间要有一息编码必须有冗余，而充分条件是码元之间要有一定的码距另外，检错要求的冗余度比纠错要低定的码距另外，检错要求的冗余度比纠错要低9/13/202437第8章 差错控制编码 把把k位信息码编成位信息码编成n位差错控制码，信息码的位数位差错控制码，信息码的位数k与差错控制码的位数与差错控制码的位数n之比定义为编码效率，用之比定义为编码效率，用Rc表示，即表示，即     因为因为k

效率尽可能的高，译码方法尽可能的简单      码元重量简称码重，定义为一个码组中非码元重量简称码重，定义为一个码组中非零码元的个数比如，码组零码元的个数比如，码组100110的码重为的码重为3，，0110的的码码重重是是2它它反反映映一一个个码码组组中中“0”和和“1”的的“比重比重”9/13/202439第8章 差错控制编码 8.5  几种常用的检错码几种常用的检错码 8.5.1 奇偶校验码奇偶校验码    是常见的简单检错码，其编码规则是：把是常见的简单检错码，其编码规则是：把信息码先分组，形成多个许用码组，在每一信息码先分组，形成多个许用码组，在每一个许用码组最后（最低位）加上一位监督码个许用码组最后（最低位）加上一位监督码元加上监督码元后使该码组中元加上监督码元后使该码组中1的数目为奇的数目为奇数的编码称为奇校验码，为偶数的编码称为数的编码称为奇校验码，为偶数的编码称为偶校验码偶校验码9/13/202440第8章 差错控制编码 奇偶校验码的监督关系可用下式进行表述假设奇偶校验码的监督关系可用下式进行表述假设一个码组的长度为一个码组的长度为n，表示为（，表示为（an-1an-2an-3…a0），），其其中前中前n-1位是信息码，最后一位位是信息码，最后一位a0为校验位，那么，为校验位，那么，对于偶校验码必对于偶校验码必须保证须保证 :监督码元监督码元a0的取值（的取值（0或或1）可由下式决定：）可由下式决定： 9/13/202441第8章 差错控制编码 对于奇校验码必须保证对于奇校验码必须保证 :监督码元监督码元a0的取值（的取值（0或或1）可由下式决定：）可由下式决定： 9/13/202442第8章 差错控制编码 根据奇偶校验的规则可以看到，当码组中根据奇偶校验的规则可以看到，当码组中的误码为偶数时，校验失效。

不会改变码组的误码为偶数时，校验失效不会改变码组的奇偶性，偶校验码中的奇偶性，偶校验码中1的个数仍为偶数，的个数仍为偶数，奇校验码中奇校验码中1的个数仍为奇数因此，简单的个数仍为奇数因此，简单的奇偶校验码只能检测出奇数个位发生错误的奇偶校验码只能检测出奇数个位发生错误的码组9/13/202443第8章 差错控制编码 讨论奇偶校检码的码距问题设两个码组讨论奇偶校检码的码距问题设两个码组同为奇（或偶）校验码组，如果两组码只有同为奇（或偶）校验码组，如果两组码只有1位不同，则它们的奇偶性就不同，这与假设位不同，则它们的奇偶性就不同，这与假设相矛盾；如果两组码有相矛盾；如果两组码有2位不同，则它们的奇位不同，则它们的奇偶性不变换句话说，构造不出码距为偶性不变换句话说，构造不出码距为1的奇的奇偶校检码，所以奇偶校验码的最小码距为偶校检码，所以奇偶校验码的最小码距为29/13/202444第8章 差错控制编码 8.5.2 水平奇偶校验码水平奇偶校验码    将经过简单奇偶校验编码的码组按行排列将经过简单奇偶校验编码的码组按行排列成方阵，每一行是一个码组，若有成方阵，每一行是一个码组，若有n个码组则个码组则方阵就有方阵就有n行。

比如，有经过奇偶校验编码的行比如，有经过奇偶校验编码的7个码组个码组  01011011001、、  01010100100、、                00110000110、、  11000111001、、                00111111110、、  00010011111、、                11101100001       排成方阵共有排成方阵共有7行9/13/202445第8章 差错控制编码 若发端按列传输，收端按列接收后再按行还原成若发端按列传输，收端按列接收后再按行还原成发端的方阵，然后按行进行奇偶校验，则纠错情况发端的方阵，然后按行进行奇偶校验，则纠错情况就会发生变化就会发生变化    在一列中不管出现几个误码（偶数或奇数），对在一列中不管出现几个误码（偶数或奇数），对应每一行都只是一位误码，故应每一行都只是一位误码，故都可以通过水平奇偶都可以通过水平奇偶校验检验出来；但对于每一行（一个码组）而言仍校验检验出来；但对于每一行（一个码组）而言仍然只能检出所有奇数个错误与简单奇偶校验编码然只能检出所有奇数个错误与简单奇偶校验编码相比，其最大优点是可以检出所有长度小于行数相比，其最大优点是可以检出所有长度小于行数（码组数）的突发错误。

码组数）的突发错误9/13/202446第8章 差错控制编码 表表8―4  水平偶校验码水平偶校验码 9/13/202447第8章 差错控制编码 8.5.3 二维奇偶校验码二维奇偶校验码     在水平奇偶校验编码的基础上，再加上垂在水平奇偶校验编码的基础上，再加上垂直奇偶校验编码就构成二维奇偶校验码如直奇偶校验编码就构成二维奇偶校验码如表表8―5所示   在发送时仍按列发送，收端顺序接收后仍在发送时仍按列发送，收端顺序接收后仍还原成表还原成表8-5的方阵形式它多了个列校验，的方阵形式它多了个列校验，因此，其检错能力有所提高因此，其检错能力有所提高9/13/202448第8章 差错控制编码       除了检出行中的所有奇数个误码及长度不除了检出行中的所有奇数个误码及长度不大于行数的突发性错误外，还可检出列中的大于行数的突发性错误外，还可检出列中的所有奇所有奇数个误码及长度不大于列数的突发性数个误码及长度不大于列数的突发性错误  同时还能检出码组中大多数出现偶数个同时还能检出码组中大多数出现偶数个错误的情况，错误的情况，但具体是哪一个码组（那一但具体是哪一个码组（那一行）出现误码还无法判断。

行）出现误码还无法判断 9/13/202449第8章 差错控制编码 表表8―5  二维偶校验码二维偶校验码 9/13/202450第8章 差错控制编码 8.5.4 群计数码群计数码     在奇偶校验码中，添加监督位将码组的码在奇偶校验码中，添加监督位将码组的码重配成奇数或偶数重配成奇数或偶数     群计数码的编码：先算出信息码组的码群计数码的编码：先算出信息码组的码重，然后用二进制计数法将码重作为监督码重，然后用二进制计数法将码重作为监督码元添加到信息码组的后面比如表元添加到信息码组的后面比如表8―4中的中的7个信息码组变成群计数码后的形式见表个信息码组变成群计数码后的形式见表8―69/13/202451第8章 差错控制编码 表表8―6  群计数码群计数码 9/13/202452第8章 差错控制编码 这种码属于非线性分组系统码，检错能力这种码属于非线性分组系统码，检错能力很强，除了能检出码组中奇数个错误之外，很强，除了能检出码组中奇数个错误之外，还能检出偶数个还能检出偶数个1变变0或或0变变1的错误，但对的错误，但对1变变0和和0变变1成对成对出现的误码无能为力。

可以出现的误码无能为力可以验证，除了无法检出验证，除了无法检出1变变0和和0变变1成对出现的成对出现的误码外，它还可检出其它所有形式的错误误码外，它还可检出其它所有形式的错误9/13/202453第8章 差错控制编码 8.5.5 恒比码恒比码       从从码码组组中中挑挑选选那那些些“1”和和“0”个个数数的的比比值值相相同的同的码组作为许用码组码组作为许用码组     表表8―7是邮电部门在国内通信中采用的五单位数是邮电部门在国内通信中采用的五单位数字保护电码，它是五中取三的恒比码每个码组的字保护电码，它是五中取三的恒比码每个码组的长度为长度为5，其中，其中“1”的个数为的个数为3，每个许用码组中，每个许用码组中“1”和和“0”个数的比值恒为个数的比值恒为3/2许用码组的个数就是许用码组的个数就是5中中取取3的组合数，即的组合数，即     C35 = 5! /(3!2!) = 10，，正好表示正好表示10个阿拉伯数字个阿拉伯数字9/13/202454第8章 差错控制编码 不难看出这种码的最小码距是不难看出这种码的最小码距是2，它能够，它能够检出码组中所有奇数个错误和部分偶数个错检出码组中所有奇数个错误和部分偶数个错误。

该码也是非线性分组码，但不是系统误该码也是非线性分组码，但不是系统码，其主要优点是简单，适用于对电传机或码，其主要优点是简单，适用于对电传机或其它键盘其它键盘设备产生的字母和符号进行编码设备产生的字母和符号进行编码 9/13/202455第8章 差错控制编码 表表8―7  五单位保护电码表五单位保护电码表 9/13/202456第8章 差错控制编码 8.6   线性分组码线性分组码     在分组码中，二元信息序列分成码元数固在分组码中，二元信息序列分成码元数固定的一组组信息，每组信息的码元由定的一组组信息，每组信息的码元由k位二进位二进制制码元组成，共有码元组成，共有2k个不同的组合信息个不同的组合信息      简单地说，将信息码进行分组，然后为简单地说，将信息码进行分组，然后为每组信息码附加若干位监督码元的编码方法每组信息码附加若干位监督码元的编码方法得到的码集合称为分组码得到的码集合称为分组码 9/13/202457第8章 差错控制编码 信息码组：信息码组：k位二进制码元，用矩阵位二进制码元，用矩阵D表示，表示，分组码：分组码：    n位二进制码元，位二进制码元，       n>k分组码元（分组码元（n位）位）=  信息码元（信息码元（k位）位）+监督码监督码                                   元（元（n-k位）位）2k个不同码组用矩阵个不同码组用矩阵C表示。

表示    有时把监督码元称为或校验码元有时把监督码元称为或校验码元9/13/202458第8章 差错控制编码 k值越大，编码设备越复杂，因为编码设值越大，编码设备越复杂，因为编码设备必须储存备必须储存2k个码长为个码长为n的码组因此，我的码组因此，我们需要构造码组之间有某种关系的分组码，们需要构造码组之间有某种关系的分组码，以降低编码的复杂性，线性分组码就是满足以降低编码的复杂性，线性分组码就是满足这一条件的一种分组码这一条件的一种分组码9/13/202459第8章 差错控制编码 线性分组码：是一种长度为线性分组码：是一种长度为n，，其中其中2k个许个许用码组（代表信息的码组）中的任意两个码用码组（代表信息的码组）中的任意两个码组的模组的模2和仍为一个许用码组的分组码称为和仍为一个许用码组的分组码称为线性（线性（n，，k）码    重要性质：重要性质：①①封闭性，即任意两个许用码封闭性，即任意两个许用码组之模组之模2和仍为一许用码组；和仍为一许用码组；②②码组的最小码码组的最小码距等于非零码的最小码重距等于非零码的最小码重9/13/202460第8章 差错控制编码 图图8―4  线性分组码格式线性分组码格式    具有这种结构的线性分组码又叫做线性分组具有这种结构的线性分组码又叫做线性分组系统码。

系统码9/13/202461第8章 差错控制编码 相应的信息码组行向量和分组码码组行向相应的信息码组行向量和分组码码组行向量为量为 C =［［ c1, c2,  ……  , cn ］］                      (8.6―1)      D =［［d1, d2,  …… , dk ］］                     (8.6―2)    一个分组码组的前一个分组码组的前k位是信息码元，后位是信息码元，后n-k位是监督码元（设监督码元位数为位是监督码元（设监督码元位数为m，则有，则有m=n-k），每一个分组码组可以由信息码元），每一个分组码组可以由信息码元线性组合而成，即：线性组合而成，即：9/13/202462第8章 差错控制编码 9/13/202463第8章 差错控制编码 式中式中,hmidi表示模表示模2乘，也可表示为乘，也可表示为hm⊙ ⊙idi其运其运算规则是：算规则是：1⊙ ⊙0=0⊙ ⊙1=0⊙ ⊙0=0；；1⊙ ⊙1=1可见，在可见，性分组码中，信息码元和监督码元可以用线性方线性分组码中，信息码元和监督码元可以用线性方程联系起来。

程联系起来     将上述将上述C与与D的的n个关系式用矩阵表示为个关系式用矩阵表示为9/13/202464第8章 差错控制编码 即即 C=D·G                                  (8.6―3)       式式中中,  G称称为为生生成成矩矩阵阵，，是是一一个个k×n阶阶矩矩阵，具体形式为阵，具体形式为9/13/202465第8章 差错控制编码 该矩阵又可分解为两个子矩阵该矩阵又可分解为两个子矩阵: 9/13/202466第8章 差错控制编码 其中其中Ik是是k×k阶单位阵，阶单位阵，P为为k×m阶矩阶矩阵，即：阵，即： 9/13/202467第8章 差错控制编码 这样，分组码这样，分组码C又可表示为又可表示为       C = D［［Ik P］］                       （（8.6―4））     需要说明的是，上述各式中的需要说明的是，上述各式中的C和和D可以是可以是由一个码组构成的一个行向量由一个码组构成的一个行向量，也可以是由，也可以是由2k个行向量构成的个行向量构成的2k×n阶分组码矩阵或阶分组码矩阵或2k×k阶信息码矩阵。

阶信息码矩阵 9/13/202468第8章 差错控制编码 式（式（8.6―3）说明：）说明：①①（（n，，k））线性码完全由生线性码完全由生成矩阵成矩阵G的的k行元素决定，即任意一个分组码码组行元素决定，即任意一个分组码码组都是都是G的线性组合的线性组合②②（（n，，k））线性码中的任何线性码中的任何k个线性无关的码组都可用来构成生成矩阵，所以，个线性无关的码组都可用来构成生成矩阵，所以，生成矩阵生成矩阵G的各行都线性无关的各行都线性无关G的各行本身就是的各行本身就是一个码组一个码组③③如果已有如果已有k个线性无个线性无关的码组，则可关的码组，则可用其直接构成用其直接构成G矩阵，并由此生成其余码组矩阵，并由此生成其余码组 9/13/202469第8章 差错控制编码 综上所述，由于可用一个综上所述，由于可用一个k×n阶矩阵阶矩阵G生生成成2k个不同的码组，因此，编码器只需储存个不同的码组，因此，编码器只需储存G矩阵的矩阵的k行元素（而不是一般分组码的行元素（而不是一般分组码的2k码码组），就可根据信息向量构造出相应的一个组），就可根据信息向量构造出相应的一个分组码码组（或根据信息码矩阵构造出相应分组码码组（或根据信息码矩阵构造出相应的一个分组码矩阵），从而降低了编码的复的一个分组码矩阵），从而降低了编码的复杂性，并提杂性，并提高了编码效率。

高了编码效率 9/13/202470第8章 差错控制编码 【【例例题题8―1】】给给定定一一个个（（7，，4））线线性性分分组组码码的生成矩阵的生成矩阵 若若信信息息码码为为d=［［1101］］，，求求该该信信息息码码的的线线性分组编码性分组编码C9/13/202471第8章 差错控制编码 解解: 根据式（根据式（8.6―3）可得）可得 9/13/202472第8章 差错控制编码 即对信息码［即对信息码［1101］的线性分组编码为］的线性分组编码为［［1101000］注意在矩阵乘法中，是模］注意在矩阵乘法中，是模2乘和模乘和模2加上式也可写成加上式也可写成9/13/202473第8章 差错控制编码 以上讨论可知，编码前的信息码组共有以上讨论可知，编码前的信息码组共有2k种组合，编码后的码组在种组合，编码后的码组在k位信息码元之外还位信息码元之外还附加了附加了m位校验码元，共有位校验码元，共有2n种组合，种组合，2n>2k，这就是说，这就是说C与与D的关系不惟一的关系不惟一     因此，选择适当的矩阵因此，选择适当的矩阵P，，就可得到既具就可得到既具有较强检错或纠错能力，又较简单且编码效有较强检错或纠错能力，又较简单且编码效率较高的线性分组码。

目前已经找到不少性率较高的线性分组码目前已经找到不少性能较好的矩阵能较好的矩阵P9/13/202474第8章 差错控制编码 【【例题例题8―2】】 已知线性（已知线性（6，，3）码的生成）码的生成    矩矩阵为阵为      求线性分组码、各码组的码重、最小码距求线性分组码、各码组的码重、最小码距和该码的差错控制能力和该码的差错控制能力解：因为解：因为k=3，故信息码组矩阵（，故信息码组矩阵（3×8）为）为9/13/202475第8章 差错控制编码 9/13/202476第8章 差错控制编码 则由式（则由式（8.6―3）可得出分组码码组）可得出分组码码组矩阵（矩阵（6×8阶）为阶）为9/13/202477第8章 差错控制编码 表表8―8  例例8―2编码表编码表 9/13/202478第8章 差错控制编码 从表中可见非零码组的最小码重为从表中可见非零码组的最小码重为3，则，则分组码的最小码距分组码的最小码距dmin=3，根据式（，根据式（8.4―1）、）、（（8.4―2）和（）和（8.4―3）可知该分组码能够检）可知该分组码能够检2位错，纠位错，纠1位错，或同时纠位错，或同时纠1位错检位错检1位错。

位错     需要说明的是，任何线性分组码都包含全需要说明的是，任何线性分组码都包含全零码组因任一码组与其本身模零码组因任一码组与其本身模2加都会得到加都会得到全零码组全零码组9/13/202479第8章 差错控制编码 下面我们简要介绍译码原理从式（下面我们简要介绍译码原理从式（8.4―7）可得）可得（（8.6―6）） （（8.6―5））      式式中中，，Cm是是k×m阶阶监监督督码码元元矩矩阵阵将将式式(8.6―6)改写为改写为: (8.6―7)(8.6―8) 9/13/202480第8章 差错控制编码 该式说明线性分组码中任一码组与校验矩该式说明线性分组码中任一码组与校验矩阵阵H的转置相乘，其结果为的转置相乘，其结果为m位全零向量，因位全零向量，因此，用校验矩阵检查二元序列是不是给定分此，用校验矩阵检查二元序列是不是给定分组码中的码组非常方便，组码中的码组非常方便，“校验校验”由此而来由此而来     可以推导出校验矩阵可以推导出校验矩阵H与生成矩阵与生成矩阵G满足满足 GHT = HGT = 0                           (8.6―9)9/13/202481第8章 差错控制编码 设行向量设行向量R=［［r1，，r2，，…，，rn］］是收信端收是收信端收到的码组。

由于信道干扰产生误码，接收向到的码组由于信道干扰产生误码，接收向量量R和发送向量和发送向量C就有差别，用向量就有差别，用向量E=［［e1，，e2，，…，，en］］表示这种差别由此定义三者之表示这种差别由此定义三者之间的关系为间的关系为（（8.6―10）） 9/13/202482第8章 差错控制编码 若若R中的某一位中的某一位ri与与C中的相同位中的相同位ci一样一样时，时，E中的中的ei=0；；若不同（即出现误码），则若不同（即出现误码），则ei=1可见向量可见向量E能够反映误码状况，故称之能够反映误码状况，故称之为错误向量或错误图样可见，为错误向量或错误图样可见，E的码重就的码重就是误码的个数，因此是误码的个数，因此E的码重越小越好的码重越小越好9/13/202483第8章 差错控制编码 式（式（8.6―10）也可写为）也可写为 R = E ⊕ ⊕ C                                    （（8.6―11）） 定义矩阵定义矩阵S为伴随式为伴随式            S = RHT                                         （（8.6―12））  S是长度为是长度为m=n-k的二元序列，有的二元序列，有2m种组合。

由式种组合由式（（8.6―8）、（）、（8.6―11）和（）和（8.6―12）得）得           S =（（E ⊕ ⊕ C））HT                    = E HT ⊕ ⊕ C HT                    = E HT                                                                 （（8.6-13））9/13/202484第8章 差错控制编码 式（式（8.6―13）表明伴随式）表明伴随式S只与错误图样只与错误图样E有关，与发送码组无关有关，与发送码组无关S称为称为R的伴随式或的伴随式或称校正子称校正子    当当S为零矢量时，说明为零矢量时，说明R没有错，没有错，R是码组是码组C；否则，说明；否则，说明R有错，有错，R不是码组不是码组C   当通信双方确定了信道编码后，生成矩阵当通信双方确定了信道编码后，生成矩阵G和监督矩阵和监督矩阵H也就随之也就随之而定收端可以知道而定收端可以知道G、、H和和R 9/13/202485第8章 差错控制编码 译码方法：译码方法：      ①① 收端先求出伴随式收端先求出伴随式 S      ②② 解出错误图样解出错误图样 E      ③③ 解出发送码组解出发送码组 C9/13/202486第8章 差错控制编码 需要说明的是，上述步骤只是一个概念上需要说明的是，上述步骤只是一个概念上的解释，具体方法还比较麻烦。

因为对于一个的解释，具体方法还比较麻烦因为对于一个伴随式伴随式S，，有有2k个错误图样与之对应，换句话个错误图样与之对应，换句话说说，，就就是是式式(8.6―13)的的解解不不唯唯一一，，真真正正的的错错误误图样只是图样只是2k个错误图样中的一个个错误图样中的一个9/13/202487第8章 差错控制编码 【【例例题题8―3】】 已已知知一一线线性性(6，，3)码码的的生生成成矩矩阵阵G、、S和和E的对照表分别为：的对照表分别为：9/13/202488第8章 差错控制编码 SE000000000101100000011010000110001000100000100010000010001000001111100010 求求当当接接收收端端收收到到码码组组R=［［111011］］时时，，所所对对应应的的信息码组信息码组D9/13/202489第8章 差错控制编码 解：解：  根据前面根据前面HT的定义式可得的定义式可得将接收码组将接收码组R=［［111011］］代入代入(8.6―12)式，可得：式，可得：9/13/202490第8章 差错控制编码 9/13/202491第8章 差错控制编码 从从S―E关系表中可知，关系表中可知，S=［［011］］所对应的错误所对应的错误图样为图样为E =［［010000］］。

将将R =［［111011］］和和E=［［010000］］代入式代入式 (8―13)或式或式(8―14)可得可得 C = R ⊕ ⊕ E =［［101011］］ 从从C中分出信息码组为中分出信息码组为            D=［［101］］ 信息码组为信息码组为D =［［101］］ 9/13/202492第8章 差错控制编码 8.7 循循 环环 码码    定义：对于一个（定义：对于一个（n，，k））线性码线性码C，，若其中若其中的任一码组向左或向右循环移动任意位后仍的任一码组向左或向右循环移动任意位后仍是是C中的一个码组，则称中的一个码组，则称C是一个循环码循是一个循环码循环码是一种分组码，前环码是一种分组码，前k位为信息码元，后位为信息码元，后m位为监督码元位为监督码元优点：纠错能力强，编解码简单优点：纠错能力强，编解码简单9/13/202493第8章 差错控制编码     若若c=［［c1，，c2，，…，，cn］］是一个循环码组，左循环是一个循环码组，左循环移移位位一一次次，，得得到到c（（1））=［［c2，，c3，，…，，cn，，c1］］也也是是许许用码组，移位用码组，移位i次得到次得到c(i)=［［ci+1，，ci+2，，…，，cn，，c1，，ci］］还是许用码组。

还是许用码组     在代数编码理论中，可以把循环码组中各码元当在代数编码理论中，可以把循环码组中各码元当作一个多项式的系数，即把一个长为作一个多项式的系数，即把一个长为n的码组表示的码组表示 c(x) = c1xn-1 + c2xn-2 + … + cn9/13/202494第8章 差错控制编码 式中，式中，c(x)称为码多项式，变量称为码多项式，变量x称为元素，其幂称为元素，其幂次对应元素的位置，它的系数即为元素的取值（我次对应元素的位置，它的系数即为元素的取值（我们不关心们不关心x本身的取值），系数之间的加法和乘法仍本身的取值），系数之间的加法和乘法仍服从模服从模2规则比如一个（规则比如一个（7，，3）循环码（见表）循环码（见表8―9）中第）中第7个码组为（个码组为（1100101），则该码组可表），则该码组可表示为示为  c7(x) =1·x6 + 1·x5 + 0·x4 + 0·x3 + 1·x2 + 0·x + 1               = x6 + x5 + x2 + 19/13/202495第8章 差错控制编码 表表8―9 一种（一种（7，，3）循环码的全部码组）循环码的全部码组 9/13/202496第8章 差错控制编码 举例说明系统码与非系统码的区别。

对一组举例说明系统码与非系统码的区别对一组4位信位信息码组，附加息码组，附加3位监督码元可编成两种（不只两种）位监督码元可编成两种（不只两种）循环码，见表循环码，见表8―10所示    系统码的前系统码的前4位对应的都是信息码，而后位对应的都是信息码，而后3位都是位都是监督码元，且编码前后信息码形式保持不变监督码元，且编码前后信息码形式保持不变    非非系系统统码码从从第第5组组开开始始信信息息码码就就“乱乱”了了，，没没有有系系统统码那种前后一致的信息码结构码那种前后一致的信息码结构9/13/202497第8章 差错控制编码 另外，还需说明的是，对于一个（另外，还需说明的是，对于一个（n，，k）线性）线性码码C，，根据不同的方法（生成矩阵）可以有多种编根据不同的方法（生成矩阵）可以有多种编码形式，其中包含系统码和非系统码，但系统码码形式，其中包含系统码和非系统码，但系统码是惟一的，其余的都是非系统码是惟一的，其余的都是非系统码        小结：简要地了解了数字（数据）通信中信小结：简要地了解了数字（数据）通信中信道编码的基本概念和常用的检纠错编码，编码所道编码的基本概念和常用的检纠错编码，编码所研究的主要问题是：研究的主要问题是：9/13/202498第8章 差错控制编码 (1)  根据系统对纠错能力的要求，寻找合适根据系统对纠错能力的要求，寻找合适的码型。

要求该码型可在数学上证明具有满的码型要求该码型可在数学上证明具有满足要求的纠错能力，并具有数学结构，且能足要求的纠错能力，并具有数学结构，且能够根据此结构具体实现编码和译码够根据此结构具体实现编码和译码2) 寻找实用的编码方法，提高编码效率寻找实用的编码方法，提高编码效率3) 寻找实用的译码方法，降低译码复杂性寻找实用的译码方法，降低译码复杂性9/13/202499第8章 差错控制编码 表表8―10 （（7，，4）循环码码组）循环码码组 9/13/2024100第8章 差错控制编码 9/13/2024101第8章 差错控制编码 图图5-4 （（7，，4）系统循环码编码器与时序图）系统循环码编码器与时序图9/13/2024102第8章 差错控制编码 节拍 1 2 3 4 5 6 7d (x) 1 0 1 0 0 0 0D1状态 0 1 1 0 1 0 0D2状态 0 0 1 1 0 1 0D3状态 0 1 1 1 0 0 1c(x) 1 0 1 0 0 0 1表表8-118-11（补）图（补）图5-45-4的电路工作过程的电路工作过程9/13/2024103。