现代通信原理技术与仿真差错控制编码PPT学习教案

1、会计学19.19.1差错控制编码原理差错控制编码原理9.1.19.1.1引起误码的原因与降低引起误码的原因与降低误码的常用方法误码的常用方法数字信号在实际通信过程中数字信号在实际通信过程中不可避免地会发生错误。这是因不可避免地会发生错误。这是因为，一方面通信系统的特性并非为，一方面通信系统的特性并非加性干扰。加性干扰。第1页/共264页对于乘性干扰，可以通过均对于乘性干扰，可以通过均衡器来消除码间串扰的影响。随衡器来消除码间串扰的影响。随机加性干扰通常由信道产生。根机加性干扰通常由信道产生。根据随机加性干扰的不同特点，从据随机加性干扰的不同特点，从差错控制角度看，相应的信道可差错控制角度看，相

2、应的信道可第2页/共264页突发信道：错码的出现是前突发信道：错码的出现是前后相关的。当错码出现时，会在后相关的。当错码出现时，会在短时间内有一连串的大量错码，短时间内有一连串的大量错码，而该时间过后又有较长的时间无而该时间过后又有较长的时间无错码。造成突发错码的原因是信错码。造成突发错码的原因是信道中存在随机的强突发脉冲干扰，道中存在随机的强突发脉冲干扰，为混合信道。为混合信道。第3页/共264页在介绍差错控制方式之前，在介绍差错控制方式之前，下面先了解一下降低误码、提高下面先了解一下降低误码、提高数字通信可靠性的几种途径。根数字通信可靠性的几种途径。根据实际通信系统对其可靠性的要据实际通信

3、系统对其可靠性的要求，可以用不同的方法提高通信求，可以用不同的方法提高通信的可靠性。的可靠性。(1) 适当增加发送信号功率。适当增加发送信号功率。增大信号的功率，即提高输入端增大信号的功率，即提高输入端无限增大。所以，此种方法在实无限增大。所以，此种方法在实际中受到了一定限制。际中受到了一定限制。第4页/共264页(2) 选择抗噪声性能好的调选择抗噪声性能好的调制解调方式。比如，在数字调制制解调方式。比如，在数字调制中移相键控中移相键控PSK比幅度键控比幅度键控ASK的误码率要小得多。所以在实际的误码率要小得多。所以在实际中多采用移相键控中多采用移相键控PSK，而很少，而很少采用幅度键控采用幅

4、度键控ASK。(3) 采用最佳接收。最佳接采用最佳接收。最佳接收可以使数字通信的误码率达到收可以使数字通信的误码率达到制方式。这是本章的主要内容。制方式。这是本章的主要内容。第5页/共264页9.1.29.1.2差错控制编码的基本方差错控制编码的基本方法与差错控制方式法与差错控制方式对于不同类型的信道，要采对于不同类型的信道，要采用不同的差错控制方式。不同的用不同的差错控制方式。不同的差错控制编码也要与相应的差错差错控制编码也要与相应的差错第6页/共264页第7页/共264页1. 1. 检错重发检错重发(ARQ)(ARQ)方式方式检错重发方式又称为自动请检错重发方式又称为自动请求重发方式。这种

5、差错控制方式求重发方式。这种差错控制方式在发送端对数据序列进行分组编在发送端对数据序列进行分组编码，加入一定多余码元使之具有码，加入一定多余码元使之具有一定的检错能力，成为能够发现一定的检错能力，成为能够发现错误的码组。接收端收到码组后，错误的码组。接收端收到码组后，候重发、返回重发和选择重发。候重发、返回重发和选择重发。ARQ方式的组成如图方式的组成如图9.2所示。所示。第8页/共264页第9页/共264页1) 停止等待停止等待ARQ停止等待停止等待ARQ是最简单的是最简单的ARQ系统，也称为空闲系统，也称为空闲RQ(idleRQ)。这种系统每发送一个分。这种系统每发送一个分第10页/共26

6、4页第11页/共264页2) 连续连续ARQ连续连续ARQ工作在全双工方式，工作在全双工方式，需要有一定的缓冲器容量。这种需要有一定的缓冲器容量。这种系统两端同时发送信息，发送端系统两端同时发送信息，发送端连续发送数据，并接收应答信号，连续发送数据，并接收应答信号，接收端连续接收数据并发送应答接收端连续接收数据并发送应答信号。连续信号。连续ARQ的工作原理如图的工作原理如图及处理及处理所带来的延时，图所带来的延时，图9.4中中N=5。第12页/共264页第13页/共264页3) 选择重发选择重发ARQ选择重发选择重发ARQ是由连续是由连续ARQ发展而来的，工作在全双工方式，发展而来的，工作在全

7、双工方式，第14页/共264页第15页/共264页2. 2. 前向纠错前向纠错(FEC)(FEC)方式方式在前向纠错在前向纠错(FEC)方式中，方式中，发送端发出的码字不仅能够发现发送端发出的码字不仅能够发现错误，而且能够纠正错误。在接错误，而且能够纠正错误。在接收端译码后，若没有错误，则直收端译码后，若没有错误，则直接输出；若有错误，则在接收端接输出；若有错误，则在接收端自动纠正后再输出。这种方式不自动纠正后再输出。这种方式不需要反向信道，特别适合于只能需要反向信道，特别适合于只能等通信中。等通信中。第16页/共264页3. 3. 混合纠错检错混合纠错检错(HEC)(HEC)方方式式混合纠错

