通信原理第9章.pptx

《通信原理第9章.pptx》由会员分享，可在线阅读，更多相关《通信原理第9章.pptx（147页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第9章 差错控制编码差错控制方式u信道分类：从差错控制角度看随机信道：错码的出现是随机的（白噪声）突发信道：错码是成串集中出现（脉冲干扰）混合信道：既存在随机错码又存在突发错码 u差错控制技术的种类检错重发（ARQ）前向纠错(FEC)反馈校验检错删除 第1页/共147页2第9章 差错控制编码自动要求重发(ARQ)系统3种ARQ系统停止等待ARQ系统 数据按分组发送。每发送一组数据后发端等待接收端的确认(ACK)答复，然后再发送下一组数据。图中的第3组接收数据有误，接收端发回一个否认(NAK)答复。这时，发送端将重发第3组数据。系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。接收码

2、组接收码组ACKACKACKACKNAKNAKACKACKACKACKNAKNAKACKACKt t1 12 23 33 34 45 55 5发送码组发送码组1 12 23 33 34 45 55 56 6t t有错码组有错码组有错码组有错码组第2页/共147页3第9章 差错控制编码拉后ARQ系统发送端连续发送数据组，接收端对于每个接收到的数据组都发回确认(ACK)或否认(NAK)答复。例如，图中第5组接收数据有误，则在发送端收到第5组接收的否认答复后，从第5组开始重发数据组。在这种系统中需要对发送的数据组和答复进行编号，以便识别。这种系统需要双工信道。接收数据接收数据有错码组有错码组有错码组

3、有错码组9 91010 11111010 111112122 21 14 43 36 65 57 79 98 85 57 76 6ACKACK1 1NAKNAK5 5NAKNAK9 9ACKACK5 5发送数据发送数据5 57 76 69 95 52 21 14 43 36 67 79 98 81010 11111010 1111 1212重发码组重发码组重发码组重发码组第3页/共147页4第9章 差错控制编码选择重发ARQ系统它只重发出错的数据组，因此进一步提高了传输效率。接收数据有错码组有错码组9214365759810 11131412发送数据995852143671011131412重

4、发码组重发码组NAK9ACK1NAK5ACK5ACK9第4页/共147页5第9章 差错控制编码ARQ的主要优点（和前向纠错方法相比）：监督码元较少即能使误码率降到很低，即码率较高；检错的计算复杂度较低；检错用的编码方法和加性干扰的统计特性基本无关，能适应不同特性的信道。ARQ的主要缺点：需要双向信道来重发，不能用于单向信道，也不能用于一点到多点的通信系统。因为重发而使ARQ系统的传输效率降低。在信道干扰严重时，可能发生因不断反复重发而造成事实上的通信中断。在要求实时通信的场合，例如电话通信，往往不允许使用ARQ法。第5页/共147页6第9章 差错控制编码ARQ系统的原理方框图第6页/共147页

5、7第9章 差错控制编码 上述的差错控制，接收端如何识别有无错码？上述的差错控制，接收端如何识别有无错码？采用差错控制编码（采用差错控制编码（纠错编码纠错编码）发端加上信道编码器发端加上信道编码器-信息码元序列信息码元序列+监督码元监督码元 监督码元监督码元：发送端在信息码元序列中增加的：发送端在信息码元序列中增加的 一些冗余码元一些冗余码元 收端加上信道译码器收端加上信道译码器-检错、纠错检错、纠错 不同的编码方法，有不同的检错或纠错能力不同的编码方法，有不同的检错或纠错能力 本章重点讨论常用的信道编码和译码方法本章重点讨论常用的信道编码和译码方法 第7页/共147页8第9章 差错控制编码9.

6、2 纠错编码的基本原理 例如：用例如：用1 1位二进制码可表示位二进制码可表示2 2种天气，种天气，0-晴，晴，1-雨雨 这种编码这种编码(只有信息位只有信息位)无检、纠错能力无检、纠错能力。（0 1或1 0）若用若用00-晴，晴，11-雨雨，（，（01、10为禁用码组）。为禁用码组）。这种编码这种编码(附加附加1 1位监督位位监督位)可检可检1 1位错。位错。（00 10或11 01）若用若用000-晴，晴，111-雨雨 ，（其它为禁用码组）。，（其它为禁用码组）。这种编码这种编码(附加附加2 2位监督位位监督位)可纠可纠1 1位错，检位错，检2 2位和位和2 2位以下错。位以下错。可见：信

