通信原理课件：纠错编码精.ppt

《通信原理课件：纠错编码精.ppt》由会员分享，可在线阅读，更多相关《通信原理课件：纠错编码精.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、通信原理课件：纠错编码第1页，本讲稿共66页2 主要内容主要内容主要内容主要内容8.1 8.1 引言引言8.2 8.2 纠错编码的基本原理纠错编码的基本原理8.3 8.3 线性分组码线性分组码8.48.4 循环码循环码8.5 8.5 小结小结第2页，本讲稿共66页38.1 引言引言 在数字信号传输中，由于在数字信号传输中，由于噪声的存在及信道特性不理噪声的存在及信道特性不理想想，都可使信号波形失真，从而在接收端就不可避免的，都可使信号波形失真，从而在接收端就不可避免的产生错误判决。产生错误判决。引起误码原因引起误码原因:(1)(1)信道特性不理想信道特性不理想(乘性干扰乘性干扰):引起码间串扰

2、，通常可采引起码间串扰，通常可采用均衡的办法纠正。用均衡的办法纠正。(2)(2)噪声影响噪声影响(加性干扰加性干扰):需借助各种差错控制编码技术来需借助各种差错控制编码技术来克服。克服。一、基本概念一、基本概念第3页，本讲稿共66页4差错控制编码差错控制编码又称为又称为信道编码信道编码(纠错编码纠错编码)，要求在，要求在满足有效性前提下，尽可能提高数字通信的可靠性满足有效性前提下，尽可能提高数字通信的可靠性n纠错编码纠错编码：在要传送的数字信息序列中按一定规则加上一：在要传送的数字信息序列中按一定规则加上一些冗余码元（监督位些冗余码元（监督位),),使序列按满足一定数学规律的码字传输使序列按满

3、足一定数学规律的码字传输(编码过程编码过程););n译码译码:在接收端在接收端,利用这种规律性来鉴别传输过程是否发生利用这种规律性来鉴别传输过程是否发生错误或纠正错误，恢复原始信息序列。错误或纠正错误，恢复原始信息序列。第4页，本讲稿共66页5二、纠错编码的分类二、纠错编码的分类 按功能分：检错码和纠错码按功能分：检错码和纠错码 按监督码元与信息码元之间是否存在线性关系分：线性码与非按监督码元与信息码元之间是否存在线性关系分：线性码与非线性码线性码 按信息码元与监督码元之间的约束关系不同分：分组码按信息码元与监督码元之间的约束关系不同分：分组码与非分组码如卷积码与非分组码如卷积码按信息码元在编

4、码后是否保持原来的信号形式分：系统码与非按信息码元在编码后是否保持原来的信号形式分：系统码与非系统码系统码按纠正差错的类型分：纠正随机错误的码与纠正突发按纠正差错的类型分：纠正随机错误的码与纠正突发错误的码错误的码 按码元的取值分：二进制码与多进制码按码元的取值分：二进制码与多进制码第5页，本讲稿共66页6三、误码的类型三、误码的类型n 随机误码随机误码n错码出现是随机的、错码之间错码出现是随机的、错码之间统计独立统计独立。n由随机噪声引起由随机噪声引起n存在随机误码的信道称为随机信道存在随机误码的信道称为随机信道n 突发误码突发误码错码错码成串集中出现成串集中出现，在很短的时间出现大量错码，

5、而过后在很短的时间出现大量错码，而过后又存在较大的无错码位，又存在较大的无错码位，且且差错之间是相关的差错之间是相关的例如：脉冲噪声，信道中衰落例如：脉冲噪声，信道中衰落存在这种差错的信道称为突发信道存在这种差错的信道称为突发信道第6页，本讲稿共66页7四、差错控制方法四、差错控制方法（1）前向纠错（前向纠错（FECFEC）第7页，本讲稿共66页8优点：无需反向信道、译码总延迟恒定，具有恒定的信息优点：无需反向信道、译码总延迟恒定，具有恒定的信息 传输速率传输速率缺点：当纠错能力强时，要增加冗余位；接收可靠性对信缺点：当纠错能力强时，要增加冗余位；接收可靠性对信道传输条件的恶化很敏感道传输条件

6、的恶化很敏感（2）自动要求重发（自动要求重发（ARQARQ）第8页，本讲稿共66页9优点：极低的不可检测概率；编译码简单；对任何信道都有效优点：极低的不可检测概率；编译码简单；对任何信道都有效缺点：需要反向信道；译码延迟不固定；需要缓冲器缺点：需要反向信道；译码延迟不固定；需要缓冲器（3）FEC/ARQFEC/ARQ混合系统混合系统分为三类：停止等待分为三类：停止等待ARQ、连续、连续ARQ和选择重发和选择重发ARQ综合利用综合利用FEC延迟小，纠错能力强和延迟小，纠错能力强和ARQ传输可靠性高传输可靠性高第9页，本讲稿共66页10发端发出同时具有检错和纠错能力的码，收端收到后，发端发出同时具