8、检错混合纠错检错(HEC)方式是方式是将将ARQ方式和方式和FEC方式结合使用方式结合使用的一种方式。在混合纠错检错系的一种方式。在混合纠错检错系统中，发送端发出同时具有检错统中，发送端发出同时具有检错和纠错能力的码，接收端收到码和纠错能力的码，接收端收到码后，检查错误情况，如果错误少后，检查错误情况，如果错误少于纠错能力，则自行纠正，即于纠错能力，则自行纠正，即FEC方式；如果干扰严重，错误方式；如果干扰严重，错误动纠正错码；在错码较多时，采动纠正错码；在错码较多时，采用用ARQ方式自动请求重发。方式自动请求重发。第17页/共264页4. 4. 反馈校验反馈校验(IRQ)(IRQ)方式方式反

9、馈校验反馈校验(IRQ)方式也称为方式也称为信息反馈方式或回程校验方式。信息反馈方式或回程校验方式。在该方式中，发送端一边发送码在该方式中，发送端一边发送码字，一边将发送的码字在发送端字，一边将发送的码字在发送端缓冲存储。当接收端收到码字后，缓冲存储。当接收端收到码字后，效率很低。效率很低。第18页/共264页9.1.39.1.3纠错编码的基本原理纠错编码的基本原理1. 有扰信道的编码定理有扰信道的编码定理香农有扰信道的编码定理指香农有扰信道的编码定理指出：在有扰信道中只要信息的传出：在有扰信道中只要信息的传输速率输速率R小于信道容量小于信道容量C，总可，总可以找到一种编码方法，使信息以以找到

10、一种编码方法，使信息以任意小的差错概率通过信道传送任意小的差错概率通过信道传送到接收端，即误码率到接收端，即误码率Pe可以任意可以任意码长码长)；E(R)为误码指数。为误码指数。E(R)与与R、C有关，其关系可用曲线有关，其关系可用曲线表示，如图表示，如图9.6所示。所示。第19页/共264页第20页/共264页由式由式(9.1)及及E(R)与与R、C的关的关系曲线可以看出，要提高抗干扰系曲线可以看出，要提高抗干扰能力，减小误码率能力，减小误码率Pe，有以下两，有以下两种途径：种途径： (1) 在编码长度在编码长度n及信息的传及信息的传输速率输速率R一定时，为减小一定时，为减小Pe，可，可以增

11、加信道容量以增加信道容量C。由图。由图9.6可见，可见，功率功率P和系统带宽和系统带宽B来实现，即通来实现，即通过增加信号功率过增加信号功率P和系统带宽和系统带宽B可可以减小误码率。以减小误码率。第21页/共264页(2) 在信道容量在信道容量C及信息的传及信息的传输速率输速率R一定的情况下，由式一定的情况下，由式(9.1)可知，增加码长可知，增加码长n也可以使误码也可以使误码率率Pe指数减小，即通过增加信道指数减小，即通过增加信道第22页/共264页2. 2. 纠错编码原理纠错编码原理第23页/共264页最大似然译码准则：在收到最大似然译码准则：在收到码码r的条件下，计算的条件下，计算2k个

12、个(许用码许用码的个数的个数)条件概率，其条件概率，其中中CL为许用码字，若条件概率为许用码字，若条件概率为最大，则认为收到的码字为最大，则认为收到的码字r就就是发送来的是发送来的C码字。码字。 式中式中: ri为接收码字的第为接收码字的第i位元素；位元素；CLi为许用码字为许用码字CL的第的第i位元素。位元素。LrPCLrPCLrPC第24页/共264页显然，当接收码元出错，即显然，当接收码元出错，即riCLi时，概率时，概率; 当当码元接收正确，即码元接收正确，即ri=CLi时，概时，概率。令率。令d为接收为接收(9.3)eLiiPCrP1ieLirPPC ee(1)n ddLrPPPC第

13、25页/共264页可见可见，由于，由于，随随d单调下降，因此，单调下降，因此，d越小，越小， 越大。越大。 越大表明接收到越大表明接收到12eP LrPCLrPCLrPC第26页/共264页9.1.49.1.4码间距离码间距离d d与检错纠错能与检错纠错能力力1 1 码间距离码间距离d d码间距离码间距离(code distances)是是一个码组中任意两个码字之间对一个码组中任意两个码字之间对应位上码元取值不同的位数，用应位上码元取值不同的位数，用位模位模2相加后相加后“1”的个数。的个数。10(,)()nijipjppd C Ccc第27页/共264页 一般两个码字的码距计算方一般两个码字

14、的码距计算方法为：设两个码字法为：设两个码字Ci、Cj分别为分别为101110 和和 101011，则码距可按下，则码距可按下式计算式计算: :101110:101011000101ijccd 第28页/共264页在一个码组中，各码字之间在一个码组中，各码字之间的距离不一定都相等，有的大，的距离不一定都相等，有的大，有的小。通常称码组中最小的码有的小。通常称码组中最小的码距为最小码间距离，用距为最小码间距离，用第29页/共264页对于三位编码的码间距离，对于三位编码的码间距离，可用三维几何空间来说明。三位可用三维几何空间来说明。三位编码的码字共有编码的码字共有23=8个，用三维个，用三维几何空

15、间立方体的几何空间立方体的8个顶点来表个顶点来表示，如图示，如图9.7所示。码字之间的距所示。码字之间的距离可用对应两顶点间沿立方体各离可用对应两顶点间沿立方体各说明。说明。第30页/共264页第31页/共264页2. 2. 最小距离最小距离d d0 0与检错纠错与检错纠错能力的关系能力的关系(1) 当码组仅用于检测错误当码组仅用于检测错误时，若要求检测时，若要求检测e个错误，则最个错误，则最小码距为小码距为d0=e+1(9.5)若要检测若要检测e个错码，则必须满足个错码，则必须满足d0e+1的要求。的要求。第32页/共264页第33页/共264页(2) 当码组仅用于纠正错误当码组仅用于纠正错

