信息论与编码第6章(3)

1、第第6 6章章 信道编码信道编码 2022-7-31信道编码信道编码 第第6 6章章第第6 6章章 信道编码信道编码 2022-7-326.16.1 有扰离散信道的编码理论有扰离散信道的编码理论6.26.2 纠错编译码的基本原理与分析方法纠错编译码的基本原理与分析方法6.3 6.3 线性分组码线性分组码6.4 6.4 卷积码卷积码6.56.5 其它信道编码其它信道编码内容第第6 6章章 信道编码信道编码 2022-7-336.3 线性分组码线性分组码 6.3.1 线性分组码的生成矩阵和校验矩阵线性分组码的生成矩阵和校验矩阵 6.3.2 伴随式与标准阵列译码伴随式与标准阵列译码 6.3.3 码距

2、码距,纠错码纠错码,MDC码等码等 6.3.4 完备码完备码 6.3.5 循环码循环码,BCH和和RS码码 6.3.6 分组码的扩展分组码的扩展,缩短和缩短和CRC第第6 6章章 信道编码信道编码 2022-7-346.3 线性分组码线性分组码(n,k)分组码是把信息流分割成一串前后独立的分组码是把信息流分割成一串前后独立的k比特信息组，比特信息组，再将每组信息元映射成再将每组信息元映射成n个码元组成的码字。如下图：个码元组成的码字。如下图：m0 m1 m2 mk-1 m0 m1 m2. mk-1 m0 m1 m2 mk-1 . C0C1C3.Cn-1 C0C1C3.Cn-1 C0C1C3.C

3、n-1 K个信息元可以写成矢量个信息元可以写成矢量(mk-1,.m1,m0)或者矩阵的形式或者矩阵的形式mk-1,.m1,m0。同样码字可以表示为同样码字可以表示为(Cn-1,.C1,C0)或者或者Cn-1,.C1,C0第第6 6章章 信道编码信道编码 2022-7-35线性分组码中，必须考虑的问题：线性分组码中，必须考虑的问题：（1）码集）码集C能否构成能否构成n维维n重矢量空间的一个重矢量空间的一个k维维n重子空间重子空间。（2）如何寻找）如何寻找最佳的码空间最佳的码空间。（3）qk个信息元组以怎样的算法一一映射到码空间。个信息元组以怎样的算法一一映射到码空间。码率码率对于对于二元二元分组

4、码分组码(n,k),其码率定义为：其码率定义为：RC=k/n对于对于q元元分组码分组码(n,k),其码率定义为：其码率定义为： RC=klbq/n 消息消息m (n , k) 码字码字c m=(mk-1,m1,m0) 分组编码器分组编码器 c=(cn-1,c1,c0) qk qn第第6 6章章 信道编码信道编码 2022-7-366.3.1生成矩阵和校验矩阵生成矩阵和校验矩阵 线性分组码的码空间线性分组码的码空间C 是由是由 k 个线性无关的基底个线性无关的基底 gk-1 g1 ，g0 张成的张成的k维维n重子空间，所有码字都可写成重子空间，所有码字都可写成k个基底的线性组合，个基底的线性组合

5、，即即c = mk-1 gk-1+ m1 g1+m0 g0 =mG(1)(1)(1)1(1)012101(1)11100(1)0100.,.,.knkkTkknngggGggg ggggggg 由于由于k个基底即个基底即G的的k个行矢量线性无关，矩阵个行矢量线性无关，矩阵G的秩一的秩一定等于定等于k。当信息元确定后，码字仅由。当信息元确定后，码字仅由G矩阵决定，因此我矩阵决定，因此我们称这们称这kn 矩阵矩阵G为该为该(n,k)线性分组码的线性分组码的生成矩阵生成矩阵。 第第6 6章章 信道编码信道编码 2022-7-37生成矩阵生成矩阵G(kn)的特点的特点 想要保证想要保证 (n,k)线性

