差错控制编码 最新课件

《差错控制编码 最新课件》由会员分享，可在线阅读，更多相关《差错控制编码 最新课件（65页珍藏版）》请在金锄头文库上搜索。

1、第第7 7章章 差错控制编码差错控制编码7.1 7.1 概述概述7.1.1 7.1.1 差差错错控制控制编码编码的概念的概念在数字通信系统中，编码器分为信源编码（解决通信的有效性问题）和信道编码（解决通信的可靠性问题）信信道道编编码码（又称差错控制编码或纠错编码），就就是是为为改改善善数数字字信信号号在在信信道道中中传传输输的的可可靠靠性性，而而对对其其进进行行再再编编码码的的数数据据编编码技术。码技术。差差错错控控制制编编码码：是是一一种种重重要要的的信信道道编编码码方方式式，是是以以可可控控制制的的方方式式，在在信信息息码码组组的的前前后后或或在在码码元元中中间间，按按照照一一定定的的规规

2、则则附附加一些码元，这些码元被称为加一些码元，这些码元被称为监督码元监督码元。 第第7章章 差错控制编码差错控制编码差错控制编码 最新第第7 7章章 差错控制编码差错控制编码差错控制的概念：差错控制的概念： 信道编码信道编码是在经过信源编码的码元序列中增是在经过信源编码的码元序列中增加一些加一些多余的多余的比特，可发现或纠正传输中发生的比特，可发现或纠正传输中发生的错误；错误； 当信道编码只有发现错码能力而不具备纠正当信道编码只有发现错码能力而不具备纠正错码能力时，需结合其他措施来纠正错码，否则错码能力时，需结合其他措施来纠正错码，否则只能将被发现为错码的码元删除，以避免错码引只能将被发现为错

3、码的码元删除，以避免错码引起的负面影响。上述手段统称为起的负面影响。上述手段统称为差错控制。差错控制。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码信道中差错的类型：信道中差错的类型：随机差错：随机差错：由随机噪声导致，表现为独立的、稀疏由随机噪声导致，表现为独立的、稀疏的和互不相关发生的差错。的和互不相关发生的差错。突发差错：突发差错：相对集中出现，即在短时段内有很多错相对集中出现，即在短时段内有很多错码出现，而在其间有较长的无错码时间段，例如由码出现，而在其间有较长的无错码时间段，例如由脉冲干扰引起的错码或信道特性产生的衰落等脉冲干扰引起的错码或信道特性产生的衰落等。差错控制编

4、码 最新第第7 7章章 差错控制编码差错控制编码7.1.2 7.1.2 差差错错控制方式控制方式常用的差错控制方式：常用的差错控制方式：检错重发（检错重发（ARQ） 常用检错重发系统：常用检错重发系统：前向纠错（前向纠错（FEC）混合纠错（混合纠错（HEC）停止停止等待重发等待重发返回重发返回重发选择重发选择重发 差错控制编码 最新第第7 7章章 差错控制编码差错控制编码常常用用的的差差错错控控制制方方式式差错控制编码 最新第第7 7章章 差错控制编码差错控制编码常用的差错控制方式常用的差错控制方式检错重发前向纠错前向纠错差错控制编码 最新第第7 7章章 差错控制编码差错控制编码反馈校验反馈校

5、验混合纠错混合纠错差错控制编码 最新第第7 7章章 差错控制编码差错控制编码7.1.2 7.1.2 差差错错控制方式控制方式（1 1）检错重发方式（）检错重发方式（ARQARQ） 接接收收端端在在收收到到的的信信码码中中检检测测出出错错码码时时，设设法法通通知知发发送送端端重重发信码，直到正确接收为止。发信码，直到正确接收为止。 ARQARQ方式需要方式需要反馈信道反馈信道来反馈收端的重发指令给发送端。来反馈收端的重发指令给发送端。 常用的检错重发系统有三种：常用的检错重发系统有三种：停发等候重发停发等候重发返回重发返回重发选择重发选择重发差错控制编码 最新第第7 7章章 差错控制编码差错控制

6、编码 图图7.1 7.1 检错重发差错控制系统工作原理检错重发差错控制系统工作原理差错控制编码 最新第第7 7章章 差错控制编码差错控制编码（2）前向）前向纠错纠错方式（方式（FEC）前向前向纠错纠错是一种在接收端能是一种在接收端能发现错误发现错误，并能自，并能自动纠动纠正正错误错误的差的差错错控制方式（也称控制方式（也称自自动纠错动纠错方式方式）。）。对对于二于二进进制系制系统统，如果能，如果能够够确定确定错码错码的位置，就能的位置，就能纠纠正它。正它。这这种方式不需要反种方式不需要反馈馈信道来信道来传递传递指令，指令，传输实时传输实时性好，性好，适合适合单单向通信向通信。差错控制编码 最新