16、误时，为纠正时，为纠正t个错误，要求最小码个错误，要求最小码距为距为d0e+t(9.6)这可用图这可用图9.8(b)来说明。码字来说明。码字A发发生两位错，落在以生两位错，落在以A为圆心、以为圆心、以2为为5。所以纠正。所以纠正t个错误，必须满个错误，必须满足足d02t+1的要求。的要求。第34页/共264页(3) 当码组既要检错，又要当码组既要检错，又要纠错时，为纠正纠错时，为纠正t个错误，同时检个错误，同时检测测e个错误，要求的最小码距为个错误，要求的最小码距为d0e+t+1et(9.7)这可用图这可用图9.4(c)来说明。当码字来说明。当码字A也即最小码距也即最小码距d0e+t+1。第3

17、5页/共264页3 3 差错控制编码的效果差错控制编码的效果对于随机错误的情况，假设对于随机错误的情况，假设误码率为误码率为P， 且且P1。在码长。在码长为为n的码字中刚好发生的码字中刚好发生r个错误的个错误的概率为概率为2.110-5, P7(3)35P3=3.510-8。 !(1)(1)!()!rrn rrn rnnnP rC PPPPr nr第36页/共264页4 4 纠错编码的分类纠错编码的分类第37页/共264页第38页/共264页(1) 按照其实现的功能，纠按照其实现的功能，纠错编码可以分为检错码和纠错码。错编码可以分为检错码和纠错码。一般来说，能够发现错误的码称一般来说，能够发现

18、错误的码称为检错码。在译码时不仅能够发为检错码。在译码时不仅能够发现错误，而且能够自动纠正错误，现错误，而且能够自动纠正错误，通过译码产生正确的码字，这样通过译码产生正确的码字，这样称为非线性码。称为非线性码。第39页/共264页(3) 按照对信息码元处理方按照对信息码元处理方法的不同，纠错编码分为分组码法的不同，纠错编码分为分组码和卷积码。分组码是将和卷积码。分组码是将k个信息个信息码元划分为一组，然后由这码元划分为一组，然后由这k个码元按照一定的规则产生个码元按照一定的规则产生r个个监督码元，从而组成长度监督码元，从而组成长度n=k+r随机错误的码和纠突发错误的码。随机错误的码和纠突发错误

19、的码。第40页/共264页5. 5. 编码效率编码效率在分组码编码中，加入的监在分组码编码中，加入的监督位越多，检错纠错能力越强。督位越多，检错纠错能力越强。但这会使总的码长增加，但这会使总的码长增加，(即要即要传输的位数增加传输的位数增加)，从而使编码，从而使编码的效率降低。设码字的信息码元的效率降低。设码字的信息码元个数为个数为k，监督码元个数为，监督码元个数为r，总，总的码元的个数的码元的个数(即总的码长即总的码长)为为可见可见, 监督位越多，编码效率越监督位越多，编码效率越低。低。1knrrnnn 第41页/共264页9.29.2常用简单差错控制编码常用简单差错控制编码9.2.19.2