7、息码可见：信息码+冗余的监督码元冗余的监督码元-检错和纠错能力检错和纠错能力第8页/共147页9第9章 差错控制编码u 纠错编码的分类 (1)线性码和非线性码 (2)分组码和卷积码。(3)检错码和纠错码。(4)系统码和非系统码。第9页/共147页10第9章 差错控制编码分组码的结构将信息码分组，为每组信息码附加若干监督码的编码称为分组码。在分组码中，监督码元仅监督本码组中的信息码元。信息位和监督位的关系：举例如下信息位信息位监督位监督位晴晴00000 0云云01011 1阴阴10101 1雨雨11110 0第10页/共147页11第9章差错控制编码分组码的一般结构分组码的符号：(n,k)n 码

8、组的总位数，又称为码组的长度（码长），k 码组中信息码元的数目，n k r 码组中的监督码元数目，或称监督位数目。编码效率(简称码率)：R=k/n=1-r/n冗余度：r/k=(n-k)/k 第11页/共147页12第9章差错控制编码分组码的码重和码距码重：码组中“1”的数目称为码组的重量，简称码重。例如：码组1011001的码重为4码距：两个码组中对应位上数字不同的位数称为 码组的距离，简称码距。码距又称汉明距离。例如：“000”晴，“011”云，“101”阴 “110”雨，任意两个码组的距离均为2。最小码距：把某种编码中各个码组之间距离的最小值称为最小码距(d0)。例如，上面编码的最小码距d

9、0=2。最小码距是一个重要参数，它直接关系到某种编码的检错、纠错能力。第12页/共147页13第9章 差错控制编码码距的几何意义每个码组的3个码元的值(a1,a2,a3)就是此立方体各顶点的坐标。而上述码距概念在此图中就对应于各顶点之间沿立方体各边行走的几何距离。由此图可以直观看出，上例中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第13页/共147页14第9章 差错控制编码码距和检纠错能力的关系 最最小小码码距距d d0 0直直接接关关系系着着码码的的检检错错和和纠纠错错能能力力；任

10、任一一(n,k)分组码，若要在码字内分组码，若要在码字内:(1)检测检测e个随机错码，则要求最小码距个随机错码，则要求最小码距 d0e+1;(2)纠正纠正t个随机错码，则要求最小码距个随机错码，则要求最小码距d02t+1;(3)纠正纠正t t个同时检测个同时检测e(t)个随机错码，则要求最小码个随机错码，则要求最小码距距 d0t+e+1。第14页/共147页15第9章 差错控制编码码距和检纠错能力的关系 【证1】设一个码组A位于O点。若码组A中发生一个错码，则我们可以认为A的位置将移动至以O点为圆心，以1为半径的圆上某点，但其位置不会超出此圆。若码组A中发生两位错码，则其位置不会超出以O点为圆

11、心，以2为半径的圆。因此，只要最小码距不小于3，码组A发生两位以下错码时，不可能变成另一个准用码组，因而能检测错码的位数等于2。0123BA汉明距离ed0第15页/共147页16第9章 差错控制编码 【证2】图中画出码组A和B的距离为5。码组A或B若发生不多于两位错码，则其位置均不会超出半径为2以原位置为圆心的圆。这两个圆是不重叠的。判决规则为：若接收码组落于以A为圆心的圆上就判决收到的是码组A，若落于以B为圆心的圆上就判决为码组B。这样，就能够纠正两位错码。BtA汉明距离012345td0第16页/共147页17第9章 差错控制编码 若这种编码中除码组A和B外，还有许多种不同码组，但任两码组

12、之间的码距均不小于5，则以各码组的位置为中心以2为半径画出之圆都不会互相重叠。这样，每种码组如果发生不超过两位错码都将能被纠正。因此，当最小码距d05时，能够纠正2个错码，且最多能纠正2个。若错码达到3个，就将落入另一圆上，从而发生错判。故一般说来，为纠正t个错码，最小码距应不小于(2t+1)。第17页/共147页18第9章 差错控制编码图中码组A和B之间距离为5。按照检错能力公式，最多能检测4个错码，即e=d0 1=5 1=4，按照纠错能力公式纠错时，能纠正2个错码。但是，不能同时作到两者，因为当错码位数超过纠错能力时，该码组立即进入另一码组的圆内而被错误地“纠正”了。例如，码组A若错了3位

