现代通信原理、技术与仿真第9章 差错控制编码ppt课件

1、第9章 过失控制编码9.1过失控制编码原理9.2常用简单过失控制编码9.3线性分组码9.4循环码9.5卷积码本章仿真实验举例习题9.1过失控制编码原理9.1.1引起误码的缘由与降低误码的常用方法数字信号在实践通讯过程中不可防止地会发生错误。这是由于，一方面通讯系统的特性并非完全理想，数字信号波形经过这样的通讯系统时会产生波形失真，因此在接纳端判决时会产生判决错误，这种干扰称为乘性干扰；另一方面，信道中的噪声也会产生干扰，这种干扰随机地与信号叠加，使信号波形产生失真，也会引起判决错误，这种干扰称为加性干扰。 对于乘性干扰，可以经过平衡器来消除码间串扰的影响。随机加性干扰通常由信道产生。根据随机加

2、性干扰的不同特点，从过失控制角度看，相应的信道可以分为三类：随机信道、突发信道、混合信道。随机信道：这种信道中错码的出现是互不相关、统计独立的。比如，当信道中的随机加性干扰主要是高斯分布的白噪声时，引起的错码就具有这种性质。突发信道：错码的出现是前后相关的。当错码出现时，会在短时间内有一连串的大量错码，而该时间过后又有较长的时间无错码。呵斥突发错码的缘由是信道中存在随机的强突发脉冲干扰，比如，闪电、电焊、电火花干扰等。当信道中的随机加性干扰主要是随机的强突发脉冲干扰时，称为突发信道。混合信道：以上两种随机干扰都存在，产生的错码既有随机错码又有突发错码，这种信道称为混合信道。在引见过失控制方式之

3、前，下面先了解一下降低误码、提高数字通讯可靠性的几种途径。根据实践通讯系统对其可靠性的要求，可以用不同的方法提高通讯的可靠性。(1) 适当添加发送信号功率。增大信号的功率，即提高输入端的信噪比，可以减少信道中随机加性干扰对信号的影响，降低误码率，提高数字通讯的可靠性。但是发送信号功率由于遭到设备和环境条件的影响而不能无限增大。比如，空间探测器上的发射机由于其体积和分量遭到限制，其发射功率不能够无限增大。所以，此种方法在实践中遭到了一定限制。(2) 选择抗噪声性能好的调制解调方式。比如，在数字调制中移相键控PSK比幅度键控ASK的误码率要小得多。所以在实践中多采用移相键控PSK，而很少采用幅度键

4、控ASK。(3) 采用最正确接纳。最正确接纳可以使数字通讯的误码率到达最小。接纳机中的滤波器可以是带通滤波器，也可以是匹配滤波器。在数字通讯中可以采用匹配滤波接纳，最大限制地抑制白噪声，在判决时辰到达最大输出信噪比，从而降低误码率。(4) 采用过失控制编码。经过一定的编码和译码方法，采用前向纠错或检错重传技术，可以自动纠正传输错误。对于不同类型的信道，应采用不同的过失控制方式。这是本章的主要内容。9.1.2过失控制编码的根本方法与过失控制方式对于不同类型的信道，要采用不同的过失控制方式。不同的过失控制编码也要与相应的过失控制方式配合运用。常用的过失控制方式可分为以下四类：检错重发(ARQ)、前

5、向纠错(FEC)、混合纠错检错(HEC)、信息反响(IRQ，也称反响校验)。图9.1所示为过失类型和过失控制方式。图9.1过失类型和过失控制方式1. 检错重发(ARQ)方式检错重发方式又称为自动恳求重发方式。这种过失控制方式在发送端对数据序列进展分组编码，参与一定多余码元使之具有一定的检错才干，成为可以发现错误的码组。接纳端收到码组后，按一定规那么对其进展有无错误的判别，并把判决结果(应对信号)经过反向信道送回发送端。假设有错误，那么发送端把前面发出的信息重新传送一次，直到接纳端以为已正确收到信息为止。在详细实现检错重发系统时，通常有3种方式，即停发等候重发、前往重发和选择重发。ARQ方式的组

6、成如图9.2所示。图9.2ARQ方式1) 停顿等待ARQ停顿等待ARQ是最简单的ARQ系统，也称为空闲RQ(idleRQ)。这种系统每发送一个分组就停顿发送等待接纳端的应对信号。收到接纳端确实认应对后，再发送下一个分组。假设收到的能否认应对，那么重发原分组。图9.3所示为停顿等待ARQ发送端和接纳端信号的传送过程表示图。 图9.3停顿等待ARQ2) 延续ARQ延续ARQ任务在全双工方式，需求有一定的缓冲器容量。这种系统两端同时发送信息，发送端延续发送数据，并接纳应对信号，接纳端延续接纳数据并发送应对信号。延续ARQ的任务原理如图9.4所示。与停顿等待ARQ不同，其发送端无停顿地送出一个个延续码