20、.1奇偶监督码奇偶监督码奇偶监督码奇偶监督码(也称奇偶校验也称奇偶校验第42页/共264页偶监督码是给信息位后增加偶监督码是给信息位后增加一位监督位，使码字中一位监督位，使码字中“1”的数的数目为偶数，满足如下关系：目为偶数，满足如下关系：(9.11)式中：式中：cn-1cn-2c1为信息位为信息位; c0为为码字有错，但检测不到，所以这码字有错，但检测不到，所以这种码不能检测偶数个错。种码不能检测偶数个错。12100nncccc第43页/共264页在编码的过程中，监督位是在编码的过程中，监督位是由信息位产生的，该编码监督位由信息位产生的，该编码监督位的产生方程为的产生方程为(9.12)奇监督

21、码是给信息位后增加奇监督码是给信息位后增加 (9.14)0121nncccc12101nncccc01211nncccc第44页/共264页奇偶监督码的编码效率奇偶监督码的编码效率较较高，尤其是当码长高，尤其是当码长n较大时这一较大时这一特点更为明显。在特点更为明显。在n值很大时编值很大时编码效率趋近于码效率趋近于1，即，即1111rnn 第45页/共264页9.2.29.2.2二维奇偶监督码二维奇偶监督码二维奇偶监督码也称为方阵二维奇偶监督码也称为方阵码、行列监督码或水平码、行列监督码或水平-垂直奇偶垂直奇偶监督码。其编码方法是把监督码。其编码方法是把m个信个信息码字排列成一个方阵，每个码息

22、码字排列成一个方阵，每个码字构成方阵的一行，在每一行的字构成方阵的一行，在每一行的9.10所示。所示。第46页/共264页第47页/共264页9.2.39.2.3恒比码恒比码恒比码的特点是每个许用码恒比码的特点是每个许用码含有相同数目的含有相同数目的“1”。在码字中，。在码字中，“1”与与“0”的个数之比是恒定的，的个数之比是恒定的，所以称之为恒比码。一个码字中所以称之为恒比码。一个码字中第48页/共264页我国电传机传输汉字采用的我国电传机传输汉字采用的是是“5中取中取3” 恒比码，其码长为恒比码，其码长为5，码字中码字中“1”的个数为的个数为3，称为保，称为保护电码。码长为护电码。码长为5

23、的二进制数共的二进制数共有有32种组合，选择其中含有种组合，选择其中含有3个个“1”的组合作为许用码，所以的组合作为许用码，所以列出了这两种编码。列出了这两种编码。第49页/共264页第50页/共264页9.39.3线线 性性 分分 组组 码码9.3.19.3.1线性分组码的概念线性分组码的概念数字通信系统的信源输出是数字通信系统的信源输出是由由“0”和和“1”组成的二进制序列，组成的二进制序列，在分组码中，该二元信息序列被在分组码中，该二元信息序列被分成码元个数固定的一分成码元个数固定的一组组信息，每组信息的码元由组组信息，每组信息的码元由k第51页/共264页所谓线性分组码，就是一种所谓线

24、性分组码，就是一种长度为长度为n，其中，其中2k个许用码组个许用码组(代代表信息的码组表信息的码组)中的任意两个码中的任意两个码组的模组的模2和仍为一个许用码组的和仍为一个许用码组的分组码。这种长度为分组码。这种长度为n，有，有2k个个第52页/共264页线性分组码的构成方法是：线性分组码的构成方法是：将信息序列分为每将信息序列分为每k位一组的信位一组的信息序列段，每一信息序列段按照息序列段，每一信息序列段按照一定规律添加一定规律添加r个监督码元，构个监督码元，构成总码长为成总码长为n=k+r的分组码，记的分组码，记为为(n, k)。在分组码中，监督码元。在分组码中，监督码元仅与本分组中的信息

25、码元有关，仅与本分组中的信息码元有关，各许用码的集合构成代数学中的各许用码的集合构成代数学中的群，又称为群码。群，又称为群码。第53页/共264页表表9.2示出了线性分组码的一示出了线性分组码的一种结构。码字的前一部分是连续种结构。码字的前一部分是连续第54页/共264页第55页/共264页9.3.29.3.2线性分组码的监督矩阵线性分组码的监督矩阵假定监督码元与信息码元的假定监督码元与信息码元的关系由下列线性方程组决定关系由下列线性方程组决定:265416530643cccccccccccc =排=排=排 第56页/共264页对式对式(9.16)移项后可得三个监移项后可得三个监督关系式督关系

26、式(该方程组在二元有限该方程组在二元有限域上求解，系数取值为域上求解，系数取值为“0”或或“1”):654265316430000cccccccccccc 排排排 第57页/共264页第58页/共264页将式将式(9.17)中的零系数项补上，中的零系数项补上，写出系数可得：写出系数可得：第59页/共264页把式把式(9.18)写成矩阵形式如下写成矩阵形式如下:第60页/共264页将式将式(9.16)写成矩阵形式写成矩阵形式:第61页/共264页令式令式(9.19)的系数矩阵为的系数矩阵为第62页/共264页进一步分析进一步分析H，利用矩阵分，利用矩阵分块的方法，块的方法，H可写为可写为第63页

27、/共264页其中其中, P见式见式(9.20)，I3为为3阶阶单位矩阵，即单位矩阵，即第64页/共264页对于对于(n，k)分组码，分组码，r=nk，H可写为可写为(9.25)第65页/共264页9.3.39.3.3线性分组码的生成矩阵线性分组码的生成矩阵生成矩阵是在已知信息码元生成矩阵是在已知信息码元时确定相应的许用码字时确定相应的许用码字C=c6c5c4c3c2c1c0的矩阵。由式的矩阵。由式第66页/共264页将式将式(9.26)写成矩阵形式写成矩阵形式:第67页/共264页对式对式(9.27)取转置得：取转置得：第68页/共264页式中：式中：第69页/共264页其中其中:(9.30)

28、第70页/共264页由式由式(9.29)得，得，G=IkQ ，其中，其中Ik为为k阶单位矩阶单位矩阵。这种形式的生成矩阵阵。这种形式的生成矩阵G是典是典型生成矩阵。同样，典型生成矩型生成矩阵。同样，典型生成矩阵的各行也是线性无关的。由典阵的各行也是线性无关的。由典型生成矩阵得出的码字型生成矩阵得出的码字C是信息是信息位在前、监督位在后的系统码。位在前、监督位在后的系统码。中一个，则另一个确定，其监督中一个，则另一个确定，其监督关系和它所对应的码也就确定了。关系和它所对应的码也就确定了。第71页/共264页在线性分组码中，任意两个在线性分组码中，任意两个许用码字对应位模许用码字对应位模2相加还是

29、此相加还是此码组中的一个码字，所以线性分码组中的一个码字，所以线性分组码具有封闭性。对组码具有封闭性。对(n，k)线性线性分组码来说，其信息位长为分组码来说，其信息位长为k，共有共有2k个不同组合的信息码。设个不同组合的信息码。设Cix、Cjx为其中两个信息码，由为其中两个信息码，由ij成矩阵为成矩阵为G的线性分组码中的一的线性分组码中的一个许用码字。个许用码字。第72页/共264页(n，k)线性分组码线性分组码A的生成的生成矩阵矩阵G的每一行都是码组的每一行都是码组A的一的一个许用码字，它一定满足个许用码字，它一定满足H矩阵矩阵所确定的所确定的r个监督关系。如果把个监督关系。如果把G当作另一

30、个码组当作另一个码组B的监督矩阵，的监督矩阵，把把H当作码组当作码组B的生成矩阵，则的生成矩阵，则码组码组B为为(n，nk)线性分组码，线性分组码，(9.32)第73页/共264页由于线性分组码具有封闭性，由于线性分组码具有封闭性，因此由码距的定义可知，任意两因此由码距的定义可知，任意两个许用码字之间的距离必然是另个许用码字之间的距离必然是另一个许用码字的重量。所以，该一个许用码字的重量。所以，该码的最小重量码的最小重量(除全除全“0”码字外码字外)必然是该线性分组码的最小距离。必然是该线性分组码的最小距离。(9.33)第74页/共264页由由CHT=0可见，当可见，当C取最小取最小重量的码字

31、，即重量的码字，即C中中“1”的个数的个数为为Wmin时，得到时，得到H中最小相关的中最小相关的列的数目，即列的数目，即H中小于或等于中小于或等于Wmin1 列是线性独立的、不相列是线性独立的、不相第75页/共264页9.3.49.3.4线性分组码的伴随式和线性分组码的伴随式和检错纠错能力检错纠错能力设发送端发出的许用码为设发送端发出的许用码为C=cn-1cn-2c1c0，它符合，它符合CHT=0 。假设经过信道传输后。假设经过信道传输后接收端收到的码字为接收端收到的码字为R=rn-1rn-2 r1r0。如果。如果R=C，把，把(9.34)第76页/共264页E称为差错序列或错误图样。称为差错

32、序列或错误图样。因为因为E表示表示R中具体哪一位发生中具体哪一位发生错误，即错误，即第77页/共264页其中，其中，S=sn-1sn-2s1s0，为为1r阶行矢量。由式阶行矢量。由式(9.35)可见，可见，S只与错误图样只与错误图样E有关，而与发送有关，而与发送的码字的码字C无关，这意味着无关，这意味着S与与E有有线性变换关系，能与线性变换关系，能与E一一对应，一一对应，可指示错码位置，所以可指示错码位置，所以S称为监称为监督矩阵为督矩阵为H的的(n，k)线性分组码线性分组码则必定有错，由则必定有错，由S可判断出错码可判断出错码的位置。的位置。第78页/共264页下面以下面以(7，4)码为例进

33、行说码为例进行说明。设明。设C=0001011,若传输中若传输中c3发生误码发生误码,即发生一位错即发生一位错,E=0001000,R=0000011,则由式则由式(9.35)可得：可得：第79页/共264页可见可见, ST刚好是错误图样刚好是错误图样E中中“1”所对应的所对应的H中的一列，即中的一列，即R的第的第i位有错，则位有错，则E的第的第i位为位为“1”，ST与与H中的第中的第i列相同。判断出错列相同。判断出错误后，可利用误后，可利用RE=C纠错。纠错。第80页/共264页当当S=0时，符合监督关系式，时，符合监督关系式，判断接收到的码无错；当判断接收到的码无错；当S=1时，时，不符合

34、监督关系式，就认为有错。不符合监督关系式，就认为有错。S的取值只有两个，它只能表示的取值只有两个，它只能表示无错、有错两种状态，而无法指无错、有错两种状态，而无法指出错在哪一位，因此，它只能检出错在哪一位，因此，它只能检错，不能纠错。如果再增加一位错，不能纠错。如果再增加一位r个可能的位置。个可能的位置。第81页/共264页由以上分析可知，对由以上分析可知，对(n，k)线性分组码，有线性分组码，有r=nk个监督关个监督关系式，有系式，有2r个不同的个不同的S。全。全0矢量矢量表示无错，所以表示无错，所以S最多可指出最多可指出2r第82页/共264页其中其中, Cin为组合数为组合数, 即即第8

35、3页/共264页线性分组码的主要性质如下：线性分组码的主要性质如下：(1) 封闭性。封闭性是指码封闭性。封闭性是指码中任意两个许用码组之和中任意两个许用码组之和(逐位逐位模模2和和)仍为一个许用码组。也就仍为一个许用码组。也就是说，若是说，若C1和和C2为分组码中的两为分组码中的两第84页/共264页在通信传输过程中如果错码在通信传输过程中如果错码较多，已超过这种编码的检错能较多，已超过这种编码的检错能力，即力，即R变为另一许用码组，则变为另一许用码组，则式式(9.22)仍成立。由于线性分组仍成立。由于线性分组码具有封闭性质，因此由式码具有封闭性质，因此由式(9.34)中中R=CE可知，只有当

36、可知，只有当E=C，即错误码组刚好等于任意许用码即错误码组刚好等于任意许用码其中，其中，Wi是重量为是重量为i的许用码组的许用码组数目。数目。第85页/共264页9.3.59.3.5汉明码汉明码汉明码是一种可以纠正单个汉明码是一种可以纠正单个随机错误的线性分组码，它是一随机错误的线性分组码，它是一种完备码，编码效率很高。在式种完备码，编码效率很高。在式(9.37)中，令中，令t=1(即纠正一位错即纠正一位错)，并取等号得并取等号得:2r1=n(9.40)0t，n越越大，大，越高。越高。1121rrrn 第86页/共264页(9.42) (9.41) 第87页/共264页汉明码只能纠正一位错，其

37、汉明码只能纠正一位错，其最小码距最小码距d0=3。当码字中出现两。当码字中出现两位错时，它检测不出来，必然会位错时，它检测不出来，必然会造成错判。如果在汉明码的基础造成错判。如果在汉明码的基础上增加一位对所有码元都进行校上增加一位对所有码元都进行校验的监督码元，则监督码元的位验的监督码元，则监督码元的位同时也能检测同时也能检测2位错。位错。第88页/共264页增余汉明码的构成是增加一增余汉明码的构成是增加一位监督码元，使原汉明码的最小位监督码元，使原汉明码的最小码重由奇数变为偶数。其监督矩码重由奇数变为偶数。其监督矩阵可以由原汉明码的监督矩阵阵可以由原汉明码的监督矩阵H得到：得到：在最后一行添

38、加一行全在最后一行添加一行全1构成的。构成的。第89页/共264页如果把上述如果把上述(7，4)汉明码变汉明码变为对应的为对应的(8，4)增余汉明码，则增余汉明码，则其监督矩阵为其监督矩阵为第90页/共264页9.49.4循环码循环码9.4.19.4.1循环码的循环特性与码循环码的循环特性与码多项式多项式循环码是线性分组码的一个循环码是线性分组码的一个重要分支。循环码除了具有线性重要分支。循环码除了具有线性码的一般性质外，还具有循环性，码的一般性质外，还具有循环性，的应用。的应用。第91页/共264页对于一个对于一个(n，k)线性码线性码C，若其中的任一码组向左或向右循若其中的任一码组向左或向

39、右循环移动任意位后仍是环移动任意位后仍是C中的一个中的一个码组，则称码组，则称C是一个循环码。循是一个循环码。循环码是一种线性分组码，它除了环码是一种线性分组码，它除了具有线性分组码的封闭性之外，具有线性分组码的封闭性之外，还具有循环性。通常其前还具有循环性。通常其前k位是位是信息码元，后信息码元，后r位为监督码元，位为监督码元，移、右移多少位，得到的结果均移、右移多少位，得到的结果均为该循环码中的一个码字。为该循环码中的一个码字。第92页/共264页下式所示的码字均为该循环下式所示的码字均为该循环码中的一个码字码中的一个码字:第93页/共264页第94页/共264页为了便于用代数学的理论分为

40、了便于用代数学的理论分析计算循环码，可把循环码中的析计算循环码，可把循环码中的码字用多项式来表示，称为码多码字用多项式来表示，称为码多项式，也就是把码字中各码元的项式，也就是把码字中各码元的第95页/共264页其中其中, xi是码元位置的标记，它表是码元位置的标记，它表示由其系数所决定的码元取值所示由其系数所决定的码元取值所处的对应位置，其系数只能取处的对应位置，其系数只能取0或或1，运算时其系数的运算为模，运算时其系数的运算为模2运算。例如，码字运算。例如，码字1001110、0011101可用码多项式表示为可用码多项式表示为1001110 0011101=1010011第96页/共264页

41、在整数的按模运算中，最熟在整数的按模运算中，最熟悉的是模悉的是模2运算，如运算，如1+10(模模2)，1+21(模模2)等。对于模等。对于模n运算，如果一个整数运算，如果一个整数m可以表示可以表示为为称称m与与p是同余的。是同余的。,mpQpnnn（）第97页/共264页在多项式中同样可以进行类在多项式中同样可以进行类似的按模运算，如似的按模运算，如(9.49)其中其中: F(x)是幂次为是幂次为n的多项式的多项式; ( )( )( )( )( )F xR xQ xN xN x第98页/共264页码多项式系数仍按模码多项式系数仍按模2运算，运算，即只取值即只取值0和和1。比如。比如, x3被被

42、x3+1除除可得余式为可得余式为1， 于是有：于是有：x31(模模x3+1)(9.52) 第99页/共264页定理定理9.4.1若若T(x)是长为是长为n的的循环码中某个许用码组的码多项循环码中某个许用码组的码多项式，则式，则xiT(x)在按模在按模xn+1运算下运算下也是该循环码中一个许用码组的也是该循环码中一个许用码组的码多项式。码多项式。例如例如, (7，3)循环码中许用码循环码中许用码0011101左移左移3次后形成的。次后形成的。365377( )1111xT xxxxxx 第100页/共264页定理定理9.4.1证明如下：证明如下：设设T(x)=cn-1xn-1+cn-2xn-2+

43、c1x1+c0，那么有，那么有第101页/共264页其中其中, Ri(x)=cn-1-ixn-1+cn-2-ixn-2+c0 xi+cn-1xi-1+cn-i是是T(x)左左移移i位后形成的码字。若把位后形成的码字。若把i取不取不同的值重复做上述运算，则可得同的值重复做上述运算，则可得第102页/共264页9.4.2循环码的生成多项式与生循环码的生成多项式与生成矩阵成矩阵定理定理9.4.2在循环码在循环码(n, k)中，中，第103页/共264页一旦一旦g(x)确定，该确定，该(n, k)循环循环码就被确定了。码就被确定了。g(x)是循环码中是循环码中幂次最低的码多项式。由它左移幂次最低的码多

44、项式。由它左移就可产生其他码多项式，比如就可产生其他码多项式，比如xg(x)、x2g(x)、x3g(x)等。用等。用k第104页/共264页例如，有一个例如，有一个(7，3)循环码循环码(其最高次幂为其最高次幂为(n, k)次次)的码字为的码字为0010111，其生成多项式，其生成多项式g(x)=x4+x2+x+1，则利用式，则利用式(9.55)可得其生成矩阵可得其生成矩阵G(x)：第105页/共264页将此生成矩阵用系数表示，将此生成矩阵用系数表示，写为生成矩阵写为生成矩阵G:(9.57)第106页/共264页例如，对于例如，对于(7，3)循环码，循环码，设信息码为设信息码为c6c5c4，由

45、生成矩，由生成矩阵多项式可以写出该循环码的码阵多项式可以写出该循环码的码字字:第107页/共264页因此因此，已知信息码，已知信息码U=uk-1uk-2u1u0和和g(x)就可求得循环就可求得循环码的所有码多项式码的所有码多项式:T(x)=uk-1uk-2u1u0G(x)=u(x)g(x)第108页/共264页定理定理9.4.3循环码循环码(n, k)的生的生成多项式成多项式g(x)是是xn+1的一个因式。的一个因式。定理分析定理分析：g(x)是最高次幂是最高次幂为为nk次的码多项式。次的码多项式。xkg(x)是是最高次幂为最高次幂为n的多项式。利用定的多项式。利用定理理9.4.1对对xkg(

46、x)作模作模xn+1运算，运算，( )( )111knnxg xR xxx 第109页/共264页对上式移项得对上式移项得:xn+1=xkg(x)+I(x)g(x)=xk+I(x)g(x)=h(x)g(x)(9.61)即即g(x)是是xn+1的因式。式中的因式。式中n的因式作为生成多项式的因式作为生成多项式g(x)。1( )( )nxh xg x第110页/共264页例如例如, 对于对于(7，3)循环码，循环码，g(x)的最高次幂为的最高次幂为4, 可以从可以从x7+1中分解得到中分解得到g(x)。x7+1 可分解为可分解为x7+1=(x+1)(x3+x2+1)(x3+x+1)(9.62)第1

47、11页/共264页9.4.3循环码的编码与解码循环码的编码与解码1 循环码的编码循环码的编码在编码时，首先要根据给定在编码时，首先要根据给定的的(n, k)值选定生成多项式值选定生成多项式g(x)，即应在即应在xn+1的因式中选一个的因式中选一个nk次多项式作为次多项式作为g(x)。(9.65)第112页/共264页信息码多项式信息码多项式m(x)的最高次的最高次幂为幂为k1。将。将m(x)左移左移nk位成位成为为xn-km(x)，其最高次幂为，其最高次幂为n-1。xn-km(x)的前一部分为连续的前一部分为连续k位信位信息码，后一部分为息码，后一部分为r=nk位位“0”，r正好是监督码的位数

48、正好是监督码的位数, 所以在它所以在它的后一部分添上监督码，就编出的后一部分添上监督码，就编出了相应的系统码。监督码由监督了相应的系统码。监督码由监督( )( )( )( )( )n kxm xr xq xg xg x第113页/共264页所得的余式所得的余式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)x码多项式，而且是系统码。码多项式，而且是系统码。第114页/