6、分组码能够构成线性分组码能够构成k维维n重子空间，重子空间，G 的的k个行矢量个行矢量gk-1, g1, g0必须是线性无关的，只有这样才符必须是线性无关的，只有这样才符合作为基底的条件。合作为基底的条件。 由于基底不是唯一的，所以由于基底不是唯一的，所以G也就不是唯一的。也就不是唯一的。 不同的基底有可能生成同一码集，但因编码涉及码集和映不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的射两个因素，码集一样而映射方法不同也不能说是同样的码。码。 第第6 6章章 信道编码信道编码 2022-7-38系统形式的生成矩阵系统形式的生成矩阵 (n,k

7、)码的任何生成矩阵都可以通过码的任何生成矩阵都可以通过行运算行运算（不改变码集，只（不改变码集，只改变映射规则）简化成改变映射规则）简化成“系统形式系统形式” 。G = Ik P =(1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp 前前k位由单位矩阵位由单位矩阵Ik决定，等于把信息组决定，等于把信息组m原封不动搬到码字的前原封不动搬到码字的前k位；其余的位；其余的n-k位叫冗余位或位叫冗余位或一致校验位一致校验位，是前，是前k个信息位的线个信息位的线性组合。这样生成的（性组合。这样生成的（n,k）码叫做）码叫做系统码系统

8、码。 若生成矩阵若生成矩阵G不具备系统形式，则生成的码叫做不具备系统形式，则生成的码叫做非系统码非系统码。 系统化不改变码集，只是改变了映射规则。系统化不改变码集，只是改变了映射规则。 第第6 6章章 信道编码信道编码 2022-7-39空间构成空间构成 n维维n重空间有相互重空间有相互正交的正交的n个基底个基底 选择选择k个基底构成个基底构成码空间码空间C 选择另外的选择另外的(n-k)个个基底构成空间基底构成空间D C和和D是对偶的是对偶的 n维维n重空间重空间V k维维k重重 k维维n重重 n-k维维 信息组信息组 码空间码空间 n重重H 空间空间m C第第6 6章章 信道编码信道编码

9、2022-7-310校验矩阵校验矩阵 将将D空间的空间的n-k个基底排列起来可构成一个个基底排列起来可构成一个(n-k)n矩阵，矩阵，称为称为校验矩阵校验矩阵H。用来校验接收到的码字是否是正确的；。用来校验接收到的码字是否是正确的；即：若即：若c为为码空间为为码空间C中的任意码字，则中的任意码字，则 若不满足此等式，则若不满足此等式，则c必定不是码空间必定不是码空间C中的码字。中的码字。0TcH G是是(n,k)码的生成矩阵，码的生成矩阵，H是它的校验矩阵；是它的校验矩阵； H是是(n,n-k)对偶码的生成矩阵，它的每一行是一个基底。对偶码的生成矩阵，它的每一行是一个基底。 G则是它的校验矩阵

10、。则是它的校验矩阵。 GHT=0 ，H PT In-k ，二进制时，负号可省略。，二进制时，负号可省略。如果系统码的生成矩阵为如果系统码的生成矩阵为G=IKP,则其对应校验矩阵为则其对应校验矩阵为H=-PTIn-k第第6 6章章 信道编码信道编码 2022-7-31121010121022032415062100123456210,101110011100100111001,101110011100100111001) 3 , 7(mmcmmcmmmcmmcmcmcmcmmmcccccccCmmmmG，则有如果信息位为为线性分组码的生成矩阵已知第第6 6章章 信道编码信道编码 2022-7-3

11、1236464326546542165651054540000,0cccccccccccccccccccccccccc由前面的等式可以得到：，即，即，即，即如果写成矩阵的形式便为：6543210101100001110100001100010001100010Tccccccc 第第6 6章章 信道编码信道编码 2022-7-3136.3.2 伴随式与标准阵列译码伴随式与标准阵列译码 m C=(cn-1,c1,c0) R=(rn-1,r1,r0) (n,k) 信道信道定义定义差错图案差错图案E(en1,e1,e0) RC (rn-1cn-1,r1c1,r0c0) 因为因为CHT = 0 , 所以

12、所以RHT(CE)HTCHTEHT= EHT 在在HT固定的前提下，固定的前提下，RHT仅仅与差错图案仅仅与差错图案E有关，而与发送码有关，而与发送码C无关。定义无关。定义伴随式伴随式S S = (sn-k-1,s1,s0) = RHT = EHT 从物理意义上看，伴随式从物理意义上看，伴随式S并不反映发送的码字是什么，而只是并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。反映信道对码字造成怎样的干扰。 差错图案差错图案E是是n重矢量，共有重矢量，共有2n个可能的组合，而伴随式个可能的组合，而伴随式S是是(n-k)重矢量，只有重矢量，只有2n-k个可能的组合，因此不同的差错图案可

13、能有相个可能的组合，因此不同的差错图案可能有相同的伴随式。同的伴随式。第第6 6章章 信道编码信道编码 2022-7-314差错图案差错图案E的求解的求解(1) 可以通过解线性方程求解可以通过解线性方程求解E：S = (sn-k-1,s1, s0) = EHT = (en-1, e1,e0)得到线性方程组：得到线性方程组：sn-k-1=en-1h(n-k-1)(n-1)+e1h(n-k-1)1+ e0 h(n-k-1)0 s1 = en-1h1(n-1) + + e1 h11 + e0 h10s0 = en-1h0(n-1) + + e1 h01 + e0 h00(1)(1)(1)1(1)01

14、(1)11100(1)0100Tn knn kn knnhhhhhhhhh 第第6 6章章 信道编码信道编码 2022-7-315 上述方程组中有上述方程组中有n个未知数个未知数en1, e1,e0 ，却只有，却只有n-k个个方程，可知方程组有多解。方程，可知方程组有多解。 在有理数或实数域中，少一个方程就可能导致无限多在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致两个解，少两个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少个方程四个解，以此类推，少n-( n-k) = k个方程导致个方程导致每个未知数有每个未知数有2k个解。个解。 概

15、率译码：概率译码：把所有把所有2k个解的重量个解的重量(差错图案差错图案E中中1的个的个数数)作比较，选择其中最轻者作为作比较，选择其中最轻者作为E的估值。该方法概的估值。该方法概念上很简单但计算效率不高。念上很简单但计算效率不高。差错图案差错图案E的求解的求解(2) 第第6 6章章 信道编码信道编码 2022-7-316标准阵列译码表标准阵列译码表 在伴随式在伴随式S的数目是有限的的数目是有限的2n-k个，如果个，如果n-k不太大不太大，我们可，我们可以预先把不同以预先把不同S下的方程组解出来，把各种情况下的最大概下的方程组解出来，把各种情况下的最大概率译码输出率译码输出列成一个码表列成一个

16、码表。这样，在实时译码时就不必再。这样，在实时译码时就不必再去解方程，而只要象查字典那样查一下码表就可以了。这去解方程，而只要象查字典那样查一下码表就可以了。这样构造的表格叫做样构造的表格叫做标准阵列译码表标准阵列译码表。 表中所列码字是接收到的码字表中所列码字是接收到的码字R； 将将没有任何差错没有任何差错时的收码时的收码R放在第一行，放在第一行，收码等于发码收码等于发码R=C(C Ci,i =0,1,2k-1), 差错图案为全零差错图案为全零E0=(0,00)，伴随，伴随式为全零式为全零S0=(0,00)。由于有。由于有2k个码字，码表有个码字，码表有2k列列。第第6 6章章 信道编码信道

17、编码 2022-7-317 在在第第2到第到第n+1的的n行中差错图案的所有行中差错图案的所有重量为重量为1 (共共n个个)。 如果如果(1+ n)t)01dte 第第6 6章章 信道编码信道编码 2022-7-327 设有设有8个码组个码组“000000”，“001110”，“010101”，011011，100011，101101，1101110，111000，试求它们的最小码距。若用，试求它们的最小码距。若用于检错，能检出几位错码？若用于纠错，能纠于检错，能检出几位错码？若用于纠错，能纠正几位错码？若纠检错结合，各能纠、检几位正几位错码？若纠检错结合，各能纠、检几位错码？错码？ 第第6

