通信原理-(第六版)第11章课件1.ppt

1、 通信原理 通信原理第11章差错控制编码 基本要求与学时分配n讲述6学时n掌握纠错编码的基本原理，熟悉常用的简单编码，掌握线性分组码和循环码的编码特点n重点：纠错编码的基本原理，线性分组码和循环码的编码特点第11章差错控制编码n11.1 概述n信道分类：从差错控制角度看n随机信道：错码的出现是随机的 n突发信道：错码是成串集中出现的n混合信道：既存在随机错码又存在突发错码 n差错控制技术的种类n 检错重发n前向纠错 n反馈校验n检错删除 差错控制的目的是使用信道编码的方法检测和纠正误码，降低误码率。根据差错控制方法的不同，其主要可以分为三种形式：检错重发法（检错重发法（ARQ）：接收端在接收到

2、的信码中检测出错码，就通知发送端重发，直到正确接收为止。所谓检测出错码，是指在若干接收码元中知道有一个或一些是错的，但不知道该错码的准确位置。采用这种差错控制的方法需要具备双向信道。采用检错重发方式，只用于检测误码。前向纠错法（前向纠错法（FEC）：接收端不仅能在收到的信码中发现有错码，还能够纠正错码。对于二进制系统，如果能够确定错码的位置，就能够纠正它。这种方法不需要反向信道，而且实时性好，但是纠错设备比较复杂。反馈校验法反馈校验法:接收端将接收到的信码原封不动的转发回发送端，并与原发送信码相比较，如发现错误，则发送端进行重发。第11章差错控制编码n差错控制编码：常称为纠错编码纠错编码n监督

3、码元：监督码元：上述4种技术中除第3种外，都是在接收端识别有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元。n不同的编码方法，有不同的检错检错或纠错纠错能力。n多余度多余度：就是指增加的监督码元多少。例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为1/3。n编码效率编码效率(简称码率码率)：设编码序列中信息码元数量为k，总码元数量为n，则比值k/n 就是码率。n冗余度：冗余度：监督码元数(n-k)和信息码元数 k 之比。n理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。第11章差错控制编码n11.2 纠错编码的基本原理n分

4、组码基本原理：举例说明如下。n设有一种由3位二进制数字构成的码组，它共有8种不同的可能组合。若将其全部用来表示天气，则可以表示8种不同天气，例如：“000”（晴），“001”（云），“010”（阴），“011”（雨），“100”（雪），“101”（霜），“110”（雾），“111”（雹）。n其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码组。这时，接收端将无法发现错误。第11章差错控制编码n若在上述8种码组中只准许使用4种来传送天气，例如：“000”晴 “011”云 “101”阴 “110”雨n这时，虽然只能传送4种不同的天气，但是接收端却有可能发现码组中的一个错码。n例如，若“

5、000”（晴）中错了一位，则接收码组将变成“100”或“010”或“001”。这3种码组都是不准使用的，称为禁用码组禁用码组。n接收端在收到禁用码组时，就认为发现了错码。当发生3个错码时，“000”变成了“111”，它也是禁用码组，故这种编码也能检测3个错码。n但是这种码不能发现一个码组中的两个错码，因为发生两个错码后产生的是许用码组许用码组。第11章差错控制编码n检错和纠错n上面这种编码只能检测错码，不能纠正错码。例如，当接收码组为禁用码组“100”时，接收端将无法判断是哪一位码发生了错误，因为晴、阴、雨三者错了一位都可以变成“100”。n要能够纠正错误，还要增加多余度。例如，若规定许用码组

6、只有两个：“000”（晴），“111”（雨），其他都是禁用码组，则能够检测两个以下错码，或能够纠正一个错码。n例如，当收到禁用码组“100”时，若当作仅有一个错码，则可以判断此错码发生在“1”位，从而纠正为“000”（晴）。因为“111”（雨）发生任何一位错码时都不会变成“100”这种形式。n但是，这时若假定错码数不超过两个，则存在两种可能性：“000”错一位和“111”错两位都可能变成“100”，因而只能检测出存在错码而无法纠正错码。第11章差错控制编码n分组码的结构n将信息码分组，为每组信息码附加若干监督码的编码称为分组分组码码。n在分组码中，监督码元仅监督本码组中的信息码元。n信息位和监

