通信原理纠错编码PPT学习教案

1、会计学1 通信原理纠错编码通信原理纠错编码 2 8.1 引言引言 在数字信号传输中，由于在数字信号传输中，由于噪声的存在及信道特性噪声的存在及信道特性 不理想不理想，都可使信号波形失真，从而在接收端就不可，都可使信号波形失真，从而在接收端就不可 避免的产生错误判决。避免的产生错误判决。 引起误码原因引起误码原因: (1)信道特性不理想(乘性干扰): 引起码间串扰，通常可采用均衡的办法纠正。 (2) 噪声影响(加性干扰) : 需借助各种差错控制编码技术来克服。 一、基本概念一、基本概念 第1页/共65页 3 差错控制编码差错控制编码又称为又称为信道编码信道编码( (纠错编码纠错编码) )，要求在

2、，要求在 满足有效性前提下，尽可能提高数字通信的可靠性满足有效性前提下，尽可能提高数字通信的可靠性 u纠错编码纠错编码：在要传送的数字信息序列中按一定规则加：在要传送的数字信息序列中按一定规则加 上一些冗余码元（监督位上一些冗余码元（监督位),),使序列按满足一定数学规使序列按满足一定数学规 律的码字传输律的码字传输( (编码过程编码过程);); u译码译码: :在接收端在接收端, ,利用这种规律性来鉴别传输过程是否利用这种规律性来鉴别传输过程是否 发生错误或纠正错误，恢复原始信息序列。发生错误或纠正错误，恢复原始信息序列。 第2页/共65页 4 二、纠错编码的分类二、纠错编码的分类 u 按功

3、能分：检错码和纠错码 u 按监督码元与信息码元之间是否存在线性关系分：线性码与非线性码 u 按信息码元与监督码元之间的约束关系不同分：分组码与非分组码如卷积码 u按信息码元在编码后是否保持原来的信号形式分：系统码与非系统码 u按纠正差错的类型分：纠正随机错误的码与纠正突发错误的码 u 按码元的取值分：二进制码与多进制码 第3页/共65页 5 三、误码的类型三、误码的类型 v 随机误码随机误码 错码出现是随机的、错码之间错码出现是随机的、错码之间统计独立统计独立。 由随机噪声引起由随机噪声引起 存在随机误码的信道称为随机信道存在随机误码的信道称为随机信道 v 突发误码突发误码 错码错码成串集中出

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

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

6、 发端发出同时具有检错和纠错能力的码，收端收到后， 检查错误情况：如果错误在纠错能力之内，则自动纠正； 若超出纠错能力，但在检错能力之内，则经反向信道要 求重发。 注意注意：不同的纠错编码方法，有不同的检错或纠错能力，：不同的纠错编码方法，有不同的检错或纠错能力， 一般说来，增加监督码元越多，检错或纠错的能力就越强，一般说来，增加监督码元越多，检错或纠错的能力就越强， 提高传输可靠性是以降低传输有效性为代价的。提高传输可靠性是以降低传输有效性为代价的。 第8页/共65页 10 8.2纠错编码的基本原理纠错编码的基本原理 简单例子：简单例子： 3位二进制码组（c1 c2 c3）,其中ci=0或1

7、。此码组有8种不同的组合： 000 001 010 011 100 101 110 111 可分别代表不同的信息含义。若将8种码组都作为有用 码组来使用，比如代表8种天气情况： 000（晴），001（雷），010（雹），011（阴）， 100（风），101（云），110（雨），111（雪） 第9页/共65页 11 任一码组在传输中若发生一个或多个错码，则将变成任一码组在传输中若发生一个或多个错码，则将变成 另一信息码组另一信息码组 这种编码方法就不具有任何抗干扰能力：这种编码方法就不具有任何抗干扰能力： 但如果在8种码组中，规定只准使用其中4种来传输信息， 比如，许用码组为： 000（晴），

8、011（阴）， 101（云）， 110（雨） 这种编码这种编码接收端有可能检测码组中出现的一位或接收端有可能检测码组中出现的一位或 三位错误，但不能发现两位错码的情况三位错误，但不能发现两位错码的情况 接收端收到禁用码组时，就认为发现了错误接收端收到禁用码组时，就认为发现了错误 第10页/共65页 12 这种方法只能检测错误，但不能纠正错误 比如：当接收端收到禁用码组比如：当接收端收到禁用码组100时，无法判决哪一位码时，无法判决哪一位码 发生了错误发生了错误 000（晴） 101（云） 110（雨） 错一位错一位 100 要想纠正错误，需要增加多余度，比如，只准使用两个码组 第11页/共65