7、有检错和纠错能力的码，收端收到后，检查错误情况：如果错误在纠错能力之内，则自动纠正；检查错误情况：如果错误在纠错能力之内，则自动纠正；若超出纠错能力，但在检错能力之内，则经反向信道要若超出纠错能力，但在检错能力之内，则经反向信道要求重发。求重发。注意注意：不同的纠错编码方法，有不同的检错或纠错能力，：不同的纠错编码方法，有不同的检错或纠错能力，一般说来，增加监督码元越多，检错或纠错的能力就越强，一般说来，增加监督码元越多，检错或纠错的能力就越强，提高传输可靠性是以降低传输有效性为代价的。提高传输可靠性是以降低传输有效性为代价的。第10页，本讲稿共66页118.2纠错编码的基本原理纠错编码的基本

8、原理简单例子：简单例子：3位二进制码组（位二进制码组（c1 c2 c3）,其中其中ci=0或或1。此码组有。此码组有8种种不同的组合：不同的组合：000 001 010 011 100 101 110 111可分别代表不同的信息含义。若将可分别代表不同的信息含义。若将8种码组都作为有用种码组都作为有用码组来使用，比如代表码组来使用，比如代表8种天气情况：种天气情况：000（晴晴），），001（雷），（雷），010（雹），（雹），011（阴阴），），100（风），（风），101（云云），），110（雨雨），），111（雪）（雪）第11页，本讲稿共66页12任一码组在传输中若发生一个或多个错码，则

9、将变成任一码组在传输中若发生一个或多个错码，则将变成另一信息码组另一信息码组这种编码方法就不具有任何抗干扰能力：这种编码方法就不具有任何抗干扰能力：但如果在但如果在8种码组中，规定只准使用其中种码组中，规定只准使用其中4种来传输信息，种来传输信息，比如，许用码组为：比如，许用码组为：000（晴），（晴），011（阴），（阴），101（云），（云），110（雨）（雨）这种编码这种编码接收端有可能检测码组中出现的一位或接收端有可能检测码组中出现的一位或三位错误，但不能发现两位错码的情况三位错误，但不能发现两位错码的情况接收端收到禁用码组时，就认为发现了错误接收端收到禁用码组时，就认为发现了错误第1

10、2页，本讲稿共66页13这种方法这种方法只能检测错误，但不能纠正错误只能检测错误，但不能纠正错误比如：当接收端收到禁用码组比如：当接收端收到禁用码组100时，无法判决哪一位码时，无法判决哪一位码发生了错误发生了错误000（晴）（晴）101（云）（云）110（雨）（雨）错一位错一位100要想纠正错误，需要增加多余度，要想纠正错误，需要增加多余度，比如，只准使用两个码比如，只准使用两个码组组第13页，本讲稿共66页14000（晴）（晴）111（阴）（阴）其他均为禁用码组，则它可检测两个错码或能纠正一个错码。其他均为禁用码组，则它可检测两个错码或能纠正一个错码。如：接收端接收到禁用码组如：接收端接收

11、到禁用码组100，若认为只有一个错码，可纠，若认为只有一个错码，可纠正，若错码数不超过正，若错码数不超过2个，只能检测错误个，只能检测错误4种信息完全可以由种信息完全可以由2位二进制数字来表示，即前两位。位二进制数字来表示，即前两位。可见，第三位完全是多余的，这第三位就作为附加的可见，第三位完全是多余的，这第三位就作为附加的监督码监督码第14页，本讲稿共66页15一、纠错编码的基本思想一、纠错编码的基本思想 发送端按照某种规则在信息序列上发送端按照某种规则在信息序列上附加监督码元附加监督码元，接收端，接收端则按照同一规则检查两者间关系则按照同一规则检查两者间关系 码的检错和纠错能力是用信息量的

12、码的检错和纠错能力是用信息量的冗余冗余来换取的。添加来换取的。添加的冗余越多，码的检错、纠错能力越强，但信道的传输效的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。率下降也越多。以以牺牲通信的有效性牺牲通信的有效性（信息传输速率）来提高（信息传输速率）来提高可靠性可靠性第15页，本讲稿共66页16二、纠错编码的理论基础二、纠错编码的理论基础理论依据：理论依据：ShannonShannon信道编码定理信道编码定理定理指出：定理指出：对于一给定的有干扰信道，若其信道容量为对于一给定的有干扰信道，若其信道容量为C C，只要，只要发送端以发送端以低于低于C C的速率的速率R R发送信息