7、第第7 7章章 差错控制编码差错控制编码（3）混合）混合纠错纠错方式（方式（HEC）混混合合纠纠错错方方式式：是是前前向向纠纠错错方方式式和和检检错错重重发发方方式式的的结结合。合。这这种种方方式式兼兼有有两两者者的的优优点点，即即对对能能自自动动纠纠正正的的错错误误，就就自自动动纠纠正正；超超出出了了自自动动纠纠错错能能力力的的错错误误，就通就通过过反反馈馈信道要求重信道要求重发发一次。一次。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码7.1.3 7.1.3 纠错码纠错码的分的分类类1 1）按差）按差错错控制控制编码编码的功能分：的功能分：检错码检错码、纠错码纠错码2 2）按信

8、息码与监督码间的检验关系分：）按信息码与监督码间的检验关系分： 线性码、非线性码线性码、非线性码3 3）按信息码与监督码间的约束关系分：）按信息码与监督码间的约束关系分：分组码、卷积码分组码、卷积码4 4）按信息码的编码前后的形式分：）按信息码的编码前后的形式分：系统码、非系统码系统码、非系统码5 5）按信道差错类型分：）按信道差错类型分：随机纠错码、突发纠错码随机纠错码、突发纠错码6 6）按用于差错编码的数学方法分：）按用于差错编码的数学方法分： 代数码、几何码、算术码代数码、几何码、算术码7 7）按不同的进制分：）按不同的进制分：二进制码、多进制码二进制码、多进制码差错控制编码 最新第第7

9、 7章章 差错控制编码差错控制编码前前面面已已经经提提到到，信信道道编编码码的的基基本本思思想想是是在在被被传传送送的的信信号号中中附附加加一一些些监监督督码码元元，并并在在信信息息码码元元和和监监督督码码元元之之间间建建立立某某种种校校验验关关系系。当当这这种种校校验验关关系系因因传传输输错错误误而而被被破破坏坏时时，利利用用已已经经建建立立的的校校验验关关系系，就可以发现错误并予以纠正。就可以发现错误并予以纠正。因因此此，可可以以说说信信道道编编码码的的这这种种纠纠错错和和检检错错能能力力是用增加信号的冗余度换取的是用增加信号的冗余度换取的。7.1.4 7.1.4 纠错编码的基本原理纠错编

10、码的基本原理差错控制编码 最新第第7 7章章 差错控制编码差错控制编码三位二进制码元共有三位二进制码元共有8种可能的组合。若将其全部用种可能的组合。若将其全部用来表示天气，则可以表示来表示天气，则可以表示8种不同的天气状况。种不同的天气状况。例如例如 若在传输过程中发生一个误码，则任何一种码组若在传输过程中发生一个误码，则任何一种码组(码字码字)会错误地变成另外一种码组。这是由于每一种码组都可能出会错误地变成另外一种码组。这是由于每一种码组都可能出现，没有多余的信息量，因此接收端不可能发现错误，以为现，没有多余的信息量，因此接收端不可能发现错误，以为发送的就是另外一种码组。发送的就是另外一种码

11、组。 若上述若上述8种码组中只选用种码组中只选用4种码组来传递信息，例如：种码组来传递信息，例如：000=晴晴011=云云101=阴阴110=雨雨000（晴晴），001(云云)，010（阴阴） 011（雨）雨）100（雪雪），101（霜）（霜），110（雾）雾） 111（雹）（雹）接收端有可能发现接收端有可能发现码组中的一个错码码组中的一个错码差错控制编码 最新第第7 7章章 差错控制编码差错控制编码 例如，若例如，若000(晴晴)这一码组中错了一位码，则接收到的这一码组中错了一位码，则接收到的码组可能变为码组可能变为100或或010或或001。由于这。由于这3种码组都是种码组都是禁用码禁用码

12、组组，故接收端在收到禁用码组时，就可以发现错误，即检，故接收端在收到禁用码组时，就可以发现错误，即检出了错误。出了错误。上述的编码方法只能检测错误，不能纠正错误。上述的编码方法只能检测错误，不能纠正错误。例如，当收到的禁用码组为例如，当收到的禁用码组为100时，接收端无法判断是时，接收端无法判断是哪一位码发生了错误，因为哪一位码发生了错误，因为晴晴(000)、阴、阴(101)、雨、雨(110)三三种码组错了一位都可能变成种码组错了一位都可能变成100。可见，若要能够纠正错误，还必须增加可见，若要能够纠正错误，还必须增加冗余度冗余度000（晴）（晴）011（云）（云）101（阴）（阴）110（雨