7、组，不再等候接纳端前往的ACK信号，但一旦接纳端发现错误并发回NAK信号，那么发送端从下一个码组开场重发前一段N组信号，N的大小取决于信号传送及处置所带来的延时，图9.4中N=5。 图9.4延续ARQ的任务原理3) 选择重发ARQ选择重发ARQ是由延续ARQ开展而来的，任务在全双工方式，需求有较大的缓冲器容量，其任务过程类似于延续ARQ。但在发送端重发时，不是将错误码组及其以后的码组全部重发，而是仅重发出错的码组。选择重发ARQ的任务原理如图9.5所示。图9.5选择重发ARQ2. 前向纠错(FEC)方式在前向纠错(FEC)方式中，发送端发出的码字不仅可以发现错误，而且可以纠正错误。在接纳端译码

8、后，假设没有错误，那么直接输出；假设有错误，那么在接纳端自动纠正后再输出。这种方式不需求反向信道，特别适宜于只能提供单向信道的场所。其优点是：能自动纠错，不要求检错重发，因此延时小，实时性好，传输效率高。其缺陷是：所选择的纠错码必需与信道的错误特性亲密配合，否那么很难到达降低错码率的要求；为了能纠正较多的错码，译码设备复杂，且要求附加的监视码元也较多，传输效果也会降低。前向纠错(FEC)主要用于话音、广播、TV等通讯中。3. 混合纠错检错(HEC)方式混合纠错检错(HEC)方式是将ARQ方式和FEC方式结合运用的一种方式。在混合纠错检错系统中，发送端发出同时具有检错和纠错才干的码，接纳端收到码

9、后，检查错误情况，假设错误少于纠错才干，那么自行纠正，即FEC方式；假设干扰严重，错误很多，超出纠正才干，但能检测出来，那么经反向信道要求发送端重发，即ARQ方式。普通的纠错编码可以检错和纠错的位数都是很有限的。比如，一种纠错编码能纠正一个码字内的两位错，检出三位错。当码组中出现两位以下错码时，它能自动纠正错码；当码组中出现两位以上错码时，它不能自动纠正。所以在传输错码较少时，采用前向纠错方式自动纠正错码；在错码较多时，采用ARQ方式自动恳求重发。4. 反响校验(IRQ)方式反响校验(IRQ)方式也称为信息反响方式或回程校验方式。在该方式中，发送端一边发送码字，一边将发送的码字在发送端缓冲存储

10、。当接纳端收到码字后，立刻将接纳到的码字前往发送端。发送端将前往的码字与发送端缓冲存储器中相应的码字进展比较，假设发现与发送码不同，即以为产生了错误，就重发上一次的码字，直到发送端校验正确为止。利用这种方式进展过失控制时设备简单，但要求双向信道，并且传输效率很低。9.1.3纠错编码的根本原理1. 有扰信道的编码定理香农有扰信道的编码定理指出：在有扰信道中只需信息的传输速率R小于信道容量C，总可以找到一种编码方法，使信息以恣意小的过失概率经过信道传送到接纳端，即误码率Pe可以恣意小，而且传输速率R可以接近信道容量C。但假设RC，那么在传输过程中必定会带来不可纠正错误，不存在使过失概率恣意小的编码

11、。其中，误码率：Pe=e-nE(R) (9.1)式中, n为编码的码字长度(简称码长)；E(R)为误码指数。E(R)与R、C有关，其关系可用曲线表示，如图9.6所示。图9.6E(R)与R的关系由式(9.1)及E(R)与R、C的关系曲线可以看出，要提高抗干扰才干，减小误码率Pe，有以下两种途径： (1) 在编码长度n及信息的传输速率R一定时，为减小Pe，可以添加信道容量C。由图9.6可见，E(R)随信道容量C的添加而增大。由式(9.1)可见，误码率Pe随E(R)的增大而指数减小，即添加信道容量可以减小误码率。由信道容量公式可见，要添加信道容量C，可以经过添加信号功率P和系统带宽B来实现，即经过添

12、加信号功率P和系统带宽B可以减小误码率。(2) 在信道容量C及信息的传输速率R一定的情况下，由式(9.1)可知，添加码长n也可以使误码率Pe指数减小，即经过添加信道中传输信息的码长可以减小误码率。香农有扰信道的编码定理本身并未给出详细的纠错编码方法，但它为信道编码奠定了实际根底，从实际上指出了信道编码的开展方向。2. 纠错编码原理纠错编码原理为：利用添加信息的编码长度(附加监视码)来减小误码率。最大似然译码准那么：在收到码r的条件下，计算2k个(许用码的个数)条件概率，其中CL为许用码字，假设条件概率为最大，那么以为收到的码字r就是发送来的CL码字。 可用下式计算： (9.2)式中: ri为接