13、，则一定存在一种编码方发送信息，则一定存在一种编码方法，使编码错误概率法，使编码错误概率P P随着码长随着码长n n的增加，按指数下降到任的增加，按指数下降到任意小的值。意小的值。E（R）称为误差指数，）称为误差指数，n编码长度，编码长度，R信息发送速率信息发送速率第16页，本讲稿共66页17三、编码距离与纠错检测的关系三、编码距离与纠错检测的关系码重码重：二进编码序列二进编码序列V中，包含中，包含1的个数为该码组的重量（权），的个数为该码组的重量（权），W(v)码距码距：两个等长码组两个等长码组V1,V2中对应码位上不同二进制码中对应码位上不同二进制码元的个数，也叫汉明距离，元的个数，也叫汉

14、明距离，d(V1,V2)例：例：V111001100和和V2=10010111 重量分别为重量分别为W14，W25；它们的距离为；它们的距离为d(V1,V2)=5。两码组间的汉明距离也等于两码组对应位模二加后所得两码组间的汉明距离也等于两码组对应位模二加后所得码组的重量码组的重量n几个基本概念几个基本概念第17页，本讲稿共66页18最小码距最小码距：对于某种编码，所含的全部码组之间的最小距离，成对于某种编码，所含的全部码组之间的最小距离，成为该码的最小码距，为该码的最小码距，用用dmin表示表示最小码距的大小最小码距的大小直接关系着这种编码的检错和纠错能力，直接关系着这种编码的检错和纠错能力，

15、它是衡量各种码抗干扰能力大小的标准。它是衡量各种码抗干扰能力大小的标准。码组的最小距离码组的最小距离越大，说明码字间的最小差别越大，抗干扰能力越强。越大，说明码字间的最小差别越大，抗干扰能力越强。n 最小码距与检错和纠错能力的关系最小码距与检错和纠错能力的关系1)如果如果 一个码能检错不多于一个码能检错不多于e个错，则要求个错，则要求2)如果如果 一个码能纠正不多于一个码能纠正不多于t个错，则要求个错，则要求第18页，本讲稿共66页192)如果如果 一个码能纠正不多于一个码能纠正不多于t个错，同时可以检个错，同时可以检e个错误个错误 则要求则要求四、编码效率四、编码效率设编码序列长度与所包含的

16、信息位数分别为设编码序列长度与所包含的信息位数分别为n,k，则，则编码效率指一个码组中信息位所占比重：编码效率指一个码组中信息位所占比重：第19页，本讲稿共66页20编码效率是衡量码性能的一个重要参量，编码效率是衡量码性能的一个重要参量，编码效率与编码效率与抗干扰能力这两个参数是相互矛盾的抗干扰能力这两个参数是相互矛盾的编码的主要任务就是如何找到一种编码，在满足一定编码的主要任务就是如何找到一种编码，在满足一定误码率要求的前提下，尽量提高编码效率。误码率要求的前提下，尽量提高编码效率。五、编码增益五、编码增益描述编码系统对非编码系统性能的改善程度，定义为描述编码系统对非编码系统性能的改善程度，

17、定义为在给定误码率要求下，非编码系统与编码系统之间所在给定误码率要求下，非编码系统与编码系统之间所需信噪比的差。需信噪比的差。编码增益越大越好编码增益越大越好第20页，本讲稿共66页218.3线性分组码线性分组码一、基本概念一、基本概念n分组码分组码将信息码首先分成若干组，然后为每组信码附加若干位将信息码首先分成若干组，然后为每组信码附加若干位监督码元，这种编码称之为监督码元，这种编码称之为“分组码分组码”分组码一般用（分组码一般用（n,k）表示，）表示，k k是信息码的位数，是信息码的位数，n n是码组长是码组长度，监督码元位数度，监督码元位数r=n-k r=n-k，分组码结构分组码结构码长

18、码长n=k+rk个信息位个信息位r个监督位个监督位第21页，本讲稿共66页22注意注意：在分组码中，监督码仅监督本码组中的信息码元。在非在分组码中，监督码仅监督本码组中的信息码元。在非分组码中如卷积码，监督码元除了与本组信息码元有关，还与分组码中如卷积码，监督码元除了与本组信息码元有关，还与其它组的信息码元有关其它组的信息码元有关n线性码线性码码组中监督码元和信息码元之间满足线性变换关系，由一组线码组中监督码元和信息码元之间满足线性变换关系，由一组线性方程（监督方程）构成。性方程（监督方程）构成。线性码是一种代数码。奇偶监督码线性码是一种代数码。奇偶监督码是最简单的线性码。是最简单的线性码。第