18、6章章 信道编码信道编码 2022-7-328 （n,k）线性码最小距离）线性码最小距离dmin的上边界是的上边界是n-k+1。如果。如果我们设计的（我们设计的（n,k）线性码的）线性码的dmin达到了达到了n-k+1，就是，就是达到了设计性能的极点。因此，达到了设计性能的极点。因此，dmin n-k+1的码称的码称为为极大最小距离码极大最小距离码 (MDC)。 (1) 二进制码中，除了将一位信息重复二进制码中，除了将一位信息重复n 次的次的 （n,1）码外，不存在其它二进制码外，不存在其它二进制MDC码；码； (2) 非二进制码中，非二进制码中，MDC码是存在的，如码是存在的，如RS码码 （

19、reed-solomon)。MDC码码（Maximized minimum Distance Code）第第6 6章章 信道编码信道编码 2022-7-329 纠错能力纠错能力t只是说明距离只是说明距离t的差错一定能纠，的差错一定能纠，并非说并非说距距离大于离大于t的差错一定不能纠。的差错一定不能纠。 总体的、平均的纠错能力不但与总体的、平均的纠错能力不但与最小距离最小距离有关，而且有关，而且与与其余码距其余码距或者说与码字的或者说与码字的重量分布特性重量分布特性有关。把码有关。把码距（码重）的分布特性称为距（码重）的分布特性称为距离（重量）谱距离（重量）谱，其中最，其中最小重量就是小重量就是

20、dmin。当所有码距相差不大时，性能较好。当所有码距相差不大时，性能较好。重量谱多项式表示：重量谱多项式表示： 含义：在码长含义：在码长n的码集里，包含重量为的码集里，包含重量为0的码字的码字A0个，个，重量为重量为1的码字的码字A1个，个，-，重量为，重量为n的码字的码字An个。个。 20121nniniiA xAAxA xA xAx重量谱重量谱第第6 6章章 信道编码信道编码 2022-7-330 任何一个二元任何一个二元(n,k)线性分组码都有线性分组码都有2n-k个伴随式，假如个伴随式，假如该码的纠错能力是该码的纠错能力是t，则对于任何一个重量小于等于，则对于任何一个重量小于等于t的的

21、差错图案，都应有一个伴随式与之对应，也就是说，差错图案，都应有一个伴随式与之对应，也就是说，伴随式的数目满足条件伴随式的数目满足条件 上式称作上式称作汉明限汉明限，任何一个纠，任何一个纠t码都应满足上述码都应满足上述条件。条件。 02012tnkinnnnnti6.3.4完备码完备码(Perfect code) 第第6 6章章 信道编码信道编码 2022-7-331完备码完备码 某二元某二元(n,k)线性分组码能使等式线性分组码能使等式 成立，即该码的伴随式数目成立，即该码的伴随式数目不多不少恰好和不大于不多不少恰好和不大于t个差错的图案数目相等个差错的图案数目相等，相当于在标准译码阵列中能，

22、相当于在标准译码阵列中能将所有重量不大于将所有重量不大于t的的差错图案差错图案选作选作陪集首陪集首，而没有一，而没有一个陪集首的重量大于个陪集首的重量大于t，这时的校验位得到最充分的利，这时的校验位得到最充分的利用。这样的二元用。这样的二元(n,k)线性分组码称为线性分组码称为完备码完备码。 02tnkini第第6 6章章 信道编码信道编码 2022-7-332汉明码汉明码(Hamming Code) 汉明码的汉明码的纠错能力纠错能力t = 1，既有二进制的，也有非二进，既有二进制的，也有非二进制的。二进制时，汉明码码长制的。二进制时，汉明码码长n和信息位和信息位k服从以下规服从以下规律：律：

23、(n,k)=(2m-1, 2m-1-m)，其中其中m= n-k，是正整数。，是正整数。 当当m3、4、5、6、7、8时，有汉明码时，有汉明码(7,4)、(15,11)、(31,26)、(63,57)、(127,120) 汉明码是完备码汉明码是完备码，因为它满足上述等式。，因为它满足上述等式。1011(21)22mmnkinni第第6 6章章 信道编码信道编码 2022-7-333汉明码校验矩阵的构成汉明码校验矩阵的构成 汉明码的校验矩阵汉明码的校验矩阵H具有特殊的性质，能使具有特殊的性质，能使构造方法简化。一个构造方法简化。一个(n,k)码的校验矩阵有码的校验矩阵有nk行和行和n列，二进制时列