13、，就会被误认为码组B错了2位造成的结果，从而被错“纠”为B。这就是说，检错和纠错公式不能同时成立或同时运用。BtA汉明距离012345td0第18页/共147页19第9章 差错控制编码 所以，为了在可以纠正t个错码的同时，能够检测e个错码，就需要像下图所示那样，使某一码组（譬如码组A）发生e个错误之后所处的位置，与其他码组（譬如码组B）的纠错圆圈至少距离等于1，不然将落在该纠错圆上从而发生错误地“纠正”。因此，由此图可以直观看出，要求最小码距这种纠错和检错结合的工作方式简称纠检结合。ABe1tt汉明距离第19页/共147页20第9章 差错控制编码这种工作方式是自动在纠错和检错之间转换的。当错码

14、数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；当错码数量多时，系统按反馈重发方式纠错，以降低系统的总误码率。所以，它适用于大多数时间中错码数量很少，少数时间中错码数量多的情况。第20页/共147页21第9章 差错控制编码9.3 纠错编码的性能系统带宽和信噪比的矛盾由上节所述的纠错编码原理可知，为了减少接收错误码元数量，需要在发送信息码元序列中加入监督码元。这样作的结果使发送序列增长，冗余度增大。若仍须保持发送信息码元速率不变，则传输速率必须增大，因而增大了系统带宽。系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。一般说来

15、，采用纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。第21页/共147页22第9章 差错控制编码编码性能举例未采用纠错编码时，若接收信噪比等于7dB，编码前误码率约为810-4，图中A点，在采用纠错编码后，误码率降至约410-5，图中B点。这样，不增大发送功率就能降低误码率约一个半数量级。10-610-510-410-310-210-1编码后PeCDEAB信噪比(dB)第22页/共147页23第9章 差错控制编码9.4 简单的实用编码9.4.1 奇偶监督码 奇偶监督码是在原信息码后面附加一个监督位，使得码组中“1”的个数是奇数或偶数。奇偶监督码又分为奇监督码和偶监督码。

16、奇偶监督码可检测出奇数个错码，它的编码效率R为 第23页/共147页24第9章 差错控制编码设码字设码字A=an-1,an-2,a1,a0，对对偶监督偶监督码有码有 监督码元监督码元a0可以由下式确定可以由下式确定 接收端译码时就是计算接收端译码时就是计算若若S为为“0”，则判定为无错码则判定为无错码；若若S为为“1”，则判定该则判定该码组经传输后有奇数个错码码组经传输后有奇数个错码。S称为校正子称为校正子第24页/共147页25第9章 差错控制编码 奇监督码情况相似，只是码组中奇监督码情况相似，只是码组中“1”的数目为奇数，的数目为奇数，即满足条件即满足条件而检错能力与偶监督码相同而检错能力

17、与偶监督码相同。例如，在例如，在ASCII码中，通常采用码中，通常采用7位二进制码元来表位二进制码元来表示示128种字符。传输时再加上一个奇偶监督位，种字符。传输时再加上一个奇偶监督位，8 8位码组。位码组。这种编码能检测奇数个错码这种编码能检测奇数个错码 第25页/共147页26第9章 差错控制编码9.4.2 二维奇偶监督码（方阵码）二维奇偶监督码的构成 图中a01 a02 a0m为m行奇偶监督码中的m个监督位。cn-1 cn-2 c1 c0为按列进行第二次编码所增加的监督位，们构成了一监督位行。第26页/共147页27第9章差错控制编码二维奇偶监督码二维奇偶监督码(66,50)第27页/共

18、147页28第9章 差错控制编码二维奇偶监督码的性能这种编码有可能检测偶数个错码。因为每行的监督位虽然不能用于检测本行中的偶数个错码，但按列的方向有可能由cn-1 cn-2 c1 c0等监督位检测出来。有一些偶数错码不可能检测出来。例如，构成矩形的4个错码。这种二维奇偶监督码适于检测突发错码。因为突发错码常常成串出现，随后有较长一段无错区间。由于方阵码只对构成矩形四角的错码无法检测，故其检错能力较强。二维奇偶监督码不仅可用来检错，还可以用来纠正一些错码。例如，仅在一行中有奇数个错码时。第28页/共147页29第9章 差错控制编码 9.4.3 恒比码在恒比码中，每个码组均含有相同数目的“1”（和