19、22页，本讲稿共66页23二、几种简单的线性分组码二、几种简单的线性分组码1、重复码、重复码(n,1)的线性分组码，最小码距为的线性分组码，最小码距为n，当，当n很大时，编码效率低，很大时，编码效率低，纠错能力强，纠错能力强，2、奇偶校验码、奇偶校验码只有只有一个监督码（校验位）的一个监督码（校验位）的（n,n-1）的分组码。分为）的分组码。分为两种：两种：奇数奇数校验码和校验码和偶数偶数校验码校验码第23页，本讲稿共66页24n奇数校验码：附加一位监督码，使奇数校验码：附加一位监督码，使码组中码组中“1”的个数为奇数的个数为奇数设码字（设码字（vn-1,vn-2,v1,v0），），v0为监督

20、元，则有：为监督元，则有：vn-1 vn-2 v1 v01 （8-1）在接收端，按上式计算各码元，若结果为在接收端，按上式计算各码元，若结果为0认为有错；认为有错；否则，无错。如：否则，无错。如：11010 0模模2加加n偶数校验码：附加一位监督码，使偶数校验码：附加一位监督码，使码组中码组中“1”的个数为偶数，的个数为偶数，vn-1 vn-2 v1 v00即满足：即满足：（8-28-2）（8-1）与与(8-2)叫做叫做监督方程监督方程或或监督关系式监督关系式第24页，本讲稿共66页25在接收端，按上式计算各码元，若结果为在接收端，按上式计算各码元，若结果为1认为有错；否认为有错；否则，无错。

21、如：则，无错。如：11010 1注意：只能检测奇数个错误注意：只能检测奇数个错误，当错码为奇数个时，由于打乱了当错码为奇数个时，由于打乱了码字中码字中”1”个数的奇偶性，故能发现差错。但当错码为偶数个个数的奇偶性，故能发现差错。但当错码为偶数个时，因码字中时，因码字中1个数奇偶性保持不变，则无法发现错码。个数奇偶性保持不变，则无法发现错码。特点：结构简单，特点：结构简单，易于实现，编码效率高，虽然不理想，但易于实现，编码效率高，虽然不理想，但干扰不严重时，且码长不长的情况下仍很有用。干扰不严重时，且码长不长的情况下仍很有用。第25页，本讲稿共66页263、方阵码、方阵码也叫二维奇偶校验码（矩阵

22、码、行列监督码），其基本原理也叫二维奇偶校验码（矩阵码、行列监督码），其基本原理与简单的奇偶校验码相似。不同的是与简单的奇偶校验码相似。不同的是每个码元都要受到行每个码元都要受到行和列的两项监督和列的两项监督编码方法：编码方法：将所要传送的码序列编成一个方阵，方阵中每一行为一个将所要传送的码序列编成一个方阵，方阵中每一行为一个码组。每行的最后加上一个监督码元，进行奇偶监督。在码组。每行的最后加上一个监督码元，进行奇偶监督。在每列的最后也加上一个监督码，进行奇偶监督每列的最后也加上一个监督码，进行奇偶监督第26页，本讲稿共66页27例：若发送码序列为（例：若发送码序列为（1100100111 0

23、100011100 0010011110 0101011000 0110000001 11）,求其奇偶监督方阵求其奇偶监督方阵 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 经编码后的校验位和信息位一起传输经编码后的校验位和信息位一起传输:（11001001110010001110000010011110101010110000011000000111001111100）第27页，本

24、讲稿共66页28特点：特点：（1）有可能检测偶数个错误，但是不能检测在方阵中构成）有可能检测偶数个错误，但是不能检测在方阵中构成 矩形矩形四个角的错误，四个角的错误，因为在行列两个方向均有偶数个错误。因为在行列两个方向均有偶数个错误。（2）适于检测突发错码，能纠正突发错误，如当码组中仅在一行）适于检测突发错码，能纠正突发错误，如当码组中仅在一行有奇数个错误时，能够确定错误位置，并纠正它。有奇数个错误时，能够确定错误位置，并纠正它。（3）第28页，本讲稿共66页294、恒比码（等比码或等重码）、恒比码（等比码或等重码）n每个码组中含每个码组中含“1”和和“0”的个数的比例恒定的个数的比例恒定n在

25、检测时，计算接收码组中在检测时，计算接收码组中“1”的数目是否正确，的数目是否正确，能检测能检测 出所有奇数个错误，并能部分检测出偶数个错误（成对交出所有奇数个错误，并能部分检测出偶数个错误（成对交 换错误检测不出）换错误检测不出）n 简单，适用于电传机或其它键盘设备产生的字母和符号简单，适用于电传机或其它键盘设备产生的字母和符号例：我国电传机用例：我国电传机用“5中取中取3”恒比码表示恒比码表示10个数字个数字第29页，本讲稿共66页30表表我国五单位保护电码表我国五单位保护电码表数字电码数字电码00 1 1 0 150 0 1 1 110 1 0 1 161 0 1 0 121 1 0 0