24、，二进制时n-k个码元所能组成的列矢个码元所能组成的列矢量总数是量总数是2n-k-1 =2m-1= n, 恰好和校验矩阵的恰好和校验矩阵的列列数相等数相等。只要排列所有列，通过。只要排列所有列，通过列置换列置换将矩阵将矩阵H转换成转换成系统形式系统形式，就可以进一步得到相应的，就可以进一步得到相应的生成矩阵生成矩阵G。 第第6 6章章 信道编码信道编码 2022-7-334例例 6.4 构造一个构造一个m=3的二元的二元(7，4)汉明码。汉明码。解：先利用汉明码的特性构造一个解：先利用汉明码的特性构造一个(7，4)汉明码的汉明码的校验矩阵校验矩阵H，再通过列置换将它变为系统形式：，再通过列置换

25、将它变为系统形式： 0 0 0 1 1 1 1 列置换列置换 1 1 1 0 1 0 0 H = 0 1 1 0 0 1 1 0 1 1 1 0 1 0 = PT I3 1 0 1 0 1 0 1 1 1 0 1 0 0 1再得生成矩阵再得生成矩阵G为为 1 0 0 0 1 0 1 G = I4 P = 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 第第6 6章章 信道编码信道编码 2022-7-335高莱（高莱（Golay）码）码 二进制（二进制（23，12）线性码）线性码，其最小距离，其最小距离dmin7，纠，纠错能力错能力t =3。 是完备码，因为满

26、足等式是完备码，因为满足等式 223-12 = 2048 = 在在(23,12)码上添加一位奇偶位即得二进制线性（码上添加一位奇偶位即得二进制线性（24，12）扩展高莱码扩展高莱码，其最小距离，其最小距离dmin8。 2323231123第第6 6章章 信道编码信道编码 2022-7-3366.3.5 6.3.5 循循 环环 码码 1 循环码的概念循环码的概念循环码是循环码是1957年由普兰奇年由普兰奇(Prange)提出的。它是线性分组码中提出的。它是线性分组码中最重要的一个子类。目前，实用差错控制编码中所使用的线性分最重要的一个子类。目前，实用差错控制编码中所使用的线性分组码几乎都是循环码

27、或循环码的子类。组码几乎都是循环码或循环码的子类。 循环码除了具有循环码除了具有(n,k)线性分组码的一般性质外，还具有线性分组码的一般性质外，还具有循环循环性性，即若将其任意一个码字，即若将其任意一个码字(cn-1,cn-2,c1,c0)的码元的码元向右或向左循环向右或向左循环移一位移一位，所得的，所得的(c0,cn-1,cn-2,c1)或或(cn-2,c1,c0,cn-1)仍然是码字。仍然是码字。第第6 6章章 信道编码信道编码 2022-7-337表表 6-3-1（7， 3）循环码）循环码 第第6 6章章 信道编码信道编码 2022-7-3382 2 循环码的码多项循环码的码多项式式在整