19、“0”）。“1”的数目与“0”的数目之比保持恒定，故得此名。这种码在检测时，只要计算接收码组中“1”的数目是否对，就知道有无错码。恒比码的主要优点是简单和适于用来传输电传机或其他键盘设备产生的字母和符号。对于信源来的二进制随机数字序列，这种码就不适合使用了。第29页/共147页30第9章 差错控制编码 3:2 恒比码阿拉伯数字阿拉伯数字码字码字阿拉伯数字阿拉伯数字码字码字101011610101211001711100310110801110411010910011500111001101第30页/共147页31第9章 差错控制编码9.4.4 正反码 它是一种简单的能够纠正错码的编码。其中的监

20、督位数目与信息位数目相同。其编码规则为：当信息位中有奇数个“1”时，监督位是信息位的重复；当信息位中有偶数个“1”时，监督位是信息位的反码。例如:若信息位为11001，则正反码为11001 11001；若信息位为10001,则正反码为10001 01110。第31页/共147页32第9章 差错控制编码正反码的解码在上例中，先将接收码组中信息位和监督位按模 2 相加，得到一个5位的合成码组。然后，由此合成码组产生一个校验码组。若接收码组的信息位中有奇数个“1”，则合成码组就是校验码组；若接收码组的信息位中有偶数个“1”，则取合成码组的反码作为校验码组。最后，观察校验码组中“1”的个数，按下表进行

21、判决及纠正可能发现的错码。第32页/共147页33第9章 差错控制编码校验码组和错码的关系 例如，若发送码组为1100111001，接收码组中无错码，则合成码组应为1100111001=00000。由于接收码组信息位中有奇数个“1”，所以校验码组就是00000。按上表判决，结论是无错码。校验码组的组成校验码组的组成错码情况错码情况1全为全为“0”无错码无错码2有有4个个“1”和和1个个“0”信息码中有信息码中有1位错码，其位置对应校验码组中位错码，其位置对应校验码组中“0”的位置的位置3有有4个个“0”和和1个个“1”监督码中有监督码中有1位错码，其位置对应校验码组中位错码，其位置对应校验码组

22、中“1”的位置的位置4其他组成其他组成错码多于错码多于1个个第33页/共147页34第9章 差错控制编码若传输中产生了差错，使接收码组变成1000111001，则合成码组为100011100101000。由于接收码组中信息位有偶数个“1”，所以校验码组应取合成码组的反码，即10111。按上表判断信息位中左边第2位为错码。若接收码组为1001111001，则合成码组为100111100101010，校验码组与其相同，按上表判断，这时错码多于1个。上述长度为10的正反码具有纠正1位错码的能力，并能检测全部2位以下的错码和大部分2位以上的错码。第34页/共147页35第9章 差错控制编码 9.5 线

23、性分组码基本概念代数码：建立在代数学基础上的编码。线性码：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。线性分组码：按照一组线性方程构成的分组码。例如在(7，4)线性分组码中，信息码每四位一组进行编码，即输入信息码元长度k=4；编码器输出码组长度n=7，监督码元长度r=n-k=7-4=3；编码效率R=k/n=4/7。第35页/共147页36第9章 差错控制编码汉明码能够纠正1位错码且编码效率较高的一种线性分组码汉明码的构造原理。在偶数监督码中，由于使用了一位监督位a0，它和信息位an-1 a1一起构成一个代数式：在接收端解码时，实际上就是在计算若S=0，就

24、认为无错码；若S=1，就认为有错码。现将上式称为监督关系式，S称为校正子。第36页/共147页37第9章 差错控制编码若监督位变成两位，则能增加一个类似的监督关系式。由于两个校正子的可能值有4中组合：00，01，10，11，故能表示4种不同的信息。若用其中1种组合表示无错，则其余3种组合就有可能用来指示一个错码的3种不同位置。同理，r个监督关系式能指示1位错码的(2r 1)个可能位置。一般来说，若码长为n，信息位数为k，则监督位数rnk。如果希望用r个监督位构造出r个监督关系式来指示1位错码的n种可能位置，则要求下面通过一个例子来说明如何具体构造这些监督关系式。第37页/共147页38第9章