26、 171 1 1 0 031 0 1 1 080 1 1 1 041 1 0 1 091 0 0 1 1在国际无线电报通信中，广泛采用在国际无线电报通信中，广泛采用“7中取中取3”恒比码。恒比码。（是一种五中取三码）（是一种五中取三码）第30页，本讲稿共66页31四、线性分组码编码原理四、线性分组码编码原理1、汉明码汉明码：能纠正单个随机错误且编码效率较高的线性：能纠正单个随机错误且编码效率较高的线性分组码，其参数：分组码，其参数：监督位：监督位：码长：码长：信息位：信息位：最小距离：最小距离：编码效率：编码效率：当当m很大时，很大时，第31页，本讲稿共66页322、以（、以（7，4）汉明码为

27、例来说明编码原理）汉明码为例来说明编码原理设码字为设码字为a6 a5 a4a3 a2 a1 a0，n信息码元信息码元a6、a5、a4、a3来源于待编码的信息序列；来源于待编码的信息序列；n监督码元监督码元 a2、a1、a0的取值应根据信息码元按监督的取值应根据信息码元按监督 关系式来决定关系式来决定na6+a5+a4+a2=0na6+a5+a3+a1=0na6+a4+a3+a0=0na2=a4+a5+a6na1=a3+a5+a6na0=a3+a4+a6（8-3）每个方程分别为某一个监督码元的奇偶校验方程。每个方程分别为某一个监督码元的奇偶校验方程。通常称这几个线性方程为对应码的一致监督关系式或

28、一致校验方程通常称这几个线性方程为对应码的一致监督关系式或一致校验方程第32页，本讲稿共66页33n给定信息位后，根据上式算出各监督位，该编码的所有码组如给定信息位后，根据上式算出各监督位，该编码的所有码组如下表下表第33页，本讲稿共66页34（1）监督矩阵（奇偶校验矩阵）监督矩阵（奇偶校验矩阵）1 a6+1 a5+1 a4+0 a3+1 a2+0 a1+0 a0=01 a6+1 a5+0 a4+1 a3+0 a2+1 a1+0 a0=01 a6+0 a5+1 a4+1 a3+0 a2+0 a1+1 a0=0na6+a5+a4+a2=0na6+a5+a3+a1=0na6+a4+a3+a0=0上

29、式监督关系式上式监督关系式(8-3)可写成可写成第34页，本讲稿共66页35写成矩阵形式写成矩阵形式可记为：可记为：HVT=0T 或或VHT=0第35页，本讲稿共66页36H H称为线性码称为线性码监督矩阵监督矩阵 rn rn阶矩阵阶矩阵 监督矩阵监督矩阵H H确定了编码时监督码元与信息码元的关系，确定了编码时监督码元与信息码元的关系，可由可由H H和信息码元求出全部码组和信息码元求出全部码组 把具有把具有PPI Ir r 形式的形式的H H矩阵称为矩阵称为典型形式典型形式的监督矩阵，其中的监督矩阵，其中P P为为r kr k阶矩阵阶矩阵,I Ir r为为r rr r阶单位方阵阶单位方阵 H

30、H矩阵的各行应矩阵的各行应线性无关线性无关。矩阵若能写成典型形式，则其各行一。矩阵若能写成典型形式，则其各行一定线性无关定线性无关监督矩阵特点监督矩阵特点:第36页，本讲稿共66页37(2)生成矩阵生成矩阵对（对（7,4）线性码，由其一致监督方程式，再附加）线性码，由其一致监督方程式，再附加4个等式个等式na6=a6na5=a5na4=a4na3=a3na2=a4+a5+a6na1=a3+a5+a6na0=a3+a4+a6第37页，本讲稿共66页38第38页，本讲稿共66页39nk nk n阶矩阵，阶矩阵，编码方法完全由生成矩阵编码方法完全由生成矩阵G G确定确定n把具有把具有IIk kQQ形

31、式的形式的G G矩阵称为典型形式的生成矩阵，其中，矩阵称为典型形式的生成矩阵，其中，I Ik k为为kkkk阶单位方阵，阶单位方阵，Q Q为为k rk r阶矩阵阶矩阵nV V可看成是可看成是G G矩阵的各行的线性组合，为保证不同的信息分组矩阵的各行的线性组合，为保证不同的信息分组对应不同的码字，对应不同的码字，G G矩阵各行应线性无关矩阵各行应线性无关生成矩阵特点：生成矩阵特点：第39页，本讲稿共66页403、线性分组码伴随式（或校验子）、线性分组码伴随式（或校验子）监督关系式监督关系式 HVT=0T 或或VHT=0码字是由码字是由H矩阵所确定的线性方程组的解，所以可以由矩阵所确定的线性方程组

