第11章差错控制编码课件讲义.ppt

1、第11章 差错控制编码 第第11章章 差错控制编码差错控制编码 11.1 概述概述 11.2 纠错编码的基本原理纠错编码的基本原理 11.3 纠错纠错编码的性能编码的性能11.4 简单的实用编码简单的实用编码 11.5 线性线性分组码分组码11.6 循环码循环码第11章 差错控制编码 11.1 概述概述 从差错角度看，按加性干扰引起的错码分布规律的从差错角度看，按加性干扰引起的错码分布规律的不同，信道可以分为三类：不同，信道可以分为三类：（1）随机信道：在此信道中错码的出现是随机的，且错）随机信道：在此信道中错码的出现是随机的，且错码之间是统计独立的。码之间是统计独立的。（2）突发信道：在此信

2、道中错码是成串集中出现的，）突发信道：在此信道中错码是成串集中出现的，（3）混合信道：既存在随机错码又存在突发错码，且哪）混合信道：既存在随机错码又存在突发错码，且哪一种都不能忽略不计的信道一种都不能忽略不计的信道 对于不同类型的信道，应采用不同的差错控制技术对于不同类型的信道，应采用不同的差错控制技术。第11章 差错控制编码 差错控制方法，常用差错控制方法，常用 的有以下几种的有以下几种（1）检错重发法（）检错重发法（ARQ）接收端在收到的信码接收端在收到的信码中检测出（发现）错码时，即设法通知发送端中检测出（发现）错码时，即设法通知发送端重发，直到正确收到为止。所谓检测出错码是重发，直到正

3、确收到为止。所谓检测出错码是指在若干接收码元中知道有一个或一些是错的，指在若干接收码元中知道有一个或一些是错的，但不一定知道该错码的准确位置。采用这种差但不一定知道该错码的准确位置。采用这种差错控制方法需要具备双向信道。错控制方法需要具备双向信道。第11章 差错控制编码（2）前向纠错法（）前向纠错法（FEC）接收端不仅能在收接收端不仅能在收到的信码中发现有错码，还能够纠正错码。对到的信码中发现有错码，还能够纠正错码。对于二进制系统，如果能够确定错码的集团，就于二进制系统，如果能够确定错码的集团，就能够纠正它。这种方法不需要么向信道，也不能够纠正它。这种方法不需要么向信道，也不存在由于反复重发而

4、延误时间，实时性好，但存在由于反复重发而延误时间，实时性好，但是纠错设备要比检错设备复杂。是纠错设备要比检错设备复杂。第11章 差错控制编码（3）反馈校验法（）反馈校验法（IF）接收端将收到的信码接收端将收到的信码原封不动地转发回发送端，并与原发送信码相原封不动地转发回发送端，并与原发送信码相比较。如果发现错误，则发送端再进行重发。比较。如果发现错误，则发送端再进行重发。这种方法原理和设备都较简单，但需要有双向这种方法原理和设备都较简单，但需要有双向信道。传输效率较低。信道。传输效率较低。第11章 差错控制编码(4)检错删除：它和检错重发的区别在于，在接收检错删除：它和检错重发的区别在于，在接

5、收端发现错码后，立即将其删除，不要求重发。端发现错码后，立即将其删除，不要求重发。这种方法只适用在少数特定系统中，在那里发这种方法只适用在少数特定系统中，在那里发送码元中有大量多余度，删除部分接收码元不送码元中有大量多余度，删除部分接收码元不影响应用。影响应用。第11章 差错控制编码 当出现少量错码并在接收端能够纠正时，即用当出现少量错码并在接收端能够纠正时，即用前向纠错法纠正；当错码较多而超过纠正能力但尚前向纠错法纠正；当错码较多而超过纠正能力但尚能检测时，就用检错重发法。此外，在某些特定场能检测时，就用检错重发法。此外，在某些特定场合，可采用检错删除法，即接收端将其中存在错误合，可采用检错

6、删除法，即接收端将其中存在错误的部分码元删除，不送给输出端。此法适用于信息的部分码元删除，不送给输出端。此法适用于信息内容有大量多余度或多次重复发送的场合。内容有大量多余度或多次重复发送的场合。第11章 差错控制编码 为使接收端能够识别接收到的信码有无错码。为使接收端能够识别接收到的信码有无错码。可以由发送端的信道编码器在信息码元序列中增可以由发送端的信道编码器在信息码元序列中增加一些监督码元。这些监督码元和信码之间有一加一些监督码元。这些监督码元和信码之间有一定的关系，使接收端可以利用这种关系由信道译定的关系，使接收端可以利用这种关系由信道译码器来发现或纠正可能存在的错码。码器来发现或纠正可