25、差错控制编码例：设分组码(n,k)中k=4，为了纠正1位错码，由上式可知，要求监督位数 r 3。若取 r=3，则n=k+r=7。我们用a6 a5 a0表示这7个码元，用S1、S2和S3表示3个监督关系式中的校正子，则S1、S2和S3的值与错码位置的对应关系可以规定如下表所列：S1 S2 S3错码位置错码位置S1 S2 S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000无错码无错码第38页/共147页39第9章 差错控制编码由表中规定可见，仅当一位错码的位置在a2、a4、a5或a6时，校正子S1为1；否则S1为零。这就意味着a2、a4、a5和a6四个

26、码元构成偶数监督关系：同理，a1、a3、a5和a6构成偶数监督关系：以及a0、a3、a4 和a6构成偶数监督关系第39页/共147页40第9章 差错控制编码在发送端编码时，信息位a6、a5、a4和a3的值决定于输入信号，因此它们是随机的。监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上3式中S1、S2和S3的值为0（表示编成的码组中应无错码）：上式经过移项运算，解出监督位给定信息位后，可以直接按上式算出监督位，结果见下表：监督方程第40页/共147页41第9章 差错控制编码信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a0信息位信息位a6 a5 a4 a3监

27、督位监督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111第41页/共147页42第9章 差错控制编码接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。例如，若接收码组为0000011，按上述公式计算可得：S1=0，S2=1，S3=1。S1 S2 S3 等于011，故查表可知在 a3位有1错码。按照上述方法构造的码称为汉明码。表中所列的(7,4)汉明码的最小码距d0=3。因此，这种码能够

28、纠正1个错码或检测2个错码。由于码率k/n=(n-r)/n=1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。第42页/共147页43第9章 差错控制编码线性分组码的一般原理线性分组码的构造H矩阵上面(7,4)汉明码的例子有现在将上面它改写为上式中已经将“”简写成“+”。第43页/共147页44第9章 差错控制编码上式可以表示成如下矩阵形式：上式还可以简记为H AT=0T 或 A HT=0第44页/共147页45第9章 差错控制编码H AT=0T 或A HT=0式中 A=a6 a5 a4 a3 a2 a1 a00=000右上标“T”表示将矩阵转置。例如，HT是H的转置，即

29、HT的第一行为H的第一列，HT的第二行为H的第二列等等。将H称为监督矩阵。只要监督矩阵H给定，编码时监督位和信息位的关系就完全确定了。第45页/共147页46第9章 差错控制编码H矩阵的性质：1)H的行数就是监督关系式的数目，它等于监督位的数目r。H的每行中“1”的位置表示相应码元之间存在的监督关系。例如，H的第一行1110100表示监督位a2是由a6 a5 a4之和决定的。H矩阵可以分成两部分，例如 式中，P为r k阶矩阵，Ir为r r阶单位方阵。我们将具有P Ir形式的H矩阵称为典型阵。2)由代数理论可知，H矩阵的各行应该是线性无关的。第46页/共147页47第9章 差错控制编码 G矩阵：

30、上面汉明码例子中的监督位公式 也可以改写成矩阵形式：第47页/共147页48第9章 差错控制编码或者写成式中，Q为一个k r阶矩阵，它为P的转置，即 Q=PT 上式表示，在信息位给定后，用信息位的行矩阵乘矩 阵Q就产生出监督位。第48页/共147页49第9章 差错控制编码我们将Q的左边加上1个k k阶单位方阵，就构成1个矩阵G G称为生成矩阵，因为由它可以产生整个码组，即有 或者因此，如果找到了码的生成矩阵G，则编码的方法就完全确定了。具有Ik Q形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。这种形式的码称为系统码。第49页/共147页50第

31、9章 差错控制编码G矩阵的性质：1)G矩阵的各行是线性无关的。任一码组A都是G的各行的线性组合。G共有k行，若它们线性无关，则可以组合出2k种不同的码组A，它恰是有k位信息位的全部码组。若G的各行有线性相关的，则不可能由G生成2k种不同的码组了。2)G的各行本身就是一个码组。如果已有k个线性无关的码组，则可以用其作为生成矩阵G，并由它生成其余码组。第50页/共147页51第9章 差错控制编码错码矩阵和错误图样 发送的码组A在传输中可能由于干扰引入差错，故接收码组一般说来与A不一定相同。若设接收码组为一n列的行矩阵B，即则发送码组和接收码组之差为B A=E(模2)它就是传输中产生的错码行矩阵 式