32、的解，所以可以由H矩阵来检验接收的序列是否为码字矩阵来检验接收的序列是否为码字若接收到码字若接收到码字R=V+E，E为为错误矢量（或错误图样）错误矢量（或错误图样）计算计算SRHT=(V+E)HT =VHT+EHT=EHT当当S0表明没错，此时表明没错，此时E0；否则，；否则，S不为不为0，表明有错，表明有错，E也不为也不为0。S称为校验子（伴随式）称为校验子（伴随式）第40页，本讲稿共66页41n任意两个许用码组任意两个许用码组模模2 2和和仍为一许用码组，即具有仍为一许用码组，即具有封闭性。封闭性。n两码组之间的距离是另一码组的重量，最小码距两码组之间的距离是另一码组的重量，最小码距=非零

33、码非零码的最小码重的最小码重(1的个数）的个数）4、线性分组码最小码距及性质、线性分组码最小码距及性质许用码字许用码字第41页，本讲稿共66页42设（设（7,47,4）线性码的生成矩阵）线性码的生成矩阵G G为：为：当信息位为当信息位为00010001时，时，（1 1）试求其后的监督位。）试求其后的监督位。（2 2）监督矩阵）监督矩阵H第42页，本讲稿共66页43解：解：（1）第43页，本讲稿共66页44（2 2）监督矩阵）监督矩阵H H根据生成矩阵和监督矩阵的关系：根据生成矩阵和监督矩阵的关系：G=IG=Ik kQQ，H=PH=PI Ir r 其中其中P=QP=QT T，可得监督矩阵，可得监

34、督矩阵H H为：为：第44页，本讲稿共66页458.48.4循环码循环码一、循环码的编码原理一、循环码的编码原理循环码是一种重要的循环码是一种重要的线性分组码线性分组码，是在代数学基，是在代数学基础上建立起来的，编码和解码设备都不太复杂，且有较强的础上建立起来的，编码和解码设备都不太复杂，且有较强的检（纠）错能力。检（纠）错能力。特点：特点：n 封闭性封闭性n 循环性循环性：即码中任一码组循环一位：即码中任一码组循环一位(将最右端的码元移将最右端的码元移 到左端或反之）以后，仍为该码中的一个码组。到左端或反之）以后，仍为该码中的一个码组。第45页，本讲稿共66页46若若(v vn-1n-1,v

35、,vn-2n-2,v,v1 1,v,v0 0)是一是一(n,k)(n,k)循环码的码组，则循环码的码组，则(v vn-2 n-2,v,vn-3 n-3,v,v1 1,v,v0 0,v,vn-1n-1)(v vn-3 n-3,v,vn-4 n-4,v,v0 0,v,vn-1n-1,v,vn-2n-2)(v v0 0,v,vn-1 n-1,v,vn-2 n-2,v,vn-3 n-3,v,v2 2,v,v1 1)也都是该循环码的码组。也都是该循环码的码组。1、码多项式、码多项式设一个设一个(n,k)线性分组码，其中的每个码字线性分组码，其中的每个码字V=(vn-1,vn-2,v1,v0)可用一个可用

36、一个n-1 次多项式表示，即次多项式表示，即V(x)=vn-1xn-1+vn-2xn-2+v1x+v0第46页，本讲稿共66页47如：对于（如：对于（7 7，3 3）循环码的任意码组可表示为：）循环码的任意码组可表示为：V(x)=aV(x)=a6 6x x6 6+a+a5 5x x5 5+a+a4 4x x4 4+a+a3 3x x3 3+a+a2 2x x2 2+a+a1 1x+ax+a0 0如码组（如码组（11001011100101）对应的码多项式可表示为）对应的码多项式可表示为 V(x)=V(x)=1*x1*x6 6+1*x+1*x5 5+0*x+0*x4 4+0*x+0*x3 3+1

37、*x+1*x2 2 +0*x+1+0*x+1 =x =x6 6+x+x5 5 +x+x2 2+1+1码多项式与码字的关系：码多项式与码字的关系：本质上是一回事，仅是表示方法的不同而已。本质上是一回事，仅是表示方法的不同而已。x x仅是码元位置仅是码元位置的标志。并不关心的标志。并不关心x x的取值。的取值。第47页，本讲稿共66页48序序号号码字码字序序号号码字码字信息位信息位a6 a5 a4a6 a5 a4监督位监督位a3 a2 a1 a0a3 a2 a1 a0信息位信息位a6 a5 a4a6 a5 a4监督位监督位a3 a2 a1 a0a3 a2 a1 a01 10 00 00 00 00

38、 00 00 05 51 10 00 01 10 01 11 12 20 00 01 10 01 11 11 16 61 10 01 11 11 10 00 03 30 01 10 01 11 11 10 07 71 11 10 00 01 10 01 14 40 01 11 11 10 00 01 18 81 11 11 10 00 01 10 0一种（一种（7 7，3 3）循环码的全部码字）循环码的全部码字第48页，本讲稿共66页49若一个整数若一个整数m m可以表示为可以表示为:则有则有mpmp（模（模n n），同样对于多项式而言），同样对于多项式而言：则可以写为：则可以写为：F(x)R

39、(x)F(x)R(x)（模（模N(x)N(x)）。）。即一任意多项式即一任意多项式F(x)F(x)被一个被一个n n次多项式次多项式N(x)N(x)除，得到商除，得到商式式Q(x)Q(x)和一个次数小于和一个次数小于n n的余式的余式R(x)R(x)第49页，本讲稿共66页50例如码组（1100101）对应的码多项式可为：V7(x)=x6+x5+x2+1其被x2+1除得x6+x5+x2+1x+1（模x2+1）重要结论重要结论在循环码中，若在循环码中，若V(x)V(x)是一个长为是一个长为n n的许用码组，的许用码组，V Vi i(x)(x)为为V(x)V(x)码组向左循环移位码组向左循环移位i

40、 i次的结果，次的结果，也是一许用码组，则也是一许用码组，则x xi i V(x)V(x)在按模在按模x xn n+1+1运算下，运算下，也是一许用码组。即也是一许用码组。即 x xi i V(x)V V(x)Vi i(x)(x)（模（模x xn n+1+1）第50页，本讲稿共66页51例如：其对应的码组为0101110，它正是表5-10中第3码字。结论：一个码长为n的(n，k)循环码，它必为按模xn+1运算的一个余式。第51页，本讲稿共66页522、循环码的生成多项式与生成矩阵、循环码的生成多项式与生成矩阵 循环码完全由其码组长度循环码完全由其码组长度n n和生成多项式和生成多项式g(x)g

41、(x)所所决定决定 问题：寻找构成生成矩阵的问题：寻找构成生成矩阵的k k个线性无关的许用个线性无关的许用码组码组（n n，k)k)循环码中一定能找到这样一个码组：前面循环码中一定能找到这样一个码组：前面的的k-1k-1位都是位都是0 0，而第，而第k k位及第位及第n n位为位为1 1，其它各位，其它各位g gi i为为0 0或或1 1：（00000001g01gn-k-1n-k-1g gn-k-2n-k-2 g g2 2 g g1 11)1)第52页，本讲稿共66页53其对应的码多项式为其对应的码多项式为g(x)g(x)，且，且 g(x)g(x)一定是码中唯一定是码中唯一的一个一的一个n-

