第十二章电子讲义差错控制编码

第十二章差错控制编码知识结构-差错控制的主要方式-检、纠错编码的基本概念和基本原理-常用的简单的检、纠错编码-线性分组码-卷积码教学目的-了解纠错编码的基本原理-了解几种常用编码：奇偶校验码、正反码等，线性分组码、循环码、卷积码的编解码原理教学重点-重点掌握线性分组码、循环码、卷积码的编解码原理。教学难点-生成矩阵和生成多项式教学方法及课时-多媒体授课（8学时）（分4个单元）备注单元二十八（2学时）§12.1引言（差错控制的作用和方式的分类）知识要点：信源编码与信道编码的基本概念、相互关系及区别差错控制的主要3种方式§12.1.1信源编码与信道编码的基本概念设计通信系统的目的就是把信源产生的信息有效可靠地传送到目的地。在数字通信系统中，为了提高数字信号传输的有效性而采取的编码称为信源编码；为了提高数字通信的可靠性而采取的编码称为信道编码。１．信源编码信源可以有各种不同的形式，例如在无线广播中，信源一般是一个语音源（话音或音乐）；在电视广播中，信源主要是活动图像的视频信号源。这些信源的输出都是模拟信号，所以称之为模拟源。而数字通信系统是设计来传送数字形式的信息，所以，这些模拟源如果想利用数字通信系统进行传输，就需要将模拟信息源的输出转化为数字信号，而这个转化构成就称为信源编码。对于信源编码的研究，在通信领域受到了人们的广泛关注。特别在移动通信系统中，信源编码（语音编码）决定了接收到的语音的质量和系统容量。因为在移动通信系统中，带宽是很珍贵的，所以，如何在有限的可分配的带宽内容纳更多的用户，已经成为经营者最为关心的问题。而低比特率语音编码提供了解决该问题的一种方法。在编码器能够传送高质量语音的前提下，如果比特率越低，就可以在一定的带宽内能容纳更多的语音通道。因此，生产商和服务提供商不断地寻求新的编码方法，以便在低比特率条件下提供高质量的语音。语音编码的目的就是在保持一定算法复杂程度和通信时延的前提下，运用尽可能少的信道容量，传送尽可能高的语音质量。目前较为常用的语音编码形式有：脉冲编码调制（PCM）、差分脉冲编码调制（DPCM）、自适应差分脉冲编码调制（ADPCM）、增量调制（DM）、连续可变斜率增量调制（CVSDM）、自适应预测编码（APC）、自带编码（SBC）、码激励线性预测编码等等。２．信道编码（差错控制编码）在实际信道传输数字信号的过程中，引起传输差错的根本原因在于信道内存在的噪声以及信道传输特性不理想所造成的码间串扰。为了提高数字传输系统的可靠性，降低信息传输的差错率，可以利用均衡技术消除码间串扰，利用增大发射功率、降低接收设备本身的噪声、选择好的调制制度和解调方法、加强天线的方向性等措施，提高数字传输系统的抗噪性能，但上述措施也只能将传输差错减小到一定程度。要进一步提高数字传输系统的可靠性，就需要采用差错控制编码，对可能或已经出现的差错进行控制。差错控制编码是在信息序列上附加上一些监督码元，利用这些冗余的码元，使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号；差错控制译码则利用这些规律性来鉴别传输过程是否发生错误，或进而纠正错误。原始数字信号是分组传输的，例如每k个二进制码元为一组（称为信息组），经信道编码后转换为每n个码元一组的码字（码组），这里n＞k，分组码通常表示为（n，k）。可见，信道编码是用增加数码，利用“冗余”来提高抗干扰能力的，也就是以降低信息传输速率为代价来减少错误的，或者说是用削弱有效性来增强可靠性的。本章首先给出了差错控制编码的基本概念，介绍了几种常用简单分组码，在此基础上，对分组码、循环码和卷积码基本原理和性能进行了研究分析。§12.1.2纠错编码的分类在差错控制系统中，信道编码存在着多种实现方式，同时信道编码也有多种分类方法。（１）按照信道编码的不同功能，可以将它分为检错码和纠错码。检错码仅能检测误码，例如，在计算机串口通信中常用到的奇偶校验码等；纠错码可以纠正误码，当然同时具有检错的能力，当发现不可纠正的错误时可以发出出错指示。（２）按照信息码元和监督码元之间的检验关系，可以将它分为线性和非线性码。若信息码元与监督码元之间的关系为线性关系，即满足一组线性方程式，称为线性码；否则，称为非线性码。（３）按照信息码元和监督码元之间的约束方式不同，可以将它分为分组码和卷积码。在分组码中，编码后的码元序列每n位分为一组，其中k位信息码元，r个监督位，r=n-k。监督码元仅与本码字的信息码元有关。卷积码则不同，监督码元不但与本信息码元有关，而且与前面码字的信息码元也有约束关系。（４）按照信息码元在编码后是否保持原来的形式，可以将它分为系统码和非系统码。在系统码中，编码后的信息码元保持原样不变，而非系统码中的信息码元则发生了变化。除了个别情况，系统码的性能大体上与非系统码相同，但是非系统码的译码较为复杂，因此，系统码得到了广泛的应用。（５）按照纠正错误的类型不同，可以将它分为纠正随机错误码和纠正突发错误码两种。前者主要用于发生零星独立错误的信道，而后者用于对付以突发错误为主的信道。（６）按照信道编码所采用的数学方法不同，可以将它分为代数码、几何码和算术码。其中代数码是目前发展最为完善的编码，线性码就是代数码的一个重要的分支。除上述信道编码的分类方法以外，还可以将它分为二进制信道编码和多进制信道编码等等。同时，随着数字通信系统的发展，可以将信道编码器和调制器统一起来综合设计，这就是所谓的网格编码调制（TCM——TrellisCodedModulation）。§12.1.3差错控制方式常用的差错控制方式主要有三种：前向纠错（简称FEC）、检错重发（简称ARQ）和混合纠错（简称HEC），它们的结构如图12-1所示。图中有斜线的方框图表示在该端进行错误的检测。前向纠错系统中，发送端经信道编码后可以发出具有纠错能力的码字；接收端译码后不仅可以发现错误码，而且可以判断错误码的位置并予以自动纠正。然而，前向纠错编码需要附加较多的冗余码元，影响数据传输效率，同时其编译码设备比较复杂。但是由于不需要反馈信道，实时性较好，因此，这种技术在单工信道中普遍采用，例如无线电寻呼系统中采用的POGSAG编码等。图12-1差错控制方式检错重发方式中，发送端经信道编码后可以发出能够检测出错误能力的码字；接收端收到后经检测如果发现传输中有错误，则通过反馈信道把这一判断结果反馈给发送端。然后，发送端把前面发出的信息重新传送一次，直到接收端认为已经正确后为止。典型系统检错重发方式的原理方框图如图12-2所示：常用的检错重发系统有三种，即停发等候重发、返回重发和选择重发。图12-2ARQ系统组成方框图在返回重发系统中，发送端无停顿的送出一个又一个码字，不再等待ACK信号，一旦接收端发现错误并发回NAK信号，则发送端从下一个码字开始重发前一段N组信号，N的大小取决于信号传递及处理所带来的延迟，这种系统比停发等候重发系统有很大的改进，在许多数据传输系统中得到应用。在选择重发系统中，发送端也是连续不断地发送码字，接收端发现错误发回NAK信号。与返回重发系统不同的是，发送端不是重发前面的所有码字，而是只重发有错误的那一组。显然，这种选择重发系统传输效率最高，但控制最为复杂。此外，返回重发系统和选择重发系统都需要全双工的链路，而停发等候重发系统只需要半双工的链路。基于上述分析，检错重发（ARQ）的优点主要表现在：（1）只需要少量的冗余码，就可以得到极低的输出误码率；（2）使用的检错码基本上与信道的统计特性无关，有一定的自适应能力；（3）与FEC相比，信道编译码器的复杂性要低得多。同时它也存在某些不足，主要表现在：（1）需要反向信道，故不能用于单向传输系统，并且实现重发控制比较复杂；（2）当信道干扰增大时，整个系统有可能处在重发循环当中，因而通信效率低，不大适合于严格实时传输系统。混合纠错方式是前向纠错方式和检错重发方式的结合。在这种系统中发送端不但具有纠正错误的能力，而且对超出纠错能力的错误有检测能力。遇到后一种情况时，系统可以通过反馈信道要求发送端重发一遍。混和纠错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷。在实际应用中，上述几种差错控制方式应根据具体情况合理选用。§12.1.4纠错编码的基本原理信道编码的基本思想就是在被传送的信息中附加一些监督码元，在收和发之间建立某种校验关系，当这种校验关系因传输错误而受到破坏时，可以被发现甚至纠正错误，这种检错与纠错能力是用信息量的冗余度来换取的。下面将介绍几个与信道编码有关的基本概念：码长：码字中码元的数目；码重：码字中非0数字的数目；对于二进制码来讲，码重W就是码元中1的数目，例如码字10100，码长n=5，码重W=2。码距：两个等长码字之间对应位不同的数目，有时也称作这两个码字的汉明距离，例如码字10100与11000之间的码距d=2。最小码距：在码字集合中全体码字之间距离的最小数值。对于二进制码字而言，两个码字之间的模二相加，其不同的对应位必为1，相同的对应位必为0。因此，两个码字之间模二相加得到的码重就是这两个码字之间的距离。以二进制分组码的纠错过程为例，可以较为详细地说明纠错码检错和纠错的基本原理。分组码对于数字序列是分段进行处理的，设每一段有k个码元组成（称作长度为k的信息组），由于每个码元有0或1两种值，故共有个不同的状态。每段长为k的信息组，以一定的规则增加r个多余度码元（称为监督元），监督这k个信息元，这样就组成长度为n＝k+r的码字（又称n重）。共可以得到个长度为n码字，它们通常被称为许用码字。而长度为n的数字序列共有2n种可能的组合，其中-个长度为n码字未被选用，故称它们为禁用码字。上述个长度为n的许用码字的集合称为分组码。分组码能够检错或纠错的原因是存在-多余度码字，或者说在码字中有禁用码字存在。下面就举一个具体的例子：设发送端发送A和B两个消息，分别用一位码元来表示，1代表A，0代表B。如果这两个信息组在传输中产生了错误，那么就会使0错成了1或1错成了0，而接收端不能发现这种错误，更谈不上纠正错误了。若在每个一位长的信息组中加上一个监督元（r＝1），其规则是与信息元重复，这样编出的两个长度为n＝2的码字，它们分别为11（代表A）和00（代表B）。这时11、00就是许用码字，这两个码字组成一个（2，1）分组码，其特点是各码字的码元是重复的，故又称为重复码。而01、10就是禁用码字。设发送11经信道传输错了一位，变成01或10，收端译码器根据重复码的规则，能发现有一位错误，但不能指明错在哪一位，也就是不能作出发送的消息是A（11）还是B（00）的判决。若信道干扰严重，使发送码字的两位都产生错误，从而使11错成了00，收端译码器根据重复码的规则检验，不认为有错，并且判决为消息B，造成了错判。这时可以发现：这种码距为2的（2，1）重复码能确定一个码元的错误，不能确定二个码元的错误，也不能纠正错误。若仍按重复码的规则，再加一个监督码元，得到（3，1）重复码，它的两个码字分别为111和000，其码距为3。这样其余六个码字（001、010、100、110、101、011）为禁用码字。设发送111（代表消息A），如果译码器收到的3重为110，根据重复码的规则，发现有错，并且当采用最大似然法译码时，把与发送码字最相似的码字认为就是发送码字。而110与111只有一位不同，与000有两位不同，故判决为111。事实上，在一般情况下，错一位的可能性比错二位的可能性要大得多，从统计的观点看，这样判决是正确的。因此，这种（3，1）码能够纠正一个错误，但不能纠正两个错误，因为若发送111，收到100时，根据译码规则将译为000，这就判错了。类似于前面的分析，这种码若用来检错，它可以发现两个错误，但不能发现三个错误。当然，还可以选用码字更长的重复码进行信道编码，随着码字的增长，重复码的检错和纠错能力会变得更强。上述例子表明：纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。因此，码字之间的最小距离是衡量该码字检错和纠