32、中第51页/共147页52第9章 差错控制编码因此，若ei=0，表示该接收码元无错；若ei=1，则表示该接收码元有错。B A=E 可以改写成 B=A+E例如，若发送码组A=1000111，错码矩阵E=0000100，则接收码组B=1000011。错码矩阵有时也称为错误图样。第52页/共147页53第9章 差错控制编码校正子S当接收码组有错时，E 0，将B当作A代入公式(A H T=0)后，该式不一定成立。在未超过检错能力时，上式不成立，即其右端不等于0。假设这时该式的右端为S，即B H T=S将B=A+E代入上式，可得S=(A+E)H T=A H T+E H T由于A HT=0，所以S=E H

33、 T式中S称为校正子。它能用来指示错码的位置。S和错码E之间有确定的线性变换关系。若S和E之间一一对应，则S将能代表错码的位置。第53页/共147页54第9章 差错控制编码线性分组码的性质封闭性：线性码中的任意两个码组之和仍为这种码中的一个码组。若A1和A2是两个码组，则有A1 HT=0,A2 HT=0 将上两式相加，得出 A1 HT+A2 HT=(A1+A2)HT=0所以(A1+A2)也是一个码组。两个码组(A1和A2)之间的距离必定是另一个码组(A1+A2)的重量（即“1”的数目）。因此，最小码距就是最小码重。第54页/共147页55第9章 差错控制编码9.6 循环码9.6.1 循环码原理

34、 循环码循环码是具有是具有循环性循环性的的线性分组码线性分组码。循环码中任意一码组向右或向左循环移一位以后，循环码中任意一码组向右或向左循环移一位以后，仍是该码的一个码组。仍是该码的一个码组。循环码的编译码设备较简单，检纠错能力较强，循环码的编译码设备较简单，检纠错能力较强，广泛应用。广泛应用。第55页/共147页56第9章 差错控制编码(7,3)循环码循环码 码组编号码组编号码码 组组码组编号码组编号码码 组组1000 0000 5100 10112001 01116101 11003010 11107110 01014011 10018111 0010第56页/共147页57第9章 差错控

35、制编码码多项式码组的多项式表示法把码组中各码元当作是一个多项式的系数，即把一个长度为n的码组 表示成例如：码组1100101（n=7）的码多项式为这种多项式中，x仅是码元位置的标记，例如上式表示码组中a6、a5、a2和a0为“1”，其他均为0。因此我们并不关心x的取值。第57页/共147页58第9章 差错控制编码 码多项式的按模运算在整数运算中，有模n运算。例如，在模2运算中，有1+1=2 0 (模2)1+2=3 1 (模2)2 3=6 0 (模2)一般说来，若一个整数m可以表示为式中，Q 整数，则在模 n 运算下，有 m p (模n)即，在模 n 运算下，一个整数m等于它被 n 除得的余数。

36、第58页/共147页59第9章 差错控制编码码多项式运算中也有类似的按模运算。若一任意多项式F(x)被一 n 次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则写为码多项式系数仍按模2运算，即系数只取 0 和1。第59页/共147页60第9章 差错控制编码例如例如：F(x)=x4+x2+1被被N(x)=x3+1除除，得到余式得到余式R(x)=x2+x+1，x即：x4+x2+1 x2+x+1（模模(x3+1)。第60页/共147页61第9章 差错控制编码循环码的码多项式在循环码中，若T(x)是一个长为n的许用码组，若则T(x)也是该编码中的一个许用码组。【证】（模(xn+1

37、)）所以，这时有T (x)正是正是T(x)代表的码组向左循环移位代表的码组向左循环移位i次的结果。次的结果。因为假定因为假定T(x)是循环码的一个码组，所以是循环码的一个码组，所以T (x)也必为该码的一个码也必为该码的一个码组。组。第61页/共147页62第9章 差错控制编码例如，循环码组(1100101)其码长n=7。现给定i=3，则 其对应的码组为0101110，它正是原码组左移3位的结果。第62页/共147页63第9章 差错控制编码循环码的生成多项式和生成矩阵由公式可知，有了生成矩阵G，就可以由k个信息位得出整个码组，而且生成矩阵G的每一行都是一个码组。若能找到k个线性不相关的已知码组

38、，就能构成矩阵G。在一个(n,k)码循环码中，若用 g(x)表示其中前(k-1)位皆为“0”的码组，则 g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且线性无关，因此可用它们构成此循环码的生成矩阵G。称这唯一的(n k)次多项式 g(x)为码的生成多项式第63页/共147页64第9章 差错控制编码因此，循环码的生成矩阵 G 可以写成 例：在上表所给出的(7,3)循环码中，唯一的一个(n k)=4次码多项式代表的码组是0010111（前 k-1=2 位皆为“0），对应的码多项式（即生成多项式）g(x)=x4+x2+x+1。并得到 或第64页/共147页65第9章 差错控制