49、共264页对对(7，3)循环码选择生成多循环码选择生成多项式项式g(x)=x4+x3+x2+1，设已知信，设已知信息码为息码为111, 则信息码多项式为则信息码多项式为第115页/共264页(2) 利用式利用式(9.66)所示的所示的做除法，求出余式做除法，求出余式r(x)。本例中。本例中为为( )( )( )( )( )n kxm xr xq xg xg x1123422234456xxxxxxxxxxx111010100100111011110000第116页/共264页(3) 构成系统码构成系统码T(x)=xn-km(x)+r(x)。本例中为。本例中为1110000+0100=11101

50、00。第117页/共264页第118页/共264页在编码器工作之前先清零，在编码器工作之前先清零，使寄存器的初态为零，使转换开使寄存器的初态为零，使转换开关关S1、S2均向下，均向下，S1使反馈线接使反馈线接通，通，S2使输入直接加到输出。开使输入直接加到输出。开始输入三位信息码。输入的信息始输入三位信息码。输入的信息码码m(x)一路直接送到输出端，作一路直接送到输出端，作为系统码的前面一部分为系统码的前面一部分(即信息即信息码部分码部分)，另一路送入除法器作，另一路送入除法器作9.5所示为上述编码过程中各点的所示为上述编码过程中各点的状态变化过程。状态变化过程。第119页/共264页第120