7、督位的关系：举例如下信息位信息位监督位监督位晴晴000云云011阴阴101雨雨110第11章差错控制编码n分组码的一般结构n分组码的符号：(n,k)nN 码组的总位数，又称为码组的长度（码长），nk 码组中信息码元的数目，nn k r 码组中的监督码元数目，或称监督位数目。第11章差错控制编码n分组码的码重和码距n码重：把码组中“1”的个数目称为码组的重量，简称码重码重。n码距：把两个码组中对应位上数字不同的位数称为码组的距离，简称码距码距。码距又称汉明距离汉明距离。n例如，“000”晴，“011”云，“101”阴，“110”雨，4个码组之间，任意两个的距离均为2。n最小码距：把某种编码中各个

8、码组之间距离的最小值称为最小最小码距码距(d0)。例如，上面的编码的最小码距d0=2。第11章差错控制编码n码距的几何意义n对于3位的编码组，可以在3维空间中说明码距的几何意义。n每个码组的3个码元的值(a1,a2,a3)就是此立方体各顶点的坐标。而上述码距概念在此图中就对应于各顶点之间沿立方体各边行走的几何距离。n由此图可以直观看出，上例中4个准用码组之间的距离均为2。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1第11章差错控制编码n码距和检纠错能力的关系n一种编码的最小码距d0的大小直接关系着这种编码的检错和纠

9、错能力n为检测e个错码，要求最小码距 d0 e+1【证】设一个码组A位于O点。若码组A中发生一个错码，则我们可以认为A的位置将移动至以O点为圆心，以1为半径的圆上某点，但其位置不会超出此圆。若码组A中发生两位错码，则其位置不会超出以O点为圆心，以2为半径的圆。因此，只要最小码距不小于3，码组A发生两位以下错码时，不可能变成另一个准用码组，因而能检测错码的位数等于2。0123BA汉明距离ed0第11章差错控制编码同理，若一种编码的最小码距为d0，则将能检测(d0-1)个错码。反之，若要求检测e个错码，则最小码距d0至少应不小于(e+1)。n为了纠正t个错码，要求最小码距d0 2t+1【证】图中画

10、出码组A和B的距离为5。码组A或B若发生不多于两位错码，则其位置均不会超出半径为2以原位置为圆心的圆。这两个圆是不重叠的。判决规则为：若接收码组落于以A为圆心的圆上就判决收到的是码组A，若落于以B为圆心的圆上就判决为码组B。这样，就能够纠正两位错码。BtA汉明距离012345td0第11章差错控制编码若这种编码中除码组A和B外，还有许多种不同码组，但任两码组之间的码距均不小于5，则以各码组的位置为中心以2为半径画出之圆都不会互相重叠。这样，每种码组如果发生不超过两位错码都将能被纠正。因此，当最小码距d05时，能够纠正2个错码，且最多能纠正2个。若错码达到3个，就将落入另一圆上，从而发生错判。故