7、能存在的错码。第11章 差错控制编码 在信息码元序列中加入监督码元就称为差错在信息码元序列中加入监督码元就称为差错控制编码，也称为纠错编码。不同的编码方法，控制编码，也称为纠错编码。不同的编码方法，有不同的检错或纠错能力，有的编码只能检错，有不同的检错或纠错能力，有的编码只能检错，不能纠错。一般来说，编码中增加的监督码元越不能纠错。一般来说，编码中增加的监督码元越多，它检（纠）错的能力就越强，但它的编码效多，它检（纠）错的能力就越强，但它的编码效率（或传码率）也就越低。率（或传码率）也就越低。第11章 差错控制编码 可见，差错控制编码原则上是以降低信息可见，差错控制编码原则上是以降低信息传输速

8、率为代价来换取提高传输可靠性。传输速率为代价来换取提高传输可靠性。第11章 差错控制编码 第11章 差错控制编码 ARQ方式的主要优点是：方式的主要优点是：（1）只需要少量的多余码元就能获得极低的输出误码）只需要少量的多余码元就能获得极低的输出误码率；率；（2）要求使用的检错码基本上与信道的差错统计特性）要求使用的检错码基本上与信道的差错统计特性无关；无关；（3）其检错译码器与前向纠错法中的纠错译码器相比，）其检错译码器与前向纠错法中的纠错译码器相比，成本和复杂性均低得多。成本和复杂性均低得多。第11章 差错控制编码 但其缺点是：但其缺点是：（1）由于需要反向信道，故不能用于单向传输系统，）由

9、于需要反向信道，故不能用于单向传输系统，并且实现实现重发控制比较复杂；并且实现实现重发控制比较复杂；（2）当信道干扰增大时，整个系统可能处在重发循）当信道干扰增大时，整个系统可能处在重发循环中，因而通信效率降低，甚至不能通信；环中，因而通信效率降低，甚至不能通信；（3）不大适于要求严格实时传输的系统。）不大适于要求严格实时传输的系统。第11章 差错控制编码 11.2 纠错编码的基本原理纠错编码的基本原理 在讨论检错和纠错问题之前，我们先介绍一在讨论检错和纠错问题之前，我们先介绍一下数字通信中码元的两种错误形式：随机错误下数字通信中码元的两种错误形式：随机错误和突发错误。和突发错误。(1)随机错

10、误。由随机噪声引起的码元错误，随机错误。由随机噪声引起的码元错误，其特点是码元中任意一位或几位发生从其特点是码元中任意一位或几位发生从0变变1或或从从1变变0的错误是相互独立的，彼此之间没有联的错误是相互独立的，彼此之间没有联系，一般不会引起成片的码元错误。系，一般不会引起成片的码元错误。第11章 差错控制编码 (2)突发错误。由突发噪声引起的码元错误，突发错误。由突发噪声引起的码元错误，比如，闪电、电器开关的瞬态、磁带缺陷等都属比如，闪电、电器开关的瞬态、磁带缺陷等都属于突发噪声。该错误的特点是各错误码元之间存于突发噪声。该错误的特点是各错误码元之间存在相关性，因此是成片出现，也就是说突发错

11、误在相关性，因此是成片出现，也就是说突发错误是一个错误序列，该序列的首部和尾部码元都是是一个错误序列，该序列的首部和尾部码元都是错的，中间的码元有错的也有对的，但错的码元错的，中间的码元有错的也有对的，但错的码元相对较多，错误序列的长度（包括首和尾在内的相对较多，错误序列的长度（包括首和尾在内的错误所波及的段落长度）称为突发长度。错误所波及的段落长度）称为突发长度。第11章 差错控制编码 假设要发送一组具有八个状态的数据信息假设要发送一组具有八个状态的数据信息“000”（晴），（晴），“001”（云），（云），“010”（阴），（阴），“011”（雨），（雨），“100”（雪），（雪），“10

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

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

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

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