13、）（雨）差错控制编码 最新第第7 7章章 差错控制编码差错控制编码码距、编码效率和编码增益：码距、编码效率和编码增益：编码的检错或纠错能力与码字间的最小距离有关。编码的检错或纠错能力与码字间的最小距离有关。1.码码距距（汉汉明明距距离离）：把把两两个个等等长长码码字字之之间间对对应应码码位位上上具具有有不不同同的的二二进进制制码码元元的的个个数数，称称为为这这两两个个码码字字的的汉汉明明距距离离，简简称称码码距距，用用d表表示示。例例如如，两两个个码码字字11000与与10011，它它们们在在第第2、4、5位上二进制码元不同，故位上二进制码元不同，故d=3。2.码码重重（汉汉明明重重量量）：分

14、分组组码码中中，一一个个码码字字中中“1”的的数数目目。用用w表示，如码字表示，如码字11010，重量，重量W=3；3.最最小小距距离离：把把一一个个编编码码的的码码组组集集合合中中，任任何何两两个个许许用用码码组组之之间距离的最小值称为最小距离，用间距离的最小值称为最小距离，用dmin表示。表示。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码图图7.2 7.2 码距的几何表示码距的几何表示差错控制编码 最新第第7 7章章 差错控制编码差错控制编码最最小小距距离离是是信信道道编编码码的的一一个个重重要要参参数数，它它直直接接与与编编码码的检错和纠错能力有关。的检错和纠错能力有关。在

15、一般情况下，对于分组码有如下结论：在一般情况下，对于分组码有如下结论：(1)为检测为检测e个错码，最小距离应满足个错码，最小距离应满足(2)为纠正为纠正t个错误，最小距离应满足个错误，最小距离应满足(3)为为纠纠正正t个个错错误误，同同时时又又能能够够检检测测e个个错错误误，最最小小码码距距应应满足满足dmine+1dmin2t+1dmine+t+1(et)差错控制编码 最新第第7 7章章 差错控制编码差错控制编码 为了提高纠、检错能力，需要加大码距。要加大码距，为了提高纠、检错能力，需要加大码距。要加大码距，就需增加更多的监督码元。这就必然会降低编码效率。就需增加更多的监督码元。这就必然会降

16、低编码效率。 因此，在考虑纠、检错能力时，要考虑编码效率。因此，在考虑纠、检错能力时，要考虑编码效率。编码效率的定义：编码效率的定义：信息码的位数与总码元位数之比。信息码的位数与总码元位数之比。 编码效率：编码效率：R R=k k/n nnn码组长度为（含监督码元）码组长度为（含监督码元）kk信息信息码码元位数元位数rr监督码元位数监督码元位数 r r=n n-k k显然，监督码元位数越大，编码效率就越低。因此，显然，监督码元位数越大，编码效率就越低。因此，编码效编码效率与纠错能力是一对矛盾。率与纠错能力是一对矛盾。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码已已知知8个个码码组

17、组为为000000，001110，010101，100011，101101，110110，111000。求：求：例如例如解：解：（1）dmin=3（2）因为）因为dmine+1且且dmin=3所以所以e2,能检出能检出2位错码；位错码；（3）因为）因为dmin2t+1且且dmin=3所以所以t1,能纠出能纠出1位错码；位错码； （4）因为）因为dmint+e+1且且dmin=3所以所以t+e2,又因为又因为et，令，令e=t=1时才能满足时才能满足条件，只能同时检测并纠正条件，只能同时检测并纠正1位错码；位错码；（1）以上码组的最小距离？）以上码组的最小距离？（2）将以上码组用于检错，能检出几

18、位错码？）将以上码组用于检错，能检出几位错码？ （3）若用于纠错，能纠出几位错码？）若用于纠错，能纠出几位错码？ （4）若同时用于检错和纠错，能同时纠、检几位错码？）若同时用于检错和纠错，能同时纠、检几位错码？差错控制编码 最新第第7 7章章 差错控制编码差错控制编码7.2 7.2 几种常用的简单编码几种常用的简单编码7.2.1 7.2.1 奇偶校验码奇偶校验码监监督督码码附加在每个信息码组的后面，若监督码元的取值是要使新的码组中“”的数目成为奇数，则称为奇奇校校验验码码；若监督码元的取值是要使新的码组中“”的数目成为偶数，则称为偶校验码偶校验码。差错控制编码 最新第第7 7章章 差错控制编码

19、差错控制编码奇偶校验码的特点 1 1）分）分为为奇校奇校验码验码和偶校和偶校验码验码，两者原理相同；，两者原理相同； 2 2）监监督位只有一位；督位只有一位； 3 3）对对偶偶校校验验码码，码码组组中中的的“”的的数数目目为为偶偶数数，用用表表达达式表示如下：式表示如下： 4 4）对对奇奇校校验验码码，码码组组中中的的“”的的数数目目为为奇奇数数，用用表表达达式表示如下：式表示如下： 5 5）无无论论是是奇奇校校验验码码还还是是偶偶校校验验码码，都都只只能能检检测测出出奇奇数数个个错码，而不能检测偶数个错码错码，而不能检测偶数个错码。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码【