9、页 13 000（晴） 111（阴） 其他均为禁用码组，则它可检测两个错码或能纠正一个错码。 如：接收端接收到禁用码组如：接收端接收到禁用码组100，若认为只有一个错，若认为只有一个错 码，可纠正，若错码数不超过码，可纠正，若错码数不超过2个，只能检测错误个，只能检测错误 4种信息完全可以由2位二进制数字来表示，即前两位。 可见，第三位完全是多余的，这第三位就作为附加的 监督码 第12页/共65页 14 一、纠错编码的基本思想一、纠错编码的基本思想 v 发送端按照某种规则在信息序列上发送端按照某种规则在信息序列上附加监督码元附加监督码元， 接收端则按照同一规则检查两者间关系接收端则按照同一规则

10、检查两者间关系 v 码的检错和纠错能力是用信息量的码的检错和纠错能力是用信息量的冗余冗余来换取的。来换取的。 添加的冗余越多，码的检错、纠错能力越强，但信道添加的冗余越多，码的检错、纠错能力越强，但信道 的传输效率下降也越多。的传输效率下降也越多。 v以以牺牲通信的有效性牺牲通信的有效性（信息传输速率）来提高（信息传输速率）来提高可靠可靠 性性 第13页/共65页 15 二、纠错编码的理论基础二、纠错编码的理论基础 v理论依据：Shannon信道编码定理 v定理指出： 对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长

11、n的增加，按指数下降到任意小的值。 )(RnE eP E（R）称为误差指数，n编码长度，R信息发送速率 第14页/共65页 16 三、编码距离与纠错检测的关系三、编码距离与纠错检测的关系 码重码重：二进编码序列二进编码序列V中，包含中，包含1的个数为该码组的重的个数为该码组的重 量（权），量（权），W(v) 码距码距：两个等长码组两个等长码组V1,V2中对应码位上不同二进制码中对应码位上不同二进制码 元的个数，也叫汉明距离，元的个数，也叫汉明距离，d(V1,V2) 例：V111001100和V2=10010111 重量分别为W14，W25；它们的距离为d(V1,V2)=5。 两码组间的汉明距离

12、也等于两码组对应位模二加后所得两码组间的汉明距离也等于两码组对应位模二加后所得 码组的重量码组的重量 )21()2, 1(VVWVVd u几个基本概念几个基本概念 第15页/共65页 17 最小码距最小码距：对于某种编码，所含的全部码组之间的最小距对于某种编码，所含的全部码组之间的最小距 离，成为该码的最小码距，离，成为该码的最小码距，用用dmin表示表示 最小码距的大小直接关系着这种编码的检错和纠错能力， 它是衡量各种码抗干扰能力大小的标准。码组的最小距离 越大，说明码字间的最小差别越大，抗干扰能力越强。 u 最小码距与检错和纠错能力的关系最小码距与检错和纠错能力的关系 1) 如果 一个码能

13、检错不多于e个错，则要求 1 min ed 2) 如果 一个码能纠正不多于t个错，则要求 12 min td 第16页/共65页 18 2)如果 一个码能纠正不多于t个错，同时可以检e个错误 则要求 1 min ted 四、编码效率四、编码效率 设编码序列长度与所包含的信息位数分别为设编码序列长度与所包含的信息位数分别为n,k，则，则 编码效率指一个码组中信息位所占比重：编码效率指一个码组中信息位所占比重： rk k n k 第17页/共65页 19 编码效率是衡量码性能的一个重要参量，编码效率与 抗干扰能力这两个参数是相互矛盾的 编码的主要任务就是如何找到一种编码，在满足一定 误码率要求的前

14、提下，尽量提高编码效率。 五、编码增益五、编码增益 描述编码系统对非编码系统性能的改善程度，定义为描述编码系统对非编码系统性能的改善程度，定义为 在给定误码率要求下，非编码系统与编码系统之间所在给定误码率要求下，非编码系统与编码系统之间所 需信噪比的差。需信噪比的差。 编码增益越大越好编码增益越大越好 第18页/共65页 20 8.3线性分组码线性分组码 一、基本概念一、基本概念 u分组码分组码 将信息码首先分成若干组，然后为每组信码附加若干位 监督码元，这种编码称之为“分组码” 分组码一般用（n,k）表示， k是信息码的位数，n是码组长度，监督码元位数r=n-k ，分组码结构 1n c 2n