51、页/共264页通常对于一个通常对于一个(n, k)循环码，循环码，若设生成多项式为若设生成多项式为第121页/共264页第122页/共264页2. 循环码的解码循环码的解码循环码的解码分为检错和纠循环码的解码分为检错和纠错两种情况。只进行检错的解码错两种情况。只进行检错的解码其原理较简单，它是利用任何码其原理较简单，它是利用任何码( )( )( )( )( )R xr xq xg xg x第123页/共264页其中其中, r(x)为余式。若余式为余式。若余式r(x)为零，接收码字为零，接收码字R(x)能被整能被整除，则除，则R(x)=T(x)，判断无错码，判断无错码; 第124页/共264页若

52、要纠正错误，若要纠正错误， 则需要知道则需要知道错误图样错误图样E(x)，以便纠正错误。，以便纠正错误。原则上纠错解码可按以下步骤进原则上纠错解码可按以下步骤进行：行：(1) 用生成多项式用生成多项式g(x)除接收除接收码字码字R(x)=T(x)+E(x)，得到余式，得到余式r(x)。(2) 按余式按余式r(x)用查表的方法用查表的方法第125页/共264页下面通过下面通过(7，3)循环码的纠循环码的纠错解码器来说明其工作原理。错解码器来说明其工作原理。(7，3)纠错解码器如图纠错解码器如图9.13所示。它所示。它包含除法器、缓冲器、门电路及包含除法器、缓冲器、门电路及输出前作模输出前作模2运

