《现代通信原理、技术与仿真第9章 差错控制编码.ppt》由会员分享，可在线阅读，更多相关《现代通信原理、技术与仿真第9章 差错控制编码.ppt（264页珍藏版）》请在三一文库上搜索。
1、,第9章 差错控制编码,9.1 差错控制编码原理 9.2 常用简单差错控制编码 9.3 线性分组码 9.4 循环码 9.5 卷积码 本章仿真实验举例 习题,9.1 差错控制编码原理 9.1.1 引起误码的原因与降低误码的常用方法 数字信号在实际通信过程中不可避免地会发生错误。这是因为，一方面通信系统的特性并非完全理想，数字信号波形通过这样的通信系统时会产生波形失真，因而在接收端判决时会产生判决错误，这种干扰称为乘性干扰；另一方面，信道中的噪声也会产生干扰，这种干扰随机地与信号叠加，使信号波形产生失真，也会引起判决错误，这种干扰称为加性干扰。,对于乘性干扰，可以通过均衡器来消除码间串扰的影响。随
2、机加性干扰通常由信道产生。根据随机加性干扰的不同特点，从差错控制角度看，相应的信道可以分为三类：随机信道、突发信道、混合信道。 随机信道：这种信道中错码的出现是互不相关、统计独立的。比如，当信道中的随机加性干扰主要是高斯分布的白噪声时，引起的错码就具有这种性质。,突发信道：错码的出现是前后相关的。当错码出现时，会在短时间内有一连串的大量错码，而该时间过后又有较长的时间无错码。造成突发错码的原因是信道中存在随机的强突发脉冲干扰，比如，闪电、电焊、电火花干扰等。当信道中的随机加性干扰主要是随机的强突发脉冲干扰时，称为突发信道。 混合信道：以上两种随机干扰都存在，产生的错码既有随机错码又有突发错码，
3、这种信道称为混合信道。,在介绍差错控制方式之前，下面先了解一下降低误码、提高数字通信可靠性的几种途径。根据实际通信系统对其可靠性的要求，可以用不同的方法提高通信的可靠性。 (1) 适当增加发送信号功率。增大信号的功率，即提高输入端的信噪比，可以减少信道中随机加性干扰对信号的影响，降低误码率，提高数字通信的可靠性。但是发送信号功率由于受到设备和环境条件的影响而不能无限增大。比如，空间探测器上的发射机由于其体积和重量受到限制，其发射功率不可能 无限增大。所以，此种方法在实际中受到了一定限制。,(2) 选择抗噪声性能好的调制解调方式。比如，在数字调制中移相键控PSK比幅度键控ASK的误码率要小得多。
4、所以在实际中多采用移相键控PSK，而很少采用幅度键控ASK。 (3) 采用最佳接收。最佳接收可以使数字通信的误码率达到最小。接收机中的滤波器可以是带通滤波器，也可以是匹配滤波器。在数字通信中可以采用匹配滤波接收，最大限度地抑制白噪声，在判决时刻达到最大输出信噪比，从而降低误码率。 (4) 采用差错控制编码。通过一定的编码和译码方法，采用前向纠错或检错重传技术，可以自动纠正传输错误。对于不同类型的信道，应采用不同的差错控制方式。这是本章的主要内容。,9.1.2 差错控制编码的基本方法与差错控制方式 对于不同类型的信道，要采用不同的差错控制方式。不同的差错控制编码也要与相应的差错控制方式配合使用。
5、 常用的差错控制方式可分为以下四类：检错重发(ARQ)、前向纠错(FEC)、混合纠错检错(HEC)、信息反馈(IRQ，也称反馈校验)。图9.1所示为差错类型和差错控制方式。,图9.1 差错类型和差错控制方式,1. 检错重发(ARQ)方式 检错重发方式又称为自动请求重发方式。这种差错控制方式在发送端对数据序列进行分组编码，加入一定多余码元使之具有一定的检错能力，成为能够发现错误的码组。接收端收到码组后，按一定规则对其进行有无错误的判别，并把判决结果(应答信号)通过反向信道送回发送端。如果有错误，则发送端 把前面发出的信息重新传送一次，直到接收端认为已正确收到信息为止。在具体实现检错重发系统时，通
6、常有3种形式，即停发等候重发、返回重发和选择重发。 ARQ方式的组成如图9.2所示。,图9.2 ARQ方式,1) 停止等待ARQ 停止等待ARQ是最简单的ARQ系统，也称为空闲RQ(idleRQ)。这种系统每发送一个分组就停止发送等待接收端的应答信号。收到接收端的确认应答后，再发送下一个分组。如果收到的是否认应答，则重发原分组。图9.3所示为停止等待ARQ发送端和接收端信号的传递过程示意图。,图9.3 停止等待ARQ,2) 连续ARQ 连续ARQ工作在全双工方式，需要有一定的缓冲器容量。这种系统两端同时发送信息，发送端连续发送数据，并接收应答信号，接收端连续接收数据并发送应答信号。连续ARQ的
7、工作原理如图9.4所示。与停止等待ARQ不同，其发送端无停顿地送出一个个连续码组，不再等候接收端返回的ACK信号，但一旦接收端发现错误并发回NAK信号，则发送端从下一个码组开始重发前一段N组信号，N的大小取决于信号传递及处理 所带来的延时，图9.4中N=5。,图9.4 连续ARQ的工作原理,3) 选择重发ARQ 选择重发ARQ是由连续ARQ发展而来的，工作在全双工方式，需要有较大的缓冲器容量，其工作过程类似于连续ARQ。但在发送端重发时，不是将错误码组及其以后的码组全部重发，而是仅重发出错的码组。选择重发ARQ的工作原理如图9.5所示。,图9.5 选择重发ARQ,2. 前向纠错(FEC)方式
8、在前向纠错(FEC)方式中，发送端发出的码字不仅能够发现错误，而且能够纠正错误。在接收端译码后，若没有错误，则直接输出；若有错误，则在接收端自动纠正后再输出。这种方式不需要反向信道，特别适合于只能提供单向信道的场合。其优点是：能自动纠错，不要求检错重发，因而延时小，实时 性好，传输效率高。其缺点是：所选择的纠错码必须与信道的错误特性密切配合，否则很难达到降低错码率的要求；为了能纠正较多的错码，译码设备复杂，且要求附加的监督码元也较多，传输效果也会降低。前向纠错(FEC)主要用于话音、广播、TV等通信中。,3. 混合纠错检错(HEC)方式 混合纠错检错(HEC)方式是将ARQ方式和FEC方式结合
9、使用的一种方式。在混合纠错检错系统中，发送端发出同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力，则自行纠正，即FEC方式；如果干扰严重，错误很多，超出纠正能力，但能检测出来，则经反向信道要求发送端重发，即ARQ方式。一般的纠错编码能够检错和纠错的位数都是很有限的。比如，一种纠错编码能纠正一个码字内的两位错，检出三位错。当码组中出现两位以下错码时，它能自动纠正错码；当码组中出现两位以上错码时，它不能自动纠正。所以在传输错码较少时，采用前向纠错方式自动纠正错码；在错码较多时，采用ARQ方式自动请求重发。,4. 反馈校验(IRQ)方式 反馈校验(IRQ)方式也称为信息
10、反馈方式或回程校验方式。在该方式中，发送端一边发送码字，一边将发送的码字在发送端缓冲存储。当接收端收到码字后，立即将接收到的码字返回发送端。发送端将返回的码字与发送端缓冲存储器中相应的码字进行比较，若发现与发送码不同，即认为产生了错误，就重发上一次的码字，直到发送端校验正确为止。利用这种方式进行差错控制时设备简单，但要求双向信道，并且传输效率很低。,9.1.3 纠错编码的基本原理 1. 有扰信道的编码定理 香农有扰信道的编码定理指出：在有扰信道中只要信息的传输速率R小于信道容量C，总可以找到一种编码方法，使信息以任意小的差错概率通过信道传送到接收端，即误码率Pe可以任意小，而且传输速率R可以接
11、近信道容量C。但若RC，则在传输过程中必定会带来不可纠正错误，不存在使差错概率任意小的编码。其中，误码率： Pe=e-nE(R) (9.1) 式中, n为编码的码字长度(简称码长)；E(R)为误码指数。E(R)与R、C有关，其关系可用曲线表示，如图9.6所示。,图9.6 E(R)与R的关系,由式(9.1)及E(R)与R、C的关系曲线可以看出，要提高抗干扰能力，减小误码率Pe，有以下两种途径： (1) 在编码长度n及信息的传输速率R一定时，为减小Pe，可以增加信道容量C。由图9.6可见，E(R)随信道容量C的 增加而增大。由式(9.1)可见，误码率Pe随E(R)的增大而指数 减小，即增加信道容量
12、可以减小误码率。由信道容量公式 可见，要增加信道容量C，可以通过增加信号功率P和系统带宽B来实现，即通过增加信号功率P和系统带宽B可以减小误码率。,(2) 在信道容量C及信息的传输速率R一定的情况下，由式(9.1)可知，增加码长n也可以使误码率Pe指数减小，即通过增加信道中传输信息的码长可以减小误码率。 香农有扰信道的编码定理本身并未给出具体的纠错编码方法，但它为信道编码奠定了理论基础，从理论上指出了信道编码的发展方向。,2. 纠错编码原理 纠错编码原理为：利用增加信息的编码长度(附加监督码)来减小误码率。,最大似然译码准则：在收到码r的条件下，计算2k个(许用码的个数)条件概率 ，其中CL为
13、许用码字，若条件概率 为最大，则认为收到的码字r就是发送来的CL码字。 可用下式计算： (9.2) 式中: ri为接收码字的第i位元素；CLi为许用码字CL的第i位元素。,显然，当接收码元出错，即riCLi时，概率 ; 当码元接收正确，即ri=CLi时，概率 。令d为接收的码字与许用码CL之间不同的位数(即出错位的位数)，则式(9.2)可以写成： (9.3),可见，由于 ， 随d单调下降，因此，d越小， 越大。 越大表明接收到的码字r越像码字CL，而不像其他许用码，因为传输中码字错的位数多比错的位数少出现的概率更小。,9.1.4 码间距离d与检错纠错能力 1 码间距离d 码间距离(code d
14、istances)是一个码组中任意两个码字之间对应位上码元取值不同的位数，用d表示。码间距离简称码距，又称为汉明(Hamming)距离。码间距离d可用下式计算: (9.4) 即码间距离d等于两个码字对应位模2相加后“1”的个数。,一般两个码字的码距计算方法为：设两个码字Ci、Cj分别为101110 和 101011，则码距可按下式计算: 故d(Ci, Cj)=2。,在一个码组中，各码字之间的距离不一定都相等，有的大，有的小。通常称码组中最小的码距为最小码间距离，用 d0表示。由上述重复编码的例子可知，两个码字之间不同的 位数越多，其检错纠错能力越强，即码间距离越大，其检错 纠错能力越强。所以一
15、个码组的最小码间距离d0就决定了该 码组的检错纠错能力。,对于三位编码的码间距离，可用三维几何空间来说明。三位编码的码字共有23=8个，用三维几何空间立方体的8个顶点来表示，如图9.7所示。码字之间的距离可用对应两顶点间沿立方体各棱行走的最短几何距离来示意。由图9.7可见，对上述重复编码的例子，其码组只有“111”、“000”两个许用码，从“111”到“000”要经过三条边，显然它们之间的距离为d=3。同样，对于多位编码的码间距离，可用多维空间来说明。,图9.7 码间距离的几何意义,2. 最小距离d0与检错纠错能力的关系 (1) 当码组仅用于检测错误时，若要求检测e个错误，则最小码距为 d0=
16、e+1 (9.5) 这可由图9.8(a)来说明。图中，A为一个码字，B为另一个码字。若码字A有两位错，A变为以2为半径的圆上某点，则只要最小码距不小于3，在半径为2的圆上及圆内就不会有其他许用码，因而能检测错码的位数等于2，即最小码距为d0，能检测d01个错码。若要检测e个错码，则必须满足d0e+1的要求。,图9.8 码间距离与检错纠错能力的关系,(2) 当码组仅用于纠正错误时，为纠正t个错误，要求最小码距为 d0e+t (9.6) 这可用图9.8(b)来说明。码字A发生两位错，落在以A为圆心、以2为半径的圆上某点。码字B有两位错，落在以B为圆心、 以2为半径的圆上某点。只要这两个圆不重叠、不
17、相交，就能区分判别出左边圆上的为码字A，右边圆上的为码字B。可见，能纠正两位错码，要求的最小码距为5。所以纠正t个错误，必须满足d02t+1的要求。,(3) 当码组既要检错，又要纠错时，为纠正t个错误，同时检测e个错误，要求的最小码距为 d0e+t+1 et (9.7) 这可用图9.4(c)来说明。当码字A出现e个错误时，将落在以A为圆心、以e为半径的圆上某点。码字B出现t个错误，将落在以 B为圆心、以t为半径的圆上某点。要纠正码字B的错误，同时又能检出码字A的错误，就要求A的大圆和B的小圆不相交、不重叠， 即A和B之间的距离要大于e+t，也即最小码距d0e+t+1。,3 差错控制编码的效果
18、对于随机错误的情况，假设误码率为P， 且P1。在码长为n的码字中刚好发生r个错误的概率为 (9.8) 当n=7， P=10-3时，P7(1)7P1=710-3, P7(2)21P2= 2.110-5, P7(3)35P3=3.510-8。,4 纠错编码的分类 从不同角度出发，纠错编码有不同的分类方法。纠错编码的分类如图9.9所示。,图9.9 纠错编码分类示意图,(1) 按照其实现的功能，纠错编码可以分为检错码和纠错码。一般来说，能够发现错误的码称为检错码。在译码时不仅能够发现错误，而且能够自动纠正错误，通过译码产生正确的码字，这样的码称为纠错码。 (2) 按信息码元与监督码元的关系，纠错编码可
19、以分为线性码和非线性码。线性码是指信息码元与监督码元之间存在线性关系的纠错编码。实际应用的一般都是线性码。信息码元与监督码元之间为非线性关系的纠错编码称为非线性码。,(3) 按照对信息码元处理方法的不同，纠错编码分为分组码和卷积码。分组码是将k个信息码元划分为一组，然后由这 k个码元按照一定的规则产生r个监督码元，从而组成长度n=k+r的码组。在分组码中，监督码元仅监督本码组中的信息码元。 另外，按照码字的结构特点是否具有循环性，纠错编码还可分为循环码和非循环码；按照码元的取值可分为二进制码和多进制码；按照纠错的类别可分为纠随机错误的码和纠突发错误的码。,5. 编码效率 在分组码编码中，加入的
20、监督位越多，检错纠错能力越强。但这会使总的码长增加，(即要传输的位数增加)，从而使编码的效率降低。设码字的信息码元个数为k，监督码元个数为r，总的码元的个数(即总的码长)为 n=k+r (9.9) 编码效率是指码字的信息码元个数k与总的码长n的比值，即 (9.10) 可见, 监督位越多，编码效率越低。,9.2 常用简单差错控制编码 9.2.1 奇偶监督码 奇偶监督码(也称奇偶校验码)广泛应用于计算机数据传输中。奇偶监督码的编码规则是在每个分组的信息位后增加监督位，无论信息位有多少位，监督位只有一位。奇偶监督码可分为奇监督码和偶监督码两种。这两种编码的工作原理和检错能力相同。,偶监督码是给信息位
21、后增加一位监督位，使码字中“1”的数目为偶数，满足如下关系： (9.11) 式中：cn-1cn-2c1为信息位; c0为监督位。式(9.11)即为偶监督码的监督关系，也称为校验方程。由校验方程能检测出奇数个错。当发生奇数个错时，异或结果为1，不满足校验方程，可判断该码字有错。当发生偶数个错时，异或结果为0，满足校验方程，虽然码字有错，但检测不到，所以这种码不能检测偶数个错。,在编码的过程中，监督位是由信息位产生的，该编码监督位的产生方程为 (9.12) 奇监督码是给信息位后增加一位监督位，使码字中“1”的数目为奇数。其校验方程为 (9.13) 奇监督码能检测出奇数个错。其监督位的产生方程为 (
22、9.14),奇偶监督码的编码效率较高，尤其是当码长n较大时这一特点更为明显。在n值很大时编码效率趋近于1，即 (9.15) 奇偶监督码的编码和译码在电路上也很容易实现，采用简单的数字电路即可完成。,9.2.2 二维奇偶监督码 二维奇偶监督码也称为方阵码、行列监督码或水平-垂直奇偶监督码。其编码方法是把m个信息码字排列成一个方阵，每个码字构成方阵的一行，在每一行的最后按奇偶监督规则增加一位水平监督位，按行检测每行的奇数个错，对行实行监督，然后按列的方向每列增加一位垂直监督位(包括行监督位的列)，按列检测每列的奇数个错，对列实行监督，构成水平-垂直奇偶监督码，如图9.10所示。,图9.10 二维奇
23、偶监督码,9.2.3 恒比码 恒比码的特点是每个许用码含有相同数目的“1”。在码字中，“1”与“0”的个数之比是恒定的，所以称之为恒比码。一个码字中“1”的个数称为该码字的码重，因此恒比码又称为等重码。对于某种特定的恒比码，当码长确定后，其“1”的个数就确定了。所以在检测中只要计算“1”的个数就可以确定是否发生错误。恒比码多用于电传机中。,我国电传机传输汉字采用的是“5中取3” 恒比码，其码长为5，码字中“1”的个数为3，称为保护电码。码长为5的二进制数共有32种组合，选择其中含有3个“1”的组合作为许用码，所以“5中取3” 恒比码许用码的个数为C35=5！/(3!2!)=10个。这十个码字刚
24、好用来表示10个阿拉伯数字09，再用这10个阿拉伯数字拼成汉字进行电传传输。我国的保护电码比国际上通用的五单位码具有更强的抗干扰能力。表9.1列出了这两种编码。,9.3 线 性 分 组 码 9.3.1 线性分组码的概念 数字通信系统的信源输出是由“0”和“1”组成的二进制序列，在分组码中，该二元信息序列被分成码元个数固定的一 组组信息，每组信息的码元由k位二进制码元组成，则共有2k个不同的组合，即不同的信息。信道编码器用2k个不同的码组(或码字)表示这2k个不同的信息。 2k个码组的位数是一样的，假设为n，且nk，则这2k个码组的集合就称做分组码。简单地讲，将信息码进行分组，然后为每组信息码附
25、加若干位监督码元的编码方法所得到的编码集合称为分组码。,所谓线性分组码，就是一种长度为n，其中2k个许用码组(代表信息的码组)中的任意两个码组的模2和仍为一个许用码组的分组码。这种长度为n，有2k个码组的线性分组码称为线性(n，k)码(或(n，k)线性码)。线性分组码有两个重要性质：其一是封闭性，即任意两个许用码组之模2和仍为一许用码组；其二是码组的最小码距等于非零码的最小码重。,线性分组码的构成方法是：将信息序列分为每k位一组的信息序列段，每一信息序列段按照一定规律添加r个监督码元，构成总码长为n=k+r的分组码，记为(n, k)。在分组码中，监督码元仅与本分组中的信息码元有关，监督码元只监
26、督本码字中的信息码元。当监督码元与信息码元之间的关系为线性关系，即监督码元与信息码元之间的关系可用模2加代数方程描述时，称其为线性分组码。线性码是建立在代数学中群论的基础上的。线性码的各许用码的集合构成代数学中的群，又称为群码。,表9.2示出了线性分组码的一种结构。码字的前一部分是连续k个信息码元，后一部分是连续r个监督码元，具有这种结构的线性分组码称为系统码。不按这种结构顺序排列的线性分组码称为非系统码。,9.3.2 线性分组码的监督矩阵 假定监督码元与信息码元的关系由下列线性方程组决定: (9.16),对式(9.16)移项后可得三个监督关系式(该方程组在二元有限域上求解，系数取值为“0”或
27、“1”): (9.17) 按照监督关系式(9.16)或式(9.17)可以确定(7，4)码的许用码共有24=16种，这是从27=128种组合中选出的，如表9.3所示。该(7，4)码的全部许用码字都必须受上述监督方程组的监督和检验，因此又称为一致监督方程。,将式(9.17)中的零系数项补上，写出系数可得： (9.18),把式(9.18)写成矩阵形式如下: (9.19),将式(9.16)写成矩阵形式: (9.20) 式中,令式(9.19)的系数矩阵为 (9.21) 式(9.19)可简写为 HCT=0T 或 CHT=0 (9.22) 其中，行矩阵C=c6c5c4c3c2c1c0为码字矢量; 0=000
28、; CT、0T、HT分别为C、0、H的转置矩阵。,进一步分析H，利用矩阵分块的方法，H可写为 (9.23),其中, P见式(9.20)，I3为3阶单位矩阵，即 (9.24),对于(n，k)分组码，r=nk， H 可写为 (9.25) 其中, P为rk阶矩阵，Ir为r阶单位矩阵。具有这种形式的H矩阵称为典型监督矩阵。典型监督矩阵H中的每一行都是彼此独立的，即线性不相关，不能从几个方程的组合推出方程组的另一个方程。应当注意，各种码的H矩阵不一定是典型阵，只有系统码才符合。,9.3.3 线性分组码的生成矩阵 生成矩阵是在已知信息码元时确定相应的许用码字C=c6c5c4c3c2c1c0的矩阵。由式(9
29、.16)已经可以产生监督码元c2c1c0，只要在其中添上信息码元的方程即可得出许用码字，即 (9.26),将式(9.26)写成矩阵形式: (9.27),对式(9.27)取转置得： (9.28),式中： (9.29),其中: (9.30) 矩阵G称为线性分组码的生成矩阵。G为kn阶矩阵，行数为信息位的个数，列数为码字的长度。已知矩阵G和信息码，由式(9.28)可生成许用码字C。,由式(9.29)得，G=IkQ ，其中Ik为k阶单位矩阵。这种形式的生成矩阵G是典型生成矩阵。同样，典型生成矩阵的各行也是线性无关的。由典型生成矩阵得出的码字C是信息位在前、监督位在后的系统码。实际上G中的每一行都是一个
30、许用码字。G中的第一行、第二行、第三行、第四行分别是信息位为1000、0100、0010 、0001 时计算出的许用码字。 由式(9.29)可知，Q=PT(或P=QT)，而H=PIr ， G=IkQ，所以若H和G已知其中一个，则另一个确定，其监督关系和它所对应的码也就确定了。,在线性分组码中，任意两个许用码字对应位模2相加还是此码组中的一个码字，所以线性分组码具有封闭性。对(n，k)线性分组码来说，其信息位长为k，共有2k个不同组合的信息码。设Cix、Cjx为其中两个信息码，由式(9.28)可算出它们所对应的许用码字Ci=CixG， Cj=CjxG, 所以 (9.31) 式中，Cl是一个k位的
31、二元序列，它必然是2k个不同组合的信息码中的一个，所以Ci Cj必然是生成矩阵为G 的线性分组码中的一个许用码字。,(n，k)线性分组码A的生成矩阵G的每一行都是码组A的一个许用码字，它一定满足H矩阵所确定的r个监督关系。如果把G当作另一个码组B的监督矩阵，把H当作码组B的生成矩阵，则码组B为(n，nk)线性分组码，H的每一行一定满足G矩阵所确定的k个监督关系。这样的码组A和码组B称为对偶码。 线性分组码的最小距离dmin等于该码的最小重量(除全“0”码字外)，即 (9.32),由于线性分组码具有封闭性，因此由码距的定义可知，任意两个许用码字之间的距离必然是另一个许用码字的重量。所以，该码的最
32、小重量(除全“0”码字外)必然是该线性分组码的最小距离。 对线性分组码，由监督矩阵H中线性不相关的列数可以得到线性分组码中最小码距的上界，即 (9.33),由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， 称为最大可辨距离。,9.3.4 线性分组码的伴随式和检错纠错能力 设发送端发出的
33、许用码为C=cn-1cn-2c1c0，它符合CHT=0 。假设经过信道传输后接收端收到的码字为R= rn-1rn-2 r1r0。如果R=C ，把R代入式(9.22)中计算，则RHT=0, 判断为正确。由于传输误差R与C不一定相同，因此 其误差为 (9.34),E称为差错序列或错误图样。因为E表示R中具体哪一位发生错误，即 把R代入式(9.22)得： 或 (9.35),其中，S=sn-1sn-2s1s0，为1r阶行矢量。由式(9.35)可见，S只与错误图样E有关，而与发送的码字C无关，这意味着S与E有线性变换关系，能与E一一对应，可指示错码位置，所以S称为监督矩阵为H的(n，k)线性分组码的伴随
34、式。当E=000001n时，S=000001r；当E不为零时，S不为零。译码器可通过伴随式S进行检错纠错。如果S为零，则译码器判断接收码字正确，并从该码字中除去监督位，然后输出信息位; 如果S不为零，则必定有错，由S可判断出错码的位置。,下面以(7，4)码为例进行说明。设C=0001011,若传输中c3发生误码,即发生一位错,E=0001000,R=0000011, 则由式(9.35)可得： (9.36),可见, ST刚好是错误图样E中“1”所对应的H中的一列，即R的第i位有错，则E的第i位为“1”，ST与H中的第i列相同。判断出错误后，可利用R E=C纠错。 对于前面所介绍的偶校验码，当总码
35、长为n时即为(n，n-1)线性分组码。它只有一位监督码元c0，其构成的监督关系式见式(9.11)。在接收端进行解码校验时，要判断接收到的码是否满足监督关系式(9.11)，实际上就是计算线性分组码的伴随式S，即,当S=0时，符合监督关系式，判断接收到的码无错；当S=1时，不符合监督关系式，就认为有错。S的取值只有两个，它只能表示无错、有错两种状态，而无法指出错在哪一位，因此，它只能检错，不能纠错。如果再增加一位监督位，相应地再增加一个监督关系式，那么S就有4种情况00、01、10、11。用其中一种00表示无错，剩余的3种能够用来指示一位错码的三种不同位置，即具有纠错功能。同理，如果有r个监督位，
36、即有r个监督关系式，则它可以指示出一位错码的2r1个可能的位置。,由以上分析可知，对(n，k)线性分组码，有r=nk个监督关系式，有2r个不同的S。全0矢量表示无错，所以S最多可指出2r1种错误。要纠正所有小于或等于t个错，必须满足: (9.37),其中, Cin为组合数, 即 (9.38) 式(9.38)说明了监督位数r与纠错能力的关系。当式(9.38)取等号时， 2r最小，即r达到满足要求时的最小值，此时监督位利用得最充分，称为完备码。,线性分组码的主要性质如下： (1) 封闭性。封闭性是指码中任意两个许用码组之和(逐位模2和)仍为一个许用码组。也就是说，若C1和C2为分组码中的两个许用码
37、组，则C1 C2仍为其中的一个许用码组。 (2) 码的最小距离等于非零码的最小重量。因为线性分组码具有封闭性，所以两个码组之间的距离必是另一码组的重量。为此，码的最小距离也就是码的最小重量，当然，除全“0”码组外。,在通信传输过程中如果错码较多，已超过这种编码的检错能力，即R变为另一许用码组，则式(9.22)仍成立。由于线性分组码具有封闭性质，因此由式(9.34)中R=C E可知，只有当E=C，即错误码组刚好等于任意许用码组时， S=0，即不能检测错码。设(n，k)线性分组码最大检错的个数为D，信道的误码率为Pe，那么不能检错的概率为 (9.39) 其中， Wi是重量为i的许用码组数目。,9.
38、3.5 汉明码 汉明码是一种可以纠正单个随机错误的线性分组码，它是一种完备码，编码效率很高。在式(9.37)中，令t=1(即纠正一位错)，并取等号得: 2r1=n (9.40) 此时构成(2r1， 2r1r)汉明码。 汉明码具有以下特点(m为任意正整数，m3)： 监督位长 r=m，码长n=2r1=2m1，信息位长k=nr= 2r1r=2m1m，最小码距d0=3，纠错能力t=1, 编码效率 ， n越大，越高。,(7，4)汉明码的典型监督矩阵H和生成矩阵G如下:,(9.42),(9.41),汉明码只能纠正一位错，其最小码距d0=3。当码字中出现两位错时，它检测不出来，必然会造成错判。如果在汉明码的
39、基础上增加一位对所有码元都进行校验的监督码元，则监督码元的位数由原来的m变为m+1。码长由原来的2m1变为2m，信息位长度不变，形成(2m， 2m1m)的线性码，这种码称为增 余汉明码或扩展汉明码。增余汉明码的最小码距在汉明码的基础上增加了一位，变为4。所以，增余汉明码不仅能纠正一位错，同时也能检测2位错。,增余汉明码的构成是增加一位监督码元，使原汉明码的最小码重由奇数变为偶数。其监督矩阵可以由原汉明码的监督矩阵H得到： (9.43) He即为增余汉明码的监督矩阵，它是在H的右边增加一列全0，再在最后一行添加一行全1构成的。,如果把上述(7，4)汉明码变为对应的(8，4)增余汉明码，则其监督矩
40、阵为 (9.44),9.4 循 环 码 9.4.1 循环码的循环特性与码多项式 循环码是线性分组码的一个重要分支。循环码除了具有线性码的一般性质外，还具有循环性，即任一码字循环一位(将最右端的码元移至左端，或反之)以后，仍为该码中的一个码字。循环码有许多特殊的代数性质，基于这些性质，循环码有较强的纠错能力，而且其编码和译码电路很容易用移位寄存器实现，因而在前向纠错(FEC)系统中得到了广泛的应用。,对于一个(n，k)线性码C，若其中的任一码组向左或向右循环移动任意位后仍是C中的一个码组，则称C是一个循环码。循环码是一种线性分组码，它除了具有线性分组码的封闭性之外，还具有循环性。通常其前k位是信
41、息码元，后r位为监督码元，具有系统码的形式。循环性是指循环码集中的任一许用码字(全“0”码除外)循环左移(或循环右移)后所得到的码字仍为该循环码中的一个许用码字。设码字矢量C=cn-1cn-2c1c0是码长为n的循环码中的一个码字。对其进行循环左移、右移，无论循环左移、右移多少位，得到的结果均为该循环码中的一个码字。,下式所示的码字均为该循环码中的一个码字: (9.45) 表9.4列出了一种(7，3)循环码的全部许用码字。,为了便于用代数学的理论分析计算循环码，可把循环码中的码字用多项式来表示，称为码多项式，也就是把码字中各码元的取值作为码多项式的系数。对于码字矢量C=cn-1cn-2 c1c
42、0, 可以用码多项式表示为 T(x)=cn-1xn-1+cn-2xn-2+c1x1+c0 (9.46),其中, xi是码元位置的标记，它表示由其系数所决定的码元取值所处的对应位置，其系数只能取0或1，运算时其系数的运算为模2运算。例如，码字1001110、0011101可用码多项式表示为 T1(x)=1x6+0x5+0x4+1x3+1x2+1x1+0x0=x6+x3+x2+x T2(x)=0x6+0x5+1x4+1x3+1x2+0x1+1x0=x4+x3+x2+1 则 T1(x)+T2(x)=x6+x4+x1+1 即 1001110 0011101=1010011,在整数的按模运算中，最熟悉的
43、是模2运算，如1+10 (模2)，1+21(模2)等。对于模n运算，如果一个整数m可以表示为 (9.47) 其中, Q为整数，p为m被n除后所得的余数, 那么 mp (模n) (9.48) 称m与p是同余的。,在多项式中同样可以进行类似的按模运算，如 (9.49) 其中: F(x)是幂次为n的多项式; Q(x)为商; R(x)为幂次低于n的余式; 多项式的系数在二元域上。式(9.49)可写为 F(x)=Q(x)N(x)+R(x) (9.50) 所以 F(x)R(x) (模N(x) (9.51) 即F(x)与R(x)是同余的。,码多项式系数仍按模2运算，即只取值0和1。比如, x3被x3+1除可
44、得余式为1， 于是有： x31 (模x3+1) (9.52) 由此可见，为了使xn=1，只需做模xn+1的运算即可。同理 有: x4+x2+1x2+x+1 (模x3+1) (9.53) 循环码的码多项式符合如下定理。,定理9.4.1 若T(x)是长为n的循环码中某个许用码组的码多项式，则xiT(x)在按模xn+1运算下也是该循环码中一个许用码组的码多项式。 例如, (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次后形成的。,定理9.4.1证明如下： 设T(x)=cn-1xn-1+cn-2xn-2+c1x1+c0，那么有 即 xiT(x)R(x) (模xn+1) (9.54),其中, Ri(x)=cn-1-ixn-1+cn-2-ixn-2+c0xi+cn-1xi-1+cn-i是T(x)左 移i位后形成的码字。若把i取不同的值重复做上述运算，则可得到该循