39、编码上式不符合G=Ik Q 的形式，所以它不是典型阵。将它作线性变换，不难化成典型阵。可以写出此循环码组，即上式表明，所有码多项式T(x)都可被g(x)整除，而且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式。第65页/共147页66第9章 差错控制编码如何寻找任一(n,k)循环码的生成多项式 任一循环码多项式T(x)都是g(x)的倍式，可写成T(x)=h(x)g(x)而生成多项式g(x)本身也是一个码组，即有 T(x)=g(x)x k T(x)是一个n次多项式。xk T(x)在模(xn+1)运算下也是一个码组，故可以写成第66页/共147页67第9章 差错控制编码 上式中Q(x)

40、=1。将 T(x)和T(x)表示式代入上式，经化简得 循环码的生成多项式g(x)应该是(xn+1)的一个(n k)次因式。例如，(x7+1)可以分解为为了求(7,3)循环码的生成多项式g(x)，需要从上式中找到一个 (n k)=4次的因子。即第67页/共147页68第9章 差错控制编码 以上两式都可作为生成多项式。选用的生成多项式不同，产生出的循环码码组也不同。第68页/共147页69第9章 差错控制编码g(x)有如下性质：g(x)是前(k-1)位皆为“0”的码组；g(x)必须是一个常数项不为“0”的唯一的(n-k)次多项式；所有码多项式T(x)都可被g(x)整除；g(x)是(xn+1)的一个

41、(n k)次因式；一旦确定了g(x)，则整个(n,k)循环码就被确定了。第69页/共147页70第9章 差错控制编码例例如如(7,3)循循环环码码，n=7,k=3,r=4，若若其其生生成成多多项项式式g(x)=x4+x3+x2+1，可得可得 即即 第70页/共147页71第9章 差错控制编码显显然然，G不不是是典典型型形形式式的的生生成成矩矩阵阵，但但经经过过简简单单的的变变换就很容易化为典型形式的生成矩阵，换就很容易化为典型形式的生成矩阵，即即 求求(7,4)循环码生成多项式循环码生成多项式g(x)和和G？第71页/共147页72第9章 差错控制编码【例例9-1】已已知知（7，4）循循环环码

42、码的的全全部部码码组组为为0000000，0100111，1000101，1100010，0001011，0101100，1001110，1101001，0010110，0110001，1010011，1110100，0011101，0111010，1011000，1111111。试求该循环码的生成多项式、生成矩阵和监督矩阵。试求该循环码的生成多项式、生成矩阵和监督矩阵。已知已知 n=7，k=4，r=nk=74=3解解：（1）求生成多项式求生成多项式 g(x)。第72页/共147页73第9章 差错控制编码生成多项式生成多项式 g(x)必须满足：必须满足：是一个是一个 nk=3次多项式（次多项式

43、（前前k-1=3 位为位为0），），其常数项不为其常数项不为0，是是x7+1的一个因子，的一个因子，x7+1=(x+1)(x3+x+1)(x3+x2+1)本本题题给给出出了了循循环环码码的的全全部部码码字字，因因此此符符合合本本题题条条件件的的生成多项式为生成多项式为 g(x)=x3+x+1 第73页/共147页74第9章 差错控制编码（2）求生成矩阵求生成矩阵G g(x)=x3+x+1第74页/共147页75第9章 差错控制编码将第三行与第四行的和加到第一行，得到将第三行与第四行的和加到第一行，得到再将第四行加到第二行，得到典型生成矩阵再将第四行加到第二行，得到典型生成矩阵 第75页/共14

44、7页76第9章 差错控制编码（4）分析该循环码的纠检错能力分析该循环码的纠检错能力（3）求监督矩阵求监督矩阵 H第76页/共147页77第9章 差错控制编码9.6.2 循环码的编解码方法循环码的编码方法设编码前的信息码设编码前的信息码 码多项式码多项式 系统码系统码循环码的码多项式可表示为循环码的码多项式可表示为 可见可见，r(x)是是 x n-k m(x)除以除以 g(x)得到余式得到余式第77页/共147页78第9章 差错控制编码循环码的编码步骤：循环码的编码步骤：(1)用用xn-k乘乘以以m(x)。是是在在信信息息码码元元后后附附加加上上n-k个个“0”。(2)用用xn-km(x)除以除