16、1或或011；如果；如果3位都错，原码就位都错，原码就是是110，我们现在无法判断出原码到底是哪一组。，我们现在无法判断出原码到底是哪一组。也就是说，通过增加也就是说，通过增加1位监督码元，我们可以检出位监督码元，我们可以检出1位或位或3位错误（位错误（3位出错的概率极小），但无法纠正位出错的概率极小），但无法纠正错误。错误。第11章 差错控制编码 要想纠正错误，还要增加多余度。即通过增加要想纠正错误，还要增加多余度。即通过增加监督码元的位数来增加检错位数或实现纠错功能。监督码元的位数来增加检错位数或实现纠错功能。如规定许用码组只有两个：如规定许用码组只有两个：“000”（晴）、（晴）、“11

17、1”（雨），其它都是禁用码组，则能够检测两个以上（雨），其它都是禁用码组，则能够检测两个以上错码，或能够纠正一个错码。错码，或能够纠正一个错码。第11章 差错控制编码 可见，简单地增加可见，简单地增加1位监督码元并没有提位监督码元并没有提高检错与纠错能力，那么，检错与纠错能力到高检错与纠错能力，那么，检错与纠错能力到底与什么有关呢？底与什么有关呢？在回答这个问题之前，我们先介绍分组码在回答这个问题之前，我们先介绍分组码的概念：将信息码分组，为每组信码附加若干的概念：将信息码分组，为每组信码附加若干监督码的编码方式称为分组码。在分组码中，监督码的编码方式称为分组码。在分组码中，监督码元仅监督本码

18、组中的信息码元。监督码元仅监督本码组中的信息码元。第11章 差错控制编码 第11章 差错控制编码 分组码一般用符号（分组码一般用符号（n，k）表示，若中）表示，若中n是是码组的总位数，又称为码组的长度（码长），码组的总位数，又称为码组的长度（码长），k是码组中信息码元的数目，是码组中信息码元的数目，n-k=r为码组中的监为码组中的监督码元数目，或称监督位数目。督码元数目，或称监督位数目。在分组码中，把码组中在分组码中，把码组中“1”的个数称为码组的个数称为码组的重量，简称码重。把两个码组中对应位上数字的重量，简称码重。把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又不同的位数

19、称为码组的距离，简称码距。码距又称汉明距离。称汉明距离。第11章 差错控制编码 码距反映的是码组之间的差异程度，比如，码距反映的是码组之间的差异程度，比如，00和和01两组码的码距为两组码的码距为1；011和和100的码距为的码距为3。那么，多个码组之间相互比较，可能会有不同的那么，多个码组之间相互比较，可能会有不同的码距，其中的最小值被称为最小码距（用码距，其中的最小值被称为最小码距（用d0表表示）。比如，示）。比如，000、001、110三个码组相比较，码三个码组相比较，码距有距有1和和2两个值，则最小码距为两个值，则最小码距为1。第11章 差错控制编码 第11章 差错控制编码 根据理论推

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

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

22、 差错控制编码 11.3 纠错编码的性能纠错编码的性能 由纠错编码原理可知由纠错编码原理可知:（1）为减少接收错误码元数量，需要在发送信息码）为减少接收错误码元数量，需要在发送信息码元序列中加入监督码元。元序列中加入监督码元。结果使发送序列增长，结果使发送序列增长，冗余度增大。冗余度增大。（2）若仍须介质发送信息码元速率不变，则传输速）若仍须介质发送信息码元速率不变，则传输速率必须增大。率必须增大。结果增大了系统带宽。结果增大了系统带宽。（3）系统带宽的增大将引起系统中噪声功率增大，）系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。使信噪比下降。结果使系统接收码元序列中的结果使系统接收码

23、元序列中的错码增多错码增多。第11章 差错控制编码 一般说来，采用纠错编码后，误码率总是一般说来，采用纠错编码后，误码率总是能够得到很大改善的，改善的程度和所用的编能够得到很大改善的，改善的程度和所用的编码有关。码有关。第11章 差错控制编码 第11章 差错控制编码 上面两种情况付出的代价是带宽增大。上面两种情况付出的代价是带宽增大。对于给定的传输系统，其传输速率和对于给定的传输系统，其传输速率和Eb/n0的关的关系为系为式中：式中：RB为码元速率。为码元速率。第11章 差错控制编码 11.4 简单的实用编码简单的实用编码 1.奇偶监督码奇偶监督码 奇偶监督码是数据通信中最常见的一种简奇偶监督