11、一般说来，为纠正t个错码，最小码距应不小于(2t+1)。第11章差错控制编码n为纠正t个错码，同时检测e个错码，要求最小码距在解释此式之前，先来分析下图所示的例子。图中码组A和B之间距离为5。按照检错能力公式，最多能检测4个错码，即e=d0 1=5 1=4，按照纠错能力公式纠错时，能纠正2个错码。但是，不能同时作到两者，因为当错码位数超过纠错能力时，该码组立即进入另一码组的圆内而被错误地“纠正”了。例如，码组A若错了3位，就会被误认为码组B错了2位造成的结果，从而被错“纠”为B。这就是说，检错和纠错公式不能同时成立或同时运用。)(10tetedBtA汉明距离012345td0第11章差错控制编

12、码所以，为了在可以纠正t个错码的同时，能够检测e个错码，就需要像下图所示那样，使某一码组（譬如码组A）发生e个错误之后所处的位置，与其他码组（譬如码组B）的纠错圆圈至少距离等于1，不然将落在该纠错圆上从而发生错误地“纠正”。因此，由此图可以直观看出，要求最小码距这种纠错和检错结合的工作方式简称纠检结合纠检结合。ABe1tt汉明距离)(10teted第11章差错控制编码这种工作方式是自动在纠错和检错之间转换的。当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；当错码数量多时，系统按反馈重发方式纠错，以降低系统的总误码率。所以，它适用于大多数时间中错码数量很少，少数时间中错码数

13、量多的情况。第11章差错控制编码n11.4简单的实用编码n11.4.1 奇偶监督码n奇偶监督码分为奇数监督码和偶数监督码两种，两者的原理相同。在偶数监督码中，无论信息位多少，监督位只有1位，它使码组中“1”的数目为偶数，即满足下式条件：式中a0为监督位，其他位为信息位。这种编码能够检测奇数个错码。在接收端，按照上式求“模2和”，若计算结果为“1”就说明存在错码，结果为“0”就认为无错码。奇数监督码与偶数监督码相似，只不过其码组中“1”的数目为奇数：0021aaann1021aaann第11章差错控制编码n11.4.2 二维奇偶监督码（方阵码）n二维奇偶监督码的构成它是先把上述奇偶监督码的若干码

14、组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位，如下图所示图中a01 a02 a0m为m行奇偶监督码中的m个监督位。cn-1 cn-2 c1 c0为按列进行第二次编码所增加的监督位，它们构成了一监督位行。012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn第11章差错控制编码n二维奇偶监督码的性能n这种编码有可能检测偶数个错码。因为每行的监督位虽然不能用于检测本行中的偶数个错码，但按列的方向有可能由cn-1 cn-2 c1 c0等监督位检测出来。有一些偶数错码不可能检测出来。例如，构成矩形的4个错码，譬如图中错了，就检测不出。

15、n这种二维奇偶监督码适于检测突发错码。因为突发错码常常成串出现，随后有较长一段无错区间。n由于方阵码只对构成矩形四角的错码无法检测，故其检错能力较强。n二维奇偶监督码不仅可用来检错，还可以用来纠正一些错码。例如，仅在一行中有奇数个错码时。mmnnaaaa122122第11章差错控制编码n 11.4.3 恒比码恒比码n在恒比码中，每个码组均含有相同数目的“1”（和“0”）。由于“1”的数目与“0”的数目之比保持恒定，故得此名。n这种码在检测时，只要计算接收码组中“1”的数目是否对，就知道有无错码。n恒比码的主要优点是简单和适于用来传输电传机或其他键盘设备产生的字母和符号。对于信源来的二进制随机数

16、字序列，这种码就不适合使用了。第11章差错控制编码n11.4.4 正反码正反码n正反码的编码：n它是一种简单的能够纠正错码的编码。其中的监督位数目与信息位数目相同，监督码元与信息码元相同或者相反则由信息码中“1”的个数而定。n例如，若码长n=10，其中信息位 k=5，监督位 r=5。其编码规则为：n当信息位中有奇数个“1”时，监督位是信息位的简单重复；n当信息位有偶数个“1”时，监督位是信息位的反码。n例如，若信息位为11001，则码组为1100111001；若信息位为10001，则码组为1000101110。第11章差错控制编码n正反码的解码n在上例中，先将接收码组中信息位和监督位按模 2

17、相加，得到一个5位的合成码组。然后，由此合成码组产生一个校验码组。n若接收码组的信息位中有奇数个“1”，则合成码组就是校验码组；若接收码组的信息位中有偶数个“1”，则取合成码组的反码作为校验码组。n最后，观察校验码组中“1”的个数，按下表进行判决及纠正可能发现的错码。第11章差错控制编码n校验码组和错码的关系例如，若发送码组为1100111001，接收码组中无错码，则合成码组应为1100111001=00000。由于接收码组信息位中有奇数个“1”，所以校验码组就是00000。按上表判决，结论是无错码。校验码组的组成校验码组的组成错码情况错码情况1全为全为“0”无错码无错码2有有4个个“1”和和

18、1个个“0”信息码中有信息码中有1位错码，其位置对应校验码组中位错码，其位置对应校验码组中“0”的位置的位置3有有4个个“0”和和1个个“1”监督码中有监督码中有1位错码，其位置对应校验码组中位错码，其位置对应校验码组中“1”的位置的位置4其他组成其他组成错码多于错码多于1个个第11章差错控制编码若传输中产生了差错，使接收码组变成1000111001，则合成码组为100011100101000。由于接收码组中信息位有偶数个“1”，所以校验码组应取合成码组的反码，即10111。由于其中有4个“1”和1个“0”，按上表判断信息位中左边第2位为错码。若接收码组错成1100101001，则合成码组变成

19、110010100110000。由于接收码组中信息位有奇数个“1”，故校验码组就是10000，按上表判断，监督位中第1位为错码。最后，若接收码组为1001111001，则合成码组为100111100101010，校验码组与其相同，按上表判断，这时错码多于1个。n上述长度为10的正反码具有纠正1位错码的能力，并能检测全部2位以下的错码和大部分2位以上的错码。第11章差错控制编码n11.5 线性分组码n基本概念n代数码代数码：建立在代数学基础上的编码。n线性码线性码：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。n线性分组码线性分组码：按照一组线性方程构成的分

20、组码。本节将以汉明码为例引入线性分组码的一般原理。第11章差错控制编码n汉明码汉明码能够纠正1位错码且编码效率较高的一种线性分组码n汉明码的构造原理。n在偶数监督码中，由于使用了一位监督位a0，它和信息位an-1 a1一起构成一个代数式：在接收端解码时，实际上就是在计算若S=0，就认为无错码；若S=1，就认为有错码。现将上式称为监督关系式监督关系式，S称为校正子校正子。由于校正子S只有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。0021aaann021aaaSnn第11章差错控制编码n若监督位增加一位，即变成两位，则能增加一个类似的监督关系式。由于两个校正子的可能值有4中

21、组合：00，01，10，11，故能表示4种不同的信息。若用其中1种组合表示无错，则其余3种组合就有可能用来指示一个错码的3种不同位置。同理，r个监督关系式能指示1位错码的(2r 1)个可能位置。n一般来说，若码长为n，信息位数为k，则监督位数rnk。如果希望用r个监督位构造出r个监督关系式来指示1位错码的n种可能位置，则要求下面通过一个例子来说明如何具体构造这些监督关系式。1212rknrr或第11章差错控制编码n例：设分组码分组码(n,k)中k=4，为了纠正1位错码，由上式可知，要求监督位数 r 3。若取 r=3，则n=k+r=7。我们用a6 a5 a0表示这7个码元，用S1、S2和S3表示

22、3个监督关系式中的校正子，则S1、S2和S3的值与错码位置的对应关系可以规定如下表所列：S1 S2 S3错码位置错码位置S1 S2 S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000无错码无错码第11章差错控制编码由表中规定可见，仅当一位错码的位置在a2、a4、a5或a6时，校正子S1为1；否则S1为零。这就意味着a2、a4、a5和a6四个码元构成偶数监督关系：同理，a1、a3、a5和a6构成偶数监督关系：以及a0、a3、a4 和a6构成偶数监督关系24561aaaaS13562aaaaS03463aaaaS第11章差错控制编码n在发送端编码时，信

23、息位a6、a5、a4和a3的值决定于输入信号，因此它们是随机的。监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上3式中S1、S2和S3的值为0（表示编成的码组中应无错码）：上式经过移项运算，解出监督位给定信息位后，可以直接按上式算出监督位，结果见下表：000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa第11章差错控制编码信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a0信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a0000000010001110001011100110000101011010

24、0100011110101100101001101100001010110111010100110011111010001110001111111第11章差错控制编码n接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。例如，若接收码组为0000011，按上述公式计算可得：S1=0，S2=1，S3=1。由于S1 S2 S3 等于011，故查表可知在a3位有1错码。n按照上述方法构造的码称为汉明码。表中所列的(7,4)汉明码的最小码距d0=3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n=(n-r)/n=1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。