13、纳码字的第i位元素；CLi为许用码字CL的第i位元素。显然，当接纳码元出错，即riCLi时，概率; 当码元接纳正确，即ri=CLi时，概率。令d为接纳的码字与许用码CL之间不同的位数(即出错位的位数)，那么式(9.2)可以写成： (9.3)可见，由于，随d单调下降，因此，d越小， 越大。 越大阐明接纳到的码字r越像码字CL，而不像其他许用码，由于传输中码字错的位数多比错的位数少出现的概率更小。9.1.4码间间隔d与检错纠错才干1 码间间隔d码间间隔(code distances)是一个码组中恣意两个码字之间对应位上码元取值不同的位数，用d表示。码间间隔简称码距，又称为汉明(Hamming)间隔

14、。码间间隔d可用下式计算: (9.4)即码间间隔d等于两个码字对应位模2相加后“1的个数。 普通两个码字的码距计算方法为：设两个码字Ci、Cj分别为101110 和 101011，那么码距可按下式计算:故d(Ci, Cj)=2。 在一个码组中，各码字之间的间隔不一定都相等，有的大，有的小。通常称码组中最小的码距为最小码间间隔，用d0表示。由上述反复编码的例子可知，两个码字之间不同的位数越多，其检错纠错才干越强，即码间间隔越大，其检错纠错才干越强。所以一个码组的最小码间间隔d0就决议了该码组的检错纠错才干。对于三位编码的码间间隔，可用三维几何空间来阐明。三位编码的码字共有23=8个，用三维几何空

15、间立方体的8个顶点来表示，如图9.7所示。码字之间的间隔可用对应两顶点间沿立方体各棱行走的最短几何间隔来表示。由图9.7可见，对上述反复编码的例子，其码组只需“111、“000两个许用码，从“111到“000要经过三条边，显然它们之间的间隔为d=3。同样，对于多位编码的码间间隔，可用多维空间来阐明。图9.7码间间隔的几何意义2. 最小间隔d0与检错纠错才干的关系(1) 当码组仅用于检测错误时，假设要求检测e个错误，那么最小码距为d0=e+1 (9.5)这可由图9.8(a)来阐明。图中，A为一个码字，B为另一个码字。假设码字A有两位错，A变为以2为半径的圆上某点，那么只需最小码距不小于3，在半径

16、为2的圆上及圆内就不会有其他许用码，因此能检测错码的位数等于2，即最小码距为d0，能检测d01个错码。假设要检测e个错码，那么必需满足d0e+1的要求。图9.8码间间隔与检错纠错才干的关系(2) 当码组仅用于纠正错误时，为纠正t个错误，要求最小码距为d0e+t (9.6)这可用图9.8(b)来阐明。码字A发生两位错，落在以A为圆心、以2为半径的圆上某点。码字B有两位错，落在以B为圆心、以2为半径的圆上某点。只需这两个圆不重叠、不相交，就能区分判别出左边圆上的为码字A，右边圆上的为码字B。可见，能纠正两位错码，要求的最小码距为5。所以纠正t个错误，必需满足d02t+1的要求。(3) 当码组既要检