28、数运算中，有模在整数运算中，有模n运算。例如，在模运算。例如，在模2运算中运算中1+1=20 (模模2)， 1+2=31 (模模2)， =60 (模模2) 对于整数对于整数m进行模进行模n运算运算, 有有 )(npnpQnm模式中，式中，Q为整数，为整数，pn。这说明：在模。这说明：在模n运算下，一个整数运算下，一个整数m等等于它被于它被n除得的余数。例如，在模除得的余数。例如，在模3运算中，运算中，7/3=2+1/31 (模模3)。 对码多项式也可以按模运算。若任意一个多项式对码多项式也可以按模运算。若任意一个多项式F(x)被一个被一个n次多项式次多项式N(x)除，得到商式除，得到商式Q(x

29、)和一个次数小于和一个次数小于n的余式的余式R(x)， 即即 第第6 6章章 信道编码信道编码 2022-7-339F(x)=N(x)Q(x)+R(x) 则在按模则在按模N(x)运算下，有运算下，有 )()(xRxF(模N(x) 此时，码多项式系数仍按模此时，码多项式系数仍按模2运算，系数只取运算，系数只取0和和1。例如。例如F(x)=x4+x2+1被被N(x)=x3+1除，得到余式除，得到余式R(x)=x2+x+1，即，即x4+x2+1 x2+x+1（模（模(x3+1)。 xxxxx424311x12 xx第第6 6章章 信道编码信道编码 2022-7-340 在在(n, k)循环码中，循环

30、码中， 若若C(x)是一个长度为是一个长度为n的码字，则的码字，则xiC(x)在按模在按模(xn+1)运算下，也是该循环码中的一个码字。运算下，也是该循环码中的一个码字。 即若即若 xiC(x)=Q(x)(xn+1)+C(x)C(x) (模模(xn+1) 则则C(x)也是该循环码中的一个码组。其中，也是该循环码中的一个码组。其中，i为码字左移的位数，为码字左移的位数，Q(x)为为xiC(x)除以除以xn+1的商式，的商式，C(x)为为xiC(x)被被xn+1除得的余式。除得的余式。 例如码字例如码字(1101001)， 若将此码字左移两位，若将此码字左移两位， 可得到可得到 x2(x6+x5+

31、x3+1)=(x+1)(x7+1)+x5+x2+x+1 即即Q(x)=x+1；C(x)=x5+x2+x+1，对应的码字为，对应的码字为(0100111)，与直接，与直接对码字进行循环左移两位的结果相同。对码字进行循环左移两位的结果相同。 第第6 6章章 信道编码信道编码 2022-7-3413 循环码的生成多项式和生成矩阵循环码的生成多项式和生成矩阵1） 循环码的生成多项式循环码的生成多项式如果一种码的所有码多项式都是多项式如果一种码的所有码多项式都是多项式g(x)的倍式，则称的倍式，则称g(x)为该码的生成多项式为该码的生成多项式。循环码的码多项式都是最低次码多项式。循环码的码多项式都是最低

32、次码多项式g(x)的倍式。例如的倍式。例如表表6-3-1所示的所示的(7，3)循环码中，生成多项式循环码中，生成多项式g(x)=x4+x3+x2+1。显然，循环码中次数最低的多项式。显然，循环码中次数最低的多项式(除全除全0码字外码字外)就是生成多项式就是生成多项式g(x)。 可以证明，可以证明，g(x)是常数项为是常数项为1的的r=(n-k)次多项式，是次多项式，是xn+1的一的一个因子。一旦确定了个因子。一旦确定了g(x)，则整个，则整个(n, k)循环码就被确定了。循环码就被确定了。 如何确定任意一个如何确定任意一个(n,k)循环码的生成多项式循环码的生成多项式g(x)?第第6 6章章

33、信道编码信道编码 2022-7-342例如，例如，(x7+1)可以分解为：可以分解为：x7+1=(x+1)(x3+x2+1)(x3+x+1)。为。为了求出了求出(7，3)循环码的生成多项式循环码的生成多项式g(x)，需要从中找到一个，需要从中找到一个r=nk=73=4次的因子。不难看出，次的因子。不难看出， 这样的因子有两个：这样的因子有两个： (x+1)(x3+x2+1)=x4+x2+x+1； (x+1)(x3+x+1)=x4+x3+x2+1。 这两个因子都可以作为生成多项式。这两个因子都可以作为生成多项式。 注意选用不同的生成多注意选用不同的生成多项式，所产生的循环码的码字不同。项式，所产

34、生的循环码的码字不同。 (n,k) 循环码的生成多项式满足下面三条性质：循环码的生成多项式满足下面三条性质： (1) g(x)是一个（是一个（nk）次多项式。）次多项式。 (2) g(x)的常数项不为的常数项不为0。 (3) g(x)是是xn+1的一个因子。的一个因子。 第第6 6章章 信道编码信道编码 2022-7-3432 2） 循环码的生成矩阵循环码的生成矩阵循环码的生成矩阵循环码的生成矩阵G常用多项式的形式来表示，即常用多项式的形式来表示，即 )()()()()(21xgxxgxgxxgxxGkk第第6 6章章 信道编码信道编码 2022-7-344例如例如表表6-3-1所示的所示的(

35、7，3)循环码，循环码，n=7,k=3, r=4，其生成，其生成多项式多项式g(x)=x4+x3+x2+1，可得，可得 1)()()()(23434524562xxxxxxxxxxxxgxxgxgxxG100010101110111011001G即 110011111101100010001G 第第6 6章章 信道编码信道编码 2022-7-3454 4 循环码的校验（监督）多项式和校验（监督）矩阵循环码的校验（监督）多项式和校验（监督）矩阵1 1） 循环码的监督多项式循环码的监督多项式由于由于g(x)能除尽能除尽xn+1，因此有，因此有 )(1)(xgxxhn其中，其中，g(x)是常数项为是

36、常数项为1的的r次生成多项式次生成多项式；h(x)是常数项为是常数项为1的的k次次多项式多项式，称为，称为监督多项式监督多项式。令。令h(x)=xk+hk-1xk-1+h1x+1，h(x)的的逆多项式逆多项式h*(x)=xk+h1xk-1+h2xk-2+hk-1x+1（ h*(x)= xkh(1/x)）。例如例如(7，3)循环码中，循环码中，g(x)=x4+x3+x2+1，则，则 1)(1)(1)(3*237xxxhxxxgxxh第第6 6章章 信道编码信道编码 2022-7-3462 2）循环码的监督矩阵）循环码的监督矩阵由监督多项式很容易得到循环码的监督矩阵，由监督多项式很容易得到循环码的

37、监督矩阵， 即即 )()()()(*1xhxxhxhxxHkn例如可得例如可得(7， 3)循环码的监督矩阵为循环码的监督矩阵为 1)()()()()(324235346*2*3xxxxxxxxxxxxhxxhxhxxhxxH1 0 1 1 0 0 00 1 0 1 1 0 00 0 1 0 1 1 00 0 0 1 0 1 1H 第第6 6章章 信道编码信道编码 2022-7-347 【例例】 已知（已知（7，4）循环码的全部码组为）循环码的全部码组为0000000， 0100111，1000101，1100010，0001011，0101100， 1001110， 1101001，00101

38、10，0110001，1010011， 1110100， 0011101， 0111010，1011000，1111111。试求该循环码的生成多项式、。试求该循环码的生成多项式、 生成矩阵和监生成矩阵和监督矩阵。督矩阵。 解解 （1） 求生成多项式求生成多项式g(x)。已知。已知 n=7，k=4， r=nk=74=3x7+1=(x+1)(x3+x+1)(x3+x2+1) 因为生成多项式因为生成多项式g(x)必须满足：必须满足： 是一个是一个nk=3次多项式，其次多项式，其常数项不为常数项不为0，是，是x7+1的一个因子，显然满足上述条件的因子有的一个因子，显然满足上述条件的因子有两个两个: x

39、3+x+1和和x3+x2+1。由于本题给出了循环码的全部码字，因。由于本题给出了循环码的全部码字，因此符合本题条件的生成多项式此符合本题条件的生成多项式g(x)只有一个，假定只有一个，假定g(x)=x3+x+1。 第第6 6章章 信道编码信道编码 2022-7-348（2） 求生成矩阵求生成矩阵G。 1)()()()()(32423534623xxxxxxxxxxxxgxxgxgxxgxxG0001011001011001011001011000G0001011001011001001111000101QIGk 第第6 6章章 信道编码信道编码 2022-7-349经检验，由经检验，由g(x)

40、=x3+x+1得到的生成矩阵得到的生成矩阵G能产生本题所给能产生本题所给定的全部生成码字。而定的全部生成码字。而g(x)=x3+x2+1所生成的循环码与本题所所生成的循环码与本题所给的码组不符。给的码组不符。 （3） 求监督矩阵。求监督矩阵。 110100101110101110100)(,110101111110,011110111101TrIPHQPQ第第6 6章章 信道编码信道编码 2022-7-350例例 6.5 研究一个长度研究一个长度n=7的循环码的构成方法的循环码的构成方法(1) 对对(x7+1)作分解，找出作分解，找出n-k次因式。次因式。 x7+1(x+1)(x3+x2+1)

41、(x3+x+1)， n-k 因式因式g(x) 对偶式对偶式h(x) 循环码循环码 1 (x+1) (x3+x2+1)(x3+x+1) (7,6) 3 (x3+x2+1) (x+1)(x3+x+1) (7,4) 3 (x3+x+1) (x+1)(x3+x2+1) (7,4) 4 (x+1)( x3+x2+1) (x3+x+1) (7,3) 4 (x+1)(x3+x+1) (x3+x2+1) (7,3) 6 (x3+x2+1)(x3+x+1) (x+1) (7,1)第第6 6章章 信道编码信道编码 2022-7-351(2) 构成构成(7,3)循环码：循环码：选选g(x) =(x+1) (x3+x

42、+1) = (x4+x3+x2+1)，则，则C(x)=m(x)g(x)= (m2x2+m1x+m0) (x4+x3+x2+1)。 当输入信息当输入信息m=(011)时，时，m(x)=(x+1)，C(x)=( x+ 1)(x4x3x21) = x5+ x2+ x1+ 1，对应码矢对应码矢C = (0100111)。 例例 6.5 研究一个长度研究一个长度n=7的循环码的构成方法的循环码的构成方法第第6 6章章 信道编码信道编码 2022-7-352信息矢量信息矢量m(m2 m1 m0) 码矢码矢C(c6c5c4c3c2c1c0) 000001010011100101110111000000000

43、11101011101001001111110100110100110011101010011例例 6.5 研究一个长度研究一个长度n=7的循环码的构成方法的循环码的构成方法第第6 6章章 信道编码信道编码 2022-7-3535 循环码的系统化编码方法循环码的系统化编码方法循环码编码时，首先要根据给定的循环码编码时，首先要根据给定的(n,k)值来选定生成多项式值来选定生成多项式g(x)，即从，即从(xn+1)的因式中选定一个的因式中选定一个r=nk次多项式作为次多项式作为g(x)。 根根据据循环码中的所有码多项式都可被循环码中的所有码多项式都可被g(x)整除整除这条原则，就可以对这条原则，就

44、可以对给定的信息码元进行编码。假设编码前的给定的信息码元进行编码。假设编码前的信息码多项式为信息码多项式为m(x)，其次数小于其次数小于k。用。用xr乘以乘以m(x)，得到，得到xrm(x)的次数小于的次数小于n。 用用xrm(x) 除以除以g(x) ，得到，得到余式余式R(x), R(x)次数必小于次数必小于g(x)的次数，即小于的次数，即小于(nk)。将此余数。将此余数R(x)加在信息码元之后作为加在信息码元之后作为监督位监督位，即将，即将R(x)与与xrm(x)相加，得到的多项式必为相加，得到的多项式必为码多项式码多项式。因为它必能被。因为它必能被g(x)整除，整除，且最高次数不大于且最

45、高次数不大于(n-1)。因此，循环码的码多项式为。因此，循环码的码多项式为 )()()(xRxmxxCr第第6 6章章 信道编码信道编码 2022-7-354循环码的编码方法可归纳如下：循环码的编码方法可归纳如下： (1) 用用xr乘以乘以m(x)。该运算的作用是在信息码元后附加上该运算的作用是在信息码元后附加上r个个“0”。例如在。例如在(7，3)码中信息码组为码中信息码组为(110)，它可以写成，它可以写成m(x)=x2+x；由于由于r=nk=73=4，所以，所以xrm(x)=x4(x2+x)=x6+x5，它表示码组，它表示码组1100000，即信息码元后附加四个，即信息码元后附加四个“0

46、”。 (2) 用用xrm(x) 除以除以g(x) ， 得到商得到商Q(x)和余式和余式R(x)， 即即 )()()()()(xgxRxQxgxmxr第第6 6章章 信道编码信道编码 2022-7-355若选定若选定g(x)=x4+x2+x+1，则有，则有 11) 1(1)()(24222456xxxxxxxxxxxxgxmxr即即Q(x)=x2+x+1，R(x)=x2+1。 上式等效于上式等效于 10111101111101111100000 (3) 编码器输出的码字为编码器输出的码字为 C(x)=xrm(x)+R(x)=1100000+101=1100101第第6 6章章 信道编码信道编码

47、2022-7-3566 循环码的译码方法循环码的译码方法1. 循环码的检错循环码的检错由于任一码多项式由于任一码多项式C(x)都应能被生成多项式都应能被生成多项式g(x)整除，整除， 因此因此在 接 收 端 可 以 将 接 收 码 组在 接 收 端 可 以 将 接 收 码 组 B ( x ) 用 生 成 多 项 式 去 除 ， 即用 生 成 多 项 式 去 除 ， 即。当传输过程中没有发生差错时，。当传输过程中没有发生差错时， 接收码组与发送码组相同接收码组与发送码组相同(C(x)=B(x)， 即接收码组即接收码组B(x)必定能被必定能被g(x)整除，即整除，即R(x)=0。 当当传输过程中发

48、生差错时，传输过程中发生差错时，C(x)B(x)， B(x)除以除以g(x)时必定除不尽时必定除不尽而有余项，即而有余项，即R(x)0。 因此，可以用余项因此，可以用余项R(x)是否为零来判定码是否为零来判定码组中是否有差错。组中是否有差错。 )()()()()(xgxRxQxgxB第第6 6章章 信道编码信道编码 2022-7-357应当注意，当接收码组中的错误数量超出编码的检错能力应当注意，当接收码组中的错误数量超出编码的检错能力时，有错误的接收码组也可能被时，有错误的接收码组也可能被g(x)整除。此时，差错就无法整除。此时，差错就无法检出。这种错误称为不可检错码。检出。这种错误称为不可检

49、错码。 【 例例 】 已 知 （已 知 （ 1 5 ， 7 ） 循 环 码 的 生 成 多 项 式 为） 循 环 码 的 生 成 多 项 式 为g(x)=x8+x7+x6+x4+1，试问接收码组，试问接收码组B(x)=x+x5+x+1是否有误。是否有误。 解解 因为因为 01)(1111)()(36746783673564678514xxxxxRxxxxxxxxxxxxxxxxxxxgxB所以接收码所以接收码B(x)=x14+x5+x+1有误。有误。 第第6 6章章 信道编码信道编码 2022-7-3582. 循环码的纠错循环码的纠错在纠错时，译码方法比检错时复杂。为了能纠错，要求每个在纠错时

50、，译码方法比检错时复杂。为了能纠错，要求每个可纠正的错误图样必须与一个特定的余式有一一对应关系。可纠正的错误图样必须与一个特定的余式有一一对应关系。 只有只有这样才可能按此余式惟一地决定错误图样，从而纠正错误。这样才可能按此余式惟一地决定错误图样，从而纠正错误。 循环循环码的纠错译码方法如下：码的纠错译码方法如下： (1) 用生成多项式用生成多项式g(x)除以接收码组除以接收码组B(x)，得到余式，得到余式R(x)。 (2) 按照余式按照余式R(x)， 用查表方法或计算校正子得出错误图样用查表方法或计算校正子得出错误图样E(x)， 就可以确定错码的位置。就可以确定错码的位置。 (3) 从从B(

51、x)中减去中减去E(x)，便得到已经纠正错码的原发送码组，便得到已经纠正错码的原发送码组C(x)。 常用的常用的循环码译码循环码译码方法主要有梅吉特译码、方法主要有梅吉特译码、 捕错译码和大数捕错译码和大数逻辑译码等。逻辑译码等。 第第6 6章章 信道编码信道编码 2022-7-359BCH码码BCH码是一种非常重要的码是一种非常重要的循环码循环码，它在编码理论研究和实际，它在编码理论研究和实际应用上占有重要地位。应用上占有重要地位。BCH码的重要性体现在：码的重要性体现在： 它有严密的代数结构，是目前研究得它有严密的代数结构，是目前研究得最透彻最透彻的一类码；的一类码； 它的它的生成多项式生

52、成多项式g(x)与最小码距与最小码距d0之间有密切的关系，人们之间有密切的关系，人们能根据所要求的纠错能力能根据所要求的纠错能力(对对d0的要求的要求)，很容易地构造出，很容易地构造出BCH码；码； BCH编编/译码比较简单，易于实现，是线性分组中应用最为译码比较简单，易于实现，是线性分组中应用最为普遍的一类码。普遍的一类码。 第第6 6章章 信道编码信道编码 2022-7-360首先引入首先引入本原多项式本原多项式的概念。如果一个的概念。如果一个m次多项式次多项式F(x)满足满足以下条件：以下条件： (1) F(x)是既约多项式是既约多项式(即不能分解因式的多项式即不能分解因式的多项式)。(

53、2) F(x)可整除可整除(xp+1)，p=2m1。 (3) F(x)除不尽除不尽(xq+1)，qp。则称则称F(x)是一个最高次数为是一个最高次数为m的本原多项式。的本原多项式。 例如当例如当m=3时，时， x2m-1+1=x7+1，此时最高次为，此时最高次为3的本原多项式为的本原多项式为x3+x2+1和和x3+x+1， 它们都能整除它们都能整除x7+1，但不能整除，但不能整除x6+1，x5+1等。等。 BCH码可分为码可分为本原本原BCH码码和和非本原非本原BCH码码。本原本原BCH码是指码是指在生成多项式在生成多项式g(x)中，含有最高次数为中，含有最高次数为m的一个本原多项式，且码的一

54、个本原多项式，且码长长n=2m1。而而非本原非本原BCH码的生成多项式码的生成多项式g(x)中不含有这种本原中不含有这种本原多项式，且码长多项式，且码长n是是2m1的一个因子，即码长的一个因子，即码长n一定能除尽一定能除尽2m1。第第6 6章章 信道编码信道编码 2022-7-361BCH码的码长码的码长n、监督位、监督位r和纠错能力和纠错能力t之间的关系如下之间的关系如下： 对于任意整数对于任意整数m(m3)和和tm/2，一定存在一个二进制，一定存在一个二进制BCH码，码，其码长其码长n=2m1，监督位数，监督位数r=nkmt，并能纠正所有不大于，并能纠正所有不大于t的的随机错误。随机错误。

55、 为了便于应用，表为了便于应用，表6-3-2 给出了码长给出了码长n63的本原的本原BCH码，表码，表 6-3-3给出了码长给出了码长n73的非本原的非本原BCH码。其中码。其中g(x)栏下的数字是八进制栏下的数字是八进制数，用于表示生成多项式数，用于表示生成多项式g(x)中的各项系数值。例如表中的各项系数值。例如表6-3-2中，于中，于八进制数八进制数“23”对应的二进制码为对应的二进制码为“010011”，故生成多项式，故生成多项式g(x)=x4+x+1。 第第6 6章章 信道编码信道编码 2022-7-362表表 6-3-2n63的本原的本原BCH码码 第第6 6章章 信道编码信道编码

56、2022-7-363表表6-3-3 部分非本原部分非本原BCH码码 在实际应用中，如果要求在实际应用中，如果要求BCH码的码长不是码的码长不是2m-1或它的因或它的因子，子， 则可采用缩短码的方法来构造缩短则可采用缩短码的方法来构造缩短BCH码。码。 第第6 6章章 信道编码信道编码 2022-7-364RS码码RS码是里德码是里德-索洛蒙索洛蒙(Reed-Solomon)码的简称。它是一种多进码的简称。它是一种多进制制BCH码，具有很强的纠错能力，特别适合在衰落信道中纠正突发码，具有很强的纠错能力，特别适合在衰落信道中纠正突发错误。在错误。在(n,k)RS码中输入信号分成码中输入信号分成km

57、比特比特一组，每组包括一组，每组包括k个个符符号，号， 每个符号由每个符号由m比特比特组成。一个能纠正组成。一个能纠正t个个符号错误的符号错误的RS码，其码，其主要参数如下：主要参数如下： (1) 码长，码长，n=2m1符号或符号或n=m(2m1)个比特。个比特。 (2) 信息段，信息段， k个符号或个符号或mk个比特。个比特。 (3) 监督段，监督段，r=nk=2t个符号或个符号或m2t个比特。个比特。 (4) 最小码距，最小码距，d0=2t+1个符号或个符号或m(2t+1)个比特。个比特。 对于一个长度为对于一个长度为n=2m1符号的符号的RS码，每个符号都可以看成是码，每个符号都可以看成

58、是有限域有限域GF(2m)中的一个元素。对于最小码距为中的一个元素。对于最小码距为d0符号符号的的RS码，其码，其生成多项式为生成多项式为 第第6 6章章 信道编码信道编码 2022-7-365)()()(120dxxxxg其中，其中，i是是GF(2m)域元素，域元素，i=1, 2, ，d01。 例如，构造一个能纠正三个错误符号，码长为例如，构造一个能纠正三个错误符号，码长为15，m=4的的RS码，最小码距为码，最小码距为d0=2t+1=23+1=7个符号，监督段有个符号，监督段有r=2t=23=6个符号，信息段有个符号，信息段有k=nr=156=9个符号，即个符号，即(15，9)RS码。从二

59、码。从二进制的角度，这是一个进制的角度，这是一个(60， 36)码。码。 则知，其生成多项式为则知，其生成多项式为g(x) =(x+)(x+2)(x+3)(x+4)(x+5)(x+6)=x6+10 x5+14x4+4x3+6x2+9x+6 第第6 6章章 信道编码信道编码 2022-7-366RS码的编码过程与码的编码过程与BCH码的大体一样，同样可以用带反码的大体一样，同样可以用带反馈的移位寄存器来实现。不同之处有：馈的移位寄存器来实现。不同之处有： 移位寄存器为移位寄存器为m级并联工作；级并联工作； 每个反馈连接必须乘以生成多项式每个反馈连接必须乘以生成多项式g(x)中相应的系数。中相应的

60、系数。 RS的译码过程也与的译码过程也与BCH码的大体相同。不同的是：需要码的大体相同。不同的是：需要在找到错误位置后，求出错误值，这是因为在找到错误位置后，求出错误值，这是因为RS译码有译码有2m1种种可能的取值。可能的取值。 第第6 6章章 信道编码信道编码 2022-7-3676.3.7 扩展码扩展码 如果给每个码字添加一位奇偶校验位如果给每个码字添加一位奇偶校验位c校校，构成（，构成（n1，k）线性码，称为）线性码，称为扩展码扩展码。 cn-1, c1, c0 cn-1, c1, c0 , c校校 c n1 c1 c0 c 校校0 在二进制在二进制偶校验偶校验时：时： 原来码字中原来码