53、算的异或门。接运算的异或门。接收到的码字收到的码字R(x)输入后分为两路：输入后分为两路：一路送入缓冲器暂存，另一路送一路送入缓冲器暂存，另一路送入除法器作除法。当码字全部进入除法器作除法。当码字全部进入除法器后，若入除法器后，若R(x)能被能被g(x)整整码字正确；另一方面反馈回除法码字正确；另一方面反馈回除法器，使各级移位寄存器清零。器，使各级移位寄存器清零。ea b c d第126页/共264页第127页/共264页实际中接收的码字是连续不实际中接收的码字是连续不断输入的，中间没有停顿。为了断输入的，中间没有停顿。为了使解码器在移位纠错时不丢失输使解码器在移位纠错时不丢失输第128页/共

54、264页9.4.4BCH码码BCH码的最小码距码的最小码距dmin2t+1，能纠，能纠t个错误。个错误。BCH码是循环码中重要的一类子码，码是循环码中重要的一类子码，它的生成多项式它的生成多项式g(x)与最小码距与最小码距第129页/共264页BCH码的特点是能纠正多个码的特点是能纠正多个随机错误，可以根据给定的纠错随机错误，可以根据给定的纠错能力找出生成多项式。能力找出生成多项式。 BCH码码分为两类：本原分为两类：本原BCH码和非本原码和非本原BCH码。本原码。本原BCH码的码长码的码长n=2m1，m3, 生成多项式生成多项式g(x)中含有最高次数为中含有最高次数为m的本原多项的本原多项式

