差错控制编码_1 (2)课件

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

1、第11章 差错控制编码,11.1 概述 11.2 纠错编码的基本原理 11.3 纠错编码的性能 11.4 简单的实用编码 11.5 线性分组码 11.6 循环码,11.1 概述,从差错角度看，按加性干扰引起的错码分布规律的不同，信道可以分为三类： （1）随机信道：在此信道中错码的出现是随机的，且错码之间是统计独立的。 （2）突发信道：在此信道中错码是成串集中出现的， （3）混合信道：既存在随机错码又存在突发错码，且哪一种都不能忽略不计的信道 对于不同类型的信道，应采用不同的差错控制技术。,差错控制方法，常用 的有以下几种 （1）检错重发法（ARQ） 接收端在收到的信码中检测出（发现）错码时，即

2、设法通知发送端重发，直到正确收到为止。所谓检测出错码是指在若干接收码元中知道有一个或一些是错的，但不一定知道该错码的准确位置。采用这种差错控制方法需要具备双向信道。,（2）前向纠错法（FEC） 接收端不仅能在收到的信码中发现有错码，还能够纠正错码。对于二进制系统，如果能够确定错码的集团，就能够纠正它。这种方法不需要么向信道，也不存在由于反复重发而延误时间，实时性好，但是纠错设备要比检错设备复杂。,（3）反馈校验法（IF） 接收端将收到的信码原封不动地转发回发送端，并与原发送信码相比较。如果发现错误，则发送端再进行重发。这种方法原理和设备都较简单，但需要有双向信道。传输效率较低。,(4)检错删除

3、：它和检错重发的区别在于，在接收端发现错码后，立即将其删除，不要求重发。这种方法只适用在少数特定系统中，在那里发送码元中有大量多余度，删除部分接收码元不影响应用。,当出现少量错码并在接收端能够纠正时，即用前向纠错法纠正；当错码较多而超过纠正能力但尚能检测时，就用检错重发法。此外，在某些特定场合，可采用检错删除法，即接收端将其中存在错误的部分码元删除，不送给输出端。此法适用于信息内容有大量多余度或多次重复发送的场合。,为使接收端能够识别接收到的信码有无错码。可以由发送端的信道编码器在信息码元序列中增加一些监督码元。这些监督码元和信码之间有一定的关系，使接收端可以利用这种关系由信道译码器来发现或纠

4、正可能存在的错码。,在信息码元序列中加入监督码元就称为差错控制编码，也称为纠错编码。不同的编码方法，有不同的检错或纠错能力，有的编码只能检错，不能纠错。一般来说，编码中增加的监督码元越多，它检（纠）错的能力就越强，但它的编码效率（或传码率）也就越低。,可见，差错控制编码原则上是以降低信息传输速率为代价来换取提高传输可靠性。,ARQ方式的主要优点是： （1）只需要少量的多余码元就能获得极低的输出误码率； （2）要求使用的检错码基本上与信道的差错统计特性无关； （3）其检错译码器与前向纠错法中的纠错译码器相比，成本和复杂性均低得多。,但其缺点是： （1）由于需要反向信道，故不能用于单向传输系统，并

5、且实现实现重发控制比较复杂； （2）当信道干扰增大时，整个系统可能处在重发循环中，因而通信效率降低，甚至不能通信； （3）不大适于要求严格实时传输的系统。,11.2 纠错编码的基本原理,在讨论检错和纠错问题之前，我们先介绍一下数字通信中码元的两种错误形式：随机错误和突发错误。 (1)随机错误。由随机噪声引起的码元错误，其特点是码元中任意一位或几位发生从0变1或从1变0的错误是相互独立的，彼此之间没有联系，一般不会引起成片的码元错误。,(2)突发错误。由突发噪声引起的码元错误，比如，闪电、电器开关的瞬态、磁带缺陷等都属于突发噪声。该错误的特点是各错误码元之间存在相关性，因此是成片出现，也就是说突