24、码是数据通信中最常见的一种简单检错码，其编码规则是：把信息码先分组，单检错码，其编码规则是：把信息码先分组，形成多个许用码组，在每一个许用码组最后形成多个许用码组，在每一个许用码组最后（最低位）加上一位监督码元即可。加上监督（最低位）加上一位监督码元即可。加上监督码元后使该码组中码元后使该码组中1的数目为奇数的编码称为的数目为奇数的编码称为奇数监督码，为偶数的编码称为偶数监督码。奇数监督码，为偶数的编码称为偶数监督码。第11章 差错控制编码 假设一个码组的长度为假设一个码组的长度为n，表示为（，表示为（an-1an-2an-3:a0），其中前），其中前n-1位是信息码，最后一位位是信息码，最后

25、一位a0为监为监督位，那么，督位，那么，对于偶数监督码必对于偶数监督码必须保证须保证 12300nnnaaaa监督码元监督码元a0的取值（的取值（0或或1）可由下式决定：）可由下式决定：01231nnnaaaaa第11章 差错控制编码 对于奇数监督码必须保证对于奇数监督码必须保证 12301nnnaaaa监督码元监督码元a0的取值（的取值（0或或1）可由下式决定：）可由下式决定：012311nnnaaaaa第11章 差错控制编码 根据奇偶监督码的规则我们可以看到，当码根据奇偶监督码的规则我们可以看到，当码组中的误码为偶数时，校验失效。比如有两位发组中的误码为偶数时，校验失效。比如有两位发生错误

26、，会有这样几种情况：生错误，会有这样几种情况：00变成变成11、11变成变成00、01变成变成10、10变成变成01，可见无论哪种情况出，可见无论哪种情况出现都不会改变码组的奇偶性，偶数监督码中现都不会改变码组的奇偶性，偶数监督码中1的的个数仍为偶数，奇数监督码中个数仍为偶数，奇数监督码中1的个数仍为奇数。的个数仍为奇数。因此，简单的奇偶监督码只能检测出奇数个位发因此，简单的奇偶监督码只能检测出奇数个位发生错误的码组。生错误的码组。第11章 差错控制编码 2.二维奇偶监督码二维奇偶监督码 二维奇偶监督码又称方阵码。二维奇偶监督码又称方阵码。二维奇偶校验码比一维奇偶校验码多了个二维奇偶校验码比一

27、维奇偶校验码多了个列校验，因此，其检错能力有所提高。除了检列校验，因此，其检错能力有所提高。除了检出行中的所有奇数个误码及长度不大于行数的出行中的所有奇数个误码及长度不大于行数的突发性错误外，还可检出列中的所有奇突发性错误外，还可检出列中的所有奇数个误数个误码及长度不大于列数的突发性错误。码及长度不大于列数的突发性错误。前述的一前述的一维奇偶监督码一般只适于检测随机错误。维奇偶监督码一般只适于检测随机错误。第11章 差错控制编码 二维奇偶监督码不仅可用来检错，还可用来二维奇偶监督码不仅可用来检错，还可用来纠正一些错码。例如，当码组中仅在一行中有奇纠正一些错码。例如，当码组中仅在一行中有奇数个错

28、误时，则能够确定错码位置，从而纠正它。数个错误时，则能够确定错码位置，从而纠正它。第11章 差错控制编码 第11章 差错控制编码 表表1 二维偶监督码二维偶监督码 第11章 差错控制编码 3.恒比码恒比码 恒比码的编码原则是从确定码长的码组中挑选那恒比码的编码原则是从确定码长的码组中挑选那些些“1”和和“0”个数的比值一样的码组作为许用码组。个数的比值一样的码组作为许用码组。这种码通过计算接收码组中这种码通过计算接收码组中“1”的数目是否正确，的数目是否正确，就可检测出有无错误。表就可检测出有无错误。表2是我国邮电部门在国内通信是我国邮电部门在国内通信中采用的五单位数字保护电码，它是一种五中取

29、三的中采用的五单位数字保护电码，它是一种五中取三的恒比码。恒比码。第11章 差错控制编码 不难看出这种码的最小码距是不难看出这种码的最小码距是2，它能够检出，它能够检出码组中所有奇数个错误和部分偶数个错误。该码码组中所有奇数个错误和部分偶数个错误。该码也是非线性分组码，但不是系统码，其主要优点也是非线性分组码，但不是系统码，其主要优点是简单，适用于对电传机或其它键盘是简单，适用于对电传机或其它键盘设备产生的设备产生的字母和符号进行编码。字母和符号进行编码。第11章 差错控制编码 每个码组的长度为每个码组的长度为5，其中，其中“1”的个数为的个数为3，每个许用码组中每个许用码组中“1”和和“0”