20、例】：字符A的编码为7位，在偶校验中，则加在字符A后面的校验码为0，即0 0。优点：优点：简单简单 缺点：缺点：只能检测出部分传输差错只能检测出部分传输差错 差错控制编码 最新第第7 7章章 差错控制编码差错控制编码7.2.2 7.2.2 行列监督码（行列监督码（二维奇偶校验码）二维奇偶校验码）行列监督码（行列监督码（又称二维奇偶校验码、方阵码），又称二维奇偶校验码、方阵码），它是垂直奇它是垂直奇偶校验与水平奇偶校验的组合，其发现差错的能力很强。这偶校验与水平奇偶校验的组合，其发现差错的能力很强。这种码是将若干码字排列成矩阵，在每行和每列的末尾均加监种码是将若干码字排列成矩阵，在每行和每列的末

21、尾均加监督码督码(奇监督或偶监督奇监督或偶监督)。例如例如1110101为用户要发送的信息序列，现将每为用户要发送的信息序列，现将每8个个码元分成一组编成方阵，对方阵的行与列都进行码元分成一组编成方阵，对方阵的行与列都进行偶偶数监督数监督，则在发送端编成如表，则在发送端编成如表7-1所示的方阵。所示的方阵。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码表表7-1二维奇偶校验二维奇偶校验行行监监督督 码码 元元110010110001010011000101100001100111010110011111010011列列监监督督码码元元 该码对每行或每列的奇数或偶数个错都能检验出来，

22、该码对每行或每列的奇数或偶数个错都能检验出来，且可以确定仅一行或一列出现奇数个错的误码的位置并纠且可以确定仅一行或一列出现奇数个错的误码的位置并纠正之，但这种码对构成正之，但这种码对构成2m2n方阵的错误无法检测出来，方阵的错误无法检测出来，如图如图7-2a所示。所示。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码XXXXXXXOXXXXXXXOX XX XXOXXXXXXXOXXXXXXXOXXXXXOXXXXXXXOOOOOOOOO图中，图中，“X”表示信息位，表示信息位，“O”表示监督位，如表示监督位，如“”所所示的位置上出现差错，差错数正好为示的位置上出现差错，差错数正好为

23、4的倍数，且差错位于构的倍数，且差错位于构成矩形的四个角上，则二维奇偶监督码不能检测出错误。成矩形的四个角上，则二维奇偶监督码不能检测出错误。图图7-2a 二维奇偶监督码的结构二维奇偶监督码的结构差错控制编码 最新第第7 7章章 差错控制编码差错控制编码行行列列监监督督码码适适用用于于检检测测突突发发错错码码。因因为为突突发发错错码码通通常常成成串串出出现现，随随后后有有较较长长一一段段无无错错码码区区间间，所所以以在在某某一一行行中中出出现现多多个个错错码码的的机机会会较较多多，这这很很容容易易在在按按列检查时发现错误。列检查时发现错误。一维奇偶校验码只适用于检测随机错码。一维奇偶校验码只适

24、用于检测随机错码。二维的奇偶校验码不仅可以检错，还可以纠错。二维的奇偶校验码不仅可以检错，还可以纠错。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码表表7.1 7.1 行列行列监监督督码码示例示例差错控制编码 最新第第7 7章章 差错控制编码差错控制编码7.2.3 7.2.3 恒比码恒比码 在在恒恒比比码码中中，每每个个码码组组均均有有相相同同数数目目的的“”（和和“”）。由由于于“”的的数数目目与与“”的的数数目目之之比比保保持持恒恒定定，故故得得名名恒恒比比码码或或称称为为定定比比码码。由由于于其其中中各各码码组组的的码码重重是是相相等等的的，故故又又称称为为等等重重码码或或定

25、权码定权码。 在在检检测测时时，只只要要计计算算接接收收码码组组中中“”的的数数目目是是否否对对，就就知知道道有有无无错错码码。这这种种码码已已应应用用于于电电报报传传输输中中，国国际际通通用用的的检检错错重重发发（ARQARQ）电电报报通通信信系系统统中中采采用用3 3个个“”、4 4个个“”的的3434码码，又又称称为为七七中中取取三三码码。这这种种码码共共有有C C3 37 7=35=35个个码码组组，分分别别表表示示2626个个字母及其他字母及其他符符号。号。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码 表表7.2 7.2 国际通用的七中取三码国际通用的七中取三码差错控制