6、发错误是一个错误序列，该序列的首部和尾部码元都是错的，中间的码元有错的也有对的，但错的码元相对较多，错误序列的长度（包括首和尾在内的错误所波及的段落长度）称为突发长度。,假设要发送一组具有八个状态的数据信息“000”（晴），“001”（云），“010”（阴），“011”（雨），“100”（雪），“101”（霜），“110”（雾），“111”（雹）。我们首先要用二进制码对数据信息进行编码，显然，用3位二进制码就可完成。但任一码组在传输中若发生一个或多个错码，则将变成另一信息码组。这时，接收端将无法发现错误。,因此，以这种编码形式得到的数字信号在传输过程中不具备检错和纠错的能力，这是我们所不希望的

7、。但若在上述8种码组中只准许使用4种来传送信息，如：“000”（晴），“011”（云），“101”（阴），“110”（雨），这时，虽然只能传送4种不同的信息，但是接收端却有可能发现码组中的一个错码。,在许用码组000、011、101、110中，右边加上的1位码元就是监督码元，它的加入原则是使码组中1的个数为偶数，这样监督码元就和前面2位信息码元发生了关系，这种编码方式称为偶校验，反之，如果加入原则是使码组中1的个数为奇数，则编码方式称为奇校验。现在我们再看一下出现误码的情况，假设许用码组000出现1位误码，即变成001、010或100三个码组中的一个，可见这三个码组中1的个数都是奇数，是禁用码

8、组。,信息位和监督位关系,因此，当收信端收到这三个码组中的任何一个时，就知道是误码，用这种方法可以发现1位或3位出现错误的码组，而无法检出2位错误，因为一个码组出现2位错误，其奇偶性不变。那么，收信端能否从误码中判断哪一位发生错误了呢（即纠正错误）？比如对误码001而言，如果是1位发生错误，原码可能是000、101或011；如果3位都错，原码就是110，我们现在无法判断出原码到底是哪一组。也就是说，通过增加1位监督码元，我们可以检出1位或3位错误（3位出错的概率极小），但无法纠正错误。,要想纠正错误，还要增加多余度。即通过增加监督码元的位数来增加检错位数或实现纠错功能。如规定许用码组只有两个：

9、“000”（晴）、“111”（雨），其它都是禁用码组，则能够检测两个以上错码，或能够纠正一个错码。,可见，简单地增加1位监督码元并没有提高检错与纠错能力，那么，检错与纠错能力到底与什么有关呢？ 在回答这个问题之前，我们先介绍分组码的概念：将信息码分组，为每组信码附加若干监督码的编码方式称为分组码。在分组码中，监督码元仅监督本码组中的信息码元。,分组码一般用符号（n，k）表示，若中n是码组的总位数，又称为码组的长度（码长），k是码组中信息码元的数目，n-k=r为码组中的监督码元数目，或称监督位数目。 在分组码中，把码组中“1”的个数称为码组的重量，简称码重。把两个码组中对应位上数字不同的位数称为

10、码组的距离，简称码距。码距又称汉明距离。,码距反映的是码组之间的差异程度，比如，00和01两组码的码距为1；011和100的码距为3。那么，多个码组之间相互比较，可能会有不同的码距，其中的最小值被称为最小码距（用d0表示）。比如，000、001、110三个码组相比较，码距有1和2两个值，则最小码距为1。,根据理论推导，可以得出以下结论： (1)在一个码组内要想检出e位误码，要求最小码距为 d0e+1 (2)在一个码组内要想纠正t位误码，要求最小码距为 d02t+1 (3)在一个码组内要想纠正t位误码，同时检测出e位误码（et）,要求最小码距为 d0t+e+1 （et）,显然，要提高编码的纠、检

11、错能力，不能仅靠简单地增加监督码元位数（即冗余度），更重要的是要加大最小码距（即码组之间的差异程度），而最小码距的大小与编码的冗余度是有关的，最小码距增大，码元的冗余度就增大，但码元的冗余度增大，最小码距不一定增大。因此，一种编码方式具有检错和纠错能力的必要条件是信息编码必须有冗余，而充分条件是码元之间要有一定的码距。,11.3 纠错编码的性能,由纠错编码原理可知: （1）为减少接收错误码元数量，需要在发送信息码元序列中加入监督码元。 结果使发送序列增长，冗余度增大。 （2）若仍须介质发送信息码元速率不变，则传输速率必须增大。 结果增大了系统带宽。 （3）系统带宽的增大将引起系统中噪声功率增大