45、以g(x)，得到商得到商Q(x)和余式和余式 r(x)。(3)编出的码组为编出的码组为第78页/共147页79第9章 差错控制编码例如例如，(7，3)循环码中信息码组为循环码中信息码组为(110)，则则 m(x)=x2+x xn-km(x)=x4(x2+x)=x6+x5 (表示码组表示码组1100000)若选定若选定g(x)=x4+x2+x+1则则r(x)=x2+1,T(x)=x6+x5+x2+1(表示码组表示码组1100101)上式等效于上式等效于第79页/共147页80第9章 差错控制编码循环码的解码方法解码要求：检错和纠错。检错解码原理 由于任意一个码组多项式T(x)都应该能被生成多项式

46、g(x)整除，所以在接收端可以将接收码组R(x)用原生成多项式g(x)去除。余项 r(x)=0 接收码组中无错码余项 r(x)0 接收码组中有错码第80页/共147页81第9章 差错控制编码纠错解码原理 为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系，从而纠正错码。纠错步骤：(1)用生成多项式g(x)除接收码组R(x)，得出余式 r(x)。(2)按r(x)，用查表法或通过某种计算得到错误图样E(x)；例如，通过计算校正子S和查表，就可以确定错码的位置。(3)从R(x)中减去E(x)，便可纠错，得到原发送码组T(x)。通常，一种编码可以有几种纠错解码方法，上述解码方法称为

47、捕错解码法。目前多采用软件运算实现上述编解码运算。第81页/共147页82第9章 差错控制编码9.6.3 截短循环码截短目的：在设计纠错编码方案时，常常信息位数k、码长n和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。这时，可以采用将码长截短的方法，得出满足要求的编码。截短方法：设给定一个(n,k)循环码，它共有2k种码组，现使其前i(0 i k)个信息位全为“0”，于是它变成仅有2k-i种码组。然后从中删去这i位全“0”的信息位，最终得到一个(n i,k i)的线性码。将这种码称为截短循环码。截短循环码性能：循环码截短前后至少具有相同的纠错能力，并且编解码方法仍和截短

48、前的方法一样。例：要求构造一个能够纠正1位错码的(13,9)码。这时可以由(15,11)循环码的11种码组中选出前两信息位均为“0”的码组，构成一个新的码组集合。然后在发送时不发送这两位“0”。于是发送码组成为(13,9)截短循环码。第82页/共147页83第9章 差错控制编码9.6.4 BCH码什么是BCH码？它是一种获得广泛应用的能够纠正多个错码的循环码，是以3位发明这种码的人名(Bose-Chaudhuri-Hocguenghem)命名的。BCH码的重要性在于它解决了生成多项式与纠错能力的关系问题，可以在给定纠错能力要求的条件下寻找到码的生成多项式。有了生成多项式，编码的基本问题就随之解

49、决了。BCH码分类：本原BCH码：其生成多项式g(x)中含有最高次数为m的本原多项式，且码长为n=2m 1，(m 3，为正整数)。非本原BCH码：其生成多项式中不含这种本原多项式，且码长n是(2m 1)的一个因子，即码长n一定除得尽2m 1。第83页/共147页84第9章 差错控制编码BCH码的性能：码长n与监督位、纠错个数 t 之间的关系：对于正整数m(m 3)和正整数t 1，且除得尽(2m-1)），则为非本原BCH码。汉明码是能够纠正单个随机错误的码。可以证明，具有循环性质的汉明码就是能纠正单个随机错误的本原BCH码。例如，(7,4)汉明码就是以g1(x)=x3+x+1或g2(x)=x3+

50、x2+1生成的BCH码，而用g3(x)=x4+x+1或g4(x)=x4+x3+1都能生成(15,11)汉明码。第84页/共147页85第9章 差错控制编码BCH码的设计在工程设计中，一般不需要用计算方法去寻找生成多项式g(x)。因为前人早已将寻找到的g(x)列成表，故可以用查表法找到所需的生成多项式。下表给出了码长n 127的二进制本原BCH码生成多项式。第85页/共147页86第9章 差错控制编码n=3k t g(x)1 1 7n=63k t g(x)57 1 10351 2 1247145 3 170131739 4 16662356736 5 103350042330 6 1574641