26、编码 最新第第7 7章章 差错控制编码差错控制编码7.2.4正反码正反码 正反码是一种简单的能够纠错的编码。其中的监督位数正反码是一种简单的能够纠错的编码。其中的监督位数目与信息位目与信息位数目相同数目相同，监督码元与信息码元相同（是信息码，监督码元与信息码元相同（是信息码的重复）或者相反（是信息码的反码），由信息码中的重复）或者相反（是信息码的反码），由信息码中“”的个数确定。的个数确定。监督码的监督码的编码规则编码规则如下：如下：当当信信息息码码有有奇奇数数个个“1”时时，则则监监督督码码是是信信息息的的重重复复，如如信息码为信息码为10101，码后的码字为，码后的码字为101011010

27、1；当当信信息息码码有有偶偶数数个个“1”时时，则则监监督督码码是是信信息息码码的的反反码码，如信息码为如信息码为11011，则编码后的码字为，则编码后的码字为1101100100。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码解解码码时时先先将将接接收收码码组组中中信信息息码码和和监监督督码码对对应应码码位位模模2 2相相加加，得到一个得到一个合成码合成码。若若接接收收的的信信息息码码中中有有奇奇数数个个“1”1”，则则此此合合成成码码就就是是检检验验码；码；若接收的信息码中有若接收的信息码中有偶数个偶数个“1”1”，则校验码为合成码的，则校验码为合成码的反码。反码。观察校验码中

28、观察校验码中“1”的个数，就能判决信码是否有错并纠的个数，就能判决信码是否有错并纠正错误。正错误。监督码的监督码的解码规则解码规则如下：如下：差错控制编码 最新第第7 7章章 差错控制编码差错控制编码正反码常用于电报通信，其信息码位数正反码常用于电报通信，其信息码位数K=5，监督码位数，监督码位数r=5，正反码码长，正反码码长n10。表。表6-4列出了其利用校验码进行判列出了其利用校验码进行判决和纠错的情况。决和纠错的情况。表表7-2A 7-2A 正反码纠错表正反码纠错表序序号号校验码组的组成校验码组的组成错码情况错码情况1全为全为“0”无错码无错码2四个四个“1”，1个个“0”信信息息码码中

29、中有有一一位位错错，位位置置对对应应于于校校验验码码中中“0”的位置的位置3四个四个“0”，1个个“1”监监督督码码中中有有一一位位错错，位位置置对对应应于于校校验验码码中中“1”的位置的位置4其它情况其它情况多于多于1个个差错控制编码 最新第第7 7章章 差错控制编码差错控制编码7 73 3 线性分组码线性分组码7.3.1基本概念基本概念 分组码一般可用分组码一般可用(n，k)表示，其中表示，其中k是每组信是每组信息码元的数目，息码元的数目，n是编码码组的码长。是编码码组的码长。r=n-k为每个为每个码组中的监督码元数目。码组中的监督码元数目。二进制共有二进制共有2k个不同信息组，相应得到个

30、不同信息组，相应得到2k个不个不同的码字，称为同的码字，称为许用码组许用码组。其余。其余2n-2k个码字未被选个码字未被选用，称为用，称为禁用码组禁用码组。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码分分组组码码的的监监督督码码元元是是根根据据一一定定的的规规则则，由由本本组组的信息码元经过变换得到。的信息码元经过变换得到。变换规则不同，得到的分组码也就不同。变换规则不同，得到的分组码也就不同。如如果果在在某某一一种种分分组组码码中中，监监督督码码与与信信息息码码间间呈呈线性代数线性代数的关系时，就称为的关系时，就称为线性分组码。线性分组码。在在接接收收端端通通过过检检查查一一个

31、个码码组组中中的的k与与r之之间间是是否否仍仍然然存存在在发发信信端端那那种种确确定定的的线线性性代代数数关关系系来来发发现现或或纠正错码。纠正错码。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码汉明码汉明码是一种能够纠正单个错误的线性分组码。它是一种能够纠正单个错误的线性分组码。它有以下特点：有以下特点： （1）最小码距）最小码距dmin3，可纠正一位错误；，可纠正一位错误；（2）码长码长n与监督元个数与监督元个数r之间满足关系式：之间满足关系式：通常二进制汉明码可以表示为：通常二进制汉明码可以表示为：7.3.2 汉明码汉明码 差错控制编码 最新第第7 7章章 差错控制编码差错控