55、；非本原式；非本原BCH码的码长码的码长m1。第130页/共264页BCH码生成多项式：码生成多项式：g(x)=LCMm1(x), m2(x), , m2t-1(x)(9.71)式中式中: t为可纠正的错误个数；为可纠正的错误个数；mi(x)为最小多项式；为最小多项式；LCM()是是指取括号内所有多项式的最小公指取括号内所有多项式的最小公g82g(x)=x3+x+1。第131页/共264页【例例9.1】构造一个能纠正构造一个能纠正3个错误、个错误、 码长为码长为15的的BCH码。码。解解： 由码长与生成多项式的由码长与生成多项式的关系可知，关系可知，n=15，t=3，m为为4，因为因为第132

56、页/共264页【例例9.2】非本原非本原BCH码码为为(23，12)，试求其生成多项式。，试求其生成多项式。解解： 对非本原对非本原BCH码码(23，第133页/共264页下面介绍几种常见的下面介绍几种常见的BCH码。码。 (1) 格雷格雷(Golay)码。码。BCH码码(23，12)是一个特殊的非本原是一个特殊的非本原BCH码，称为戈雷码，它的最小码，称为戈雷码，它的最小码距码距dmin=2t+1=7，能纠正，能纠正t=3个个错误，其生成多项式为错误，其生成多项式为119765第134页/共264页 (3) 缩短形式。几乎所有的缩短形式。几乎所有的循环码都存在其另一种缩短形式循环码都存在其另

57、一种缩短形式(ns, ks)。实际应用中，可能。实际应用中，可能需要的码长不是需要的码长不是2m1或它的因或它的因子，我们可以从子，我们可以从(2m1, k)码中挑码中挑出前出前s位为位为0的码组构成新的码，的码组构成新的码，这种码的监督位数不变，因此纠这种码的监督位数不变，因此纠错能力保持不变，但是没有了循错能力保持不变，但是没有了循环性。环性。(4) RS码。码。RS码是码是Reed-m(nk)比特；最小码距比特；最小码距d=2t+1或或m(2t+1)比特。比特。第135页/共264页RS码非常适合于纠正突发错码非常适合于纠正突发错误。它可以纠正的错误图样为：误。它可以纠正的错误图样为：总

58、长度总长度qi=(t2i1)m+2i1的的i个突发错误。个突发错误。对于一个长度为对于一个长度为2m1符号符号的的RS码，每个符号都可以看成是码，每个符号都可以看成是。22420,1,m 第136页/共264页例如，构造一个能纠错误例如，构造一个能纠错误t=3个，码长为个，码长为n=15，m=4的的RS码。由码。由RS码的参数可知，该码的参数可知，该码的码距码的码距d=2t+1=7，监督位，监督位第137页/共264页9.59.5卷积码卷积码9.5.19.5.1卷积码编码原理卷积码编码原理1. 1. 卷积码的概念卷积码的概念第138页/共264页2 卷积码的结构及原理卷积码的结构及原理1) 卷

59、积码的结构卷积码的结构图图9.14示出了卷积码编码器示出了卷积码编码器的一般结构。它由输入移位寄存的一般结构。它由输入移位寄存器、模器、模2加法器、输出移位寄存加法器、输出移位寄存器三部分构成。输入移位寄存器器三部分构成。输入移位寄存器共有共有N段，每段有段，每段有k级，共级，共Nk位位寄存器，信息序列由此不断输入。寄存器，信息序列由此不断输入。第139页/共264页输入移位寄存器每移入输入移位寄存器每移入k位，位，则输出则输出n个比特的编码。所以，个比特的编码。所以，卷积码编码效率为卷积码编码效率为n, , kn第140页/共264页第141页/共264页图图9.15所示是一个最简单的所示是

60、一个最简单的(2，1，2)卷积码编码器，它由两卷积码编码器，它由两个移位寄存器个移位寄存器D1、D2和模和模2相加相加电路组成。编码器的输入信息码电路组成。编码器的输入信息码位一方面可以直接输出，另一方位一方面可以直接输出，另一方第142页/共264页第143页/共264页第144页/共264页编码器的工作过程是：移位编码器的工作过程是：移位寄存器按信息位的节拍工作，输寄存器按信息位的节拍工作，输入一位信息，电子开关倒换一次，入一位信息，电子开关倒换一次，即前半拍即前半拍(半个输入码元宽半个输入码元宽)接通接通m端，后半拍接通端，后半拍接通c端。因此，若端。因此，若 1121232310iii