1、1 1第第9章章 差错控制编码差错控制编码第9章 差错控制编码9.1差错控制编码原理9.2常用简单差错控制编码9.3线性分组码9.4循环码9.5卷积码本章仿真实验举例习题2 2第第9章章 差错控制编码差错控制编码9.1差错控制编码原理9.1.1引起误码的原因与降低误码的常用方法数字信号在实际通信过程中不可避免地会发生错误。这是因为，一方面通信系统的特性并非完全理想，数字信号波形通过这样的通信系统时会产生波形失真，因而在接收端判决时会产生判决错误，这种干扰称为乘性干扰；另一方面，信道中的噪声也会产生干扰，这种干扰随机地与信号叠加，使信号波形产生失真，也会引起判决错误，这种干扰称为加性干扰。3 3
2、第第9章章 差错控制编码差错控制编码对于乘性干扰，可以通过均衡器来消除码间串扰的影响。随机加性干扰通常由信道产生。根据随机加性干扰的不同特点，从差错控制角度看，相应的信道可以分为三类：随机信道、突发信道、混合信道。随机信道：这种信道中错码的出现是互不相关、统计独立的。比如，当信道中的随机加性干扰主要是高斯分布的白噪声时，引起的错码就具有这种性质。4 4第第9章章 差错控制编码差错控制编码突发信道：错码的出现是前后相关的。当错码出现时，会在短时间内有一连串的大量错码，而该时间过后又有较长的时间无错码。造成突发错码的原因是信道中存在随机的强突发脉冲干扰，比如，闪电、电焊、电火花干扰等。当信道中的随
3、机加性干扰主要是随机的强突发脉冲干扰时，称为突发信道。混合信道：以上两种随机干扰都存在，产生的错码既有随机错码又有突发错码，这种信道称为混合信道。5 5第第9章章 差错控制编码差错控制编码在介绍差错控制方式之前，下面先了解一下降低误码、提高数字通信可靠性的几种途径。根据实际通信系统对其可靠性的要求，可以用不同的方法提高通信的可靠性。(1)适当增加发送信号功率。增大信号的功率，即提高输入端的信噪比，可以减少信道中随机加性干扰对信号的影响，降低误码率，提高数字通信的可靠性。但是发送信号功率由于受到设备和环境条件的影响而不能无限增大。比如，空间探测器上的发射机由于其体积和重量受到限制，其发射功率不可
4、能无限增大。所以，此种方法在实际中受到了一定限制。6 6第第9章章 差错控制编码差错控制编码(2)选择抗噪声性能好的调制解调方式。比如，在数字调制中移相键控PSK比幅度键控ASK的误码率要小得多。所以在实际中多采用移相键控PSK，而很少采用幅度键控ASK。(3)采用最佳接收。最佳接收可以使数字通信的误码率达到最小。接收机中的滤波器可以是带通滤波器，也可以是匹配滤波器。在数字通信中可以采用匹配滤波接收，最大限度地抑制白噪声，在判决时刻达到最大输出信噪比，从而降低误码率。(4)采用差错控制编码。通过一定的编码和译码方法，采用前向纠错或检错重传技术，可以自动纠正传输错误。对于不同类型的信道，应采用不
5、同的差错控制方式。这是本章的主要内容。7 7第第9章章 差错控制编码差错控制编码9.1.2差错控制编码的基本方法与差错控制方式对于不同类型的信道，要采用不同的差错控制方式。不同的差错控制编码也要与相应的差错控制方式配合使用。常用的差错控制方式可分为以下四类：检错重发(ARQ)、前向纠错(FEC)、混合纠错检错(HEC)、信息反馈(IRQ，也称反馈校验)。图9.1所示为差错类型和差错控制方式。8 8第第9章章 差错控制编码差错控制编码图9.1差错类型和差错控制方式9 9第第9章章 差错控制编码差错控制编码1.检错重发(ARQ)方式检错重发方式又称为自动请求重发方式。这种差错控制方式在发送端对数据
6、序列进行分组编码，加入一定多余码元使之具有一定的检错能力，成为能够发现错误的码组。接收端收到码组后，按一定规则对其进行有无错误的判别，并把判决结果(应答信号)通过反向信道送回发送端。如果有错误，则发送端把前面发出的信息重新传送一次，直到接收端认为已正确收到信息为止。在具体实现检错重发系统时，通常有3种形式，即停发等候重发、返回重发和选择重发。ARQ方式的组成如图9.2所示。1010第第9章章 差错控制编码差错控制编码图9.2ARQ方式1111第第9章章 差错控制编码差错控制编码1)停止等待ARQ停止等待ARQ是最简单的ARQ系统，也称为空闲RQ(idleRQ)。这种系统每发送一个分组就停止发送
7、等待接收端的应答信号。收到接收端的确认应答后，再发送下一个分组。如果收到的是否认应答，则重发原分组。图9.3所示为停止等待ARQ发送端和接收端信号的传递过程示意图。1212第第9章章 差错控制编码差错控制编码图9.3停止等待ARQ1313第第9章章 差错控制编码差错控制编码2)连续ARQ连续ARQ工作在全双工方式，需要有一定的缓冲器容量。这种系统两端同时发送信息，发送端连续发送数据，并接收应答信号，接收端连续接收数据并发送应答信号。连续ARQ的工作原理如图9.4所示。与停止等待ARQ不同，其发送端无停顿地送出一个个连续码组，不再等候接收端返回的ACK信号，但一旦接收端发现错误并发回NAK信号，
8、则发送端从下一个码组开始重发前一段N组信号，N的大小取决于信号传递及处理所带来的延时，图9.4中N=5。1414第第9章章 差错控制编码差错控制编码图9.4连续ARQ的工作原理1515第第9章章 差错控制编码差错控制编码3)选择重发ARQ选择重发ARQ是由连续ARQ发展而来的，工作在全双工方式，需要有较大的缓冲器容量，其工作过程类似于连续ARQ。但在发送端重发时，不是将错误码组及其以后的码组全部重发，而是仅重发出错的码组。选择重发ARQ的工作原理如图9.5所示。1616第第9章章 差错控制编码差错控制编码图9.5选择重发ARQ1717第第9章章 差错控制编码差错控制编码2.前向纠错(FEC)方
9、式在前向纠错(FEC)方式中，发送端发出的码字不仅能够发现错误，而且能够纠正错误。在接收端译码后，若没有错误，则直接输出；若有错误，则在接收端自动纠正后再输出。这种方式不需要反向信道，特别适合于只能提供单向信道的场合。其优点是：能自动纠错，不要求检错重发，因而延时小，实时性好，传输效率高。其缺点是：所选择的纠错码必须与信道的错误特性密切配合，否则很难达到降低错码率的要求；为了能纠正较多的错码，译码设备复杂，且要求附加的监督码元也较多，传输效果也会降低。前向纠错(FEC)主要用于话音、广播、TV等通信中。1818第第9章章 差错控制编码差错控制编码3.混合纠错检错(HEC)方式混合纠错检错(HE
10、C)方式是将ARQ方式和FEC方式结合使用的一种方式。在混合纠错检错系统中，发送端发出同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力，则自行纠正，即FEC方式；如果干扰严重，错误很多，超出纠正能力，但能检测出来，则经反向信道要求发送端重发，即ARQ方式。一般的纠错编码能够检错和纠错的位数都是很有限的。比如，一种纠错编码能纠正一个码字内的两位错，检出三位错。当码组中出现两位以下错码时，它能自动纠正错码；当码组中出现两位以上错码时，它不能自动纠正。所以在传输错码较少时，采用前向纠错方式自动纠正错码；在错码较多时，采用ARQ方式自动请求重发。1919第第9章章 差错控
11、制编码差错控制编码4.反馈校验(IRQ)方式反馈校验(IRQ)方式也称为信息反馈方式或回程校验方式。在该方式中，发送端一边发送码字，一边将发送的码字在发送端缓冲存储。当接收端收到码字后，立即将接收到的码字返回发送端。发送端将返回的码字与发送端缓冲存储器中相应的码字进行比较，若发现与发送码不同，即认为产生了错误，就重发上一次的码字，直到发送端校验正确为止。利用这种方式进行差错控制时设备简单，但要求双向信道，并且传输效率很低。2020第第9章章 差错控制编码差错控制编码9.1.3纠错编码的基本原理1.有扰信道的编码定理香农有扰信道的编码定理指出：在有扰信道中只要信息的传输速率R小于信道容量C，总可
12、以找到一种编码方法，使信息以任意小的差错概率通过信道传送到接收端，即误码率Pe可以任意小，而且传输速率R可以接近信道容量C。但若RC，则在传输过程中必定会带来不可纠正错误，不存在使差错概率任意小的编码。其中，误码率：Pe=e-nE(R)(9.1)式中,n为编码的码字长度(简称码长)；E(R)为误码指数。E(R)与R、C有关，其关系可用曲线表示，如图9.6所示。2121第第9章章 差错控制编码差错控制编码图9.6E(R)与R的关系2222第第9章章 差错控制编码差错控制编码由式(9.1)及E(R)与R、C的关系曲线可以看出，要提高抗干扰能力，减小误码率Pe，有以下两种途径：(1)在编码长度n及信
13、息的传输速率R一定时，为减小Pe，可以增加信道容量C。由图9.6可见，E(R)随信道容量C的增加而增大。由式(9.1)可见，误码率Pe随E(R)的增大而指数减小，即增加信道容量可以减小误码率。由信道容量公式可见，要增加信道容量C，可以通过增加信号功率P和系统带宽B来实现，即通过增加信号功率P和系统带宽B可以减小误码率。2323第第9章章 差错控制编码差错控制编码(2)在信道容量C及信息的传输速率R一定的情况下，由式(9.1)可知，增加码长n也可以使误码率Pe指数减小，即通过增加信道中传输信息的码长可以减小误码率。香农有扰信道的编码定理本身并未给出具体的纠错编码方法，但它为信道编码奠定了理论基础
14、，从理论上指出了信道编码的发展方向。2424第第9章章 差错控制编码差错控制编码2.纠错编码原理纠错编码原理为：利用增加信息的编码长度(附加监督码)来减小误码率。2525第第9章章 差错控制编码差错控制编码最大似然译码准则：在收到码r的条件下，计算2k个(许用码的个数)条件概率，其中CL为许用码字，若条件概率为最大，则认为收到的码字r就是发送来的CL码字。可用下式计算：(9.2)式中:ri为接收码字的第i位元素；CLi为许用码字CL的第i位元素。2626第第9章章 差错控制编码差错控制编码显然，当接收码元出错，即riCLi时，概率;当码元接收正确，即ri=CLi时，概率。令d为接收的码字与许用
15、码CL之间不同的位数(即出错位的位数)，则式(9.2)可以写成：(9.3)2727第第9章章 差错控制编码差错控制编码可见，由于，随d单调下降，因此，d越小，越大。越大表明接收到的码字r越像码字CL，而不像其他许用码，因为传输中码字错的位数多比错的位数少出现的概率更小。2828第第9章章 差错控制编码差错控制编码9.1.4码间距离d与检错纠错能力1 码间距离d码间距离(code distances)是一个码组中任意两个码字之间对应位上码元取值不同的位数，用d表示。码间距离简称码距，又称为汉明(Hamming)距离。码间距离d可用下式计算:(9.4)即码间距离d等于两个码字对应位模2相加后“1”
16、的个数。2929第第9章章 差错控制编码差错控制编码 一般两个码字的码距计算方法为：设两个码字Ci、Cj分别为101110 和 101011，则码距可按下式计算:故d(Ci,Cj)=2。3030第第9章章 差错控制编码差错控制编码在一个码组中，各码字之间的距离不一定都相等，有的大，有的小。通常称码组中最小的码距为最小码间距离，用d0表示。由上述重复编码的例子可知，两个码字之间不同的位数越多，其检错纠错能力越强，即码间距离越大，其检错纠错能力越强。所以一个码组的最小码间距离d0就决定了该码组的检错纠错能力。3131第第9章章 差错控制编码差错控制编码对于三位编码的码间距离，可用三维几何空间来说明
17、。三位编码的码字共有23=8个，用三维几何空间立方体的8个顶点来表示，如图9.7所示。码字之间的距离可用对应两顶点间沿立方体各棱行走的最短几何距离来示意。由图9.7可见，对上述重复编码的例子，其码组只有“111”、“000”两个许用码，从“111”到“000”要经过三条边，显然它们之间的距离为d=3。同样，对于多位编码的码间距离，可用多维空间来说明。3232第第9章章 差错控制编码差错控制编码图9.7码间距离的几何意义3333第第9章章 差错控制编码差错控制编码2.最小距离d0与检错纠错能力的关系(1)当码组仅用于检测错误时，若要求检测e个错误，则最小码距为d0=e+1 (9.5)这可由图9.
18、8(a)来说明。图中，A为一个码字，B为另一个码字。若码字A有两位错，A变为以2为半径的圆上某点，则只要最小码距不小于3，在半径为2的圆上及圆内就不会有其他许用码，因而能检测错码的位数等于2，即最小码距为d0，能检测d01个错码。若要检测e个错码，则必须满足d0e+1的要求。3434第第9章章 差错控制编码差错控制编码图9.8码间距离与检错纠错能力的关系3535第第9章章 差错控制编码差错控制编码(2)当码组仅用于纠正错误时，为纠正t个错误，要求最小码距为d0e+t (9.6)这可用图9.8(b)来说明。码字A发生两位错，落在以A为圆心、以2为半径的圆上某点。码字B有两位错，落在以B为圆心、以
19、2为半径的圆上某点。只要这两个圆不重叠、不相交，就能区分判别出左边圆上的为码字A，右边圆上的为码字B。可见，能纠正两位错码，要求的最小码距为5。所以纠正t个错误，必须满足d02t+1的要求。3636第第9章章 差错控制编码差错控制编码(3)当码组既要检错，又要纠错时，为纠正t个错误，同时检测e个错误，要求的最小码距为d0e+t+1et (9.7)这可用图9.4(c)来说明。当码字A出现e个错误时，将落在以A为圆心、以e为半径的圆上某点。码字B出现t个错误，将落在以B为圆心、以t为半径的圆上某点。要纠正码字B的错误，同时又能检出码字A的错误，就要求A的大圆和B的小圆不相交、不重叠，即A和B之间的
20、距离要大于e+t，也即最小码距d0e+t+1。3737第第9章章 差错控制编码差错控制编码3 差错控制编码的效果对于随机错误的情况，假设误码率为P，且Pk，则这2k个码组的集合就称做分组码。简单地讲，将信息码进行分组，然后为每组信息码附加若干位监督码元的编码方法所得到的编码集合称为分组码。5353第第9章章 差错控制编码差错控制编码所谓线性分组码，就是一种长度为n，其中2k个许用码组(代表信息的码组)中的任意两个码组的模2和仍为一个许用码组的分组码。这种长度为n，有2k个码组的线性分组码称为线性(n，k)码(或(n，k)线性码)。线性分组码有两个重要性质：其一是封闭性，即任意两个许用码组之模2
21、和仍为一许用码组；其二是码组的最小码距等于非零码的最小码重。5454第第9章章 差错控制编码差错控制编码线性分组码的构成方法是：将信息序列分为每k位一组的信息序列段，每一信息序列段按照一定规律添加r个监督码元，构成总码长为n=k+r的分组码，记为(n,k)。在分组码中，监督码元仅与本分组中的信息码元有关，监督码元只监督本码字中的信息码元。当监督码元与信息码元之间的关系为线性关系，即监督码元与信息码元之间的关系可用模2加代数方程描述时，称其为线性分组码。线性码是建立在代数学中群论的基础上的。线性码的各许用码的集合构成代数学中的群，又称为群码。5555第第9章章 差错控制编码差错控制编码表9.2示
22、出了线性分组码的一种结构。码字的前一部分是连续k个信息码元，后一部分是连续r个监督码元，具有这种结构的线性分组码称为系统码。不按这种结构顺序排列的线性分组码称为非系统码。5656第第9章章 差错控制编码差错控制编码5757第第9章章 差错控制编码差错控制编码9.3.2线性分组码的监督矩阵假定监督码元与信息码元的关系由下列线性方程组决定:(9.16)5858第第9章章 差错控制编码差错控制编码对式(9.16)移项后可得三个监督关系式(该方程组在二元有限域上求解，系数取值为“0”或“1”):(9.17)按照监督关系式(9.16)或式(9.17)可以确定(7，4)码的许用码共有24=16种，这是从2
23、7=128种组合中选出的，如表9.3所示。该(7，4)码的全部许用码字都必须受上述监督方程组的监督和检验，因此又称为一致监督方程。5959第第9章章 差错控制编码差错控制编码6060第第9章章 差错控制编码差错控制编码将式(9.17)中的零系数项补上，写出系数可得：(9.18)6161第第9章章 差错控制编码差错控制编码把式(9.18)写成矩阵形式如下:(9.19)6262第第9章章 差错控制编码差错控制编码将式(9.16)写成矩阵形式:(9.20)式中,6363第第9章章 差错控制编码差错控制编码令式(9.19)的系数矩阵为 (9.21)式(9.19)可简写为 HCT=0T或CHT=0 (9
24、.22)其中，行矩阵C=c6c5c4c3c2c1c0为码字矢量;0=000;CT、0T、HT分别为C、0、H的转置矩阵。6464第第9章章 差错控制编码差错控制编码进一步分析H，利用矩阵分块的方法，H可写为(9.23)6565第第9章章 差错控制编码差错控制编码其中,P见式(9.20)，I3为3阶单位矩阵，即 (9.24)6666第第9章章 差错控制编码差错控制编码对于(n，k)分组码，r=nk，H 可写为 (9.25)其中,P为rk阶矩阵，Ir为r阶单位矩阵。具有这种形式的H矩阵称为典型监督矩阵。典型监督矩阵H中的每一行都是彼此独立的，即线性不相关，不能从几个方程的组合推出方程组的另一个方程
25、。应当注意，各种码的H矩阵不一定是典型阵，只有系统码才符合。6767第第9章章 差错控制编码差错控制编码9.3.3线性分组码的生成矩阵生成矩阵是在已知信息码元时确定相应的许用码字C=c6c5c4c3c2c1c0的矩阵。由式(9.16)已经可以产生监督码元c2c1c0，只要在其中添上信息码元的方程即可得出许用码字，即 (9.26)6868第第9章章 差错控制编码差错控制编码将式(9.26)写成矩阵形式:(9.27)6969第第9章章 差错控制编码差错控制编码对式(9.27)取转置得：(9.28)7070第第9章章 差错控制编码差错控制编码式中：(9.29)7171第第9章章 差错控制编码差错控制
26、编码其中:(9.30)矩阵G称为线性分组码的生成矩阵。G为kn阶矩阵，行数为信息位的个数，列数为码字的长度。已知矩阵G和信息码，由式(9.28)可生成许用码字C。7272第第9章章 差错控制编码差错控制编码由式(9.29)得，G=IkQ，其中Ik为k阶单位矩阵。这种形式的生成矩阵G是典型生成矩阵。同样，典型生成矩阵的各行也是线性无关的。由典型生成矩阵得出的码字C是信息位在前、监督位在后的系统码。实际上G中的每一行都是一个许用码字。G中的第一行、第二行、第三行、第四行分别是信息位为1000、0100、0010、0001 时计算出的许用码字。由式(9.29)可知，Q=PT(或P=QT)，而H=PI
27、r，G=IkQ，所以若H和G已知其中一个，则另一个确定，其监督关系和它所对应的码也就确定了。7373第第9章章 差错控制编码差错控制编码在线性分组码中，任意两个许用码字对应位模2相加还是此码组中的一个码字，所以线性分组码具有封闭性。对(n，k)线性分组码来说，其信息位长为k，共有2k个不同组合的信息码。设Cix、Cjx为其中两个信息码，由式(9.28)可算出它们所对应的许用码字Ci=CixG，Cj=CjxG,所以 (9.31)式中，Cl是一个k位的二元序列，它必然是2k个不同组合的信息码中的一个，所以Ci Cj必然是生成矩阵为G 的线性分组码中的一个许用码字。7474第第9章章 差错控制编码差
28、错控制编码(n，k)线性分组码A的生成矩阵G的每一行都是码组A的一个许用码字，它一定满足H矩阵所确定的r个监督关系。如果把G当作另一个码组B的监督矩阵，把H当作码组B的生成矩阵，则码组B为(n，nk)线性分组码，H的每一行一定满足G矩阵所确定的k个监督关系。这样的码组A和码组B称为对偶码。线性分组码的最小距离dmin等于该码的最小重量(除全“0”码字外)，即 (9.32)7575第第9章章 差错控制编码差错控制编码由于线性分组码具有封闭性，因此由码距的定义可知，任意两个许用码字之间的距离必然是另一个许用码字的重量。所以，该码的最小重量(除全“0”码字外)必然是该线性分组码的最小距离。对线性分组
29、码，由监督矩阵H中线性不相关的列数可以得到线性分组码中最小码距的上界，即 (9.33)7676第第9章章 差错控制编码差错控制编码由CHT=0可见，当C取最小重量的码字，即C中“1”的个数为Wmin时，得到H中最小相关的列的数目，即H中小于或等于Wmin1 列是线性独立的、不相关的。H为 nk行的矩阵，其最大的秩为nk。根据矩阵的性质，H中最大不相关的列数小于或等于H的秩，则Wmin1nk，即dmin1nk，或写为dminnk+1=r+1。当上式取等号时，dmin=nk+1=r+1，称为最大可辨距离。7777第第9章章 差错控制编码差错控制编码9.3.4线性分组码的伴随式和检错纠错能力设发送端
30、发出的许用码为C=cn-1cn-2c1c0，它符合CHT=0。假设经过信道传输后接收端收到的码字为R=rn-1rn-2 r1r0。如果R=C，把R代入式(9.22)中计算，则RHT=0,判断为正确。由于传输误差R与C不一定相同，因此其误差为 (9.34)7878第第9章章 差错控制编码差错控制编码E称为差错序列或错误图样。因为E表示R中具体哪一位发生错误，即把R代入式(9.22)得：或(9.35)7979第第9章章 差错控制编码差错控制编码其中，S=sn-1sn-2s1s0，为1r阶行矢量。由式(9.35)可见，S只与错误图样E有关，而与发送的码字C无关，这意味着S与E有线性变换关系，能与E一
31、一对应，可指示错码位置，所以S称为监督矩阵为H的(n，k)线性分组码的伴随式。当E=000001n时，S=000001r；当E不为零时，S不为零。译码器可通过伴随式S进行检错纠错。如果S为零，则译码器判断接收码字正确，并从该码字中除去监督位，然后输出信息位;如果S不为零，则必定有错，由S可判断出错码的位置。8080第第9章章 差错控制编码差错控制编码下面以(7，4)码为例进行说明。设C=0001011,若传输中c3发生误码,即发生一位错,E=0001000,R=0000011,则由式(9.35)可得：(9.36)8181第第9章章 差错控制编码差错控制编码可见,ST刚好是错误图样E中“1”所对
32、应的H中的一列，即R的第i位有错，则E的第i位为“1”，ST与H中的第i列相同。判断出错误后，可利用R E=C纠错。对于前面所介绍的偶校验码，当总码长为n时即为(n，n-1)线性分组码。它只有一位监督码元c0，其构成的监督关系式见式(9.11)。在接收端进行解码校验时，要判断接收到的码是否满足监督关系式(9.11)，实际上就是计算线性分组码的伴随式S，即8282第第9章章 差错控制编码差错控制编码当S=0时，符合监督关系式，判断接收到的码无错；当S=1时，不符合监督关系式，就认为有错。S的取值只有两个，它只能表示无错、有错两种状态，而无法指出错在哪一位，因此，它只能检错，不能纠错。如果再增加一
33、位监督位，相应地再增加一个监督关系式，那么S就有4种情况00、01、10、11。用其中一种00表示无错，剩余的3种能够用来指示一位错码的三种不同位置，即具有纠错功能。同理，如果有r个监督位，即有r个监督关系式，则它可以指示出一位错码的2r1个可能的位置。8383第第9章章 差错控制编码差错控制编码由以上分析可知，对(n，k)线性分组码，有r=nk个监督关系式，有2r个不同的S。全0矢量表示无错，所以S最多可指出2r1种错误。要纠正所有小于或等于t个错，必须满足:(9.37)8484第第9章章 差错控制编码差错控制编码其中,Cin为组合数,即 (9.38)式(9.38)说明了监督位数r与纠错能力
34、的关系。当式(9.38)取等号时，2r最小，即r达到满足要求时的最小值，此时监督位利用得最充分，称为完备码。8585第第9章章 差错控制编码差错控制编码线性分组码的主要性质如下：(1)封闭性。封闭性是指码中任意两个许用码组之和(逐位模2和)仍为一个许用码组。也就是说，若C1和C2为分组码中的两个许用码组，则C1 C2仍为其中的一个许用码组。(2)码的最小距离等于非零码的最小重量。因为线性分组码具有封闭性，所以两个码组之间的距离必是另一码组的重量。为此，码的最小距离也就是码的最小重量，当然，除全“0”码组外。8686第第9章章 差错控制编码差错控制编码在通信传输过程中如果错码较多，已超过这种编码
35、的检错能力，即R变为另一许用码组，则式(9.22)仍成立。由于线性分组码具有封闭性质，因此由式(9.34)中R=C E可知，只有当E=C，即错误码组刚好等于任意许用码组时，S=0，即不能检测错码。设(n，k)线性分组码最大检错的个数为D，信道的误码率为Pe，那么不能检错的概率为 (9.39)其中，Wi是重量为i的许用码组数目。8787第第9章章 差错控制编码差错控制编码9.3.5汉明码汉明码是一种可以纠正单个随机错误的线性分组码，它是一种完备码，编码效率很高。在式(9.37)中，令t=1(即纠正一位错)，并取等号得:2r1=n (9.40)此时构成(2r1，2r1r)汉明码。汉明码具有以下特点
36、(m为任意正整数，m3)：监督位长 r=m，码长n=2r1=2m1，信息位长k=nr=2r1r=2m1m，最小码距d0=3，纠错能力t=1,编码效率，n越大，越高。8888第第9章章 差错控制编码差错控制编码(7，4)汉明码的典型监督矩阵H和生成矩阵G如下:(9.42)(9.41)8989第第9章章 差错控制编码差错控制编码汉明码只能纠正一位错，其最小码距d0=3。当码字中出现两位错时，它检测不出来，必然会造成错判。如果在汉明码的基础上增加一位对所有码元都进行校验的监督码元，则监督码元的位数由原来的m变为m+1。码长由原来的2m1变为2m，信息位长度不变，形成(2m，2m1m)的线性码，这种码
37、称为增余汉明码或扩展汉明码。增余汉明码的最小码距在汉明码的基础上增加了一位，变为4。所以，增余汉明码不仅能纠正一位错，同时也能检测2位错。9090第第9章章 差错控制编码差错控制编码增余汉明码的构成是增加一位监督码元，使原汉明码的最小码重由奇数变为偶数。其监督矩阵可以由原汉明码的监督矩阵H得到：(9.43)He即为增余汉明码的监督矩阵，它是在H的右边增加一列全0，再在最后一行添加一行全1构成的。9191第第9章章 差错控制编码差错控制编码如果把上述(7，4)汉明码变为对应的(8，4)增余汉明码，则其监督矩阵为(9.44)9292第第9章章 差错控制编码差错控制编码9.4循环码9.4.1循环码的
38、循环特性与码多项式循环码是线性分组码的一个重要分支。循环码除了具有线性码的一般性质外，还具有循环性，即任一码字循环一位(将最右端的码元移至左端，或反之)以后，仍为该码中的一个码字。循环码有许多特殊的代数性质，基于这些性质，循环码有较强的纠错能力，而且其编码和译码电路很容易用移位寄存器实现，因而在前向纠错(FEC)系统中得到了广泛的应用。9393第第9章章 差错控制编码差错控制编码对于一个(n，k)线性码C，若其中的任一码组向左或向右循环移动任意位后仍是C中的一个码组，则称C是一个循环码。循环码是一种线性分组码，它除了具有线性分组码的封闭性之外，还具有循环性。通常其前k位是信息码元，后r位为监督
39、码元，具有系统码的形式。循环性是指循环码集中的任一许用码字(全“0”码除外)循环左移(或循环右移)后所得到的码字仍为该循环码中的一个许用码字。设码字矢量C=cn-1cn-2c1c0是码长为n的循环码中的一个码字。对其进行循环左移、右移，无论循环左移、右移多少位，得到的结果均为该循环码中的一个码字。9494第第9章章 差错控制编码差错控制编码下式所示的码字均为该循环码中的一个码字:(9.45)表9.4列出了一种(7，3)循环码的全部许用码字。9595第第9章章 差错控制编码差错控制编码9696第第9章章 差错控制编码差错控制编码为了便于用代数学的理论分析计算循环码，可把循环码中的码字用多项式来表
40、示，称为码多项式，也就是把码字中各码元的取值作为码多项式的系数。对于码字矢量C=cn-1cn-2c1c0,可以用码多项式表示为T(x)=cn-1xn-1+cn-2xn-2+c1x1+c0 (9.46)9797第第9章章 差错控制编码差错控制编码其中,xi是码元位置的标记，它表示由其系数所决定的码元取值所处的对应位置，其系数只能取0或1，运算时其系数的运算为模2运算。例如，码字1001110、0011101可用码多项式表示为T1(x)=1x6+0 x5+0 x4+1x3+1x2+1x1+0 x0=x6+x3+x2+xT2(x)=0 x6+0 x5+1x4+1x3+1x2+0 x1+1x0=x4+
41、x3+x2+1则T1(x)+T2(x)=x6+x4+x1+1即1001110 0011101=1010011 9898第第9章章 差错控制编码差错控制编码在整数的按模运算中，最熟悉的是模2运算，如1+10(模2)，1+21(模2)等。对于模n运算，如果一个整数m可以表示为 (9.47)其中,Q为整数，p为m被n除后所得的余数,那么mp(模n)(9.48)称m与p是同余的。9999第第9章章 差错控制编码差错控制编码在多项式中同样可以进行类似的按模运算，如 (9.49)其中:F(x)是幂次为n的多项式;Q(x)为商;R(x)为幂次低于n的余式;多项式的系数在二元域上。式(9.49)可写为 F(x
42、)=Q(x)N(x)+R(x)(9.50)所以 F(x)R(x)(模N(x)(9.51)即F(x)与R(x)是同余的。100100第第9章章 差错控制编码差错控制编码码多项式系数仍按模2运算，即只取值0和1。比如,x3被x3+1除可得余式为1，于是有：x31(模x3+1)(9.52)由此可见，为了使xn=1，只需做模xn+1的运算即可。同理有:x4+x2+1x2+x+1(模x3+1)(9.53)循环码的码多项式符合如下定理。101101第第9章章 差错控制编码差错控制编码定理定理9.4.1若T(x)是长为n的循环码中某个许用码组的码多项式，则xiT(x)在按模xn+1运算下也是该循环码中一个许
43、用码组的码多项式。例如,(7，3)循环码中许用码组0011101的码多项式为T(x)=x4+x3+x2+1，则x3T(x)x6+x5+x3+1(模x7+1)x6+x5+x3+1对应的码字为1101001，它是该(7，3)循环码中的一个许用码组，而且它是上述循环码0011101左移3次后形成的。102102第第9章章 差错控制编码差错控制编码定理9.4.1证明如下：设T(x)=cn-1xn-1+cn-2xn-2+c1x1+c0，那么有即xiT(x)R(x)(模xn+1)(9.54)103103第第9章章 差错控制编码差错控制编码其中,Ri(x)=cn-1-ixn-1+cn-2-ixn-2+c0
44、xi+cn-1xi-1+cn-i是T(x)左移i位后形成的码字。若把i取不同的值重复做上述运算，则可得到该循环码的其他许用码字。所以，码长为n的循环码的每一个许用码字都是按模xn+1运算的余式。如果已知码多项式T(x)，则相应的循环码就可以由xiT(x)按模xn+1运算的余式求得。104104第第9章章 差错控制编码差错控制编码9.4.2循环码的生成多项式与生成矩阵循环码的生成多项式与生成矩阵定理定理9.4.2在循环码(n,k)中，nk次幂的码多项式有一个，且仅有一个,用g(x)表示,称为循环码的生成多项式。g(x)的常数项不为零。105105第第9章章 差错控制编码差错控制编码一旦g(x)确
45、定，该(n,k)循环码就被确定了。g(x)是循环码中幂次最低的码多项式。由它左移就可产生其他码多项式，比如xg(x)、x2g(x)、x3g(x)等。用k个互相独立的码多项式g(x)、xg(x)、x2g(x)、x3g(x)、xk-1g(x)可以构造出循环码的生成矩阵G(x):(9.55)106106第第9章章 差错控制编码差错控制编码例如，有一个(7，3)循环码(其最高次幂为(n,k)次)的码字为0010111，其生成多项式g(x)=x4+x2+x+1，则利用式(9.55)可得其生成矩阵G(x)：(9.56)107107第第9章章 差错控制编码差错控制编码将此生成矩阵用系数表示，写为生成矩阵G:
46、(9.57)式(9.57)不符合典型生成矩阵的形式，所以它不是典型生成矩阵，由它编出的码字不是系统码，但是对此矩阵作线性变换(行变换)可以变换成典型生成矩阵的形式。108108第第9章章 差错控制编码差错控制编码例如，对于(7，3)循环码，设信息码为c6c5c4，由生成矩阵多项式可以写出该循环码的码字:(9.58)式中,u(x)为信息码c6c5c4的多项式。109109第第9章章 差错控制编码差错控制编码因此，已知信息码U=uk-1uk-2u1u0和g(x)就可求得循环码的所有码多项式:T(x)=uk-1uk-2u1u0G(x)=u(x)g(x)(9.59)其中,u(x)为信息位所对应的多项式
47、。信息位有k位，所以u(x)的最高阶数为k1次幂。此种方法求得的码多项式为非系统码。由式(9.59)还可见，所有的码多项式都可以被g(x)整除。110110第第9章章 差错控制编码差错控制编码定理定理9.4.3循环码(n,k)的生成多项式g(x)是xn+1的一个因式。定理分析定理分析：g(x)是最高次幂为nk次的码多项式。xkg(x)是最高次幂为n的多项式。利用定理9.4.1对xkg(x)作模xn+1运算，则 (9.60)R(x)也是该循环码的一个码多项式，它可以被g(x)整除，即R(x)=I(x)g(x),代入式(9.60)得：xkg(x)=(xn+1)+R(x)=(xn+1)+I(x)g(
48、x)111111第第9章章 差错控制编码差错控制编码对上式移项得:xn+1=xkg(x)+I(x)g(x)=xk+I(x)g(x)=h(x)g(x)(9.61)即g(x)是xn+1的因式。式中为循环码的一致校验多项式。由式(9.61)可见,g(x)是xn+1的一个因式。利用这一特点就可以产生g(x)，即可以通过对xn+1的因式分解得到g(x)。其方法是对(xn+1)进行因式分解，从中找出一个最高次幂为nk次且常数项不为零的因式作为生成多项式g(x)。112112第第9章章 差错控制编码差错控制编码例如,对于(7，3)循环码，g(x)的最高次幂为4,可以从x7+1中分解得到g(x)。x7+1 可
49、分解为x7+1=(x+1)(x3+x2+1)(x3+x+1)(9.62)生成多项式可选为g1(x)=(x+1)(x3+x2+1)=x4+x2+x+1 (9.63)或者g2(x)=(x+1)(x3+x+1)=x4+x3+x2+1 (9.64)两种生成多项式g1(x)或g2(x)可以产生两种(7，3)循环码。113113第第9章章 差错控制编码差错控制编码9.4.3循环码的编码与解码循环码的编码与解码1 循环码的编码循环码的编码在编码时，首先要根据给定的(n,k)值选定生成多项式g(x)，即应在xn+1的因式中选一个nk次多项式作为g(x)。对(n,k)循环码，通过对xn+1进行因式分解选择出生成
50、多项式g(x)，就可由信息码编出相应的循环码字。下面讨论如何从g(x)和信息码直接编出相应的系统码。设信息码多项式为m(x)=mk-1xk-1+mk-2xk-2+m1x1+m0 (9.65)114114第第9章章 差错控制编码差错控制编码信息码多项式m(x)的最高次幂为k1。将m(x)左移nk位成为xn-km(x)，其最高次幂为n-1。xn-km(x)的前一部分为连续k位信息码，后一部分为r=nk位“0”，r正好是监督码的位数,所以在它的后一部分添上监督码，就编出了相应的系统码。监督码由监督关系确定，循环码的生成多项式g(x)确定循环码，因此g(x)也确定监督关系。由上述分析可知，循环码的任何