30、个数的比值恒为个数的比值恒为3/2。许用码组的个数就是许用码组的个数就是5中取中取3的组合数，即的组合数，即 C+3-5=5!/(3!2!)=10，正好可以表示，正好可以表示10个阿拉个阿拉伯数字。伯数字。第11章 差错控制编码 表表2 五单位保护电码表五单位保护电码表 第11章 差错控制编码 4.正反码正反码 正反码是一种简单的纠正错码的编码。其中正反码是一种简单的纠正错码的编码。其中的监督位数目与信息位数目相同，监督码元与信的监督位数目与信息位数目相同，监督码元与信息码元相（信息码元的重复）或者相反（是信息息码元相（信息码元的重复）或者相反（是信息码的反码），则由信息码中码的反码），则由信

31、息码中“1”的个数而定。的个数而定。如电报通信用的正反码的码长如电报通信用的正反码的码长n=10，其中信，其中信息位息位k=5，监督位，监督位r=5。其编码规则为。其编码规则为：第11章 差错控制编码（1）当信息位中有奇数个）当信息位中有奇数个“1”时，监督位是信时，监督位是信息位的简单重复；息位的简单重复；（2）当信息位有偶数个）当信息位有偶数个“1”时，监督位是信息时，监督位是信息位的反码。位的反码。第11章 差错控制编码 接收端解码的方法为：先将接收码组中信息接收端解码的方法为：先将接收码组中信息位和监督位按位模位和监督位按位模2相加，得到一个相加，得到一个5位的合成码位的合成码组，然后

32、，由此合成码组产生一校验码组。若接组，然后，由此合成码组产生一校验码组。若接收码组的信息位中有奇数个收码组的信息位中有奇数个“1”，则合成码组就，则合成码组就是校验码组；若接收码组的信息位中有偶数个是校验码组；若接收码组的信息位中有偶数个“1”，则取合成码组的反码作为校验码组。最后，则取合成码组的反码作为校验码组。最后，观察校验码组中观察校验码组中“1”的个数，按表的个数，按表3进行判决及进行判决及纠正可能发现的错码。纠正可能发现的错码。第11章 差错控制编码 第11章 差错控制编码 11.5 线性分组码线性分组码 一、线性分组码定义：一、线性分组码定义：信息码元与监督码元之间可以用一组线性方

33、程信息码元与监督码元之间可以用一组线性方程来表示，且监督码元仅由本码组的信息码元确定。来表示，且监督码元仅由本码组的信息码元确定。二、线性分组码的表示：二、线性分组码的表示：（n，k），），监督位监督位 r=n-k 其编码效率其编码效率 =k/n第11章 差错控制编码 三、线性分组码的性质：三、线性分组码的性质：（1）封闭性，即任意两个许用码组之模）封闭性，即任意两个许用码组之模2和仍为一许和仍为一许用码组；用码组；（2）码组的最小码）码组的最小码d0距等于非零码的最小码重。距等于非零码的最小码重。设有一（设有一（n，k）线性分组码，即）线性分组码，即c1、c2、cn，其中信息码组为其中信息码

34、组为d1、d2、dk，分组码码组系统格，分组码码组系统格式见下图。具有这种结构的线性分组码又叫做线性式见下图。具有这种结构的线性分组码又叫做线性分组系统码。分组系统码。第11章 差错控制编码 四、汉明码：四、汉明码：要纠正（要纠正（n，k）线性分组码中的单个错误，则线性分组码中的单个错误，则监督码元的个数监督码元的个数r必须满足关系必须满足关系2n-k（n+1）。当当2n-k=（n+1）时所得的线性编码就是汉明码。可以由时所得的线性编码就是汉明码。可以由此推知汉明码的两个特性：此推知汉明码的两个特性：（1）只要给定）只要给定r，就可确定线性分组码的码长，就可确定线性分组码的码长n=2r-1及及

