第6章差错控制编码

1、第6章 差错控制编码技术 第第6章章 差错控制编码技术差错控制编码技术 6.2 信道容量与香农公式信道容量与香农公式 6.3 信道编码信道编码 6.4 线性线性分组码分组码 6.5 循环码循环码 第6章 差错控制编码技术 6.2 信道容量与香农公式信道容量与香农公式 信道容量是指信道能够传输的最大平均信息信道容量是指信道能够传输的最大平均信息 速率。速率。 第6章 差错控制编码技术 1、模拟（连续）信道的信道容量、模拟（连续）信道的信道容量 假设信道的带宽为假设信道的带宽为B（Hz），信道输出的信号功率），信道输出的信号功率 为为S(W)及输出加性高斯白噪声功率为及输出加性高斯白噪声功率为N(

2、W)，则可以证明，则可以证明 该信道的信道容量为：该信道的信道容量为： C 上式就是著名的香农上式就是著名的香农(Shannon)信道容量公式，简称信道容量公式，简称 香农公式。香农公式表明的是当信号与作用在信道上噪香农公式。香农公式表明的是当信号与作用在信道上噪 声的平均功率给定时，在具有一定频带宽度声的平均功率给定时，在具有一定频带宽度B的信道上，的信道上， 理论上单位时间内可能传输的信息量的极限数值。同时，理论上单位时间内可能传输的信息量的极限数值。同时， 该式还是扩展频谱技术的理论基础。该式还是扩展频谱技术的理论基础。 )/)(1 (log2sb N s B 第6章 差错控制编码技术

3、只要传输速率小于等于信道容量，则总可以找到一种信道只要传输速率小于等于信道容量，则总可以找到一种信道 编码方式，实现无差错传输；若传输速率大于信道容量，则不编码方式，实现无差错传输；若传输速率大于信道容量，则不 可能实现无差错传输。可能实现无差错传输。 若噪声若噪声n(t)的单边功率谱密度为的单边功率谱密度为n0，则在信道带宽，则在信道带宽B内的噪内的噪 声功率声功率N=n0B。因此，香农公式的另一形式为：。因此，香农公式的另一形式为： C=Blog2 由香农公式可得以下结论：由香农公式可得以下结论： (1) 增大信号功率增大信号功率S可以增加信道容量，若信号功率趋于无可以增加信道容量，若信号

4、功率趋于无 穷大，则信道容量也趋于无穷大，即穷大，则信道容量也趋于无穷大，即 )/)(1 ( 0 sb Bn s )1 (log 0 2limlim Bn s Bc ss 第6章 差错控制编码技术 (2) 减小噪声功率减小噪声功率N (或减小噪声功率谱密度或减小噪声功率谱密度n0)可以增加信可以增加信 道容量，若噪声功率趋于零道容量，若噪声功率趋于零(或噪声功率谱密度趋于零或噪声功率谱密度趋于零)，则信，则信 道容量趋于无穷大，即：道容量趋于无穷大，即： )1 (log2 00 limlim N s Bc NN (3) 增大信道带宽增大信道带宽B可以增加信道容量，但不能使信道容量可以增加信道容

5、量，但不能使信道容量 无限制增大。信道带宽无限制增大。信道带宽B趋于无穷大时，信道容量的极限值为：趋于无穷大时，信道容量的极限值为： )1 (log)1 (log 0 2 0 00 2limlimlim Bn s S Bn n s Bn s BBB Bc 0 2 0 44. 1log n s e n s 第6章 差错控制编码技术 第6章 差错控制编码技术 第6章 差错控制编码技术 信道的容量信道的容量C必须不小于此必须不小于此RB值。根据香农公式有：值。根据香农公式有： 22.5106 又因：又因： 推出：推出： S/N=1000（倍）（倍） )1 (log2 N S B dB N S 30l

6、og10 10 第6章 差错控制编码技术 2、数字信道无噪声时的容量、数字信道无噪声时的容量 其中：其中：N为每秒传输的码元数为每秒传输的码元数 K为进制数为进制数 )(log 2max bpsKnRC 第6章 差错控制编码技术 6.3 信道编码信道编码 6.3.1 差错控制原理差错控制原理 1. 差错控制编码的基本原理差错控制编码的基本原理 信道编码的基本思想就是用系统的有效性来换取可靠信道编码的基本思想就是用系统的有效性来换取可靠 性，实际上就是在传输的信息码元中附加一定数量的冗余性，实际上就是在传输的信息码元中附加一定数量的冗余 码（通常称之为监督码元），冗余码在整个编码中的位置码（通常

7、称之为监督码元），冗余码在整个编码中的位置 及代码选择由某一事先确定的规则来决定，收端接收到这及代码选择由某一事先确定的规则来决定，收端接收到这 样的编码后，根据已知的规则，对接收信息进行检验，发样的编码后，根据已知的规则，对接收信息进行检验，发 现、纠正和删除错误。下面我们举例说明差错控制编码的现、纠正和删除错误。下面我们举例说明差错控制编码的 原理。原理。 第6章 差错控制编码技术 假设要发送一组具有八个状态的数据信息假设要发送一组具有八个状态的数据信息 “000”（晴），（晴），“001”（云），（云），“010”（阴），（阴）， “011”（雨），（雨），“100”（雪），（雪），“1

8、01”（霜），（霜）， “110”（雾），（雾），“111”（雹）。我们首先要用二（雹）。我们首先要用二 进制码对数据信息进行编码，显然，用进制码对数据信息进行编码，显然，用3位二进位二进 制码就可完成。但任一码组在传输中若发生一制码就可完成。但任一码组在传输中若发生一 个或多个错码，则将变成另一信息码组。这时，个或多个错码，则将变成另一信息码组。这时， 接收端将无法发现错误。接收端将无法发现错误。 第6章 差错控制编码技术 因此，以这种编码形式得到的数字信号在传因此，以这种编码形式得到的数字信号在传 输过程中不具备检错和纠错的能力，这是我们所输过程中不具备检错和纠错的能力，这是我们所 不希望

9、的。但若在上述不希望的。但若在上述8种码组中只准许使用种码组中只准许使用4种种 来传送信息，如：来传送信息，如：“000”（晴），（晴），“011”（云），（云）， “101”（阴），（阴），“110”（雨），这时，虽然只能（雨），这时，虽然只能 传送传送4种不同的信息，但是接收端却有可能发现种不同的信息，但是接收端却有可能发现 码组中的一个错码。码组中的一个错码。 第6章 差错控制编码技术 在许用码组在许用码组000、011、101、110中，右边加上中，右边加上 的的1位码元就是位码元就是监督码元监督码元，它的加入原则是使码组，它的加入原则是使码组 中中1的个数为偶数，这样监督码元就和前面

10、的个数为偶数，这样监督码元就和前面2位信息位信息 码元发生了关系，这种编码方式称为偶校验，反之，码元发生了关系，这种编码方式称为偶校验，反之， 如果加入原则是使码组中如果加入原则是使码组中1的个数为奇数，则编码的个数为奇数，则编码 方式称为奇校验。现在我们再看一下出现误码的情方式称为奇校验。现在我们再看一下出现误码的情 况，假设许用码组况，假设许用码组000出现出现1位误码，即变成位误码，即变成001、 010或或100三个码组中的一个，可见这三个码组中三个码组中的一个，可见这三个码组中1 的个数都是奇数，是禁用码组。的个数都是奇数，是禁用码组。 第6章 差错控制编码技术 信息位和监督位关系信

11、息位和监督位关系 信息位信息位监督位监督位 睛睛000 云云011 阴阴101 雨雨110 第6章 差错控制编码技术 因此，当收信端收到这三个码组中的任何一个因此，当收信端收到这三个码组中的任何一个 时，就知道是误码，用这种方法可以发现时，就知道是误码，用这种方法可以发现1位或位或3位位 出现错误的码组，而无法检出出现错误的码组，而无法检出2位错误，因为一个位错误，因为一个 码组出现码组出现2位错误，其奇偶性不变。那么，收信端位错误，其奇偶性不变。那么，收信端 能否从误码中判断哪一位发生错误了呢（即纠正错能否从误码中判断哪一位发生错误了呢（即纠正错 误）？比如对误码误）？比如对误码001而言，

12、如果是而言，如果是1位发生错误，位发生错误， 原码可能是原码可能是000、101或或011；如果；如果3位都错，原码就位都错，原码就 是是110，我们现在无法判断出原码到底是哪一组。，我们现在无法判断出原码到底是哪一组。 也就是说，通过增加也就是说，通过增加1位监督码元，我们可以检出位监督码元，我们可以检出1 位或位或3位错误（位错误（3位出错的概率极小），但无法纠正位出错的概率极小），但无法纠正 错误。错误。 第6章 差错控制编码技术 要想纠正错误，还要增加多余度。即通过增加要想纠正错误，还要增加多余度。即通过增加 监督码元的位数来增加检错位数或实现纠错功能。监督码元的位数来增加检错位数或实

13、现纠错功能。 如规定许用码组只有两个：如规定许用码组只有两个：“000”（晴）、（晴）、“111” （雨），其它都是禁用码组，则能够检测两个以上（雨），其它都是禁用码组，则能够检测两个以上 错码，或能够纠正一个错码。错码，或能够纠正一个错码。 第6章 差错控制编码技术 可见，简单地增加可见，简单地增加1位监督码元并没有提高检错与位监督码元并没有提高检错与 纠错能力，那么，检错与纠错能力到底与什么有关呢？纠错能力，那么，检错与纠错能力到底与什么有关呢？ 归纳如下归纳如下: （1）在信息码元序列中加入监督码元的过程称为差错控）在信息码元序列中加入监督码元的过程称为差错控 制编码。制编码。 （2）不

14、同的编码方法具有不同的检错或纪错能力。）不同的编码方法具有不同的检错或纪错能力。 （3）增加的监督位数越多，则检（纠）错能力越强。）增加的监督位数越多，则检（纠）错能力越强。 编码效率编码效率=信息码位数信息码位数/码组总位数码组总位数 多余度多余度=监督码位数监督码位数/码组总位数码组总位数 所以，差错控制编码是用降低信息传输速率来提高所以，差错控制编码是用降低信息传输速率来提高 传输可靠性。传输可靠性。 第6章 差错控制编码技术 2差错控制方式差错控制方式 差错控制方法，常用差错控制方法，常用 的有以下几种：的有以下几种： （1）前向纠错法（）前向纠错法（FEC） 接收端不仅能在收接收端不

15、仅能在收 到到 的信码中发现有错码，还能够纠正错码。对于二的信码中发现有错码，还能够纠正错码。对于二 进制系统，如果能够确定错码的地方，就能够纠进制系统，如果能够确定错码的地方，就能够纠 正它。这种方法正它。这种方法优点优点：不需要反向信道，也不存：不需要反向信道，也不存 在由于反复重发而延误时间，实时性好，在由于反复重发而延误时间，实时性好，缺点缺点： 但是纠错设备要比检错设备复杂。但是纠错设备要比检错设备复杂。 第6章 差错控制编码技术 （2）检错重发法（）检错重发法（ARQ） 接收端在收到的信码接收端在收到的信码 中检测出（发现）错码时，即设法通知发送端重中检测出（发现）错码时，即设法通

16、知发送端重 发，直到正确收到为止。所谓检测出错码是指在发，直到正确收到为止。所谓检测出错码是指在 若干接收码元中知道有一个或一些是错的，但不若干接收码元中知道有一个或一些是错的，但不 一定知道该错码的准确位置。采用这种差错控制一定知道该错码的准确位置。采用这种差错控制 方法需要具备双向信道。方法需要具备双向信道。 第6章 差错控制编码技术 检错重发法（检错重发法（ARQ）原理方框图）原理方框图 第6章 差错控制编码技术 ARQ方式的主要优点：方式的主要优点： （1）只需要少量的多余码元就能获得极低的输出误）只需要少量的多余码元就能获得极低的输出误 码率；码率； （2）要求使用的检错码基本上与信

17、道的差错统计特）要求使用的检错码基本上与信道的差错统计特 性无关；性无关； （3）其检错译码器与前向纠错法中的纠错译码器相）其检错译码器与前向纠错法中的纠错译码器相 比，成本和复杂性均低得多。比，成本和复杂性均低得多。 第6章 差错控制编码技术 缺点：缺点： （1）由于需要反向信道，故不能用于单向传输系统，）由于需要反向信道，故不能用于单向传输系统， 并且实现实现重发控制比较复杂；并且实现实现重发控制比较复杂； （2）当信道干扰增大时，整个系统可能处在重发循）当信道干扰增大时，整个系统可能处在重发循 环中，因而通信效率降低，甚至不能通信；环中，因而通信效率降低，甚至不能通信； （3）不大适于要

18、求严格实时传输的系统。）不大适于要求严格实时传输的系统。 第6章 差错控制编码技术 图图6.5 ARQ系统的工作方式系统的工作方式 发发 端端 收收 端端 1 2 3 4 5 6 7 8 4 5 6 7 8 9 10 11 12 13 14 1 2 3 4 5 6 7 8 4 5 6 7 8 9 10 11 12 13 14 发送出错信号发送出错信号 重发信号重发信号 发现错误发现错误 第6章 差错控制编码技术 （3）混合纠错混合纠错HEC 这一方式实质上是这一方式实质上是 FEC和和 ARQ方式的综合。方式的综合。 当收端接收到少量错码时，就在接收端直接纠当收端接收到少量错码时，就在接收端直

19、接纠 正，即采用前向纠错方案；当错码太多超过其纠正，即采用前向纠错方案；当错码太多超过其纠 错能力时，则采用检错重发方式。错能力时，则采用检错重发方式。HEC充分利用充分利用 了前向纠错和检错重发系统的特点，性能较好。了前向纠错和检错重发系统的特点，性能较好。 但需要双向信道，且系统设备较复杂。但需要双向信道，且系统设备较复杂。 第6章 差错控制编码技术 （4）信息反馈（）信息反馈（IF） 接收端将收到的信码原封不动地转发接收端将收到的信码原封不动地转发 回发送端，并与原发送信码相比较。如果回发送端，并与原发送信码相比较。如果 发现错误，则发送端再进行重发，否则不发现错误，则发送端再进行重发，

20、否则不 做任何处理，继续发送后面的信息。这种做任何处理，继续发送后面的信息。这种 方法原理和设备都较简单，但需要有双向方法原理和设备都较简单，但需要有双向 信道，传输效率较低。信道，传输效率较低。 第6章 差错控制编码技术 3差错控制编码的分类差错控制编码的分类 （1）按照编码的不同用途，差错控制码可分为）按照编码的不同用途，差错控制码可分为检错码、纠错码和纠删检错码、纠错码和纠删 码。码。 （2）按照监督码元和信息码元之间的不同关系，差错控制码分为）按照监督码元和信息码元之间的不同关系，差错控制码分为线性线性 码和非线性码。码和非线性码。 （3）按照对信息码元的处理方式不同，差错控制码可分为

21、）按照对信息码元的处理方式不同，差错控制码可分为分组码和卷分组码和卷 积码。积码。 （4）按照码组中信息码元在编码前后的位置是否发生变化，可将差错）按照码组中信息码元在编码前后的位置是否发生变化，可将差错 控制码分为控制码分为系统码和非系统码。系统码和非系统码。 （5）按照编码针对的不同干扰类型，差错控制码可分为）按照编码针对的不同干扰类型，差错控制码可分为纠（检）随机纠（检）随机 （或独立）错误码、纠（检）突发错误码和既能纠（检）随机错误同时（或独立）错误码、纠（检）突发错误码和既能纠（检）随机错误同时 又能纠（检）突发错误码。又能纠（检）突发错误码。 第6章 差错控制编码技术 6.3.2

22、码重与码距码重与码距 1几个基本概念几个基本概念 （1）分组码的概念：将信息码分组，为每组信码附）分组码的概念：将信息码分组，为每组信码附 加若干监督码的编码方式称为分组码。在分组码加若干监督码的编码方式称为分组码。在分组码 中，监督码元仅监督本码组中的信息码元。中，监督码元仅监督本码组中的信息码元。 分组码一般用符号（分组码一般用符号（n，k）表示，其中）表示，其中n是码组是码组 的总位数，又称为码组的长度（码长），的总位数，又称为码组的长度（码长），k是码组中是码组中 信息码元的数目，信息码元的数目，n-k=r为码组中的监督码元数目，为码组中的监督码元数目， 或称监督位数目。或称监督位数目

23、。 第6章 差错控制编码技术 分组码的结构分组码的结构 第6章 差错控制编码技术 （2）码长）码长 码组中码元的总位数，又称为码组长度。码组中码元的总位数，又称为码组长度。 （3）码重）码重 在分组码中，把码组中在分组码中，把码组中“1”的个数称为码组的的个数称为码组的 重重 量，简称码重。量，简称码重。 （4）码距）码距 把两个码组中对应位上数字不同的位数称为码把两个码组中对应位上数字不同的位数称为码 组的距离，简称码距。码距又称汉明距离。组的距离，简称码距。码距又称汉明距离。 第6章 差错控制编码技术 码距反映的是码组之间的差异程度，比如，码距反映的是码组之间的差异程度，比如， 00和和0

24、1两组码的码距为两组码的码距为1；011和和100的码距为的码距为3。 （5）最小码距）最小码距dmin 多个码组之间相互比较，可能会有不同的码多个码组之间相互比较，可能会有不同的码 距，其中的最小值被称为最小码距。比如，距，其中的最小值被称为最小码距。比如，000、 001、110三个码组相比较，码距有三个码组相比较，码距有1和和2两个值，两个值， 则最小码距为则最小码距为1。 最小码距是衡量一种编码的纠检错能力强最小码距是衡量一种编码的纠检错能力强 弱的主要依据弱的主要依据。 第6章 差错控制编码技术 2 纠检错能力与最小码距纠检错能力与最小码距dmin的关系的关系 根据理论推导，可以得出

25、以下结论：根据理论推导，可以得出以下结论： (1)在一个码组内要想检出在一个码组内要想检出e位误码，要求最小码距为位误码，要求最小码距为 d0e+1 (2)在一个码组内要想纠正在一个码组内要想纠正t位误码，要求最小码距为位误码，要求最小码距为 d02t+1 (3)在一个码组内要想纠正在一个码组内要想纠正t位误码，同时检测出位误码，同时检测出e位误位误 码（码（et）,要求最小码距为要求最小码距为 d0t+e+1 （et） 第6章 差错控制编码技术 第6章 差错控制编码技术 第6章 差错控制编码技术 显然，要提高编码的纠、检错能力，不能仅显然，要提高编码的纠、检错能力，不能仅 靠简单地增加监督码

26、元位数（即冗余度），更重靠简单地增加监督码元位数（即冗余度），更重 要的是要加大最小码距（即码组之间的差异程要的是要加大最小码距（即码组之间的差异程 度），而最小码距的大小与编码的冗余度是有关度），而最小码距的大小与编码的冗余度是有关 的，最小码距增大，码元的冗余度就增大，但码的，最小码距增大，码元的冗余度就增大，但码 元的冗余度增大，最小码距不一定增大。因此，元的冗余度增大，最小码距不一定增大。因此， 一种编码方式具有检错和纠错能力的必要条件是一种编码方式具有检错和纠错能力的必要条件是 信息编码必须有冗余，而充分条件是码组之间要信息编码必须有冗余，而充分条件是码组之间要 有一定的码距。有一定

27、的码距。 第6章 差错控制编码技术 6.3.3 几种常用的差错控制码几种常用的差错控制码 重复码重复码 （1）逐位重复）逐位重复 将信息码元以位为单位，重复传送将信息码元以位为单位，重复传送N次。如待次。如待 发的信息码序列为发的信息码序列为 110100101则它的三重码则它的三重码 为：为：111 111 000 111 000 000 111 000 111 （2）分段重复）分段重复 将待传送信息码元以固定的若干位为单位，重将待传送信息码元以固定的若干位为单位，重 复传送复传送N次。设待发的信息码序列为：次。设待发的信息码序列为： 110100101若以三位为一段，则它的三重码为：若以三

28、位为一段，则它的三重码为： 110 110 110 100 100 100 101 101 101 第6章 差错控制编码技术 2. 奇偶监督码奇偶监督码 奇偶监督码是数据通信中最常见的一种简奇偶监督码是数据通信中最常见的一种简 单检错码，其编码规则是：把信息码先分组，单检错码，其编码规则是：把信息码先分组， 形成多个许用码组，在每一个许用码组最后形成多个许用码组，在每一个许用码组最后 （最低位）加上一位监督码元即可。加上监督（最低位）加上一位监督码元即可。加上监督 码元后使该码组中码元后使该码组中1的数目为奇数的编码称为奇的数目为奇数的编码称为奇 数监督码，为偶数的编码称为偶数监督码。数监督码

29、，为偶数的编码称为偶数监督码。 第6章 差错控制编码技术 假设一个码组的长度为假设一个码组的长度为n，表示为（，表示为（an-1an-2an- 3a0），其中前 ），其中前n-1位是信息码，最后一位位是信息码，最后一位a0为为 监督位，那么：监督位，那么： 对于偶数监督码必须保证对于偶数监督码必须保证 1230 0 nnn aaaa 监督码元监督码元a0的取值（的取值（0或或1）可由下式决定：）可由下式决定： 01231nnn aaaaa 第6章 差错控制编码技术 对于奇数监督码必须保证对于奇数监督码必须保证 1230 1 nnn aaaa 监督码元监督码元a0的取值（的取值（0或或1）可由下

30、式决定：）可由下式决定： 01231 1 nnn aaaaa 第6章 差错控制编码技术 根据奇偶监督码的规则我们可以看到，当码根据奇偶监督码的规则我们可以看到，当码 组中的组中的误码为偶数误码为偶数时，校验失效。比如有两位发时，校验失效。比如有两位发 生错误，会有这样几种情况：生错误，会有这样几种情况：00变成变成11、11变成变成 00、01变成变成10、10变成变成01，可见无论哪种情况出，可见无论哪种情况出 现都不会改变码组的奇偶性，偶数监督码中现都不会改变码组的奇偶性，偶数监督码中1的的 个数仍为偶数，奇数监督码中个数仍为偶数，奇数监督码中1的个数仍为奇数。的个数仍为奇数。 因此，因此

31、，简单的奇偶监督码只能检测出发生奇数个简单的奇偶监督码只能检测出发生奇数个 错误的码组。错误的码组。 第6章 差错控制编码技术 3. 二维奇偶监督码二维奇偶监督码 二维奇偶监督码又称方阵码。二维奇偶监督码又称方阵码。 二维奇偶校验码比一维奇偶校验码多了个二维奇偶校验码比一维奇偶校验码多了个 列校验，因此，其检错能力有所提高。除了检列校验，因此，其检错能力有所提高。除了检 出行中的所有奇数个误码及长度不大于行数的出行中的所有奇数个误码及长度不大于行数的 突发性错误外，还可检出列中的所有奇数个误突发性错误外，还可检出列中的所有奇数个误 码及长度不大于列数的突发性错误。码及长度不大于列数的突发性错误

32、。 前述的一前述的一 维奇偶监督码一般只适于检测随机错误。维奇偶监督码一般只适于检测随机错误。 第6章 差错控制编码技术 二维奇偶监督码不仅可用来检错，还可用来二维奇偶监督码不仅可用来检错，还可用来 纠正一些错码。例如，当码组中仅在一行中有奇纠正一些错码。例如，当码组中仅在一行中有奇 数个错误时，则能够确定错码位置，从而纠正它。数个错误时，则能够确定错码位置，从而纠正它。 第6章 差错控制编码技术 第6章 差错控制编码技术 二维偶监督码二维偶监督码 第6章 差错控制编码技术 4. 定（恒）比码定（恒）比码 定比码又称等比码或等重码，它的每个许用码组中定比码又称等比码或等重码，它的每个许用码组中

33、 含含1、0的个数是固定的。编码时，取所有含的个数是固定的。编码时，取所有含l、0个数符合个数符合 要求的码组为许用码组，其余则为禁用码组。在收端进要求的码组为许用码组，其余则为禁用码组。在收端进 行检测时，只要检测码组中行检测时，只要检测码组中1、0的个数是否等于规定的的个数是否等于规定的 数目，就可判断有无错误。常见的定比码有五三定比码数目，就可判断有无错误。常见的定比码有五三定比码 和七三定比码。我国电传通信中普遍采用五三定比码，和七三定比码。我国电传通信中普遍采用五三定比码， 又称又称5中取中取3码。它的每个码字都由码。它的每个码字都由3个个l、2个个0共共5个码元个码元 组成。其许用

34、码组的数目为组成。其许用码组的数目为5中取中取3的组合数，即的组合数，即 =5！ /(3！2！)= 10，正好可以唯一表示，正好可以唯一表示10个阿拉伯数字。个阿拉伯数字。 3 5 C 第6章 差错控制编码技术 不难看出这种码的最小码距是不难看出这种码的最小码距是2，它能，它能 够检出码组中所有奇数个错误和部分偶数够检出码组中所有奇数个错误和部分偶数 个错误。主要优点是简单，适用于对电传个错误。主要优点是简单，适用于对电传 机或其它键盘设备产生的字母和符号进行机或其它键盘设备产生的字母和符号进行 编码。编码。 第6章 差错控制编码技术 5. 群计数码群计数码 群计数码针对分组后的信息码元组，计

35、算出每组码元中群计数码针对分组后的信息码元组，计算出每组码元中l 的个数，再将该数目的二进制编码作为监督码元，加在信息的个数，再将该数目的二进制编码作为监督码元，加在信息 码元之后一起发送。码元之后一起发送。 设有一组设有一组7位信息码元位信息码元1001101，由于其，由于其l的个数为的个数为4，监督，监督 码元就是码元就是100。这样，发送的代码为。这样，发送的代码为1001101100。接收端只。接收端只 需检测监督码元所表示的需检测监督码元所表示的1的个数与信息码元中的的个数与信息码元中的1的个数是的个数是 否相同，就可立即判断正误。否相同，就可立即判断正误。 除了除了1变为变为0和和

36、0变为变为1成对出现的错误以外，群计数码可成对出现的错误以外，群计数码可 以检测到所有其他形式的错误，检错能力很强。以检测到所有其他形式的错误，检错能力很强。 第6章 差错控制编码技术 6.4 线性分组码线性分组码 6.4.1 线性分组码的定义及性质线性分组码的定义及性质 一、线性分组码定义一、线性分组码定义 信息码元与监督码元之间可以用一组线性方程信息码元与监督码元之间可以用一组线性方程 来表示，且监督码元仅由本码组的信息码元确定。来表示，且监督码元仅由本码组的信息码元确定。 二、线性分组码的表示二、线性分组码的表示 （n，k），监督位监督位 r=n-k 其编码效率其编码效率 = k/n 第

37、6章 差错控制编码技术 三、线性分组码的性质三、线性分组码的性质 （1）封闭性：任意两个许用码组之模）封闭性：任意两个许用码组之模2和仍为和仍为 一许用码组；一许用码组； （2）码组的最小码）码组的最小码dmin距等于非零码的最小码距等于非零码的最小码 重。重。 第6章 差错控制编码技术 6.4.2 线性分组码编码方法线性分组码编码方法 一、编码要求一、编码要求 从已知的从已知的k个信息码元中求出满足要求的个信息码元中求出满足要求的r=n-k 个监督码元（校验码），然后附在信息码元之后个监督码元（校验码），然后附在信息码元之后 构成个码组。构成个码组。 第6章 差错控制编码技术 二、编码过程二

38、、编码过程 例例: 有一个线性分组码的（有一个线性分组码的（n，k）为（）为（7，3） 即即 C6 C5 C4 C3 C2 C1 C0 k r 第6章 差错控制编码技术 1、设已知确定监督位的线性方程为、设已知确定监督位的线性方程为 C3=C6+C4 C6+C4+C3=0 C2=C6+C5+C4 C6+C5+C4+C2=0 C1=C6+C5 C6+C5+C1=0 C0=C5+C4 C5+C4+C0=0 第6章 差错控制编码技术 2、根据线性方程可得出所有许用码组、根据线性方程可得出所有许用码组 C6 C5 C4 C3 C2 C1 C0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0

39、 1 0 0 1 1 1 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 1 0 0 第6章 差错控制编码技术 3、根据改写后的线性方程有下列矩阵关系、根据改写后的线性方程有下列矩阵关系 C6 1 0 1 1 0 0 0 C5 0 1 1 1 0 1 0 0 C4 = 0 1 1 0 0 0 1 0 C3 0 0 1 1 0 0 0 1 C2 0 C1 C0 第6章 差错控制编码技术 其中，令其中，令 1 0 1 1 0 0 0 P11 P12 P13P1k 1 0 1 H= 1 1 1 0 1 0 0 = P21

40、 P22 P23P2k 0 1 0 1 1 0 0 0 1 0 . 0 1 1 0 0 0 1 Pr1 Pr2 Pr3Prk 0 0 1 = P Ir 为监督矩阵为监督矩阵，其中，其中: 列数列数=n，行数，行数=k， P为为rk阶矩阵，阶矩阵，Ir为为r阶单位方阵阶单位方阵 第6章 差错控制编码技术 4、引入、引入Q矩阵：矩阵： 令令 Q=PT，或，或 P=QT（倒置矩阵）（倒置矩阵） 得出得出 G= Ik Q Ik k阶单位方阵阶单位方阵 G 生成矩阵生成矩阵 综上所述：只要找到了线性分组码的生成矩阵综上所述：只要找到了线性分组码的生成矩阵 G，编码的方法就完全确定了。，编码的方法就完全确

41、定了。 第6章 差错控制编码技术 【例题【例题1】已知一个（】已知一个（7，4）线性分组码的生成）线性分组码的生成 矩阵矩阵 1 2 3 4 1000110 0100011 0010111 0001101 g g G g g 求该信息码的监督矩阵，并列出所有许用码组。求该信息码的监督矩阵，并列出所有许用码组。 第6章 差错控制编码技术 解：因为解：因为 1 2 3 4 1000110 0100011 0010111 0001101 g g G g g = IkQ 1 1 0 1 0 1 1 则则 Q= 0 1 1 P=QT = 1 1 1 0 1 1 1 0 1 1 1 1 0 1 第6章 差

42、错控制编码技术 所以所以 1 0 1 1 1 0 0 C6+C4+C3+C2=0 H= P Ir = 1 1 1 0 0 1 0 C6+C5+C4+C1=0 0 1 1 1 0 0 1 C5+C4+C3+C0=0 即有线性方程组即有线性方程组 C2=C6+C4+C3 C1=C6+C5+C4 C0=C5+C4+C3 第6章 差错控制编码技术 根据线性方程组可到许用码组根据线性方程组可到许用码组 C6C5C4C3C2C1C0C6C5C4C3C2C1C0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 0 10 1 1 0 0 1 0 1 1 1 1 0

43、1 00 0 1 0 0 1 1 0 1 0 1 0 1 11 0 0 0 1 0 0 0 1 1 1 1 0 01 0 1 0 1 0 1 1 1 0 1 1 0 10 0 0 0 1 1 0 1 0 0 1 1 1 00 1 0 0 1 1 1 0 0 1 1 1 1 11 1 1 第6章 差错控制编码技术 从许用码组可看出其从许用码组可看出其dmin=3 因此其检错能力因此其检错能力 dmine+1 e dmin-1=2 纠错能力纠错能力 dmin2t+1 t(dmin-1)/2=1 第6章 差错控制编码技术 6.4.3 汉明码：汉明码： 要纠正（要纠正（n，k）线性分组码中的单个错误，

44、则监线性分组码中的单个错误，则监 督码元的个数督码元的个数r必须满足关系必须满足关系2n-k（n+1）。）。 当当2n-k=（n+1）时所得的线性编码就是汉明码。）时所得的线性编码就是汉明码。 可以由此推知汉明码的两个特性：可以由此推知汉明码的两个特性： （1）只要给定）只要给定r，就可确定线性分组码的码长，就可确定线性分组码的码长 n=2r-1及信息码元的个数及信息码元的个数k=n-r。 第6章 差错控制编码技术 （2）在信息码元长度相同、纠正单个错误线）在信息码元长度相同、纠正单个错误线 性分组码中，汉明码所用的监督码元个数性分组码中，汉明码所用的监督码元个数r最最 少，相对而言的编码效率

45、最高。少，相对而言的编码效率最高。 不难发现，无论码长不难发现，无论码长n为多少，汉明码的最为多少，汉明码的最 小码距小码距dmin=3，所以它只能纠正，所以它只能纠正1位错码。位错码。 第6章 差错控制编码技术 6.5 循循 环环 码码 CRC 一、循环码的概念一、循环码的概念 （1）循环码是线性分组码的一个重要分支，它）循环码是线性分组码的一个重要分支，它 具有较强的纠错能力，而且其编码和译码电路很容具有较强的纠错能力，而且其编码和译码电路很容 易用移位寄存器实现。易用移位寄存器实现。 （2）循环码是一种分组码，它除了具有线性分）循环码是一种分组码，它除了具有线性分 组码的封闭性之外，还具

46、有一个独特的性质即循环组码的封闭性之外，还具有一个独特的性质即循环 性。性。 第6章 差错控制编码技术 （3）循环码可定义为：对于一个（）循环码可定义为：对于一个（n，k）线性码）线性码C，若，若 其中的任一码组向左或向右循环移动任意位后仍是其中的任一码组向左或向右循环移动任意位后仍是C中的一中的一 个码组，则称个码组，则称C是一个循环码。是一个循环码。 如如c=c1，c2，cn是一个循环码组，对它左循环移是一个循环码组，对它左循环移 位一次，得到位一次，得到c（ （1）= c2，c3，cn，c1也是许用码组，也是许用码组， 移位移位i次得到次得到c(i)=ci+1，ci+2，cn，c1，ci

47、还是许用码组。还是许用码组。 不论右移或左移，移位位数多少，其结果均为循环码组。不论右移或左移，移位位数多少，其结果均为循环码组。 第6章 差错控制编码技术 二、循环码的生成多项式二、循环码的生成多项式 通过代数变换，可以得到循环码的表示式：通过代数变换，可以得到循环码的表示式： T(x)=m(x)g(x) 式中，式中， m(x)表示信息码元的代数多项式表示信息码元的代数多项式; g(x)称为循环码的生成多项式。称为循环码的生成多项式。 显然，生成的循环码多项式显然，生成的循环码多项式T(x)由其码组长度由其码组长度 n及生成多项式及生成多项式g(x)所决定，它是所决定，它是g(x)的倍式，即

48、凡的倍式，即凡 能被能被g(x)除尽，且次数不超过除尽，且次数不超过(n-1)的多项式，一定的多项式，一定 是是 这一组循环码的码多项式。这一组循环码的码多项式。 )()()(xgxmxc 第6章 差错控制编码技术 那么，如何确定生成多项式呢？数学分析发现，那么，如何确定生成多项式呢？数学分析发现， g(x)是一个能除尽是一个能除尽xn+1的的(n-k)阶多项式，所以，对阶多项式，所以，对 xn+1进行因式分解所得到的因式就是进行因式分解所得到的因式就是g(x) 。因此。因此 g(x)必须是一个常数项不为必须是一个常数项不为“0”的（的（n-k）次多项）次多项 式，而且，这个式，而且，这个g(

49、x)还是这种（还是这种（n，k）码中次数为）码中次数为 （n-k）的唯一的一个多项式。我们称这唯一的）的唯一的一个多项式。我们称这唯一的 （n-k）多项式）多项式g(x) 为码的生成多项式。一旦确定为码的生成多项式。一旦确定 了了g(x)，则整个（，则整个（n，k）循环码就被确定了。）循环码就被确定了。 第6章 差错控制编码技术 三、循环码的编码过程三、循环码的编码过程 (1) 将将k位信息位对应的码多项式位信息位对应的码多项式m(x)乘以乘以Xn-k， 得得y(x)； (2) 用用y(x)除以生成多项式除以生成多项式G(x) ，得余式，得余式r(x) ； (3) 将余式将余式r(x)对应的码

50、列出，即为其校验码对应的码列出，即为其校验码(监督监督 码码)； (4) 将信息码与监督码一起则构成循环码。将信息码与监督码一起则构成循环码。 第6章 差错控制编码技术 例例 有（有（7，3）线性码，设其生成多项式）线性码，设其生成多项式G(x)=X4+X3+X2+1， 试写出信息位为试写出信息位为101的循环码，并写出其全部码组。的循环码，并写出其全部码组。 解：解：（1）信息码为）信息码为101，所以，所以 m(x)=X2+1 Xn-k=Xr=X4，则，则 y(x)=X4 m(x)=X6+X4 （2）生成多项式）生成多项式 G(x)= X4+X3+X2+1 所以所以 y(x)/ G(x) =（X6+X4）/（ X4+X3+X2+1） =X2+X+1X+1(余式余式) 即即 r(x)= X+1，其对应的监督码为，其对应的监督码为0011 1010000 11101 第6章 差错控制编码技术 1 1 1 1 1 1 0 1 1 0 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 r(x) 第6