32、制编码现现以以(7，4)分分组组码码为为例例来来说说明明线线性性分分组组码码的的特特点点。设设其其码码字字为为A=a6a5a4a3a2a1a0，其其中中前前4位位是是信信息息码码元元，后后3位位是是监监督督元元，可可用用下下列列线线性性方程组来描述该分组码，产生监督码元。方程组来描述该分组码，产生监督码元。显显然然，这这3个个方方程程是是线线性性无无关关的的。经经计计算算可可得得（7，4）码的全部码字，如表）码的全部码字，如表7-3所示。所示。式（式（7-3）【例如】【例如】 差错控制编码 最新第第7 7章章 差错控制编码差错控制编码表表7.3 7.3 （7 7，4 4）码的码字表）码的码字表

33、不不难难看看出出，上上述述（7，4）码码的的最最小小码码距距dmin=3，它它能能纠纠正一个错误或检测两个错误。正一个错误或检测两个错误。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码（7，4）系统汉明码的编码器和译码器电路：）系统汉明码的编码器和译码器电路：差错控制编码 最新第第7 7章章 差错控制编码差错控制编码差错控制编码 最新第第7 7章章 差错控制编码差错控制编码7.3.3循环码循环码 循环码是线性分组码的一个重要子集，是目前研究循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码，它有许多特殊的代数性质。得最成熟的一类码，它有许多特殊的代数性质。（n,k）循环码

34、是另一种常用的线性分组系统码。前）循环码是另一种常用的线性分组系统码。前k位为信息码元，后位为信息码元，后r=n-k位为监督码元。位为监督码元。（1）循环码的特点循环码的特点 特点：特点：它具有封闭性、系统性和循环性。它具有封闭性、系统性和循环性。 循环码中任一许用码组经过循环移位后，不论右移或左循环码中任一许用码组经过循环移位后，不论右移或左移，移位位数是多少，所得到的码组仍然是许用码组。移，移位位数是多少，所得到的码组仍然是许用码组。循环码编码电路简单，性能优良，不仅可以纠正独立的循环码编码电路简单，性能优良，不仅可以纠正独立的随机错误，还能纠正突发错误。随机错误，还能纠正突发错误。 差错

35、控制编码 最新第第7 7章章 差错控制编码差错控制编码表表7.4 7.4 （7 7，3 3）循环码码字表）循环码码字表差错控制编码 最新第第7 7章章 差错控制编码差错控制编码一般说来，若一般说来，若（a an-1 n-1 a an-2 n-2 a a1 1 a a0 0) )是一个循环码组，则是一个循环码组，则 （a an-2 n-2 a an-3 n-3 a a0 0 a an-1n-1) ) （a an-3 n-3 a an-4 n-4 a an-1 n-1 a an-2n-2) ) （a a0 0 a an-1 n-1 a a2 2 a a1 1) )也是该编码中的码组。也是该编码中的

36、码组。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码（2 2）码多项式）码多项式为了利用代数理论研究循环码，可以将码组用代数为了利用代数理论研究循环码，可以将码组用代数多项式来表示，这个多项式被称为多项式来表示，这个多项式被称为码多项式码多项式，用，用T(x)T(x)表表示。示。（n n，k k）循环码的许用码组可以表示为：）循环码的许用码组可以表示为：例如：例如：表表7.47.4中的中的第第4 4码组码组可以用多可以用多项项式表示式表示为为：想一想想一想想一想想一想 是表是表7.47.4中的第中的第 ？码组的码组的多项式？多项式？（以降幂顺序排列）（以降幂顺序排列）差错控制编码

37、最新第第7 7章章 差错控制编码差错控制编码循环码的码多项式特点 把许用码组把许用码组T=T=（a an-1 n-1 a an-2 n-2 a a1 1 a a0 0) ) 表示为：表示为： x x为一个任意的实变量，其幂次代表移位次数。当码为一个任意的实变量，其幂次代表移位次数。当码组组T T向左循环移向左循环移i i位后的码组位后的码组 ，其码多项式，其码多项式为：为： 差错控制编码 最新第第7 7章章 差错控制编码差错控制编码码多项式的除法运算：码多项式的除法运算：设有设有A码组（码组（1101）和）和B码组（码组（10111），则），则A码多项式码多项式为：为：A(x)=x4+x3+x

38、2+1，B码多项式为：码多项式为：B(x)=x2+x+1，A(x) B(x)得（余数为得（余数为0）：）：差错控制编码 最新第第7 7章章 差错控制编码差错控制编码（3 3）循环码的编码方法）循环码的编码方法 循环码循环码T(x)是按下述方法编制的：是按下述方法编制的： 式中：式中： n n- -k k监监督督码码的位数；的位数； m(x)信息信息码码多多项项式；式； r(x)余式多项式，即余式多项式，即xn-km(x)/g(x)的余式多项式；的余式多项式； g(x)生成多生成多项项式。式。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码循环码的生成多项式循环码的生成多项式 循环码中

