《最新差错控制编码纠错码PPT课件》由会员分享，可在线阅读，更多相关《最新差错控制编码纠错码PPT课件（67页珍藏版）》请在金锄头文库上搜索。
1、差错控制编码纠错码差错控制编码纠错码 主要内容主要内容主要内容主要内容8.1 8.1 引言引言8.2 8.2 纠错编码的基本原理纠错编码的基本原理8.3 8.3 线性分组码线性分组码8.48.4 循环码循环码8.5 8.5 小结小结2优点：极低的不可检测概率；编译码简单；对任何信道都有效优点：极低的不可检测概率；编译码简单；对任何信道都有效缺点：需要反向信道；译码延迟不固定；需要缓冲器缺点：需要反向信道；译码延迟不固定；需要缓冲器（3）FEC/ARQFEC/ARQ混合系统混合系统分为三类：停止等待分为三类：停止等待ARQ、连续、连续ARQ和选择重发和选择重发ARQ综合利用综合利用FEC延迟小，
2、纠错能力强和延迟小，纠错能力强和ARQ传输可靠性高传输可靠性高9发端发出同时具有检错和纠错能力的码，收端收到后，发端发出同时具有检错和纠错能力的码，收端收到后，检查错误情况：如果错误在纠错能力之内，则自动纠正；检查错误情况：如果错误在纠错能力之内，则自动纠正；若超出纠错能力，但在检错能力之内，则经反向信道要若超出纠错能力，但在检错能力之内，则经反向信道要求重发。求重发。注意注意：不同的纠错编码方法，有不同的检错或纠错能力，：不同的纠错编码方法，有不同的检错或纠错能力，一般说来，增加监督码元越多，检错或纠错的能力就越强，一般说来，增加监督码元越多，检错或纠错的能力就越强，提高传输可靠性是以降低传
3、输有效性为代价的。提高传输可靠性是以降低传输有效性为代价的。108.2纠错编码的基本原理纠错编码的基本原理简单例子：简单例子：3位二进制码组（位二进制码组（c1c2c3）,其中其中ci=0或或1。此码组。此码组有有8种不同的组合：种不同的组合：000001010011100101110111可分别代表不同的信息含义。若将可分别代表不同的信息含义。若将8种码组都作为有用种码组都作为有用码组来使用，比如代表码组来使用，比如代表8种天气情况：种天气情况：000（晴晴），），001（雷），（雷），010（雹），（雹），011（阴阴），），100（风），（风），101（云云），），110（雨雨），），1
4、11（雪）（雪）11任一码组在传输中若发生一个或多个错码，则将变成任一码组在传输中若发生一个或多个错码，则将变成另一信息码组另一信息码组这种编码方法就不具有任何抗干扰能力：这种编码方法就不具有任何抗干扰能力：但如果在但如果在8种码组中，规定只准使用其中种码组中，规定只准使用其中4种来传输信息，种来传输信息，比如，许用码组为：比如，许用码组为：000（晴），（晴），011（阴），（阴），101（云），（云），110（雨）（雨）这种编码这种编码接收端有可能检测码组中出现的一位或接收端有可能检测码组中出现的一位或三位错误，但不能发现两位错码的情况三位错误，但不能发现两位错码的情况接收端收到禁用码组时
5、，就认为发现了错误接收端收到禁用码组时，就认为发现了错误12这种方法这种方法只能检测错误，但不能纠正错误只能检测错误，但不能纠正错误比如：当接收端收到禁用码组比如：当接收端收到禁用码组100时，无法判决哪一位码时，无法判决哪一位码发生了错误发生了错误000（晴）（晴）101（云）（云）110（雨）（雨）错一位错一位100要想纠正错误，需要增加多余度，要想纠正错误，需要增加多余度，比如，只准使用两比如，只准使用两个码组个码组13000（晴）（晴）111（阴）（阴）其他均为禁用码组，则它可检测两个错码或能纠正一其他均为禁用码组，则它可检测两个错码或能纠正一个错码。个错码。如：接收端接收到禁用码组如
6、：接收端接收到禁用码组100，若认为只有一个错码，若认为只有一个错码，可纠正，若错码数不超过可纠正，若错码数不超过2个，只能检测错误个，只能检测错误4种信息完全可以由种信息完全可以由2位二进制数字来表示，即前两位。位二进制数字来表示，即前两位。可见，第三位完全是多余的，这第三位就作为附加的可见，第三位完全是多余的，这第三位就作为附加的监督码监督码14一、纠错编码的基本思想一、纠错编码的基本思想v 发送端按照某种规则在信息序列上发送端按照某种规则在信息序列上附加监督码元附加监督码元，接收端则按照同一规则检查两者间关系接收端则按照同一规则检查两者间关系v 码的检错和纠错能力是用信息量的码的检错和纠
7、错能力是用信息量的冗余冗余来换取的。来换取的。添加的冗余越多，码的检错、纠错能力越强，但信道的添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。传输效率下降也越多。v以以牺牲通信的有效性牺牲通信的有效性（信息传输速率）来提高（信息传输速率）来提高可靠性可靠性15二、纠错编码的理论基础二、纠错编码的理论基础v理论依据：理论依据：ShannonShannon信道编码定理信道编码定理v定理指出：定理指出： 对于一给定的有干扰信道，若其信道容量为对于一给定的有干扰信道，若其信道容量为C C，只要发送端以只要发送端以低于低于C C的速率的速率R R发送信息，则一定存在发送信息，则一定存
8、在一种编码方法，使编码错误概率一种编码方法，使编码错误概率P P随着码长随着码长n n的增加，的增加，按指数下降到任意小的值。按指数下降到任意小的值。E（R）称为误差指数，）称为误差指数，n编码长度，编码长度，R信息发送速率信息发送速率16三、编码距离与纠错检测的关系三、编码距离与纠错检测的关系码重码重：二进编码序列二进编码序列V中，包含中，包含1的个数为该码组的重的个数为该码组的重量（权），量（权），W(v)码距码距：两个等长码组两个等长码组V1,V2中对应码位上不同二进制码中对应码位上不同二进制码元的个数，也叫汉明距离，元的个数，也叫汉明距离，d(V1,V2)例：例：V111001100和
9、和V2=10010111重量分别为重量分别为W14，W25；它们的距离为；它们的距离为d(V1,V2)=5。两码组间的汉明距离也等于两码组对应位模二加后所得两码组间的汉明距离也等于两码组对应位模二加后所得码组的重量码组的重量u几个基本概念几个基本概念17最小码距最小码距：对于某种编码，所含的全部码组之间的最小距离，对于某种编码，所含的全部码组之间的最小距离，成为该码的最小码距，成为该码的最小码距，用用dmin表示表示最小码距的大小最小码距的大小直接关系着这种编码的检错和纠错能力，直接关系着这种编码的检错和纠错能力，它是衡量各种码抗干扰能力大小的标准。它是衡量各种码抗干扰能力大小的标准。码组的最
10、小距离码组的最小距离越大，说明码字间的最小差别越大，抗干扰能力越强。越大，说明码字间的最小差别越大，抗干扰能力越强。u 最小码距与检错和纠错能力的关系最小码距与检错和纠错能力的关系1)如果如果一个码能检错不多于一个码能检错不多于e个错，则要求个错，则要求2)如果如果一个码能纠正不多于一个码能纠正不多于t个错，则要求个错，则要求182)如果如果一个码能纠正不多于一个码能纠正不多于t个错，同时可以检个错，同时可以检e个错误个错误则要求则要求四、编码效率四、编码效率设编码序列长度与所包含的信息位数分别为设编码序列长度与所包含的信息位数分别为n,k，则，则编码效率编码效率指一个码组中信息位所占比重指一
11、个码组中信息位所占比重：19编码效率是衡量码性能的一个重要参量，编码效率是衡量码性能的一个重要参量，编码效率与编码效率与抗干扰能力这两个参数是相互矛盾的抗干扰能力这两个参数是相互矛盾的编码的主要任务就是如何找到一种编码，在满足一定编码的主要任务就是如何找到一种编码，在满足一定误码率要求的前提下，尽量提高编码效率。误码率要求的前提下，尽量提高编码效率。五、编码增益五、编码增益描述编码系统对非编码系统性能的改善程度，定义为描述编码系统对非编码系统性能的改善程度，定义为在给定误码率要求下，非编码系统与编码系统之间所在给定误码率要求下，非编码系统与编码系统之间所需信噪比的差。需信噪比的差。编码增益越大
12、越好编码增益越大越好208.3线性分组码线性分组码一、基本概念一、基本概念u分组码分组码将信息码首先分成若干组，然后为每组信码附加若干位将信息码首先分成若干组，然后为每组信码附加若干位监督码元，这种编码称之为监督码元，这种编码称之为“分组码分组码”分组码一般用（分组码一般用（n,k）表示，）表示，k k是信息码的位数，是信息码的位数，n n是码是码组长度，监督码元位数组长度，监督码元位数r=n-k r=n-k ，分组码结构分组码结构码长码长n=k+rk个信息位个信息位r个监督位个监督位21注意注意：在分组码中，监督码仅监督本码组中的信息码元。在分组码中，监督码仅监督本码组中的信息码元。在非分组
13、码中如卷积码，监督码元除了与本组信息码元在非分组码中如卷积码，监督码元除了与本组信息码元有关，还与其它组的信息码元有关有关，还与其它组的信息码元有关u线性码线性码码组中监督码元和信息码元之间满足线性变换关系，由一码组中监督码元和信息码元之间满足线性变换关系，由一组线性方程（监督方程）构成。组线性方程（监督方程）构成。线性码是一种代数码。奇线性码是一种代数码。奇偶监督码是最简单的线性码。偶监督码是最简单的线性码。22二、几种简单的线性分组码二、几种简单的线性分组码1、重复码、重复码(n,1)的线性分组码，最小码距为的线性分组码，最小码距为n，当，当n很大时，编码效率低，很大时，编码效率低，纠错能
14、力强，纠错能力强，2、奇偶校验码、奇偶校验码只有只有一个监督码（校验位）的一个监督码（校验位）的（n,n-1）的分组码。分为）的分组码。分为两种：两种：奇数奇数校验码和校验码和偶数偶数校验码校验码23u奇数校验码：附加一位监督码，使奇数校验码：附加一位监督码，使码组中码组中“1”的个数为奇数的个数为奇数设码字（设码字（vn-1,vn-2,v1,v0），），v0为监督元，则有：为监督元，则有：vn-1vn-2v1v01（8-1）在接收端，按上式计算各码元，若结果为在接收端，按上式计算各码元，若结果为0认为有错；认为有错；否则，无错。如：否则，无错。如：110100模模2加加u偶数校验码：附加一位
15、监督码，使偶数校验码：附加一位监督码，使码组中码组中“1”的个数为偶数，的个数为偶数，vn-1vn-2v1v00即满足：即满足：（8-28-2）（8-1）与与(8-2)叫做叫做监督方程监督方程或或监督关系式监督关系式24在接收端，按上式计算各码元，若结果为在接收端，按上式计算各码元，若结果为1认为有错；认为有错；否则，无错。如：否则，无错。如：110101注意：注意：只能检测奇数个错误只能检测奇数个错误，当错码为奇数个时，由于当错码为奇数个时，由于打乱了码字中打乱了码字中”1”个数的奇偶性，故能发现差错。但个数的奇偶性，故能发现差错。但当错码为偶数个时，因码字中当错码为偶数个时，因码字中1个数
16、奇偶性保持不变，个数奇偶性保持不变，则无法发现错码。则无法发现错码。特点：结构简单，特点：结构简单，易于实现，编码效率高，虽然不理想，易于实现，编码效率高，虽然不理想，但干扰不严重时，且码长不长的情况下仍很有用。但干扰不严重时，且码长不长的情况下仍很有用。253、方阵码、方阵码也叫二维奇偶校验码（矩阵码、行列监督码），也叫二维奇偶校验码（矩阵码、行列监督码），其基其基本原理与简单的奇偶校验码相似。不同的是本原理与简单的奇偶校验码相似。不同的是每个码元每个码元都要受到行和列的两项监督都要受到行和列的两项监督编码方法：编码方法：将所要传送的码序列编成一个方阵，方阵中每一行为将所要传送的码序列编成一
17、个方阵，方阵中每一行为一个码组。每行的最后加上一个监督码元，进行奇偶一个码组。每行的最后加上一个监督码元，进行奇偶监督。在每列的最后也加上一个监督码，进行奇偶监监督。在每列的最后也加上一个监督码，进行奇偶监督督26例：若发送码序列为（例：若发送码序列为（1100100111010001110000100111100101011000011000000111）,求其奇偶监督方阵求其奇偶监督方阵11001001110010001110000010011110101010110000011000000111001111100经编码后的校验位和信息位一起传输经编码后的校验位和信息位一起传输: :（11
18、001001110010001110000010011110101010110000011000000111001111100）27特点：特点：（1）有可能检测偶数个错误，但是不能检测在方阵中）有可能检测偶数个错误，但是不能检测在方阵中构成构成矩形四个角的错误，矩形四个角的错误，因为在行列两个方向均有偶因为在行列两个方向均有偶数个错误。数个错误。（2）适于检测突发错码，能纠正突发错误，如）适于检测突发错码，能纠正突发错误，如当码组当码组中仅在一行有奇数个错误时，能够确定错误位置，并纠中仅在一行有奇数个错误时，能够确定错误位置，并纠正它。正它。（3）284、恒比码（等比码或等重码）、恒比码（等比
19、码或等重码）u每个码组中含每个码组中含“1”和和“0”的个数的比例恒定的个数的比例恒定u在检测时，计算接收码组中在检测时，计算接收码组中“1”的数目是否正确，的数目是否正确，能检测能检测出所有奇数个错误，并能部分检测出偶数个错误（成对交出所有奇数个错误，并能部分检测出偶数个错误（成对交换错误检测不出）换错误检测不出）u简单，适用于电传机或其它键盘设备产生的字母和符号简单，适用于电传机或其它键盘设备产生的字母和符号例：我国电传机用例：我国电传机用“5中取中取3”恒比码表示恒比码表示10个数字个数字29表表我国五单位保护电码表我国五单位保护电码表数字数字电码电码数字数字电码电码0011015001
20、11101011610101211001711100310110801110411010910011在国际无线电报通信中，广泛采用在国际无线电报通信中，广泛采用“7中取中取3”恒比码。恒比码。（是一种五中取三码）（是一种五中取三码）30四、线性分组码编码原理四、线性分组码编码原理1、汉明码汉明码：能纠正单个随机错误且编码效率较高的线性：能纠正单个随机错误且编码效率较高的线性分组码，其参数：分组码，其参数：监督位：监督位：码长：码长：信息位：信息位：最小距离：最小距离：编码效率：编码效率：当当m很大时，很大时，312、以（、以（7，4）汉明码为例来说明编码原理）汉明码为例来说明编码原理设码字为设
21、码字为a6 a5 a4a3 a2 a1 a0，u信息码元信息码元a6、a5、a4、a3来源于待编码的信息序列；来源于待编码的信息序列；u监督码元监督码元a2、a1、a0的取值应的取值应根据信息码元按监督根据信息码元按监督关系式来决定关系式来决定Fa6+a5+a4+a2=0Fa6+a5+a3+a1=0Fa6+a4+a3+a0=0Fa2=a4+a5+a6Fa1=a3+a5+a6Fa0=a3+a4+a6（8-3）每个方程分别为某一个监督码元的奇偶校验方程。每个方程分别为某一个监督码元的奇偶校验方程。通常称这几个线性方程为对应码的一致监督关系式或一致校验方程通常称这几个线性方程为对应码的一致监督关系式
22、或一致校验方程32u给定信息位后，根据上式算出各监督位，该编码的所给定信息位后，根据上式算出各监督位，该编码的所有码组如下表有码组如下表33（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=0Fa6+a5+a4+a2=0Fa6+a5+a3+a1=0Fa6+a4+a3+a0=0上式监督关系式上式监督关系式(8-3)可写成可写成34写成矩阵形
23、式写成矩阵形式可记为：可记为： HVT=0T或或VHT=035H H称为线性码称为线性码监督矩阵监督矩阵v rn rn阶矩阵阶矩阵v 监督矩阵监督矩阵H H确定了编码时监督码元与信息码元的关系确定了编码时监督码元与信息码元的关系， 可由可由H H和信息码元求出全部码组和信息码元求出全部码组v 把具有把具有PPI Ir r 形式的形式的H H矩阵称为矩阵称为典型形式典型形式的监督矩阵，的监督矩阵，其中其中P P为为r kr k阶矩阵阶矩阵, , I Ir r为为r rr r阶单位方阵阶单位方阵v H H矩阵的各行应矩阵的各行应线性无关线性无关。矩阵若能写成典型形式，则。矩阵若能写成典型形式，则其
24、各行一定线性无关其各行一定线性无关监督矩阵特点监督矩阵特点:36(2)生成矩阵生成矩阵对（对（7,4）线性码，由其一致监督方程式，再附加）线性码，由其一致监督方程式，再附加4个等式个等式Fa6=a6Fa5=a5Fa4=a4Fa3=a3Fa2=a4+a5+a6Fa1=a3+a5+a6Fa0=a3+a4+a63738vk nk n阶矩阵阶矩阵，编码方法完全由生成矩阵编码方法完全由生成矩阵G G确定确定v把具有把具有IIk kQQ形式的形式的G G矩阵称为典型形式的生成矩阵，矩阵称为典型形式的生成矩阵，其中，其中，I Ik k为为kkkk阶单位方阵，阶单位方阵，Q Q为为k rk r阶矩阵阶矩阵vV
25、 V可看成是可看成是G G矩阵的各行的线性组合，为保证不同的信矩阵的各行的线性组合，为保证不同的信息分组对应不同的码字，息分组对应不同的码字，G G矩阵各行应线性无关矩阵各行应线性无关生成矩阵特点：生成矩阵特点：393、线性分组码伴随式（或校验子）、线性分组码伴随式（或校验子）监督关系式监督关系式HVT=0T或或VHT=0码字是码字是由由H矩阵所确定的线性方程组的解，所以可以由矩阵所确定的线性方程组的解，所以可以由H矩阵来检验接收的序列是否为码字矩阵来检验接收的序列是否为码字若接收到码字若接收到码字R=V+E，E为为错误矢量（或错误图样）错误矢量（或错误图样）计算计算SRHT=(V+E)HT=
26、VHT+EHT=EHT当当S0表明没错，此时表明没错，此时E0；否则，；否则，S不为不为0，表明有错，表明有错，E也不为也不为0。S称为校验子（伴随式）称为校验子（伴随式）40v任意两个许用码组任意两个许用码组模模2 2和和仍为一许用码组，即具有仍为一许用码组，即具有封闭封闭性。性。v两码组之间的距离是另一码组的重量，最小码距两码组之间的距离是另一码组的重量，最小码距=非非零码的最小码重零码的最小码重(1的个数）的个数）4、线性分组码最小码距及性质、线性分组码最小码距及性质许用码字许用码字41设（设（7,47,4）线性码的生成矩阵）线性码的生成矩阵G G为：为：当信息位为当信息位为000100
27、01时，时，（1 1）试求其后的监督位。）试求其后的监督位。（2 2）监督矩阵）监督矩阵H42解：解：（1）43（2 2）监督矩阵）监督矩阵H H根据生成矩阵和监督矩阵的关系：根据生成矩阵和监督矩阵的关系：G= IG= Ik kQQ，H=PH=PI Ir r 其中其中P=QP=QT T，可得监督矩阵，可得监督矩阵H H为：为：448.48.4循环码循环码一、循环码的编码原理一、循环码的编码原理循环码是一种重要的循环码是一种重要的线性分组码线性分组码，是在代数学，是在代数学基础上建立起来的，编码和解码设备都不太复杂，基础上建立起来的，编码和解码设备都不太复杂，且有较强的检（纠）错能力。且有较强的
28、检（纠）错能力。特点：特点：v 封闭性封闭性v 循环性循环性：即码中任一码组循环一位：即码中任一码组循环一位( (将最右端的码元移将最右端的码元移 到左端或反之）以后，仍为该码中的一个码组。到左端或反之）以后，仍为该码中的一个码组。4546若若( (v vn-1n-1,v,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
29、 ,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)可用一个可用一个n-1次多项式表示，即次多项式表示，即V(x)= vn-1xn-1+ vn-2xn-2+ + v1x+ v047如：对于（如：对于（7 7，3 3）循环码的任意码组可表示为：）循环码的任意码组可表示为： V(x)= aV(x)= a6 6x x
30、6 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*x + 1*x2 2 + 0*x+1+ 0*x+1 = x = x6 6 + x + x5 5 + x+ x2 2 +1 +1码多项式与码字的关系：码多项式与码字的关系：本质上是一回事，仅是表示方法的不
31、同而已。本质上是一回事，仅是表示方法的不同而已。x x仅是码仅是码元位置的标志。并不关心元位置的标志。并不关心x x的取值。的取值。48序号码字序号码字信息位a6a5a4监督位a3a2a1a0信息位a6a5a4监督位a3a2a1a01000000051001011200101116101110030101110711001014011100181110010一种（7，3）循环码的全部码字49若一个整数若一个整数m m可以表示为可以表示为: :则有则有mpmp（模（模n n），同样对于多项式而言），同样对于多项式而言：则可以写为：则可以写为：F(x)R(x)F(x)R(x) （模（模N(x)N(
32、x)）。）。即一任意多项式即一任意多项式F(x)F(x)被一个被一个n n次多项式次多项式N(x)N(x)除，除，得到商式得到商式Q(x)Q(x)和一个次数小于和一个次数小于n n的余式的余式R(x)R(x)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 i次的结果，次的结果，也是一许用码组，则也是一许用码组，则x x
33、i 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）51例如：其对应的码组为0101110，它正是表5-10中第3码字。结论：一个码长为n的(n，k)循环码，它必为按模xn+1运算的一个余式。522、循环码的生成多项式与生成矩阵、循环码的生成多项式与生成矩阵v 循环码完全由其码组长度循环码完全由其码组长度n n和生成多项式和生成多项式g(x)g(x)所决定所决定v 问题：寻找构成生成矩阵的问题：寻找构成生成矩阵的k k个线性无关的个线性无关的许用码
34、组许用码组v（n n，k)k)循环码中一定能找到这样一个码组：循环码中一定能找到这样一个码组：前面的前面的k-1k-1位都是位都是0 0，而第，而第k k位及第位及第n n位为位为1 1，其，其它各位它各位g gi i为为0 0或或1 1：v（00000001g01gn-k-1n-k-1g gn-k-2n-k-2 g g2 2 g g1 11) 1) 53v其对应的码多项式为其对应的码多项式为g(x)g(x)，且，且 g(x)g(x)一定是码中一定是码中唯一的一个唯一的一个n-kn-k次多项式，这唯一的次多项式，这唯一的n-kn-k次多项式次多项式g(x)g(x)称为码的生成多项式称为码的生成
35、多项式可以证明生成多项式可以证明生成多项式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) )54g(x)g(x)， ， x xk-1k-1g(x)g(x)都是许用码组，连同都是许用码组，连同g(x)g(x)共共k k个许用码组，构成个许用码组，构成码的生成矩阵码的生成矩阵
36、G(x)G(x)注：该生成矩阵并不是典型形式的，但可通过注：该生成矩阵并不是典型形式的，但可通过线性变换变换成典型的生成矩阵线性变换变换成典型的生成矩阵。55一旦生成多项式一旦生成多项式g(x)g(x)确定以后，该循环码的生确定以后，该循环码的生成矩阵成矩阵G(x)G(x)就可以确定，进而该循环码的所有就可以确定，进而该循环码的所有码字就可以确定。生成矩阵码字就可以确定。生成矩阵G(x)G(x)的每一行都是的每一行都是一个码组。一个码组。 例例 试求（试求（7 7，3 3）循环码的生成多项式和生成）循环码的生成多项式和生成矩阵。矩阵。生成多项式生成多项式g(x)g(x)是是x xn n+1+1
37、的一个因式，且的一个因式，且g(x)g(x)是一个是一个n-kn-k次次因式。因此，就可以先对因式。因此，就可以先对x xn n+1+1进行因式分解，找到它的进行因式分解，找到它的n-k次因式。次因式。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第二步：构造第二步：构造r=n-kr=n-k次生成多项式次生成多项式g(x)g(x)。要从式（1）中找到r=n-k=4次的因子,这样的因子有两个：(x+1)
38、(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+157生成矩阵为：将第1行与第3行模2加作为第1行，则有为典型生成矩阵58若按(b)构成生成多项式:生成多项式为：g(x)=x4+x3+x2+1生成矩阵为：进行线性变换，得典型生成矩阵为：593、循环码的监督多项式与监督矩阵、循环码的监督多项式与监督矩阵其中其中是是逆多项式逆多项式1、方法、方法1：60方法方法2：根据生成矩阵和监督矩阵的关系求：根据生成矩阵和监督矩阵的关系求：G=IkQ，H=PIr其中其中P=QT例例试求
39、（试求（7，3）循环码的监督多项式和监督矩阵。）循环码的监督多项式和监督矩阵。已知生成多项式已知生成多项式g(x)=x4+x3+x2+161二、循环码的编码、解码方法二、循环码的编码、解码方法1、编码方法、编码方法（1）原理）原理62u首先从首先从x xn n+1+1的因子中选一个（的因子中选一个（n-kn-k）次多项式作为）次多项式作为g(x)g(x)；u然后，利用循环码的编码特点，即所有循环码多项式然后，利用循环码的编码特点，即所有循环码多项式V(x)V(x)都可以被都可以被g(x)g(x)整除，来定义生成多项式整除，来定义生成多项式g(x)g(x)。 (2)编码步骤编码步骤设信息位对应的
40、多项式为设信息位对应的多项式为m(x)m(x)u用用x xn-kn-k乘乘m(x)m(x)，相当于把信息码后附加上（，相当于把信息码后附加上（n-kn-k）个）个“0 0” u用用g(x)g(x)除除x xn-kn-k m(x) m(x)，得到余式为，得到余式为r(x)r(x)u编出码组为：编出码组为： V(x)= xV(x)= xn-k n-k m(x)+ r(x)m(x)+ r(x)63例题例题设（设（7，3）循环码的生成多项式为）循环码的生成多项式为g(x)=x4+x2+x+1，待编码信息位为待编码信息位为110，求对应循，求对应循环码码组。环码码组。即余式即余式r(x)=x2+1于是，
41、对应码组于是，对应码组V(x)=xn-km(x)+r(x）=x6+x5+x2+1编码为编码为1100101解：解：m(x)=x2+x，xn-km(x)=x4(x2+x)=x6+x5642、译码方法、译码方法（1 1）目的）目的检错、纠错检错、纠错（2 2）采用手段：）采用手段：判断接收到的码组多项式判断接收到的码组多项式B(x)B(x)是否能被生成多项式是否能被生成多项式g(x)g(x)整整除作为依据除作为依据 当传输中未发生错误时，当传输中未发生错误时，B(x)=V(x)B(x)=V(x)，则接收的码组，则接收的码组B(x)B(x)必能被必能被g(x)g(x)整除；整除；若传输中发生了错误，
42、若传输中发生了错误， 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)整除整除 不可检错误不可检错误 653、译码步骤译码步骤由接收到的码多项式由接收到的码多项式B(x)B(x)计算校正子（伴随式）多项式计算校正子（伴随式）多项式S(x)S(x)；即求解；即求解B(x)B(x)整除整除g(x)g(x)的余式的余式r(x)r(x)由校正子由校正子S(x)S(x)确定错误图样确定错误图样E(x)E(x)；将错误图样将错误图样E(x)E(x)与与B(x)B(x)相加，纠正错误。相加，纠正错误。 8.4小结小结1、纠错编码的基本概念、纠错编码的基本概念码重、码距、编码效率、最小码距，差错控制方法码重、码距、编码效率、最小码距，差错控制方法2、最小码距与检测纠错能力的关系、最小码距与检测纠错能力的关系3、线性分组码的编码译码原理，监督矩阵和生成矩阵、线性分组码的编码译码原理，监督矩阵和生成矩阵的概念的概念66结束语结束语谢谢大家聆听！谢谢大家聆听！67