15、 c rn c 1r c 2n c 0 c 码长n=k+r k个信息位 r个监督位 第19页/共65页 21 注意：在分组码中，监督码仅监督本码组中的信息码元。在非分组码中如卷积码，监督码元除了与本组信息码元有关，还与其它组的信息码元有关 u线性码线性码 码组中监督码元和信息码元之间满足线性变换关系，由一组线性方程（监督方程）构成。线性码是一种代数码。奇偶监督码是最简单的线性码。 第20页/共65页 22 二、几种简单的线性分组码二、几种简单的线性分组码 1、重复码、重复码 (n,1)的线性分组码，最小码距为的线性分组码，最小码距为n，当，当n很大时，编码效率低，很大时，编码效率低， 纠错能力

16、强，纠错能力强， 2、奇偶校验码、奇偶校验码 只有一个监督码（校验位）的（n,n-1）的分组码。分为 两种：奇数校验码和偶数校验码 第21页/共65页 23 u奇数校验码：附加一位监督码，使奇数校验码：附加一位监督码，使码组中码组中“1”的个数为奇数的个数为奇数 设码字（vn-1, vn-2, , v1, v0），v0为监督元，则有： vn-1 vn-2 v1 v01 （8-1） 在接收端，按上式计算各码元，若结果为0认为有错； 否则，无错。如：11010 0 模模2加加 u偶数校验码：附加一位监督码，使偶数校验码：附加一位监督码，使码组中码组中“1”的个数为偶数，的个数为偶数， vn-1 v

17、n-2 v1 v00 即满足：即满足：（8-2） （8-1）与(8-2)叫做监督方程或监督关系式 第22页/共65页 24 在接收端，按上式计算各码元，若结果为1认为有错；否则，无错。如： 11010 1 注意：只能检测奇数个错误注意：只能检测奇数个错误，当错码为奇数个时，由于当错码为奇数个时，由于 打乱了码字中打乱了码字中”1”个数的奇偶性，故能发现差错。但当个数的奇偶性，故能发现差错。但当 错码为偶数个时，因码字中错码为偶数个时，因码字中1个数奇偶性保持不变，则个数奇偶性保持不变，则 无法发现错码。无法发现错码。 特点：结构简单，特点：结构简单，易于实现，编码效率高，虽然不理想，易于实现，

18、编码效率高，虽然不理想， 但干扰不严重时，且码长不长的情况下仍很有用。但干扰不严重时，且码长不长的情况下仍很有用。 第23页/共65页 25 3、方阵码、方阵码 也叫二维奇偶校验码（矩阵码、行列监督码），也叫二维奇偶校验码（矩阵码、行列监督码），其其 基本原理与简单的奇偶校验码相似。不同的是基本原理与简单的奇偶校验码相似。不同的是每个每个 码元都要受到行和列的两项监督码元都要受到行和列的两项监督 编码方法：编码方法： 将所要传送的码序列编成一个方阵，方阵中每一行为一个码组。每行的最后加上一个监督码元，进行奇偶监督。在每列的最后也加上一个监督码，进行奇偶监督 第24页/共65页 26 例：若发送

19、码序列为（1100100111 0100011100 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 经编码后的校验位和信息位一起传输:（ 110010011100100011100000100111101010 10110000011000000111001111100 ） 第25页/共65页

20、 27 特点：特点： （1）有可能检测偶数个错误，但是不能检测在方阵中）有可能检测偶数个错误，但是不能检测在方阵中 构成构成 矩形四个角的错误，矩形四个角的错误，因为在行列两个方向均有偶因为在行列两个方向均有偶 数个错误。数个错误。 （2）适于检测突发错码，能纠正突发错误，如）适于检测突发错码，能纠正突发错误，如当码组当码组 中仅在一行有奇数个错误时，能够确定错误位置，并纠中仅在一行有奇数个错误时，能够确定错误位置，并纠 正它。正它。 （3） mn (m1)(n1) 编编码码效效率率信信息息码码元元共共m m行行n n列列 第26页/共65页 28 4、恒比码（等比码或等重码）、恒比码（等比码

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