17、错，又要纠错时，为纠正t个错误，同时检测e个错误，要求的最小码距为d0e+t+1et (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 过失控制编码的效果对于随机错误的情况，假设误码率为P， 且Pk，那么这2k个码组的集合就称做分组码。简单地讲，将信息码进展分组，然后为每组信息码附加假设干位监视码元的编码方法所得到的编码集合称为分组码

18、。所谓线性分组码，就是一种长度为n，其中2k个许用码组(代表信息的码组)中的恣意两个码组的模2和仍为一个许用码组的分组码。这种长度为n，有2k个码组的线性分组码称为线性(n，k)码(或(n，k)线性码)。线性分组码有两个重要性质：其一是封锁性，即恣意两个许用码组之模2和仍为一许用码组；其二是码组的最小码距等于非零码的最小码重。线性分组码的构成方法是：将信息序列分为每k位一组的信息序列段，每一信息序列段按照一定规律添加r个监视码元，构成总码长为n=k+r的分组码，记为(n, k)。在分组码中，监视码元仅与本分组中的信息码元有关，监视码元只监视本码字中的信息码元。当监视码元与信息码元之间的关系为线

19、性关系，即监视码元与信息码元之间的关系可用模2加代数方程描画时，称其为线性分组码。线性码是建立在代数学中群论的根底上的。线性码的各许用码的集合构成代数学中的群，又称为群码。表9.2示出了线性分组码的一种构造。码字的前一部分是延续k个信息码元，后一部分是延续r个监视码元，具有这种构造的线性分组码称为系统码。不按这种构造顺序陈列的线性分组码称为非系统码。9.3.2线性分组码的监视矩阵假定监视码元与信息码元的关系由以下线性方程组决议: (9.16)对式(9.16)移项后可得三个监视关系式(该方程组在二元有限域上求解，系数取值为“0或“1): (9.17)按照监视关系式(9.16)或式(9.17)可以

20、确定(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; CT、0T、HT分别为C、0、H的转置矩阵。进一步分析H，利用矩阵分块的方法，H可

21、写为 (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.16)曾经可以产生监视码元c2c1c0，只需在其中添上信息码元的方程即可得出许用码字，即 (9.26

22、)将式(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中的每一行都是一个许用码字。G中的第一行、第二行、第三行、第四行分别是信息位为1000、0100、0010 、0001 时计算出的许用

23、码字。由式(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位的二元序列，它必然是2k个不同组合的信息码中的一个，所以Ci Cj必然是生成矩阵为G 的线性分组码中的一个许用码字。 (

24、n，k)线性分组码A的生成矩阵G的每一行都是码组A的一个许用码字，它一定满足H矩阵所确定的r个监视关系。假设把G当作另一个码组B的监视矩阵，把H当作码组B的生成矩阵，那么码组B为(n，nk)线性分组码，H的每一行一定满足G矩阵所确定的k个监视关系。这样的码组A和码组B称为对偶码。线性分组码的最小间隔dmin等于该码的最小分量(除全“0码字外)，即 (9.32)由于线性分组码具有封锁性，因此由码距的定义可知，恣意两个许用码字之间的间隔必然是另一个许用码字的分量。所以，该码的最小分量(除全“0码字外)必然是该线性分组码的最小间隔。对线性分组码，由监视矩阵H中线性不相关的列数可以得到线性分组码中最小

25、码距的上界，即 (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线性分组码的伴随式和检错纠错才干设发送端发出的许用码为C=cn-1cn-2c1c0，它符合CHT=0 。假设经过信道传输后接纳端收到的码字为R=rn-1rn-2 r1r0。假设R=

26、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)线性分组码的伴随式。当E=000001n时，S=000001r；当E不为零时，S不为零。译码器可经过伴随式S进展检错纠错。假设S为零，那么译码器判别接纳码字正确

27、，并从该码字中除去监视位，然后输出信息位; 假设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纠错。对于前面所引见的偶校验码，当总码长为n时即为(n，n-1)线性分组码。它只需一位监视码元c0，其构成的监视关系式见式(9.11)。在接纳端进展解码校验时，要判别接纳到的码能否满足

28、监视关系式(9.11)，实践上就是计算线性分组码的伴随式S，即当S=0时，符合监视关系式，判别接纳到的码无错；当S=1时，不符合监视关系式，就以为有错。S的取值只需两个，它只能表示无错、有错两种形状，而无法指出错在哪一位，因此，它只能检错，不能纠错。假设再添加一位监视位，相应地再添加一个监视关系式，那么S就有4种情况00、01、10、11。用其中一种00表示无错，剩余的3种可以用来指示一位错码的三种不同位置，即具有纠错功能。同理，假设有r个监视位，即有r个监视关系式，那么它可以指示出一位错码的2r1个能够的位置。由以上分析可知，对(n，k)线性分组码，有r=nk个监视关系式，有2r个不同的S。

29、全0矢量表示无错，所以S最多可指出2r1种错误。要纠正一切小于或等于t个错，必需满足: (9.37)其中, Cin为组合数, 即 (9.38)式(9.38)阐明了监视位数r与纠错才干的关系。当式(9.38)取等号时， 2r最小，即r到达满足要求时的最小值，此时监视位利用得最充分，称为完备码。线性分组码的主要性质如下： (1) 封锁性。封锁性是指码中恣意两个许用码组之和(逐位模2和)仍为一个许用码组。也就是说，假设C1和C2为分组码中的两个许用码组，那么C1 C2仍为其中的一个许用码组。 (2) 码的最小间隔等于非零码的最小分量。由于线性分组码具有封锁性，所以两个码组之间的间隔必是另一码组的分量

30、。为此，码的最小间隔也就是码的最小分量，当然，除全“0码组外。在通讯传输过程中假设错码较多，已超越这种编码的检错才干，即R变为另一许用码组，那么式(9.22)仍成立。由于线性分组码具有封锁性质，因此由式(9.34)中R=C E可知，只需当E=C，即错误码组刚好等于恣意许用码组时， S=0，即不能检测错码。设(n，k)线性分组码最大检错的个数为D，信道的误码率为Pe，那么不能检错的概率为 (9.39)其中， Wi是分量为i的许用码组数目。9.3.5汉明码汉明码是一种可以纠正单个随机错误的线性分组码，它是一种完备码，编码效率很高。在式(9.37)中，令t=1(即纠正一位错)，并取等号得:2r1=n

31、 (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。当码字中出现两位错时，它检测不出来，必然会呵斥错判。假设在汉明码的根底上添加一位对一切码元都进展校验的监视码元，那么监视码元的位数由原来的m变为m+1。码长由原来的2m1变为2m，信息位长度不变，构成(2m， 2m1m)的线性码，这种码称为增

32、余汉明码或扩展汉明码。增余汉明码的最小码距在汉明码的根底上添加了一位，变为4。所以，增余汉明码不仅能纠正一位错，同时也能检测2位错。增余汉明码的构成是添加一位监视码元，使原汉明码的最小码重由奇数变为偶数。其监视矩阵可以由原汉明码的监视矩阵H得到： (9.43)He即为增余汉明码的监视矩阵，它是在H的右边添加一列全0，再在最后一行添加一行全1构成的。假设把上述(7，4)汉明码变为对应的(8，4)增余汉明码，那么其监视矩阵为(9.44)9.4循环码9.4.1循环码的循环特性与码多项式循环码是线性分组码的一个重要分支。循环码除了具有线性码的普通性质外，还具有循环性，即任一码字循环一位(将最右端的码元

33、移至左端，或反之)以后，仍为该码中的一个码字。循环码有许多特殊的代数性质，基于这些性质，循环码有较强的纠错才干，而且其编码和译码电路很容易用移位存放器实现，因此在前向纠错(FEC)系统中得到了广泛的运用。对于一个(n，k)线性码C，假设其中的任一码组向左或向右循环挪动恣意位后仍是C中的一个码组，那么称C是一个循环码。循环码是一种线性分组码，它除了具有线性分组码的封锁性之外，还具有循环性。通常其前k位是信息码元，后r位为监视码元，具有系统码的方式。循环性是指循环码集中的任一许用码字(全“0码除外)循环左移(或循环右移)后所得到的码字仍为该循环码中的一个许用码字。设码字矢量C=cn-1cn-2c1

34、c0是码长为n的循环码中的一个码字。对其进展循环左移、右移，无论循环左移、右移多少位，得到的结果均为该循环码中的一个码字。 下式所示的码字均为该循环码中的一个码字: (9.45)表9.4列出了一种(7，3)循环码的全部许用码字。为了便于用代数学的实际分析计算循环码，可把循环码中的码字用多项式来表示，称为码多项式，也就是把码字中各码元的取值作为码多项式的系数。对于码字矢量C=cn-1cn-2c1c0, 可以用码多项式表示为T(x)=cn-1xn-1+cn-2xn-2+c1x1+c0 (9.46)其中, xi是码元位置的标志，它表示由其系数所决议的码元取值所处的对应位置，其系数只能取0或1，运算时

35、其系数的运算为模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+x3+x2+1那么T1(x)+T2(x)=x6+x4+x1+1即1001110 0011101=1010011 在整数的按模运算中，最熟习的是模2运算，如1+10(模2)，1+21(模2)等。对于模n运算，假设一个整数m可以表示为 (9.47)其中, Q为整数，p为m被n除后所得的余数, 那么mp(模n) (9.48)称m与p是同余的。在多项

36、式中同样可以进展类似的按模运算，如 (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除可得余式为1， 于是有：x31(模x3+1) (9.52)由此可见，为了使xn=1，只需做模xn+1的运算即可。同理有: x4+x2+1x2+x+1(模x3+1) (9.53)循环码的码多项式符合如下定理。定理9.4.1假设T(

37、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-ix

38、n-2+c0 xi+cn-1xi-1+cn-i是T(x)左移i位后构成的码字。假设把i取不同的值反复做上述运算，那么可得到该循环码的其他许用码字。所以，码长为n的循环码的每一个许用码字都是按模xn+1运算的余式。假设知码多项式T(x)，那么相应的循环码就可以由xiT(x)按模xn+1运算的余式求得。9.4.2循环码的生成多项式与生成矩阵定理9.4.2在循环码(n, k)中， nk次幂的码多项式有一个，且仅有一个, 用g(x)表示, 称为循环码的生成多项式。 g(x)的常数项不为零。一旦g(x)确定，该(n, k)循环码就被确定了。 g(x)是循环码中幂次最低的码多项式。由它左移就可产生其他码多

39、项式，比如xg(x)、 x2g(x)、 x3g(x)等。用k个相互独立的码多项式g(x)、 xg(x)、 x2g(x)、 x3g(x)、 xk-1g(x)可以构造出循环码的生成矩阵G(x): (9.55)例如，有一个(7，3)循环码(其最高次幂为(n, k)次)的码字为0010111，其生成多项式g(x)=x4+x2+x+1，那么利用式(9.55)可得其生成矩阵G(x)： (9.56)将此生成矩阵用系数表示，写为生成矩阵G: (9.57)式(9.57)不符合典型生成矩阵的方式，所以它不是典型生成矩阵，由它编出的码字不是系统码，但是对此矩阵作线性变换(行变换)可以变换成典型生成矩阵的方式。例如，

40、对于(7，3)循环码，设信息码为c6c5c4，由生成矩阵多项式可以写出该循环码的码字: (9.58)式中, u(x)为信息码c6c5c4的多项式。因此，知信息码U=uk-1uk-2u1u0和g(x)就可求得循环码的一切码多项式:T(x)=uk-1uk-2u1u0G(x)=u(x)g(x) (9.59)其中, u(x)为信息位所对应的多项式。信息位有k位，所以u(x)的最高阶数为k1次幂。此种方法求得的码多项式为非系统码。由式(9.59)还可见，一切的码多项式都可以被g(x)整除。定理9.4.3循环码(n, k)的生成多项式g(x)是xn+1的一个因式。定理分析： g(x)是最高次幂为nk次的码

41、多项式。 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(x)对上式移项得: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)。其方法

42、是对(xn+1)进展因式分解，从中找出一个最高次幂为nk次且常数项不为零的因式作为生成多项式g(x)。例如, 对于(7，3)循环码， g(x)的最高次幂为4, 可以从x7+1中分解得到g(x)。x7+1 可分解为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)循环码。9.4.3循环码的编码与解码1 循环码的编码在编码时，首先要根据给定的(n, k)值选

43、定生成多项式g(x)，即应在xn+1的因式中选一个nk次多项式作为g(x)。对(n, k)循环码，经过对xn+1进展因式分解选择出生成多项式g(x)，就可由信息码编出相应的循环码字。下面讨论如何从g(x)和信息码直接编出相应的系统码。设信息码多项式为m(x)=mk-1xk-1+mk-2xk-2+m1x1+m0 (9.65)信息码多项式m(x)的最高次幂为k1。将m(x)左移nk位成为xn-km(x)，其最高次幂为n-1。xn-km(x)的前一部分为延续k位信息码，后一部分为r=nk位“0， r正好是监视码的位数, 所以在它的后一部分添上监视码，就编出了相应的系统码。监视码由监视关系确定，循环码

44、的生成多项式g(x)确定循环码，因此g(x)也确定监视关系。由上述分析可知，循环码的任何码多项式都可以被g(x)整除，即T(x)=I(x)g(x)。用xn-km(x)除以g(x)得： (9.66)所得的余式r(x)的最高次幂为nk1，即r(x)=rn-k-1xn-k-1+rn-k-2xn-k-2+r1x1+r0将r(x)作为监视位的多项式，与xn-km(x)模2相加，构成新的多项式:T(x)=xn-km(x)+r(x)(9.67)由式(9.66)可见:xn-km(x)+r(x)=g(x)q(x)(9.68)所以T(x)能被g(x)整除，其最高次幂为n1。 T(x)的前一部分为延续k位信息码，后

45、一部分为r=nk位监视码。 T(x)为循环码的码多项式，而且是系统码。对(7，3)循环码选择生成多项式g(x)=x4+x3+x2+1，设知信息码为111, 那么信息码多项式为m(x)=x2+x+1。编码如下:(1) 将信息位m(x)左移nk位成为xn-km(x)。在本例中，信息码111左移4位成为1110000，即xn-km(x)=x7-3(x2+x+1)=x6+x5+x4(2) 利用式(9.66)所示的做除法，求出余式r(x)。本例中为得余式r(x)=x2，即监视码的多项式。把此码多项式的方式用其系数替代，写成码字的方式为余式的码字为0100。(3) 构成系统码T(x)=xn-km(x)+r

46、(x)。本例中为 1110000+0100=1110100。上述编码过程可以用模2除法电路完成。它可由移位存放器和模2加法电路实现。对(7，3)循环码， g(x)=x4+x3+x2+1时的编码器如图9.11所示。图9.11(7，3)循环码的编码器在编码器任务之前先清零，使存放器的初态为零，使转换开关S1、S2均向下，S1使反响线接通，S2使输入直接加到输出。开场输入三位信息码。输入的信息码m(x)一路直接送到输出端，作为系统码的前面一部分(即信息码部分)，另一路送入除法器作为被除数。三位信息码送完之后，使开关S1、S2均向上，S1使反响线断开，S2使输出与除法器的输出相连，输入端输入的为全零。

47、此种开关形状下，输出的是除法器的余数，即监视位。经过这两个阶段，输出端得到前面为信息码、后面为监视码的系统码。表9.5所示为上述编码过程中各点的形状变化过程。通常对于一个(n, k)循环码，假设设生成多项式为g(x)=xn-k+gn-k-1xn-k-1+g1x+1 (9.69)其编码器如图9.12所示。图9.12(n，k)循环码的编码器2. 循环码的解码循环码的解码分为检错和纠错两种情况。只进展检错的解码其原理较简单，它是利用任何码多项式都可以被生成多项式g(x)整除的原理实现的。设发送码字为T(x)，接纳到的码多项式为R(x)，做除法有: (9.70)其中, r(x)为余式。假设余式r(x)

48、为零，接纳码字R(x)能被整除，那么R(x)=T(x)，判别无错码; 假设余式r(x)不为零，即接纳码字R(x)不能被整除，那么R(x)T(x)，判别有错码。可以经过ARQ过失控制方式使发送端重发，得到正确的码字。假设要纠正错误， 那么需求知道错误图样E(x)，以便纠正错误。原那么上纠错解码可按以下步骤进展：(1) 用生成多项式g(x)除接纳码字R(x)=T(x)+E(x)，得到余式r(x)。(2) 按余式r(x)用查表的方法或经过某种运算得到错误图样E(x)。(3) 从R(x)中减去E(x)，得到纠错后的原发送码字T(x)。第(1)步与检错解码一样，用除法器等就可实现。第(3)步做减法也较简

49、单。第(2)步能够需求较复杂的设备，并且在计算余式和决议错误图样E(x)时，需求把接纳码组R(x)暂时存储起来。下面经过(7，3)循环码的纠错解码器来阐明其任务原理。(7，3)纠错解码器如图9.13所示。它包含除法器、缓冲器、门电路及输出前作模2运算的异或门。接纳到的码字R(x)输入后分为两路：一路送入缓冲器暂存，另一路送入除法器作除法。当码字全部进入除法器后，假设R(x)能被g(x)整除，那么除法器中移位存放器的形状全为零，阐明接纳码字为许用码字，判别为无错，直接将缓冲器暂存的R(x)输出; 假设R(x)不能被g(x)整除，那么除法器中的存数指出错误位置。经移位(码字全部进入除法器后再移位，

50、那么输入为零)，与门输出, 在相应的出错码位上输出“1。该“1与缓冲器输出的错码模2相加，纠正错误，使输出码字正确；另一方面反响回除法器，使各级移位存放器清零。图9.13(7，3)循环码纠单个错的解码器实践中接纳的码字是延续不断输入的，中间没有停顿。为了使解码器在移位纠错时不丧失输入的接纳码字，需求两套除法电路及与门和一个缓冲存放器配合运用。这种解码方法称为捕错解码，又称为梅吉特(Meggitt)解码法。9.4.4BCH码BCH码的最小码距dmin2t+1，能纠t个错误。BCH码是循环码中重要的一类子码，它的生成多项式g(x)与最小码距dmin之间有亲密的关系，可根据所要求的纠错才干t很容易地

51、构造出来。BCH码的译码也比较容易实现，是线性分组码中运用最为普遍的一类码。BCH码建立在近代数论的根底上，有严密的数学构造，这里只作简单的引见。 BCH码的特点是能纠正多个随机错误，可以根据给定的纠错才干找出生成多项式。 BCH码分为两类：本原BCH码和非本原BCH码。本原BCH码的码长n=2m1， m3, 生成多项式g(x)中含有最高次数为m的本原多项式；非本原BCH码的码长n是2m1的一个因子，它的生成多项式中不含有最高次数为m的本原多项式。BCH码的码长n与监视位r和纠错个数t之间的关系如下：对于正整数m(m3)和t(t2)，必存在满足以下参数的二进制BCH码, 即码长n=2m1，监视

52、位数rmt，能纠正一切的小于或等于t个随机错误的BCH码。因此，这类码的长度n=2m1，信息位k2mmt1。BCH码生成多项式：g(x)=LCMm1(x), m2(x), , m2t-1(x) (9.71)式中: t为可纠正的错误个数；mi(x)为最小多项式；LCM()是指取括号内一切多项式的最小公倍式。BCH码的生成多项式普通用查表法确定(码长和生成多项式表可参看相关书籍)。查表法得到的生成多项式普通用八进制数表示。 例如，当n=7， k=4， t=1时， g=(13)8=(001011)2，即g(x)=x3+x+1。【例9.1】构造一个能纠正3个错误、 码长为15的BCH码。解： 由码长与

53、生成多项式的关系可知， n=15， t=3， m为4，由于nkmt=43=12所以选用n=15、 k=5、 t=3的BCH码，对应的生成多项式标号为g=(2467)8=(10100110111)2因此，所求的生成多项式为g(x)=x10+x8+x5+x4+x2+x+1【例9.2】非本原BCH码为(23，12)，试求其生成多项式。解： 对非本原BCH码(23，12)， n=23， t=3， m=11，其对应的生成多项式标号为g=(5343)8=(101011100011)2。因此，所对应的生成多项式为 g(x)=x11+x9+x7+x6+x5+x+1下面引见几种常见的BCH码。 (1) 格雷(G

54、olay)码。BCH码(23，12)是一个特殊的非本原BCH码，称为戈雷码，它的最小码距dmin=2t+1=7，能纠正t=3个错误，其生成多项式为g(x)=x11+x9+x7+x6+x5+x+1。它是目前为止发现的独一能纠正多个错误的完备码。 (2) 扩展方式。 实践运用中，为了得到偶数码长，并提高检错才干，可以在BCH码的生成多项式中乘x+1，从而得到(n+1, k+1)扩展BCH码。扩展BCH码相当于将原有BCH码再加上一位偶校验，它不再具有循环性。 (3) 缩短方式。几乎一切的循环码都存在其另一种缩短方式(ns, ks)。实践运用中，能够需求的码长不是2m1或它的因子，我们可以从(2m1

55、, k)码中挑出前s位为0的码组构成新的码，这种码的监视位数不变，因此纠错才干坚持不变，但是没有了循环性。(4) RS码。RS码是Reed-Solomon码(理德-所罗门码)的简称，是一类具有很强纠错才干的多进制BCH码。在(n, k)RS码中，输入信号码被分成km比特一组，每组包括k个符号，每个符号由m个比特组成，而不是前面所述的二进制码由一个比特组成。一个可纠正t个错误的RS码，其参数为：码长n=2m1或m(2m1)比特；信息位k或mk比特；监视位r=n-k=2t或mr=m(nk)比特；最小码距d=2t+1或m(2t+1)比特。RS码非常适宜于纠正突发错误。它可以纠正的错误图样为：总长度q

56、i=(t2i1)m+2i1的i个突发错误。 对于一个长度为2m1符号的RS码，每个符号都可以看成是有限域GF(2m)中的一个元素。最小码距为d的RS码的生成多项式具有如下方式：g(x)=(x+)(x+2)(x+d-1) (9.72)式中, i是GF(m)中的一个元素。 GF(m)的一切元素为 。例如，构造一个能纠错误t=3个，码长为n=15， m=4的RS码。由RS码的参数可知，该码的码距d=2t+1=7，监视位r=nk=2t=6。因此该码为(15，9)RS码, 生成的多项式为 g(x)=(x+)(x+2)(x+3)(x+4)(x+5)(x+6) =x6+10 x5+14x4+4x3+6x2+

57、9x+6所以从二进制角度看，这是一个(60，36)码。 9.5卷积码9.5.1卷积码编码原理1. 卷积码的概念卷积码是一种延续处置信息序列的编码方式。码字的监视位不仅和本段的信息位有关，而且与其他段落的信息位有关。整个编码过程前后相互关联，延续进展，所以又称为连环码。 2 卷积码的构造及原理1) 卷积码的构造图9.14示出了卷积码编码器的普通构造。它由输入移位存放器、模2加法器、输出移位存放器三部分构成。输入移位存放器共有N段，每段有k级，共Nk位存放器，信息序列由此不断输入。当信息序列进入这种构造的输入移位存放器时即被自动划分为N段，每段k位，它使输出的n个比特的卷积码与N段每段有k位的信息

58、位相关联。通常把N称为约束长度(有些文献中把N1称为约束长度)。由于该N段信息共Nk个信息比特，所以也有人将Nk称为约束长度。模2加法器共n个，用于实现卷积码的编码算法。输出移位存放器共有n级。 输入移位存放器每移入k位，那么输出n个比特的编码。所以，卷积码编码效率为 (9.73)此n比特的编码不仅与当前输入的k个信息位有关，而且与之前的(N1)k个信息位有关。普通来说，对于卷积码， k和n是较小的整数， 通常把具有上述构造的卷积码记做(n, k, N)卷积码。图9.14卷积码编码器的普通构造图9.15所示是一个最简单的(2，1，2)卷积码编码器，它由两个移位存放器D1、 D2和模2相加电路组

59、成。编码器的输入信息码位一方面可以直接输出，另一方面可暂存在移位器中。每当输入编码的一个信息位，就立刻计算出一个监视位，并且此监视位紧跟此信息位之后发送出去。为便于了解，把各信息位用mi表示，监视位用ci表示，那么该编码器的输入、输出关系如图9.16所示。图9.15简单的卷积码编码器图9.16编码器的输入、输出关系编码器的任务过程是：移位存放器按信息位的节拍任务，输入一位信息，电子开关倒换一次，即前半拍(半个输入码元宽)接通m端，后半拍接通c端。因此，假设输入信息为m1, m2, m3, ，那么输出卷积码为m1, c1, m2, c2, m3, c3, ，其中ci为监视码元。由图9.16可知:

60、 (9.74)可见，卷积码的构造是：“信息元，监视元，信息元，监视元，, 一个信息元与一个监视元组成一组，但每组中的监视元除了与本组信息元有关外，还跟上一组信息元有关，或者说，每个信息元除受本组监视元监视外，还受下一组监视元的监视。本例中，n=2，k=1，nk=1，N=2，可记做(2，1，2)卷积。图9.17所示为(2，1，3)卷积码编码器，它由三个移位存放器D1、 D2、D3和模2相加电路组成。本例中，n=2, k=1, N=3，编码效率。图9.17中输出移位存放器用开关替代。 图9.17(2, 1, 3)卷积码编码器编码输出的卷积码各码元的信息位用x1j表示，监视位用x2j表示。输入k=1