12、，使信噪比下降。 结果使系统接收码元序列中的错码增多。,一般说来，采用纠错编码后，误码率总是能够得到很大改善的，改善的程度和所用的编码有关。,上面两种情况付出的代价是带宽增大。 对于给定的传输系统，其传输速率和Eb/n0的关系为 式中：RB为码元速率。,11.4 简单的实用编码,1. 奇偶监督码 奇偶监督码是数据通信中最常见的一种简单检错码，其编码规则是：把信息码先分组，形成多个许用码组，在每一个许用码组最后（最低位）加上一位监督码元即可。加上监督码元后使该码组中1的数目为奇数的编码称为奇数监督码，为偶数的编码称为偶数监督码。,假设一个码组的长度为n，表示为（an-1an-2an-3:a0），

13、其中前n-1位是信息码，最后一位a0为监督位，那么， 对于偶数监督码必须保证,监督码元a0的取值（0或1）可由下式决定：,对于奇数监督码必须保证,监督码元a0的取值（0或1）可由下式决定：,根据奇偶监督码的规则我们可以看到，当码组中的误码为偶数时，校验失效。比如有两位发生错误，会有这样几种情况：00变成11、11变成00、01变成10、10变成01，可见无论哪种情况出现都不会改变码组的奇偶性，偶数监督码中1的个数仍为偶数，奇数监督码中1的个数仍为奇数。因此，简单的奇偶监督码只能检测出奇数个位发生错误的码组。,2. 二维奇偶监督码 二维奇偶监督码又称方阵码。 二维奇偶校验码比一维奇偶校验码多了个

14、列校验，因此，其检错能力有所提高。除了检出行中的所有奇数个误码及长度不大于行数的突发性错误外，还可检出列中的所有奇数个误码及长度不大于列数的突发性错误。 前述的一维奇偶监督码一般只适于检测随机错误。,二维奇偶监督码不仅可用来检错，还可用来纠正一些错码。例如，当码组中仅在一行中有奇数个错误时，则能够确定错码位置，从而纠正它。,表1 二维偶监督码,3. 恒比码 恒比码的编码原则是从确定码长的码组中挑选那些“1”和“0”个数的比值一样的码组作为许用码组。 这种码通过计算接收码组中“1”的数目是否正确，就可检测出有无错误。表2是我国邮电部门在国内通信中采用的五单位数字保护电码，它是一种五中取三的恒比码

15、。,不难看出这种码的最小码距是2，它能够检出码组中所有奇数个错误和部分偶数个错误。该码也是非线性分组码，但不是系统码，其主要优点是简单，适用于对电传机或其它键盘设备产生的字母和符号进行编码。,每个码组的长度为5，其中“1”的个数为3，每个许用码组中“1”和“0”个数的比值恒为3/2。许用码组的个数就是5中取3的组合数，即 C+3-5=5! /(3!2!)=10，正好可以表示10个阿拉伯数字。,表2 五单位保护电码表,4.正反码 正反码是一种简单的纠正错码的编码。其中的监督位数目与信息位数目相同，监督码元与信息码元相（信息码元的重复）或者相反（是信息码的反码），则由信息码中“1”的个数而定。 如

16、电报通信用的正反码的码长n=10，其中信息位k=5，监督位r=5。其编码规则为：,（1）当信息位中有奇数个“1”时，监督位是信息位的简单重复； （2）当信息位有偶数个“1”时，监督位是信息位的反码。,接收端解码的方法为：先将接收码组中信息位和监督位按位模2相加，得到一个5位的合成码组，然后，由此合成码组产生一校验码组。若接收码组的信息位中有奇数个“1”，则合成码组就是校验码组；若接收码组的信息位中有偶数个“1”，则取合成码组的反码作为校验码组。最后，观察校验码组中“1”的个数，按表3进行判决及纠正可能发现的错码。,11.5 线性分组码,一、线性分组码定义： 信息码元与监督码元之间可以用一组线性方程来表示，且监督码元仅由本码组的信息码元确定。 二、线性分组码的表示： （n，k），监督位 r=n-k 其编码效率 = k/n,三、线性分组码的性质： （1）封闭性，即任意两个许用码组之模2和仍为一许用码组； （2）码组的最小码d0距等于非零码的最小码重。 设有一（n，k）线性分组码，即c1、c2、