22、41 1 0 1 091 0 0 1 1 在国际无线电报通信中，广泛采用“7中取3”恒比码。 （是一种五中取三码） 第28页/共65页 30 四、线性分组码编码原理四、线性分组码编码原理 1、汉明码汉明码：能纠正单个随机错误且编码效率较高的线性：能纠正单个随机错误且编码效率较高的线性 分组码，其参数：分组码，其参数： 监督位：监督位：3m 且knm 码长：码长： 12 m n 信息位：信息位： m m 12 最小距离：最小距离： 3 min d 编码效率：编码效率： 12 1 12 12 mm m mm n k 当当m很大时，很大时，1 第29页/共65页 31 2、以（7，4）汉明码为例来说

23、明编码原理 设码字为设码字为a6 a5 a4a3 a2 a1 a0， u信息码元信息码元a6 、a5 、a4、a3来源于待编码的信息序列；来源于待编码的信息序列； u监督码元监督码元 a2 、a1、 a0的取值应根据信息码元按监督的取值应根据信息码元按监督 关系式来决定关系式来决定 Fa6+a5+a4+a2= 0 Fa6+a5+a3+a1= 0 Fa6+a4+a3+a0= 0 Fa2 = a4+a5+a6 Fa1 = a3+a5+a6 Fa0 = a3+a4+a6 （8-3） 每个方程分别为某一个监督码元的奇偶校验方程。 通常称这几个线性方程为对应码的一致监督关系式或一致校验方程 第30页/共

24、65页 32 信息位信息位 监督位监督位 信息位信息位 监督位监督位 a6a5a4a3a2a1a0a6a5a4a3a2a1a0 00000001000111 00010111001100 00101011010010 00111101011001 01001101100001 01011011101010 01100111110100 01110001111111 u给定信息位后，根据上式算出各监督位，该编码的所给定信息位后，根据上式算出各监督位，该编码的所 有码组如下表有码组如下表 第31页/共65页 33 （1）监督矩阵（奇偶校验矩阵）监督矩阵（奇偶校验矩阵） 1 a6+ 1 a5+ 1

25、a4 +0 a3+ 1 a2 + 0 a1+ 0 a0=0 1 a6+ 1 a5+ 0 a4 +1 a3+ 0 a2 + 1 a1+ 0 a0=0 1 a6+ 0 a5+ 1 a4 +1 a3+ 0 a2 + 0 a1+ 1 a0=0 Fa6+a5+a4+a2= 0 Fa6+a5+a3+a1= 0 Fa6+a4+a3+a0= 0 上式监督关系式上式监督关系式(8-3)可写成可写成 第32页/共65页 34 0 0 0 1001101 0101011 0010111 0 1 2 3 4 5 6 a a a a a a a 写成矩阵形式写成矩阵形式 可记为：可记为： HVT=0T 或或VHT=0

26、6543210 Va a a a a a a O0 0 0 第33页/共65页 35 r 1110100 H1101010 1011001 P I H称为线性码监督矩阵 v rn阶矩阵 v 监督矩阵H确定了编码时监督码元与信息码元的关系， 可由H和信息码元求出全部码组 v 把具有PIr形式的H矩阵称为典型形式的监督矩阵，其中P为r k阶矩阵, Ir为r r阶单位方阵 v H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关 监督矩阵特点监督矩阵特点: 第34页/共65页 36 (2)生成矩阵生成矩阵 对（7,4）线性码，由其一致监督方程式，再附加4个等式 Fa6 = a6 Fa5

27、 = a5 Fa4 = a4 Fa3= a3 Fa2 = a4+a5+a6 Fa1 = a3+a5+a6 Fa0 = a3+a4+a6 第35页/共65页 37 1101000 1010100 0110010 1110001 34560123456 aaaaaaaaaaa T kk 1000111 0100110 GI QI P 0010101 0001011 生生成成矩矩阵阵 第36页/共65页 38 vk n阶矩阵，编码方法完全由生成矩阵G确定 v把具有IkQ形式的G矩阵称为典型形式的生成矩阵，其中，Ik为kk阶单位方阵，Q为k r阶矩阵 vV可看成是G矩阵的各行的线性组合，为保证不同的信