35、信息码元的个数信息码元的个数k=n-r。第11章 差错控制编码（2）在信息码元长度相同、纠正单个错误线性）在信息码元长度相同、纠正单个错误线性分组码中，汉明码所用的监督码元个数分组码中，汉明码所用的监督码元个数r最少，最少，相对而言的编码效率最高。相对而言的编码效率最高。不难发现，无论码长不难发现，无论码长n为多少，汉明码的为多少，汉明码的最小码距最小码距d0=3，所以它只能纠正，所以它只能纠正1位错码。位错码。第11章 差错控制编码 五、编码要求：五、编码要求：从已知的从已知的k个信息码元中求出满足要求的个信息码元中求出满足要求的r=n-k个监督码元（校验码），然后附在信息码元之后个监督码元

36、（校验码），然后附在信息码元之后构成个码组。构成个码组。第11章 差错控制编码 六、编码过程：六、编码过程：例例 有一个线性分组码的（有一个线性分组码的（n，k）为（）为（7，3）即即 C6 C5 C4 C3 C2 C1 C0 k r 第11章 差错控制编码 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第11章 差错控制编码 2、根据线性方程可得出所有许用码组、根据线性方程可得出所有许用码组 C6 C5 C

37、4 C3 C2 C1 C0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 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第11章 差错控制编码 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第11章 差错控制编码 其中，令其中，令 1 0 1 1 0 0 0 P11 P

38、12 P13P1K 1 0 1 H=1 1 1 0 1 0 0 =P21 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阶单位方阵阶单位方阵第11章 差错控制编码 4、引入、引入Q矩阵：矩阵：令令 Q=PT，或，或 P=QT（倒置矩阵）（倒置矩阵）得出得出 G=Ik Q Ik k阶单位方阵阶单位方阵 G 生成矩阵生成矩阵综上所述：只要找到了线性分组码的生成矩阵综上所述：只要找到了线性分组码的生成矩

39、阵G，编码的方法就完全确定了。编码的方法就完全确定了。第11章 差错控制编码【例题【例题1】已知一个（】已知一个（7，4）线性分组码的生成）线性分组码的生成矩阵矩阵12341000110010001100101110001101ggGgg求该信息码的监督矩阵，并列出所有许用码组。求该信息码的监督矩阵，并列出所有许用码组。第11章 差错控制编码 解：因为解：因为 12341000110010001100101110001101ggGgg =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第11章 差错控制编码 所以所以 1

40、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+C3C1=C6+C5+C4C0=C5+C4+C3第11章 差错控制编码 根据线性方程组可到许用码组根据线性方程组可到许用码组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 1 00 0 1 0 0 1 1 0 1 0

41、 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第11章 差错控制编码 从许用码组可看出其从许用码组可看出其d0=3 因此其检错能力因此其检错能力 d0e+1 e d0-1=2 纠错能力纠错能力 d02t+1 t(d0-1)/2=1 第11章 差错控制编码 设设 A为发送码组，它是一为发送码组，它是一n列的行矩阵。列的行矩阵。B为接收码组，且是一为接收码组，且是一n列的行矩阵，即列的行矩阵，即 B=bn

42、-1bn-2b0 则发送码组和接收码组之差为则发送码组和接收码组之差为 B A=E (模模2)它就是传输中产生的错码行矩阵它就是传输中产生的错码行矩阵 E=en-1en-2e0 其中其中 ei=0，当，当 bi=ai （表示接收码元无错）（表示接收码元无错）1，当，当 biai （表示接收码元有错）（表示接收码元有错）第11章 差错控制编码 11.6 循循 环环 码码 一、循环码的概念：一、循环码的概念：（1）循环码是线性分组码的一个重要分支，它具循环码是线性分组码的一个重要分支，它具有较强的纠错能力，而且其编码和译码电路很容有较强的纠错能力，而且其编码和译码电路很容易用移位寄存器实现。易用移

43、位寄存器实现。（2）循环码是一种分组码，它除了具有线性分组码）循环码是一种分组码，它除了具有线性分组码的封闭性之外，还具有一个独特的性质即循环性的封闭性之外，还具有一个独特的性质即循环性。第11章 差错控制编码（3）循环码可定义为：对于一个（）循环码可定义为：对于一个（n，k）线性码）线性码C，若其中，若其中的任一码组向左或向右循环移动任意位后仍是的任一码组向左或向右循环移动任意位后仍是C中的一个中的一个码组，则称码组，则称C是一个循环码。是一个循环码。如如c=c1，c2，cn是一个循环码组，对它左循环是一个循环码组，对它左循环移位一次，得到移位一次，得到c（1）=c2，c3，cn，c1也是许

