1、11.1 11.1 概述概述11.2 11.2 纠错编码的基本原理纠错编码的基本原理11.3 11.3 纠错编码的性能纠错编码的性能11.4 11.4 常用的简单编码常用的简单编码11.5 11.5 线性分组码线性分组码11.11 11.11 小结小结第第11章章 差错控制编码差错控制编码一、信道分类一、信道分类1 1、随机信道：错码是随机的，、随机信道：错码是随机的，相互之间统计独立的，如正态分相互之间统计独立的，如正态分布白噪声引起的；布白噪声引起的；2 2、突发信道：错码是成串集中、突发信道：错码是成串集中出现的。如脉冲干扰和信道衰出现的。如脉冲干扰和信道衰落现象引起的；落现象引起的；3
2、 3、混合信道：、混合信道：11.1 概概 述述1 1、检错重发法：需要双向信道。、检错重发法：需要双向信道。2 2、前向纠错法：不需要反向信道，、前向纠错法：不需要反向信道，但纠错设备要复杂一些。但纠错设备要复杂一些。3 3、反馈校验法：需双向信道，传输、反馈校验法：需双向信道，传输效率低。效率低。4 4、检错删除法、检错删除法11.1 概概 述述二、差错控制方法二、差错控制方法三、差错控制编码三、差错控制编码在信息码元中加入监督码元就称差在信息码元中加入监督码元就称差错控制编码，也称纠错编码。错控制编码，也称纠错编码。监督码元：监督码元：在发送端需要在信息码在发送端需要在信息码元序列中增加
3、一些差错控制码元，元序列中增加一些差错控制码元，它们称为监督码元。它们称为监督码元。不同的编码方法，有不同的不同的编码方法，有不同的检错检错或或纠错纠错能力。能力。11.1 概概 述述多余度：多余度：就是指增加的监督码元多就是指增加的监督码元多少。少。编码效率编码效率(简称码率简称码率)：设信息码元设信息码元数量为数量为k，则比值，则比值k/n 就是码率。就是码率。冗余度：冗余度：监督码元数监督码元数(n-k)和信息码和信息码元数元数 k 之比。之比。理论上，差错控制以降低信息传输理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。速率为代价换取提高传输可靠性。11.1 概概 述述1
4、1、简述、简述:3 3种种ARQARQ系统系统(1)(1)停止等待停止等待ARQARQ系统系统 四、自动要求重发系统四、自动要求重发系统接收码组接收码组ACKACKACKACKNAKNAKACKACKACKACKNAKNAKACKACKt t1 12 23 33 34 45 55 5发送码组发送码组1 12 23 33 34 45 55 56 6t t有错码组有错码组有错码组有错码组11.1 概概 述述(2)拉后拉后ARQ系统系统接收数据有错码组有错码组有错码组有错码组910 1110 1112214365798576ACK1NAK5NAK9ACK5发送数据576952143679810 11
5、1011 12重发码组重发码组11.1 概概 述述2、ARQ的主要优点：的主要优点：（1）监督码元较少即能使误码率）监督码元较少即能使误码率降到很低，即码率较高；降到很低，即码率较高；（2）检错的计算复杂度较低；）检错的计算复杂度较低；(3)(3)选择重发选择重发ARQARQ系统系统接收数据有错码组有错码组921436575981011131412发送数据995852143671011131412重发码组重发码组NAK9ACK1NAK5ACK5ACK911.1 概概 述述（3）检错用的编码方法和加性干扰）检错用的编码方法和加性干扰的统计特性基本无关，能适应不同的统计特性基本无关，能适应不同特性
6、的信道。特性的信道。3、ARQ的主要缺点：的主要缺点：（1）需要双向信道来重发，不能用）需要双向信道来重发，不能用于单向信道，也不能用于一点到多于单向信道，也不能用于一点到多点的通信系统。点的通信系统。（2）因为重发而使）因为重发而使ARQ系统的传系统的传输效率降低。输效率降低。11.1 概概 述述11.1 概概 述述（3）在信道干扰严重时，可能发生）在信道干扰严重时，可能发生因不断反复重发而造成事实上的通因不断反复重发而造成事实上的通信中断。信中断。（4）在要求实时通信的场合，例如）在要求实时通信的场合，例如电话通信，往往不允许使用电话通信，往往不允许使用ARQ法法4、ARQ系统的原理方框图
7、系统的原理方框图11.1 概概 述述（1）发送端，输入的信息码元在编）发送端，输入的信息码元在编码器中被分组编码（加入监督码元）码器中被分组编码（加入监督码元）后，除了立即发送外，还暂存于缓后，除了立即发送外，还暂存于缓冲存储器中。冲存储器中。11.1 概概 述述（2）接收端仅当解码器认为接收）接收端仅当解码器认为接收信息码元正确时，才将信息码元送信息码元正确时，才将信息码元送给收信者。给收信者。（3）当解码器未发现错码时，经）当解码器未发现错码时，经过反向信道发出不需重发指令。发过反向信道发出不需重发指令。发送端收到此指令后，即继续发送后送端收到此指令后，即继续发送后一码组，发送端的缓冲存储
8、器中的一码组，发送端的缓冲存储器中的内容也随之更新内容也随之更新一、纠（检）错举例一、纠（检）错举例1 1、三位二进制码有、三位二进制码有8 8种不同的组合，种不同的组合，可以表示可以表示8 8种不同的天气，无法发种不同的天气，无法发现错误。此时编码效率为现错误。此时编码效率为100100。2 2、若只用其中四种来传送信息（、若只用其中四种来传送信息（4 4种天气），接收端就有可能发现一种天气），接收端就有可能发现一个错码，但如果错两位，个错码，但如果错两位，11.2纠错编码的基本原理纠错编码的基本原理就是许用码组，不能发现错误。且就是许用码组，不能发现错误。且这种码只能发现错误（检错），不这
9、种码只能发现错误（检错），不能纠错。此时编码效率能纠错。此时编码效率2/32/3。3 3、若只用、若只用2 2种来传送信息，种来传送信息，000000和和111111，就可以检，就可以检2 2个错，纠一个错。个错，纠一个错。此时编码效率为此时编码效率为1/31/3。11.2纠错编码的基本原理纠错编码的基本原理二、分组码的一般概念二、分组码的一般概念1 1、分组码的表示、分组码的表示信息信息位位监督监督位位晴晴云云阴阴雨雨00000101101011110 01 11 10 0这种信息码分组，为这种信息码分组，为每组信息码附加若干每组信息码附加若干监督码的编码集合，监督码的编码集合，称为分组码。
10、且监督称为分组码。且监督位仅监督本码组中的位仅监督本码组中的码元。码元。11.2纠错编码的基本原理纠错编码的基本原理2 2、分组码的一般结构、分组码的一般结构分组码一般用（分组码一般用（n,kn,k）表示，）表示，k k是二是二进制信息码的数目，进制信息码的数目，n n是编码组的总是编码组的总位数，称为码长，位数，称为码长，n-k=rn-k=r是监督码位是监督码位数。数。11.2纠错编码的基本原理纠错编码的基本原理最小码距：最小码距：某种编码中各个码组间某种编码中各个码组间距离最小值称为最小码距距离最小值称为最小码距d d0 0。与纠、。与纠、检错能力有关。检错能力有关。码组重量：码组重量：把
11、把“1”1”的数目称为码的数目称为码组重量；组重量；码组距离：码组距离：把两个码组中对应位上把两个码组中对应位上数字不同的位数称为码距，又称数字不同的位数称为码距，又称“Hamming”Hamming”距离。距离。3 3、一般概念、一般概念11.2纠错编码的基本原理纠错编码的基本原理每个码组的每个码组的3个码元值个码元值(a1,a2,a3)就是就是此立方体各顶点的坐标。而上述码此立方体各顶点的坐标。而上述码距概念在此图中就对应于各顶点之距概念在此图中就对应于各顶点之间沿立方体各边行走的几何距离。间沿立方体各边行走的几何距离。11.2纠错编码的基本原理纠错编码的基本原理(0,0,0)(0,0,1
12、)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a14 4、最小码距、最小码距d d0 0与纠、检错能力的关与纠、检错能力的关系系（1 1）为检测）为检测e e个错码，要求最小码个错码，要求最小码距距d d0 0e+1e+10123BA汉明距离汉明距离ed011.2纠错编码的基本原理纠错编码的基本原理(2)为了纠正为了纠正t个错码，要求最小码距个错码，要求最小码距d0 2t+1BtA汉明距离汉明距离012345td0(3)为纠正为纠正t个错码，同时检测个错码，同时检测e个错个错码，码，d0 e+t+1（et)11.2纠错编码的基本原理纠错编码的基本
13、原理BtA汉明距离汉明距离012345td011.2纠错编码的基本原理纠错编码的基本原理图中码组图中码组A和和B之间距离为之间距离为5。当错。当错码位数超过纠错能力时，该码组立码位数超过纠错能力时，该码组立即进入另一码组的圆内而被错误地即进入另一码组的圆内而被错误地“纠正纠正”了。了。所以，发生所以，发生e个错误之后所处的位个错误之后所处的位置，与其他码组（譬如码组置，与其他码组（譬如码组B）的）的纠错圆圈至少距离等于纠错圆圈至少距离等于1，要求最，要求最小码距小码距ABe1tt汉明距离汉明距离)(10teted这种纠错和检错结合的工作方式简这种纠错和检错结合的工作方式简称称纠检结合纠检结合。
14、11.2纠错编码的基本原理纠错编码的基本原理。，且为”的错误概率相等，都”和“设发送“110pp11.3 纠错编码的性能纠错编码的性能一、系统带宽和信噪比的矛盾：一、系统带宽和信噪比的矛盾：为了减少接收错误码元数量，需要为了减少接收错误码元数量，需要在发送信息码元序列中加入监督码在发送信息码元序列中加入监督码元。这样作的结果增大了系统带宽。元。这样作的结果增大了系统带宽。系统带宽的增大将引起系统中噪声系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。一般说功率增大，使信噪比下降。一般说来，采用纠错编码后，误码率总是来，采用纠错编码后，误码率总是能够得到很大改善的。能够得到很大改善的。10-
15、610-510-410-310-210-1编码后PeCDEAB信噪比(dB)11.3 纠错编码的性能纠错编码的性能二、编码性能举二、编码性能举例图中例图中A点，在点，在采用纠错编码后，采用纠错编码后，误码率降至约误码率降至约410-5，图中，图中B点。这样，不增点。这样，不增大发送功率就能大发送功率就能降低误码率约一降低误码率约一个半数量级个半数量级11.3 纠错编码的性能纠错编码的性能若保持误码率在若保持误码率在10-5，图中，图中C点，约点，约需要信噪比需要信噪比Eb/n0=10.5 dB。在采用。在采用这种编码时，约需要信噪比这种编码时，约需要信噪比7.5 dB，图中图中D点。可以节省功
16、率点。可以节省功率2dB。通常。通常称这称这2dB为编码增益。为编码增益。传输速率和传输速率和Eb/n0的关系：对于给的关系：对于给定的传输系统定的传输系统BsssbRnPTnPnTPnE0000)/1(11.3 纠错编码的性能纠错编码的性能式中，式中，RB为码元速率。若希望提高为码元速率。若希望提高传输速率，由上式看出势必使信噪传输速率，由上式看出势必使信噪比下降，误码率增大。假设系统误比下降，误码率增大。假设系统误码率希望下降，付出的代价仍是带码率希望下降，付出的代价仍是带宽增大宽增大三、差错控制编码的效用三、差错控制编码的效用可见用纠错编码，可使误码率下降可见用纠错编码，可使误码率下降几
17、个数量级。几个数量级。在突发信道中，纠错编码的效用不在突发信道中，纠错编码的效用不如随机信道明显。如随机信道明显。rrnrrnnprnrnppCrpr!1个错码的概率为个错码的概率为发生发生码长为n的码组中恰好码长为n的码组中恰好11.3 纠错编码的性能纠错编码的性能11.4.1 奇偶监督码奇偶监督码奇数监督码和偶数监督码。无论信奇数监督码和偶数监督码。无论信息位有多少，监督位只有一位。息位有多少，监督位只有一位。误误；为为监监督督位位，检检奇奇数数个个错错为为奇奇数数：奇奇数数：使使“1 1”的的数数目目误误；为为监监督督位位，检检奇奇数数个个错错为为偶偶数数：偶偶数数：使使“1 1”的的数
18、数目目0021002110aaaaaaaannnn；在接收端同样进行模二加检测。在接收端同样进行模二加检测。11.4 简单的实用编码简单的实用编码11.4.2 二维奇偶监督码二维奇偶监督码又称方阵码，是把奇偶监督码的若干又称方阵码，是把奇偶监督码的若干码组排列成矩阵，每一码组写成一行，码组排列成矩阵，每一码组写成一行，再对每列进行二维监督。再对每列进行二维监督。012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn11.4 简单的实用编码简单的实用编码这种码可能检测出偶数个错误，按这种码可能检测出偶数个错误，按列的方向可能检测出来。列的方向可能
19、检测出来。有一些偶数错码不可能检测出来，有一些偶数错码不可能检测出来，如构成矩形的如构成矩形的4 4个错码就不行。个错码就不行。适于检测突发错误，常成串出现，适于检测突发错误，常成串出现，在某一行出现较多。在某一行出现较多。还可以纠错，如只有一行中有奇数还可以纠错，如只有一行中有奇数个错时，能定位错码位置纠正。个错时，能定位错码位置纠正。11.4 简单的实用编码简单的实用编码11.4.3 恒比码恒比码每个码组中均含有相同数目的每个码组中均含有相同数目的“1”1”（和（和“0”0”）。那么）。那么“1”1”和和“0”0”的的数目之比恒定。检测时，只要看接数目之比恒定。检测时，只要看接收到的码中收
20、到的码中“1”1”的数目是否对。的数目是否对。由于长度为由于长度为5的码组共有的码组共有25=32种，种，有有22组禁用码，多余度较高。下图组禁用码，多余度较高。下图所示所示11.4 简单的实用编码简单的实用编码11.4 简单的实用编码简单的实用编码11.4.4 正反码正反码电报通信中，电报通信中，n=10n=10，信息位，信息位k=5k=5，监督位监督位r=5r=5。（1 1）信息位中有奇数个）信息位中有奇数个“1”1”时，时，监督位是信息位的简单重复；监督位是信息位的简单重复；（2 2）信息位中有偶数个）信息位中有偶数个“1”1”时，时，监督位是信息位的反码；监督位是信息位的反码；11.4
21、 简单的实用编码简单的实用编码（3 3）解码方法：先将信息位和监）解码方法：先将信息位和监督位按模督位按模2 2加，得到一个加，得到一个5 5位的合成位的合成码组，即产生一个校验码组。若接码组，即产生一个校验码组。若接收到的信息位有奇数个收到的信息位有奇数个“1”1”，则，则合成码组就是校验码组；若有偶数合成码组就是校验码组；若有偶数个个“1”1”，则取合成码的反码为校，则取合成码的反码为校验码组。验码组。11.4 简单的实用编码简单的实用编码11.4 简单的实用编码简单的实用编码校验码组的组成校验码组的组成错码情况错码情况1全为全为“0”无错码无错码2 有有4个个“1”和和1个个“0”信息码
22、中有信息码中有1位错码，其位置对应校验码组位错码，其位置对应校验码组中中“0”的位置的位置3 有有4个个“0”和和1个个“1”监督码中有监督码中有1位错码，其位置对应校验码组位错码，其位置对应校验码组中中“1”的位置的位置4其他组成其他组成错码多于错码多于1个个例如，若发送码组为例如，若发送码组为1100111001，接收码组中无错码，则合成码组应接收码组中无错码，则合成码组应为为00000。无错。无错。一、代数码一、代数码建立在代数学基础上的编码称为代建立在代数学基础上的编码称为代数码，常见的是线性码。其中的信数码，常见的是线性码。其中的信息位和监督位是由一些线性代数方息位和监督位是由一些线
23、性代数方程联系着的。程联系着的。二、汉明码二、汉明码是一种能够纠正一位错码且编码效是一种能够纠正一位错码且编码效率较高的线性分组码。率较高的线性分组码。11.5 线性分组码线性分组码1、构造原理、构造原理在偶数监督码中，使用了一位监督在偶数监督码中，使用了一位监督位位a0，它和信息位，它和信息位an-1，a1构成构成代数式：代数式：在接收端解码时，实际上就是计算在接收端解码时，实际上就是计算11.5 线性分组码线性分组码0021aaann021aaaSnn11.5 线性分组码线性分组码若若S=0，就认为无错码；若，就认为无错码；若S=1，就认为有错码。现将上式称为就认为有错码。现将上式称为监督
24、监督关系式关系式，S称为称为校正子校正子。由于校正。由于校正子子S只有两种取值，故它只能代表只有两种取值，故它只能代表有错和无错这两种信息，而不能指有错和无错这两种信息，而不能指出错码的位置。出错码的位置。若监督位增加一位，即变成两位，若监督位增加一位，即变成两位，则能增加一个类似的监督关系式。则能增加一个类似的监督关系式。11.5 线性分组码线性分组码由于两个校正子的可能值有由于两个校正子的可能值有4中组合：中组合：00，01，10，11，故能表示，故能表示4种不同种不同的信息。若用其中的信息。若用其中1种组合表示无错，种组合表示无错，则其余则其余3种组合就有可能用来指示一种组合就有可能用来
25、指示一个错码的个错码的3种不同位置。同理，种不同位置。同理，r个个监督关系式能指示监督关系式能指示1位错码的位错码的(2r 1)个可能位置。个可能位置。11.5 线性分组码线性分组码1212rknrr或一般来说，若码长为一般来说，若码长为n，信息位数，信息位数为为k，则监督位数，则监督位数rnk。如果希。如果希望用望用r个监督位构造出个监督位构造出r个监督关系个监督关系式来指示式来指示1位错码的位错码的n种可能位置，种可能位置，则要求则要求下面通过一个例子来说明如何具体下面通过一个例子来说明如何具体构造这些监督关系式。构造这些监督关系式。2 2、（、（7 7，4 4）汉明码）汉明码设分组码设分
26、组码(n，k)中中k=4，为了纠正一，为了纠正一位错码，要求位错码，要求r=3，取，取r=3，则，则n=k+r=7。用。用a6 a5 a0表示这表示这7个码个码元元S S1 1S S2 2S S3 3错误位置错误位置S S1 1S S2 2S S3 3错误位置错误位置001001a a0 0101101a a4 4010010a a1 1110110a a5 5100100a a2 2111111a a6 6011011a a3 3000000无错无错11.5 线性分组码线性分组码034631356224561aaaaSaaaaSaaaaS11.5 线性分组码线性分组码由表中规定可见，仅当一位
27、错码的由表中规定可见，仅当一位错码的位置在位置在a2、a4、a5或或a6时，校正子时，校正子S1为为1；否则；否则S1为零。这就意味着为零。这就意味着a2、a4、a5和和a6四个码元构成偶数监督关四个码元构成偶数监督关系：系：000034613562456aaaaaaaaaaaa11.5 线性分组码线性分组码在发送端编码时，信息位在发送端编码时，信息位a6、a5、a4和和a3的值决定于输入信号，因此它的值决定于输入信号，因此它们是随机的。监督位们是随机的。监督位a2、a1和和a0应根应根据信息位的取值按监督关系来确定，据信息位的取值按监督关系来确定，即监督位应使上即监督位应使上3式中式中S1、
28、S2和和S3的的值为值为0：346035614562aaaaaaaaaaaa如下表所示如下表所示11.5 线性分组码线性分组码信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a0信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111111.5 线性分组码线性分组码11.5 线性分组码线性分组码例如，若接收码组为例如，若接收码组为0000011，按上，按上述公
29、式计算可得：述公式计算可得：S1=0，S2=1，S3=1。由于。由于S1 S2 S3 等于等于011，故查，故查表可知在表可知在a3位有位有1错码。错码。表中所列的表中所列的(7,4)汉明码的最小码距汉明码的最小码距d0=3。因此，这种码能够纠正。因此，这种码能够纠正1个个错码或检测错码或检测2个错码。汉明码是一种个错码。汉明码是一种高效码高效码3 3、线性分组码的一般原理、线性分组码的一般原理上述（上述（7 7，4 4）汉明码的）汉明码的d d0 0=3=3，所以，所以能纠一个错码或检能纠一个错码或检2 2个错码，将信个错码，将信息位和监督位的关系写成一般方程息位和监督位的关系写成一般方程将
30、上式写成矩阵形式：将上式写成矩阵形式：010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa11.5 线性分组码线性分组码OHAOAHTTT或可简写为）（模20001011001110101011101000123456aaaaaaa上式还可以简记为上式还可以简记为H AT=0T 或或A HT=011.5 线性分组码线性分组码101100111010101110100H11.5 线性分组码线性分组码式中式中 A=a6 a5 a4 a3 a2 a1 a0 0=000右上标右上标“T”表示将矩阵转置。只要表示将矩阵转置。
31、只要监督矩阵监督矩阵H给定，编码时监督位和给定，编码时监督位和信息位的关系就完全确定了。信息位的关系就完全确定了。11.5 线性分组码线性分组码H矩阵的性质：矩阵的性质：1)H的行数就是监督关系式的数目，的行数就是监督关系式的数目，它等于监督位的数目它等于监督位的数目r。H的每行中的每行中“1”的位置表示相应码元之间存在的位置表示相应码元之间存在的监督关系。例如，的监督关系。例如，H的第一行的第一行1110100表示监督位表示监督位a2是由是由a6 a5 a4之之和决定的。和决定的。H矩阵可以分成两部分，矩阵可以分成两部分，例如例如11.5 线性分组码线性分组码rPIH001101101011
32、011001110式中，式中，P为为rk阶矩阵，阶矩阵，Ir为为rr阶阶单位方阵。我们将具有单位方阵。我们将具有P Ir形式的形式的H矩阵称为典型阵。矩阵称为典型阵。2)由代数理论可知，由代数理论可知，H矩阵的各行矩阵的各行应该是线性无关的，否则将得应该是线性无关的，否则将得11.5 线性分组码线性分组码不到不到 r个线性无关的监督关系式，个线性无关的监督关系式，从而也得不到从而也得不到 r个独立的监督位。个独立的监督位。若一矩阵能写成典型阵形式若一矩阵能写成典型阵形式P Ir，则其各行一定是线性无关的。因为则其各行一定是线性无关的。因为容易验证容易验证Ir的各行是线性无关的，的各行是线性无关
33、的，故故P Ir的各行也是线性无关的。的各行也是线性无关的。3456012101111011110aaaaaaa11.5 线性分组码线性分组码346035614562aaaaaaaaaaaaG矩阵：矩阵：上面汉明码例中的监督位公式为上面汉明码例中的监督位公式为也可以改写成矩阵形式：也可以改写成矩阵形式：Qaaaaaaaaaaa3456345601201110111011111.5 线性分组码线性分组码或写成或写成式中，式中，Q为一个为一个kr阶矩阵，它为阶矩阵，它为P的转置，即的转置，即 Q=PT上式表示，在信息位给定后，用信上式表示，在信息位给定后，用信息位的行矩阵乘矩阵息位的行矩阵乘矩阵Q
34、就产生出监就产生出监督位。督位。11.5 线性分组码线性分组码我们将我们将Q的左边加上的左边加上1个个k k阶单位阶单位方阵，就构成方阵，就构成1个矩阵个矩阵G0110001101001011001001111000QGkI I G34560123456aaaaaaaaaaaG称为称为生成矩阵生成矩阵，因为由它可以产，因为由它可以产生整个码组，即有生整个码组，即有11.5 线性分组码线性分组码因此，如果找到了码的生成矩阵因此，如果找到了码的生成矩阵G，则编码的方法就完全确定了。具有则编码的方法就完全确定了。具有IkQ形式的生成矩阵称为形式的生成矩阵称为典型生成典型生成矩阵矩阵。由典型生成矩阵得
35、出的码组。由典型生成矩阵得出的码组A中，信息位的位置不变，监督位中，信息位的位置不变，监督位附加于其后。这种形式的码称为附加于其后。这种形式的码称为系系统码统码。生成矩阵生成矩阵G的性质：的性质：1)G矩阵的各行是线性无关的。任一矩阵的各行是线性无关的。任一码组码组A都是都是G的各行的线性组合。的各行的线性组合。若若G的各行有线性相关的，则不可的各行有线性相关的，则不可能由能由G生成生成2k种不同的码组。种不同的码组。2)实际上，实际上，G的各行本身就是一个的各行本身就是一个码组。因此如果已有码组。因此如果已有k个线性无关个线性无关的码组，则可以作为生成矩阵的码组，则可以作为生成矩阵G，并由它
36、生成其余码组。并由它生成其余码组。11.5 线性分组码线性分组码4 4、接收码组的检验：、接收码组的检验：A A为一为一n n列的行矩阵，是发送码组；列的行矩阵，是发送码组；B B为一为一n n列的行矩阵，是收到码组；列的行矩阵，是收到码组；021bbbBnn发送和接收码组之差为：发送和接收码组之差为：B BA AE E （模（模2 2）021eeeEnn11.5 线性分组码线性分组码有错，当，无错，当，iiiiiababe10EAB11.5 线性分组码线性分组码因此，若因此，若ei=0，表示该接收码元无，表示该接收码元无错；若错；若ei=1，则表示该接收码元有，则表示该接收码元有错。错。B
37、A=E 可以改写成可以改写成 B=A+E错码矩阵有时也称为错误图样。错码矩阵有时也称为错误图样。校正子校正子S:当接收码组有错时，当接收码组有错时，E0，将，将B当作当作A代入公式代入公式(A HT=0)后，该式不后，该式不一定成立。假设这时该式的右端为一定成立。假设这时该式的右端为S，即，即 B HT=SS=(A+E)HT=AH T+EHT由于由于AHT=0，所以，所以S=EHT式中式中S称为校正子。它能用来指示称为校正子。它能用来指示错码的位置。错码的位置。EAB11.5 线性分组码线性分组码5 5、线性码的封闭性、线性码的封闭性即一种信息码中的任意两个码组之即一种信息码中的任意两个码组之
38、和仍为这种码中的一个码组。和仍为这种码中的一个码组。所以两个码组之间的距离必定是另所以两个码组之间的距离必定是另一个码组的重量。因此，码的最小一个码组的重量。因此，码的最小距离就是码的最小重量（除全距离就是码的最小重量（除全“0”码组外）。码组外）。也是一组码。，证明：212121000AAHAAHAHATTT11.5 线性分组码线性分组码11.6 循环码循环码11.6.1 循环码原理循环码原理循环性：循环性是指任一码组循环循环性：循环性是指任一码组循环一位（即将最右端的一个码元移至一位（即将最右端的一个码元移至左端，或反之）以后，仍为该码中左端，或反之）以后，仍为该码中的一个码组。在下表中给
39、出一种的一个码组。在下表中给出一种(7,3)循环码的全部码组。循环码的全部码组。例如，表中的第例如，表中的第2码组向右移一码组向右移一位即得到第位即得到第5码组；第码组；第6码组向右移码组向右移一位即得到第一位即得到第7码组。码组。11.6 循环码循环码码组编码组编号号信息位信息位监督位监督位码组编码组编号号信息位信息位监督位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001011.6 循环码循环码一般说来，若一般说来，若(an-1 an-2 a0)是循环是
40、循环码的一个码组，则循环移位后的码码的一个码组，则循环移位后的码组组(an-2 an-3 a0 an-1)(an-3 an-4 an-1 an-2)(a0 an-1 a2 a1)也是该编码中的码组。也是该编码中的码组。11.6 循环码循环码码多项式码多项式码组的多项式表示法码组的多项式表示法把码组中各码元当作是一个多把码组中各码元当作是一个多项式的系数，即把一个长度为项式的系数，即把一个长度为n的的码组表示成码组表示成例如，上表中的任意一个码组例如，上表中的任意一个码组可以表示为可以表示为012211)(axaxaxaxTnnnn012233445566)(axaxaxaxaxaxaxT11.
41、6 循环码循环码其中第其中第7个码组可以表示为个码组可以表示为这种多项式中，这种多项式中，x仅是码元位置的仅是码元位置的标记，例如上式表示第标记，例如上式表示第7码组中码组中a6、a5、a2和和a0为为“1”，其他均为，其他均为0。因。因此我们并不关心此我们并不关心x的取值。的取值。11010011)(25623456xxxxxxxxxxT11.6 循环码循环码码多项式的按模运算码多项式的按模运算若一个整数若一个整数m可以表示为可以表示为式中，式中，Q 整数，整数，则在模则在模 n 运算下，有运算下，有m p (模模n)即，在模即，在模 n 运算下，一个整数运算下，一个整数m等等于它被于它被
42、n 除得的余数。除得的余数。npnpQnm,11.6 循环码循环码在码多项式运算中也有类似的按模在码多项式运算中也有类似的按模运算。运算。若一任意多项式若一任意多项式F(x)被一被一 n 次次多项式多项式N(x)除，得到商式除，得到商式Q(x)和一和一个次数小于个次数小于n的余式的余式R(x)，即，即则写为则写为)()()()(xRxQxNxF）（模)()()(xNxRxF11.6 循环码循环码这时，码多项式系数仍按模这时，码多项式系数仍按模2 运算，运算，即系数只取即系数只取 0 和和1。例如，。例如，x3被被(x3+1)除，得到余项除，得到余项1。所以有。所以有同理同理）（模)1(133x
43、x）（模)1(113224xxxxx11.6 循环码循环码循环码的码多项式循环码的码多项式在循环码中，若在循环码中，若T(x)是一个长为是一个长为n的的许用码组，则许用码组，则xiT(x)在按模在按模xn+1运算下，也是该编码中的一个许用运算下，也是该编码中的一个许用码组，即若码组，即若则则T(x)也是该编码中的一个许用码也是该编码中的一个许用码组。组。）（模)1()()(nixxTxTx11.6 循环码循环码循环码的生成矩阵循环码的生成矩阵G由上节中公式由上节中公式可知，有了生成矩阵可知，有了生成矩阵G，就可以由，就可以由k个信息位得出整个码组，而且生成个信息位得出整个码组，而且生成矩阵矩阵
44、G的每一行都是一个码组。由的每一行都是一个码组。由于于G是是k行行n列的矩阵，因此若能找列的矩阵，因此若能找到到k个已知码组，就能构成矩阵个已知码组，就能构成矩阵G。GA3456aaaa11.6 循环码循环码如前所述，这如前所述，这k个已知码组必须是个已知码组必须是线性不相关的。线性不相关的。在循环码中，一个在循环码中，一个(n,k)码有码有2k个不个不同的码组。若用同的码组。若用g(x)表示其中前表示其中前(k-1)位皆为位皆为“0”的码组，则的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都都是码组，而且这是码组，而且这k个码组是线性无个码组是线性无关的。因此它们可以用
45、来构成此循关的。因此它们可以用来构成此循环码的生成矩阵环码的生成矩阵G。11.6 循环码循环码在循环码中除全在循环码中除全“0”码组外，连码组外，连“0”的长度最多只能有的长度最多只能有(k-1)位。位。因此，因此，g(x)必须是一个常数项不为必须是一个常数项不为“0”的的(n-k)次多项式，而且这个次多项式，而且这个g(x)还是这种还是这种(n,k)码中次数为码中次数为(n k)的唯一多项式。我们称这唯一的的唯一多项式。我们称这唯一的(n k)次多项式次多项式g(x)为码的生成多为码的生成多项式。一旦确定了项式。一旦确定了g(x)，则整个，则整个(n,k)循环码就被确定了。循环码就被确定了。
46、11.6 循环码循环码因此，循环码的生成矩阵因此，循环码的生成矩阵G可以写可以写成成 例：在上表所给出的例：在上表所给出的(7,3)循环码中，循环码中，n=7,k=3,n k=4。)()()()()(21xgxxgxgxxgxxkkG由此表可见，唯一的一个由此表可见，唯一的一个(n k)=4次码多项式代表的码组是第二码次码多项式代表的码组是第二码组组0010111，与它相对应的码多项，与它相对应的码多项式（即生成多项式）式（即生成多项式）g(x)=x4+x2+x+1。将此。将此g(x)代入上式，得到代入上式，得到或或11.6 循环码循环码)()()()(2xgxxgxgxxG001011101
47、011101011100)(xG11.6 循环码循环码如何寻找任一如何寻找任一(n,k)循环码的生成循环码的生成多项式多项式 由上式可知，任一循环码多项由上式可知，任一循环码多项式式T(x)都是都是g(x)的倍式，故它可以的倍式，故它可以写成写成 T(x)=h(x)g(x)而生成多项式而生成多项式g(x)本身也是一本身也是一个码组，即有个码组，即有 T(x)=g(x)11.6 循环码循环码由于码组由于码组T(x)是一个是一个(n k)次多项次多项式，故式，故xk T(x)是一个是一个n次多项式。次多项式。由下式由下式可知，可知，xk T(x)在模在模(xn+1)运算运算下也是一个码组，故可以写
48、成下也是一个码组，故可以写成）（模)1()()(nixxTxTx1)()(1)(nnkxxTxQxxTx11.6 循环码循环码上式左端分子和分母都是上式左端分子和分母都是n次多项次多项式，故商式式，故商式Q(x)=1。因此，上式。因此，上式可以化成可以化成将将T(x)和和T(x)表示式代入上式，表示式代入上式，经过化简后得到经过化简后得到)()1()(xTxxTxnk)()(1xhxxgxkn11.6 循环码循环码上式表明，生成多项式上式表明，生成多项式g(x)应该是应该是(xn+1)的一个因子。例如，的一个因子。例如，(x7+1)可以分解为可以分解为为了求为了求(7,3)循环码的生成多项循环
49、码的生成多项式式g(x)，需要从上式中找到一个，需要从上式中找到一个(n k)=4次的因子。不难看出，这样的次的因子。不难看出，这样的因子有两个，即因子有两个，即)1)(1)(1(13237xxxxxx11.6 循环码循环码1)1)(1(2423xxxxxx1)1)(1(2343xxxxxx以上两式都可作为生成多项式。不以上两式都可作为生成多项式。不过，选用的生成多项式不同，产生过，选用的生成多项式不同，产生出的循环码码组也不同。出的循环码码组也不同。11.6 循环码循环码11.6.2 循环码的编解码方法循环码的编解码方法循环码的编码方法循环码的编码方法1、编码原则、编码原则在编码时，首先要根
50、据给定的在编码时，首先要根据给定的(n,k)值选定生成多项式值选定生成多项式g(x)，即从，即从(xn+1)的因子中选一个的因子中选一个(n-k)次多次多项式作为项式作为g(x)。11.6 循环码循环码2、编码步骤：、编码步骤：用用xn-k乘乘m(x)。例如，信息码为例如，信息码为110，它相当于，它相当于m(x)=x2+x。当。当n k=7 3=4时，时，xn-k m(x)=x4(x2+x)=x6+x5，它相当于，它相当于1100000。用用g(x)除除xn-k m(x)，得到商，得到商Q(x)和和余式余式r(x)，即，即)()()()()(xgxrxQxgxmxkn11.6 循环码循环码循