39、次数最低的码多项式（全循环码中次数最低的码多项式（全“0”码字除码字除外）称为生成多项式，用外）称为生成多项式，用g(x)表示。可以证明生成表示。可以证明生成多项式多项式g(x)具有以下特性具有以下特性：（1）g(x)是一个常数项为是一个常数项为1的的r=n-k r=n-k 次多项式；次多项式；（2）g(x)是是xn+1的一个因式；的一个因式；（3）该循环码中其它码多项式都是该循环码中其它码多项式都是g(x)的倍式。的倍式。（这给出了产生及解译循环码的方法，即发端的码多项式一（这给出了产生及解译循环码的方法，即发端的码多项式一定能被定能被g(x)整除，接收端整除，接收端的码多项式不一定能被多项

40、式整除）的码多项式不一定能被多项式整除）差错控制编码 最新第第7 7章章 差错控制编码差错控制编码循环码的生成多项式循环码的生成多项式1.1.循环码循环码T(x)T(x)的表示式：的表示式：2.2.对于任意对于任意n n值，必然存在值，必然存在 (1)取取（x+1)为生成多项式，由此构成的循环码即为简单的为生成多项式，由此构成的循环码即为简单的偶监督码偶监督码(n，n-1)。由于。由于g(x)为一阶多项式，因此只有一为一阶多项式，因此只有一位监督码。位监督码。(x+1)的任何倍式的码重必定保持偶数，其的任何倍式的码重必定保持偶数，其最小码距最小码距dmin=2。(2)以以为生成多项式，由于生成

41、多为生成多项式，由于生成多项式为项式为n-1阶多项式，故信息码位数为阶多项式，故信息码位数为1。它只有两个许。它只有两个许用码组：全用码组：全“0”和全和全“1”，因此这种循环码是，因此这种循环码是（n,1）重复码，其最小码距）重复码，其最小码距dmin=n。T(x)=m(x) g(x)差错控制编码 最新第第7 7章章 差错控制编码差错控制编码循环码的生成多项式循环码的生成多项式(3)例如：（例如：（7，3）循环码）循环码g(x)可由可由x7+1分解分解因式（系数按模二加运算）得到：因式（系数按模二加运算）得到：差错控制编码 最新第第7 7章章 差错控制编码差错控制编码编码过程编码过程首先需要

42、根据给定循环码的参数（首先需要根据给定循环码的参数（n，k）确定）确定生成多项式生成多项式g(x)，即从（，即从（xn+1）的因子中选一（）的因子中选一（n-k）次多项式作为）次多项式作为g(x)。然后，利用循环码的编码然后，利用循环码的编码特点，即特点，即所有循环码多项式所有循环码多项式T(x)都可以被都可以被g(x)整除，整除，来定义生成多项式来定义生成多项式g(x)。下面就将以上各步处理加以解释：下面就将以上各步处理加以解释：差错控制编码 最新第第7 7章章 差错控制编码差错控制编码【编码举例【编码举例】信息码为信息码为110，生成多项式为，生成多项式为g(x)=x4+x3+x2+1，编