42、kn-k次多项式，这唯一的次多项式，这唯一的n-kn-k次多项式次多项式g(x)g(x)称称为码的生成多项式为码的生成多项式可以证明生成多项式可以证明生成多项式g(x)g(x)具有以下特性：具有以下特性：（1 1）g(x)g(x)是一个常数项为是一个常数项为1 1的的 次多次多项式；项式；（2 2）g(x)g(x)是是 的一个因式；的一个因式；（3 3）该循环码中其它码多项式都是）该循环码中其它码多项式都是g(x)g(x)的倍式。的倍式。g(x)g(x)，xg(x)xg(x)，x xk-1k-1g(xg(x)第53页，本讲稿共66页54g(x)g(x)，x xk-1k-1g(x)g(x)都是许

43、用码组，连同都是许用码组，连同g(x)g(x)共共k k个许用码组，构成个许用码组，构成码的生成矩阵码的生成矩阵G(x)G(x)注：该生成矩阵并不是典型形式的，但可通过线注：该生成矩阵并不是典型形式的，但可通过线性变换变换成典型的生成矩阵性变换变换成典型的生成矩阵。第54页，本讲稿共66页55一旦生成多项式一旦生成多项式g(x)g(x)确定以后，该循环码的生成矩确定以后，该循环码的生成矩阵阵G(x)G(x)就可以确定，进而该循环码的所有码字就可就可以确定，进而该循环码的所有码字就可以确定。生成矩阵以确定。生成矩阵G(x)G(x)的每一行都是一个码组。的每一行都是一个码组。例例 试求（试求（7

44、7，3 3）循环码的生成多项式和生成矩阵。）循环码的生成多项式和生成矩阵。生成多项式生成多项式g(x)g(x)是是x xn n+1+1的一个因式，且的一个因式，且g(x)g(x)是一个是一个n-kn-k次因式。次因式。因此，就可以先对因此，就可以先对x xn n+1+1进行因式分解，找到它的进行因式分解，找到它的n-k次因式。次因式。第55页，本讲稿共66页56解解2 2：对（：对（7,37,3）循环码，）循环码，n=7n=7，k=3,r=4k=3,r=4n第一步：对第一步：对x x7 7+1+1进行因式分解得：进行因式分解得：x7+1=(x+1)(x3+x2+1)(x3+x+1).(1)n第

45、二步：构造第二步：构造r=n-kr=n-k次生成多项式次生成多项式g(x)g(x)。要从式（1）中找到r=n-k=4次的因子,这样的因子有两个：(x+1)(x3+x2+1)=x4+x2+x+1(a)(x+1)(x3+x+1)=x4+x3+x2+1(b)n第三步：若按(a)构成生成多项式:生成多项式为：g(x)=x4+x2+x+1第56页，本讲稿共66页57生成矩阵为：将第1行与第3行模2加作为第1行，则有为典型生成矩阵第57页，本讲稿共66页58若按(b)构成生成多项式:生成多项式为：g(x)=x4+x3+x2+1生成矩阵为：进行线性变换，得典型生成矩阵为：第58页，本讲稿共66页593、循环

46、码的监督多项式与监督矩阵、循环码的监督多项式与监督矩阵其中其中是是逆多项式逆多项式1、方法、方法1：第59页，本讲稿共66页60方法方法2：根据生成矩阵和监督矩阵的关系求：根据生成矩阵和监督矩阵的关系求：G=IkQ，H=PIr其中其中P=QT例例试求（试求（7，3）循环码的监督多项式和监督矩阵。已）循环码的监督多项式和监督矩阵。已知生成多项式知生成多项式g(x)=x4+x3+x2+1第60页，本讲稿共66页61二、循环码的编码、解码方法二、循环码的编码、解码方法1、编码方法、编码方法（1）原理）原理第61页，本讲稿共66页62n首先从首先从x xn n+1+1的因子中选一个（的因子中选一个（n

47、-kn-k）次多项式作为）次多项式作为g(x)g(x)；n然后，利用循环码的编码特点，即所有循环码多项式然后，利用循环码的编码特点，即所有循环码多项式V(x)V(x)都可以被都可以被g(x)g(x)整除，来定义生成多项式整除，来定义生成多项式g(x)g(x)。(2)编码步骤编码步骤设信息位对应的多项式为设信息位对应的多项式为m(x)m(x)用用x xn-kn-k乘乘m(x)m(x)，相当于把信息码后附加上（，相当于把信息码后附加上（n-kn-k）个）个“0 0”用用g(x)g(x)除除x xn-kn-k m(x)m(x)，得到余式为，得到余式为r(x)r(x)编出码组为：编出码组为：V(x)=

48、xV(x)=xn-k n-k m(x)+r(x)m(x)+r(x)第62页，本讲稿共66页63例题例题设（设（7，3）循环码的生成多项式为）循环码的生成多项式为g(x)=x4+x2+x+1，待编码信息位为，待编码信息位为110，求对应循环码码组。，求对应循环码码组。即余式即余式r(x)=x2+1于是，对应码组于是，对应码组V(x)=xn-km(x)+r(x）=x6+x5+x2+1编码为编码为1100101解：解：m(x)=x2+x，xn-km(x)=x4(x2+x)=x6+x5第63页，本讲稿共66页642、译码方法、译码方法（1 1）目的）目的检错、纠错检错、纠错（2 2）采用手段：）采用手

49、段：判断接收到的码组多项式判断接收到的码组多项式B(x)B(x)是否能被生成多项式是否能被生成多项式g(x)g(x)整整除作为依据除作为依据 n当传输中未发生错误时，当传输中未发生错误时，B(x)=V(x)B(x)=V(x)，则接收的码组，则接收的码组B(x)B(x)必能被必能被g(x)g(x)整除；整除；n若传输中发生了错误，若传输中发生了错误，B(x)V(x)B(x)V(x)，B(x)B(x)不能被不能被g(x)g(x)整除整除 B(x)V(x)B(x)V(x)，B(x)B(x)能被能被g(x)g(x)整除整除 不可检错误不可检错误 第64页，本讲稿共66页653、译码步骤译码步骤n由接收

50、到的码多项式由接收到的码多项式B(x)B(x)计算校正子（伴随式）多项式计算校正子（伴随式）多项式S(x)S(x)；即求解；即求解B(x)B(x)整除整除g(x)g(x)的余式的余式r(x)r(x)n由校正子由校正子S(x)S(x)确定错误图样确定错误图样E(x)E(x)；n将错误图样将错误图样E(x)E(x)与与B(x)B(x)相加，纠正错误。相加，纠正错误。第65页，本讲稿共66页668.4小结小结1、纠错编码的基本概念、纠错编码的基本概念码重、码距、编码效率、最小码距，差错控制方法码重、码距、编码效率、最小码距，差错控制方法2、最小码距与检测纠错能力的关系、最小码距与检测纠错能力的关系3