44、用码也是许用码组，移位组，移位i次得到次得到c(i)=ci+1，ci+2，cn，c1，ci还是许还是许用码组。不论右移或左移，移位位数多少，其结果均为循用码组。不论右移或左移，移位位数多少，其结果均为循环码组。环码组。第11章 差错控制编码 在代数编码理论中，可以把循环码组中各码元在代数编码理论中，可以把循环码组中各码元当作一个多项式的系数，即把一个长为当作一个多项式的系数，即把一个长为n的码组的码组表示为表示为 c(x)=c1xn-1+c2xn-2+cn第11章 差错控制编码 式中，式中，c(x)称为码多项式，变量称为码多项式，变量x称为元素，称为元素，其幂次对应元素的位置，它的系数即为元素

45、的其幂次对应元素的位置，它的系数即为元素的取值（我们不关心取值（我们不关心x本身的取值），系数之间本身的取值），系数之间的加法和乘法仍服从模的加法和乘法仍服从模2规则。比如一个（规则。比如一个（7，3）循环码（见表）循环码（见表11-6）中第）中第7个码组为个码组为（1100101），则该码组可表示为），则该码组可表示为 c7(x)=1x6+1x5+0 x4+0 x3+1x2+0 x+1 =x6+x5+x2+1第11章 差错控制编码 表表115 一种（一种（7，3）循环码的全部码组）循环码的全部码组 第11章 差错控制编码 二、循环码的生成多项式二、循环码的生成多项式通过代数变换，可以得到循环

46、码的表示式：通过代数变换，可以得到循环码的表示式：T(x)=m(x)g(x)式中，式中，m(x)表示信息码元的代数多项式表示信息码元的代数多项式;g(x)称为循环码的生成多项式。称为循环码的生成多项式。显然，生成的循环码的多项式显然，生成的循环码的多项式T(x)由其码组长度由其码组长度 n及及生成多项式生成多项式g(x)所决定，它是所决定，它是g(x)的倍式，即凡能的倍式，即凡能被被g(x)除尽，且次数不超过除尽，且次数不超过(n-1)的多项式，一定的多项式，一定是这一组循环码的码多项式。是这一组循环码的码多项式。)()()(xgxmxc 第11章 差错控制编码 那么，如何确定生成多项式呢？数

47、学分析发现，那么，如何确定生成多项式呢？数学分析发现，g(x)是一个能除尽是一个能除尽xn+1的的(n-k)阶多项式，所以，对阶多项式，所以，对xn+1进行因式分解所得到的因式就是进行因式分解所得到的因式就是g(x)。因此。因此g(x)必须是一个常数项不为必须是一个常数项不为“0”的（的（n-k）次多项）次多项式，而且，这个式，而且，这个g(x)还是这种（还是这种（n，k）码中次数为）码中次数为（n-k）的唯一的一个多项式。我们称这唯一的）的唯一的一个多项式。我们称这唯一的（n-k）多项式）多项式g(x)为码的生成多项式。一旦确定为码的生成多项式。一旦确定了了g(x)，则整个（，则整个（n，k

48、）循环码就被确定了。）循环码就被确定了。第11章 差错控制编码 三、循环码的编码过程：三、循环码的编码过程：(1)将将k位信息位对应的码多项式位信息位对应的码多项式m(x)乘以乘以Xn-k，得，得y(x)；(2)用用y(t)除以生成多项式除以生成多项式G(x)，得余式，得余式r(x)；(3)将余式将余式r(x)对应的码列出，即为其校验码对应的码列出，即为其校验码(监督码监督码)；(4)将信息码与监督码一起则构成循环码。将信息码与监督码一起则构成循环码。第11章 差错控制编码 例例 有（有（7，3）线性码，设其生成多项式）线性码，设其生成多项式G(x)=X4+X3+X2+1，试写出信息位为，试写

49、出信息位为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第11章 差错控制编码（4）这样信息码）这样信息码101对应的循环码为对应的循环码为1010011；（5）则其全部码组）则其全部码组 0 0 0 0 0 0

50、0 1 0 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1第11章 差错控制编码（6）数据在传输过程中，若没有发生差错，则接收端收）数据在传输过程中，若没有发生差错，则接收端收到的循环码序列一定能被同一生成多项式整除。到的循环码序列一定能被同一生成多项式整除。例例 循环码循环码1010011对应的多项式为对应的多项式为X6+X4+X+1 生成多项式生成多项式G(x)=X4+X3+X2+1则（则（X6+X4+X+1）/（X4+X3+X2+1）=X2+X+10