43、出，编出对应的（对应的（7，3）码组。）码组。编码方法归结为以下几步：编码方法归结为以下几步：（1）用用xn-k乘乘m(x)。这一运算实际上是把信息码后。这一运算实际上是把信息码后附加上（附加上（n-k）个）个“0”。信息码为信息码为110，m(x)=x2+x，n-k=7-3=4时，时，xn-km(x)=x4(x2+x)=x6+x5(相当于相当于1100000）差错控制编码 最新第第7 7章章 差错控制编码差错控制编码（2）求求r(x)。用生成多项式。用生成多项式g(x)除除xn-km(x)，得到，得到商和余式商和余式r(x)r(x)，即，即相当于相当于1100000/11101（3）编码输出

44、系统循环码多项式编码输出系统循环码多项式T(x)为：为： 差错控制编码 最新第第7 7章章 差错控制编码差错控制编码 上述三步编码过程，在硬件实现时，可以利用上述三步编码过程，在硬件实现时，可以利用除法除法电路电路来实现。来实现。 g(x)的次数等于移位寄存器的级数，的次数等于移位寄存器的级数，g(x)=xo,x1,x2.,xr的非零系数对应移位寄存器的反馈抽头。的非零系数对应移位寄存器的反馈抽头。首先，移位寄存器清零。首先，移位寄存器清零。3位信息码元输入时，门位信息码元输入时，门1断开，门断开，门2接通，直接输出信息元。第接通，直接输出信息元。第3次移位脉冲到来时将除法电路所次移位脉冲到来

45、时将除法电路所得的余数存入移位寄存器。第得的余数存入移位寄存器。第47移位时，门移位时，门1接通，门接通，门2断开，断开，输出监督码元。此时输入信息码元为输出监督码元。此时输入信息码元为110。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码差错控制编码 最新第第7 7章章 差错控制编码差错控制编码2、译码过程、译码过程 循环码的译码可以分三步进行：循环码的译码可以分三步进行： （1）由接收到的码多项式）由接收到的码多项式B(x)计算校正子（伴计算校正子（伴随式）多项式随式）多项式S(x)；差错控制编码 最新第第7 7章章 差错控制编码差错控制编码（2）由校正子由校正子S(x)确定错

46、误图样确定错误图样E(x)；（3）将错误图样将错误图样E(x)与与B(x)相加，纠正错误。相加，纠正错误。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码（4 4）循）循环码环码的其他常的其他常见类见类型型1）BCH码码 BCH码码是一种特是一种特别别重要的循重要的循环码环码，是目，是目前研究得最前研究得最为为透透彻彻的一的一类纠错码类纠错码。2）R- -S码码 R- -S码码是里德是里德所所罗门码罗门码（Reed SolomonCode）的）的简简称，于称，于20世世纪纪60年代提出，是一年代提出，是一类类非二非二进进制制BCH码码。差错控制编码 最新第第7 7章章 差错控制编码差

47、错控制编码7.47.4卷积码卷积码卷积码卷积码卷积码：卷积码：监督码元不仅与本组的信息有关，而且监督码元不仅与本组的信息有关，而且还与以前码组的信息有约束关系，各组之间具有还与以前码组的信息有约束关系，各组之间具有相关性。相关性。卷积码中编码后的卷积码中编码后的n个码元不仅与当前段的个码元不仅与当前段的k个信息有关，个信息有关，而且也与前面（而且也与前面（N-1）段的信息有关，编码过程中）段的信息有关，编码过程中相互关联的相互关联的码元为码元为nN个个。因此，这。因此，这N段时间内的码元数目段时间内的码元数目nN通常被称为通常被称为这种码的这种码的约束长度。约束长度。由于与前面由于与前面m段规

48、定时间内的信息位有关，这里的段规定时间内的信息位有关，这里的mN-1，通常用（通常用（n，k，m）表示卷积码）表示卷积码。m m为编码存储，为编码存储，n n为码长，为码长， k k为信息码元位数，为信息码元位数，(n(n，k)k)称称为子码，通常较短为子码，通常较短 。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码卷积码的编码规则：卷积码的编码规则：先将信息序列分成长度为先将信息序列分成长度为k的子组，然后编成长为的子组，然后编成长为n的子码，其中长为的子码，其中长为r=n-k的监的监督码元不仅与本子码的督码元不仅与本子码的k个信息码元有关，而且还与个信息码元有关，而且还与前面前

49、面m个子码的信息码元密切相关。即各子码内的监个子码的信息码元密切相关。即各子码内的监督码元不仅对本子码有监督作用，而且对前面督码元不仅对本子码有监督作用，而且对前面m个子个子码内的信息元也有监督作用。码内的信息元也有监督作用。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码例如：例如：卷积码的卷积码的n=2，k=1，m=2，因此，它的，因此，它的约束长度约束长度nN = n(m+1) )=23=6。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码【例】【例】下图是（下图是（3,1,23,1,2）卷积码编码器。它由两级移）卷积码编码器。它由两级移位寄存器（位寄存器（m mj-

50、1,m,mj-2）、两个模二加法器和开关电路组）、两个模二加法器和开关电路组成。编码前，各级寄存器清零，信息码元按成。编码前，各级寄存器清零，信息码元按m m1,m,m2, m, mj,的顺序送入编码器。每输入的顺序送入编码器。每输入一个信息码元一个信息码元m mj，开关电路依次接到，开关电路依次接到x x1.j,x,x2.j和和x x3.j各端各端点一次。点一次。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码卷积码卷积码当输入数据D=11010时，可以计算出码字，如表差错控制编码 最新第第7 7章章 差错控制编码差错控制编码a,b,c,d分别表示分别表示mj-2,mj-1的四种状

51、态：的四种状态：00，11，10，11。当第一位信息码元为当第一位信息码元为1时，即时，即m1=1，因，因mj-2,mj-1=00，故输，故输出比特出比特x1.jx2.jx3.j=111;当第二位信息码元为当第二位信息码元为1时，即时，即m2=1，因因mj-2,mj-1=01，故输出比特，故输出比特x1.jx2.jx3.j=110；依此类推。；依此类推。为保证输入的全部信息位为保证输入的全部信息位11010都能通过移位寄存器，都能通过移位寄存器，还必须在信息位后加还必须在信息位后加3个零。个零。差错控制编码 最新第第7 7章章 差错控制编码差错控制编码图图7.3 7.3 卷积码编码器的一般结构图卷积码编码器的一般结构图差错控制编码 最新