28、息分组对应不同的码字，G矩阵各行应线性无关 生成矩阵特点：生成矩阵特点： 6543 VaaaaG 第37页/共65页 39 3、线性分组码伴随式（或校验子）、线性分组码伴随式（或校验子） 监督关系式监督关系式 HVT=0T 或或VHT=0 码字是码字是由由H矩阵所确定的线性方程组的解，所以可以由矩阵所确定的线性方程组的解，所以可以由H 矩阵来检验接收的序列是否为码字矩阵来检验接收的序列是否为码字 若接收到码字若接收到码字R=V+E，E为为错误矢量（或错误图样）错误矢量（或错误图样） 计算计算 SRHT=(V+E)HT =VHT+EHT=EHT 当S0表明没错，此时E0；否则，S不为0，表明有错

29、， E也不为0。 S称为校验子（伴随式） 第38页/共65页 40 v任意两个许用码组任意两个许用码组模模2 2和和仍为一许用码组，即具有仍为一许用码组，即具有封封 闭性。闭性。 v两码组之间的距离是另一码组的重量，最小码距两码组之间的距离是另一码组的重量，最小码距=非非 零码的最小码重零码的最小码重(1的个数）的个数） 4、线性分组码最小码距及性质、线性分组码最小码距及性质 )(min),(min minji ji ji ji VVWVVdd 许用码字许用码字 )(min 0 mini V VWd i 第39页/共65页 41 1101000 1010100 0110010 1110001

30、设（设（7,47,4）线性码的生成矩阵）线性码的生成矩阵G G为：为： 当信息位为当信息位为00010001时，时， （1 1）试求其后的监督位。）试求其后的监督位。 （2 2）监督矩阵）监督矩阵H 第40页/共65页 42 6543 AaaaaG 解：解： （1） 1000111 0100110 A0 0 0 10 0 0 1 0 1 1 0010101 0001011 第41页/共65页 43 （2）监督矩阵H 根据生成矩阵和监督矩阵的关系： G= IkQ，H=PIr 其中P=QT，可得监督矩阵H为： 1001101 0101011 0010111 第42页/共65页 44 8.48.4循

31、环码循环码 一、循环码的编码原理一、循环码的编码原理 循环码是一种重要的线性分组码，是在代数学基础上建立起来的，编码和解码设备都不太复杂，且有较强的检（纠）错能力。 特点：特点： v 封闭性封闭性 v 循环性循环性：即码中任一码组循环一位：即码中任一码组循环一位( (将最右端的码元移将最右端的码元移 到左端或反之）以后，仍为该码中的一个码组。到左端或反之）以后，仍为该码中的一个码组。 第43页/共65页 45 若(vn-1,vn-2,v1,v0)是一(n,k)循环码的码组，则 (vn-2 ,vn-3 ,v1,v0 ,vn-1) (vn-3 ,vn-4 , , v0 , vn-1 ,vn-2)

32、( v0 ,vn-1 , vn-2 ,vn-3 ,v2 ,v1) 也都是该循环码的码组。 1、码多项式、码多项式 设一个设一个(n,k) 线性分组码，其中的每个码字线性分组码，其中的每个码字V= (vn-1,vn-2, v1,v0)可用一个可用一个n-1 次多项式表示，即次多项式表示，即 V(x)= vn-1xn-1+ vn-2xn-2+ + v1x+ v0 第44页/共65页 46 如：对于（7，3）循环码的任意码组可表示为： V(x)= a6x6+ a5x5+ a4x4 + a3x3 + a2x2 + a1x+ a0 如码组（1100101）对应的码多项式可表示为 V(x)=1*x6+1*

33、x5+ 0*x4 + 0*x3 + 1*x2 + 0*x+1 = x6 + x5 + x2 +1 码多项式与码字的关系：码多项式与码字的关系： 本质上是一回事，仅是表示方法的不同而已。本质上是一回事，仅是表示方法的不同而已。x x仅是码仅是码 元位置的标志。并不关心元位置的标志。并不关心x x的取值。的取值。 第45页/共65页 47 序号 码字 序号 码字 信息位 a6 a5 a4 监督位 a3 a2 a1 a0 信息位 a6 a5 a4 监督位 a3 a2 a1 a0 1000 0000 51001011 2 001011161011100 3 010 1110 7 1100101 4 0

34、11100181110010 一种（7，3）循环码的全部码字 第46页/共65页 48 若一个整数若一个整数m m可以表示为可以表示为: : 是整数Qnp n p Q n m 则有则有mpmp（模（模n n），同样对于多项式而言），同样对于多项式而言： xN xR xQ xN xF 则可以写为：则可以写为：F(x)R(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) 第47页/共65页 49

35、 例如码组（1100101）对应的码多项式可为： V7(x)=x6+x5+x2+1 其被x2+1除得 x6+x5+x2+1x+1（模x2+1） 重要结论 在循环码中，若V(x)是一个长为n的许用码组， Vi(x)为V(x)码组向左循环移位i次的结果， 也是一许用码组，则xi V(x)在按模xn+1运算 下，也是一许用码组。即 xi V(x)Vi(x) （模xn+1） 第48页/共65页 50 例如： 1 1 7235 35892563 7 3 xxxxx xxxxxxxxxAx 模 其对应的码组为0101110，它正是表5-10中第3码字。 结论：一个码长为n的(n，k)循环码，它必 为按模x

36、n+1运算的一个余式。 第49页/共65页 51 2、循环码的生成多项式与生成矩阵、循环码的生成多项式与生成矩阵 v 循环码完全由其码组长度n和生成多项式 g(x)所决定 v 问题：寻找构成生成矩阵的k个线性无关 的许用码组 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-1 n-k-1g gn-k-2n-k-2 g g2 2 g g1 11) 1) 第50页/共65页 52

37、 v其对应的码多项式为其对应的码多项式为g(x)g(x)，且，且 g(x)g(x)一定是码一定是码 中唯一的一个中唯一的一个n-kn-k次多项式，这唯一的次多项式，这唯一的n-kn-k次多次多 项式项式g(x)g(x)称为码的生成多项式称为码的生成多项式 可以证明生成多项式g(x)具有以下特性： （1） g(x)是一个常数项为1的 次多项式； （2） g(x)是 的一个因式； （3）该循环码中其它码多项式都是g(x)的倍式 。 g(x)， xg(x) ， xk-1g(x) knr 1 n x 第51页/共65页 53 g(x)g(x)， ， x xk-1 k-1g(x) g(x)都是许用码组，

38、连同都是许用码组，连同 g(x)g(x)共共k k个许用码组，构成个许用码组，构成码的生成矩阵码的生成矩阵G(x)G(x) )( )( )( )( )( 2 1 xg xxg xgx xgx XG k k 注：该生成矩阵并不是典型形式的，但可通 过线性变换变换成典型的生成矩阵。 第52页/共65页 54 一旦生成多项式一旦生成多项式g(x)g(x)确定以后，该循环码的生确定以后，该循环码的生 成矩阵成矩阵G(x)G(x)就可以确定，进而该循环码的所有就可以确定，进而该循环码的所有 码字就可以确定。生成矩阵码字就可以确定。生成矩阵G(x)G(x)的每一行都是的每一行都是 一个码组。一个码组。 例

39、例 试求（试求（7 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次因式。次因式。 第53页/共65页 55 解2：对（7,3）循环码，n=7，k=3, r=4 n第一步：对x7+1进行因式分解得： x7+1=(x+1)(x3+x2+1)(x3+x+1).(1) n第二步：构造r=n-k次生成多项式g(x)。 要从式

40、（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 第54页/共65页 56 生成矩阵为： 1110100 0111010 0011101 1)( )( )( )( 24 235 23462 G xxx xxxx xxxx xg xxg xgx XG 将第1行与第3行模2加作为第1行，则有 1110100 0111010 1101001 G 为典型生 成矩阵 第55页/共65页 57 若按(b)构

41、成生成多项式: 生成多项式为：g(x)=x4+x3+x2+1 生成矩阵为： 1011100 0101110 0010111 1)( )( )( )( 234 345 24562 G xxx xxxx xxxx xg xxg xgx XG 进行线性变换，得典型生成矩阵为： 1011100 1110010 0111001 G 第56页/共65页 58 3、循环码的监督多项式与监督矩阵、循环码的监督多项式与监督矩阵 其中是逆多项式 1、方法、方法1 ： 第57页/共65页 59 方法方法2： 根据生成矩阵和监督矩阵的关系求： G=IkQ，H=PIr 其中P=QT 例例试求（试求（7，3）循环码的监督多项式和监督矩阵。）循环码的监督多项式和监督矩阵。 已知生成多项式已知生成多项式g(x)=x4+x3+x2+1 第58页/共6