信息论与编码第八章 纠错编码

1、第八章第八章 纠错编码纠错编码白慧慧办公地址：9号教学楼北605Email: 手机容提要n一、纠错码的基本概念n二、纠错编码的代数基础n三、线性分组码n四、循环码n五、卷积码内容提要一、纠错码的基本概念一、纠错码的基本概念n二、纠错编码的代数基础n三、线性分组码n四、循环码n五、卷积码1.信道纠错编码一、纠错码的基本概念一、纠错码的基本概念2. 差错控制系统模型及分类一、纠错码的基本概念一、纠错码的基本概念2. 差错控制系统模型及分类一、纠错码的基本概念一、纠错码的基本概念2. 差错控制系统模型及分类一、纠错码的基本概念一、纠错码的基本概念2. 差错控制系统模型及分类

2、一、纠错码的基本概念一、纠错码的基本概念2. 差错控制系统模型及分类一、纠错码的基本概念一、纠错码的基本概念3. 差错类型一、纠错码的基本概念一、纠错码的基本概念3. 差错类型一、纠错码的基本概念一、纠错码的基本概念4. 纠错码的分类一、纠错码的基本概念一、纠错码的基本概念4. 纠错码的分类一、纠错码的基本概念一、纠错码的基本概念内容提要n一、纠错码的基本概念二、纠错编码的代数基础二、纠错编码的代数基础n三、线性分组码n四、循环码n五、卷积码近世代数简介n近世代数又称抽象代数，其研究对研究对象是定义在某些运算下的集合象是定义在某些运算下的集合，运算对象可以是数、多项式、矢量、矩阵、线性空间等。

3、n编码理论是建立在码的代数结构基础上的，为便于初学者理解，我们将简单介绍抽象代数中与编码直接相关的基础知识，主要涉及整数及多项式的一些基本概念及群、环、群、环、域域的基本知识。二、纠错编码的代数基础二、纠错编码的代数基础1. 群二、纠错编码的代数基础二、纠错编码的代数基础整数的相关概念整数的相关概念1. 群二、纠错编码的代数基础二、纠错编码的代数基础1. 群二、纠错编码的代数基础二、纠错编码的代数基础群的定义群的定义1. 群二、纠错编码的代数基础二、纠错编码的代数基础n在实数加法下整数集是一个交换群。在这种情况下，整数0是单位元，整数-i是整数i的逆元。除去0的有理数集合在实数乘法下是交换群。

4、整数1是关于实数乘法的单位元，有理数b/a是a/b的乘法逆元。1. 群n这样的二元运算称为模2(modulo-2)加法。集合G=0,1在模2加法下是一个群。由模2加法 的定义，G在 下是封闭的，同时 满足交换律、结合律。元素0是单位元，0的逆元是它本身，1的逆元也是它本身。这样，定义了 的G是一个交换群。二、纠错编码的代数基础二、纠错编码的代数基础模模2加加1. 群二、纠错编码的代数基础二、纠错编码的代数基础1. 群二、纠错编码的代数基础二、纠错编码的代数基础1. 群二、纠错编码的代数基础二、纠错编码的代数基础1. 群n令p为一个素数(例如p=2,3,5,7,11,)二、纠错编码的代数基础二、

5、纠错编码的代数基础模模p乘乘n易验证模p乘法满足交换律和结合律，其单位元是1。G中任何元素i关于模p乘法都有逆元。n群G=1,2,3,p-1在模p乘法下称为乘群 (multiplication group)1. 群二、纠错编码的代数基础二、纠错编码的代数基础模模p乘乘1. 群二、纠错编码的代数基础二、纠错编码的代数基础群的同构群的同构1. 群二、纠错编码的代数基础二、纠错编码的代数基础群的同构群的同构1. 群二、纠错编码的代数基础二、纠错编码的代数基础子群子群1. 群二、纠错编码的代数基础二、纠错编码的代数基础子群子群1. 群二、纠错编码的代数基础二、纠错编码的代数基础群的陪集群的陪集1. 群

6、二、纠错编码的代数基础二、纠错编码的代数基础群的陪集分解群的陪集分解1. 群二、纠错编码的代数基础二、纠错编码的代数基础群的陪集分解群的陪集分解2. 域二、纠错编码的代数基础二、纠错编码的代数基础域的定义域的定义2. 域二、纠错编码的代数基础二、纠错编码的代数基础群和域的区别群和域的区别n需要指出群(G)与域(F)的区别：n一个群只有规定的一种代数运算(加法或乘法)，n而域是有两种代数运算(加法和乘法)的代数系统。2. 域二、纠错编码的代数基础二、纠错编码的代数基础群和域的区别群和域的区别2. 域二、纠错编码的代数基础二、纠错编码的代数基础素数域素数域G(p)2. 域二、纠错编码的代数基础二、

7、纠错编码的代数基础素数域素数域G(p)3. 环二、纠错编码的代数基础二、纠错编码的代数基础多项式的相关概念多项式的相关概念3. 环二、纠错编码的代数基础二、纠错编码的代数基础多项式的相关概念多项式的相关概念3. 环二、纠错编码的代数基础二、纠错编码的代数基础环的定义环的定义3. 环二、纠错编码的代数基础二、纠错编码的代数基础整数剩余类环整数剩余类环3. 环二、纠错编码的代数基础二、纠错编码的代数基础多项式剩余类环多项式剩余类环3. 环二、纠错编码的代数基础二、纠错编码的代数基础内容提要n一、纠错码的基本概念n二、纠错编码的代数基础三、线性分组码三、线性分组码n四、循环码n五、卷积码1. 分组码

8、相关定义三、线性分组码三、线性分组码n假设信源信息是二进制数字序列，将信道编码器的输出序列构成长度为n的段，记为C C=c1,c2,cn 设有m个不同的信息序列，每个不同的序列由k(kn)位相继的信息数字组成。由于每个信息序列组成k位二进制数字，则有2k个可能不同的信息序列，即m=2k，这2k个码字的集合称为(n,k)分组码。(n,k)分组码定义分组码定义1.分组码相关定义n对于2k个n长码字全体构成的分组码，其码字中的k位称为信息位，n-k位称为校验位或监督位。n例如，当k=3，n=7时，可能的消息序列数m=2k=8个，可能的长为n=7的预选序列有27=128个。具体如表：n对于所选定的n长

9、序列称为允许使用序列，即码字；而其他序列则是不允许使用的，即禁用序列。n该例中，信息位为3，码长为7，监督位为4，如果用R=k/n表示码字中信息位所占比重，称为编码效率。表明了信道的利用率。三、线性分组码三、线性分组码消息序列码字00000000000010011101010010011101101110101001001110101101001111011010011111110100校验位和信息位校验位和信息位1.分组码相关定义n若(n,k)分组码中k个信息位同原始k个信息位相同，且位于n长码字的前(或后)k位，而校验位位于其后(或前)，则称该分组码为系统码，否则为非系统码。n右表所示为系

10、统码。三、线性分组码三、线性分组码消息序列码字00000000000010011101010010011101101110101001001110101101001111011010011111110100系统码与非系统码系统码与非系统码n定义：定义：n, k线性分组码是GF(q)上的n维线性空间中的一个k维子空间。2k2n2. 线性分组码定义三、线性分组码三、线性分组码2. 线性分组码定义三、线性分组码三、线性分组码n也可以这样理解：n长码字C=c1,c2,cn中每一位同原始的k个信息位d=d1,d2,dk之间满足一定的函数关系ci=f(d1,d2,dk), (n=1,2,n) 若函数关系是

11、线性的，则称该分组码为线性分组码，否则为非线性分组码。2. 线性分组码定义三、线性分组码三、线性分组码2. 线性分组码定义三、线性分组码三、线性分组码2. 线性分组码定义三、线性分组码三、线性分组码n容易验证C是线性的。假设消息序列与码字序列的映射关系为如下两种：n第一种： 映射关系为：n第二种： 映射关系与第一种截然不同。三、线性分组码三、线性分组码2. 线性分组码定义三、线性分组码三、线性分组码3. 线性分组码编码消息序列码字00000000000010011101010010011101101110101001001110101101001111011010011111110100三、线

12、性分组码三、线性分组码3. 线性分组码编码n由校验方程，可将n=7，k=3的线性分组码写成6655443642654165054ccccccccccccccccccc654,mc c c100111001001110011101G令则因此，C=mG且 G=Ik Pk*(n-k)三、线性分组码三、线性分组码3. 线性分组码编码令则因此，C=mG三、线性分组码三、线性分组码3. 线性分组码编码三、线性分组码三、线性分组码3. 线性分组码编码三、线性分组码三、线性分组码3. 线性分组码编码消息序列码字00000000000010011101010010011101101110101001001110

13、1011010011110110100111111101001011000111010011000100110001H三、线性分组码三、线性分组码3. 线性分组码编码n生成矩阵和校验矩阵关系生成矩阵和校验矩阵关系*()kkn kGIP()*Tn kkn kHPI100111001001110011101G1011000111010011000100110001H例题111001111101P100111001001110011101GTQP已知生成矩阵为求其校验矩阵H，如果将H作为生成矩阵，则所生成的码字是什么？由于G=Ik Pk*(n-k)则有又因为101100011101001100010

14、0110001HQI100111001001110011101G由生成矩阵生成的(7,3)码为：mC00000000000010011101010010011101101110101001001110101101001111011010011111110100把校验矩阵当作生成矩阵，mC000000000000001000101100100010110001100111010100010011101010101100011001100010111011101010001000101100110011101010101001110111011000110011000101101110100111

15、101110100111111111111011000111010011000100110001H产生(7,4)码为：1000101010011100101100001011H（n，k）线性分组码编码电路6655443642654165054ccccccccccccccccccc4. 伴随式与译码4. 伴随式与译码4. 伴随式与译码n证明：根据线性分组码的封闭性可知，任意两个码字的和应为一个码字。根据码字之间距离的定义可知，两个码字和的非零个数则与其距离相等，且又为新码字的重量。所以，不难理解，线性分组码的最小距离必定等于非零码字的最小重量。4. 伴随式与译码 设设C是线性分组码，是线性分组码

16、，H是它的校验矩阵，那么码是它的校验矩阵，那么码C的最小重量就等的最小重量就等于于H中线性相关的最小列数。因此，如果中线性相关的最小列数。因此，如果H中的中的2t个和小于个和小于2t个列个列的任一子集都线性无关，而的任一子集都线性无关，而H中有中有2t+1个列线性相关，那么码个列线性相关，那么码C就就是纠正是纠正t个错误的纠错码，或能检出个错误的纠错码，或能检出2t个错误的检错码。个错误的检错码。【例】（【例】（7，4）线性分组码）线性分组码100101101011010011110HH的前的前3列相加等于列相加等于0，因此，因此H线性相关的最小列数为线性相关的最小列数为3故：故：wmin(C

17、)=3例：某一个例：某一个(5,2)系统线性码的生成矩阵是系统线性码的生成矩阵是 设接收到码字是设接收到码字是r=(10101)，先构造该码的标准阵，先构造该码的标准阵列译码表，然后译出发码的估值列译码表，然后译出发码的估值C。1 0 1 1 01 1 1 0 1G(1)(1)信息组：信息组：m=(00),(10),(01),(11)m=(00),(10),(01),(11)(2)(2)求得求得4 4个许用码字个许用码字C=mGC=mG为为 C C1 1=(00000),C=(00000),C2 2=(10111=(10111 ),), C C3 3=(01101), C=(01101), C

18、4 4=(11010) =(11010) (3)(3)求出校验矩阵求出校验矩阵 1 1 1 0 01 0 0 1 01 1 0 0 1H1 0 1 1 01 1 1 0 1G(4)求出伴随式求出伴随式1 1 1 0 010101 1 0 0 1 01 1 0 0 111110110101010100010001TTSrH(5)标准阵列标准阵列S1=000E1+ C1=00000C2=10111C3=01101C4=11010S2=111E2=10000001111110101010S3=101E3=01000111110010110010S4=100E4=0010010011010011111

19、0S5=010E5=00010101010111111000S6=001E6=00001101100100111011S7=011E7=00011101000111011001S8=110E8=00110100010101111100选择重量最小的n重作为陪集首S=EHT111101100010001TH【例【例】（7，3）线性分组码）线性分组码101110011100100111001G1000110010001100101110001101H00101110101110110010110010110111001111001010111000000000c4)(minCw31minttd11

20、2minttd能检出能检出3重错误，纠正重错误，纠正1重错误。重错误。0111101r如：如： （一个错）（一个错）11101000000011101000001101001000010000001000010000001000010000001000010000001seTTrH)0111(10111101000110010001100101110001101)0011101()0100000()0111101(erc如两个错：如两个错：1111101r0)1001(TTrH，但无伴随式与之对应，不能纠正。，但无伴随式与之对应，不能纠正。n例例 已知（7，3）码的校验矩阵为101100011

21、1010011000100110001Hn若错误图样en =（0010000），则00101100011110100()0110001000110001010101Tn TSHe 是是H矩阵第三列！矩阵第三列！若错误图样中只有一个分量非零，则ST是H矩阵相应的列，因而能够纠正单个错误！n若错误图样en =（0010100），则001011000101111010011()01100010001011010000011100Tn TSHe 是是H矩阵第三列与第矩阵第三列与第五列之和！五列之和！由定义可以求得， rn的伴随式：是是H矩阵第一列与第矩阵第一列与第二列之和！二列之和！111011000

22、100111010011()01100010110011010001011000Tn TSHe 若发生两个错误，译码器只能判决传输有错（ en 0 ）,不能判定由哪几位错误引起！汉明码：汉明码：一类能纠单个错误的纠错码。一类能纠单个错误的纠错码。【例【例】（7，4）线性码）线性码100101101011010011110H1h2h3h4h5h6h0h5. 汉明码（1）H中列为非全零元素；中列为非全零元素；（2）H中任意两列都不相同，但存中任意两列都不相同，但存 在相加等于在相加等于0的三个列的子集。的三个列的子集。0120hhhH中线性相关的最小列数为中线性相关的最小列数为3，故，故 ，该码是

23、纠单个，该码是纠单个错误的码。错误的码。3)(minminCwd定理：定理：C是一个线性分组码，是一个线性分组码，H是校验矩阵，是校验矩阵，C是可以纠单个错误的纠错是可以纠单个错误的纠错码的充要条件：码的充要条件：（1）H中没有元素全为中没有元素全为0的列矢量；的列矢量；（2）H中任意两个列矢量都不相同。中任意两个列矢量都不相同。100101101011010011110H0h1h2h3h4h5h6h几个结论：几个结论：对于具有纠单个错误能力的线性分组码。对于具有纠单个错误能力的线性分组码。（1）若接收矢量的伴随式）若接收矢量的伴随式 ，则译码器认为接收矢量没有错误；，则译码器认为接收矢量没有

24、错误；0s （2）如果）如果 ，且，且 等于等于H矩阵中的某一列，则译码器纠认为接矩阵中的某一列，则译码器纠认为接收矢量在该列对应校验矩阵中的位置出错，此时只需将接收字该收矢量在该列对应校验矩阵中的位置出错，此时只需将接收字该位置的码元取反就能纠错；位置的码元取反就能纠错；Ts0Ts（3）若）若 ，但不等于，但不等于H中的任一列，则错误不能纠正。中的任一列，则错误不能纠正。【例【例】101000111011001110101011100011111000H)101000101 (r（1）0s 00011101000101101000111011001110101011100011111000T

25、TrHs伴随式对应于伴随式对应于H中的第五列，故：中的第五列，故：) 101010101 (erc) 101000100(r0)1101(s（2）H中无对应列与之对应，不能正确译码。中无对应列与之对应，不能正确译码。结论：为了得到具有纠一个错误的二元（结论：为了得到具有纠一个错误的二元（n，n-m）线性码，（其中）线性码，（其中n-m=k，m为校验位的个数），只需从定义在为校验位的个数），只需从定义在F2上的上的m维非零列矢量中选取彼此不维非零列矢量中选取彼此不同的同的n个列矢量个列矢量 并依任意次序把它们排成一个并依任意次序把它们排成一个mn的矩阵：的矩阵：011nHhhh那么以那么以H为校

26、验矩阵的二元（为校验矩阵的二元（n，n-m）线性码）线性码C就是一个可以纠正所有就是一个可以纠正所有单个错误的的码。单个错误的的码。1定义：定义：设设Vm(F2)是定义在是定义在F2上的一个上的一个m维的矢量空间维的矢量空间 令令H是二元是二元 m（2m-1）矩阵，这个矩阵的列是）矩阵，这个矩阵的列是Vm（F2）中按某种）中按某种次序排列的次序排列的2m-1个非零矢量，那么定义在个非零矢量，那么定义在F2上的上的n=2m-1，k = 2m-1-m的线性分组码（校验矩阵为的线性分组码（校验矩阵为H）就称为长）就称为长2m-1的汉明码。的汉明码。1,.,10,nhhh设消息或数据以二进制形式表示，

27、并以设消息或数据以二进制形式表示，并以F2 = 0 , 1 表示这个二元集。表示这个二元集。如：如：100101101011010011110H的（的（7，4）线性分组码就是汉明码）线性分组码就是汉明码m=3，n=23-1=7，k=7-3=42定理：定理：二元（二元（2m-1，2m-1-m）汉明码是能够纠单个错误的线性码，而）汉明码是能够纠单个错误的线性码，而且是校验位数为且是校验位数为m的所有二元线性码种编码效率最高的码，其的所有二元线性码种编码效率最高的码，其最小重量：最小重量：wmin（C）=3。3完备码：完备码：设设C是（是（n，k）线性分组码，其纠错能力为）线性分组码，其纠错能力为t

28、，如果用且只用，如果用且只用小于等于小于等于t个错误的全部错误图样作为陪集首就能做成标准阵个错误的全部错误图样作为陪集首就能做成标准阵列，那么称这个码为完备码。列，那么称这个码为完备码。 四四. . 汉明码的编译码电路框图汉明码的编译码电路框图1.1.编码器设计编码器设计例例 (7,4)(7,4)汉明码汉明码011110010110101101001H1000110010001100101110001101GvuG 0123()uuuuu由 ，402350126123,0 3iivu ivuuuvuuuvuuu2. 2. 译码器设计译码器设计令接收字为令接收字为 0123456()rrrrrr

29、rr0123456()rrrrrrrr伴随式为伴随式为 012()ssss由校验矩阵由校验矩阵H， 01234srrrr51023srrrr20136srrrr 令令5012346()eeeeeeee11010000000110100000111001000010100010001000000100010000001000100000010s5e4e3e2e1e0e2s1s6e00 1 2es s s10 1 2es s s20 1 2es s s30 1 2es s s40 1 2es s s50 1 2es s s60 1 2es s s 汉明码的译码电路框图汉明码的译码电路框图vre00

30、1166()rerere 内容提要n一、纠错码的基本概念n二、纠错编码的代数基础三、线性分组码四、循环码四、循环码n五、卷积码1.循环码的定义n定义一 一个(n,k)线性分组码，如果每个码字经任意循环移位之后仍然在码字的集合中，那么就称此码是一个循环码。n定义二 设 是某(n,k)线性分组码的码字集合， 如果对于任何 ， 它的循环移位 ，则称该码为循环码。 这种循环性可以推广到任意 次循环移位， 记作：120(,.,)nnAaaa(1)201(,.,)nnAaa a(01)iin ( )121012(,.,.,)in in innn iAaaa a aaa 【例】（【例】（7，3）线性分组码）

31、线性分组码1000110010001100101110001101H101110011100100111001G由：由： 得得vu G由两组码字循环构成的循环码由两组码字循环构成的循环码。2. 码字的多项式描述n对于任意个长度为n的码字， 可用下列多项式来描述：121210( ).nnnnA xaxaxa xan这里，把各码元当作多项式的系数；x及其幂次数仅是码元位置的标记，我们并不关心它的取值；称系数不为零的x的最高次数为多项式A(x)的次数，或称为多项式的阶数。120(,.,)nnAaaa多项式的模运算示例 如果A（an-1 an-2 a1 a0）是（n，k）循环码的一个码字，则A (1)

32、（an-2 a1 a0 an-1）也是该循环码的一个码字。这就是说A (x)an-1xn-1an-2xn-2a1xa0 和 A (1) (x)an-2xn-1a1x2a0 xan-1都是（n，k）循环码的码字多项式。 循环多项式的模运算比较A(x)和A (1) (x)后可得 A (1) (x)x A (x), mod xn+1以及 A(i) (x)xiA (x) （i1,2,n1）, mod xn+1 循环多项式的模运算n定理：对于(n,k)循环码， 若A(x)对应码字 ， 对应A(x)的i次左循环移位， 则 等于 除以 后的余式，即： 120(,.,)nnAaaa( )( )iAx( )(

33、)iAx( )ix A x(1)nx ( )( )( )(1)iinx A xAxx模n例题：设循环码(7,4)中一个码字为00001101，则该循环码的所有码字及其码多项式如表所示。序号循环码左移位数i00011010001101010110100211010003101000140100011510001106( )ix A x7(1)x 求模的余数多项式321xx32(1)x xx232(1)xxx332(1)xxx432(1)xxx532(1)xxx632(1)xxx321xx43xxx542xxx653xxx641xx51xx62xxx3.生成多项式和生成矩阵n生成多项式记为g(x)

34、,所有循环码(n,k)的码多项式A(x)可由g(x)生成，即A(x)=m(x)g(x), 式中，m(x)为消息多项式，它与消息位对应。n生成多项式g(x)性质：循环码(n,k)的生成多项式是xn+1的一个因子，且最高次数为n-k。 证明： 由于A(x)=m(x)g(x), 而m(x)最高次数为k-1，A(x)最高次数为n-1， 所以g(x)最高次数为 (n-1)-(k-1)=n-k。n例：求循环码(7,4)的生成多项式g(x)解：将x7+1分解得 x7+1=(x+1)(x3+x+1)(x3+x2+1) ， 因为g(x)最高次数为n-k=3，所以，其生成多项式有两种可能，即： x3+x+1或x3

35、+x2+1n由生成多项式g(x)容易得到生成矩阵。生成矩阵的每一行必定为线性无关的，且每行都是一个码字。g(x)为n-k阶多项式，则g(x),xg(x), x2g(x), xk-1g(x)必是线性无关的，将此对应的码字作为矩阵的每一行，得到生成矩阵。与生成矩阵对应的生成矩阵多项式G(x)可记作：3.生成多项式和生成矩阵12( )( )( )( )( )kxg xG xx g xxg xg x例题：已知循环码(7,4)的生成多项式g(x)有两种可能 x3+x+1或x3+x2+1，分别求其生成矩阵n解：若生成多项式g(x)=x3+x+1,则生成矩阵多项式为：336432353234233(1)(1

36、)( )(1)11xxxxxxxxxxxxG xx xxxxxxxxxn所对应的生成矩阵为：1011000010110000101100001011G例题：已知循环码(7,4)的生成多项式g(x)有两种可能 x3+x+1或x3+x2+1，分别求其生成矩阵n解：若生成多项式g(x)=x3+x2+1,则生成矩阵多项式为：33265323254232433232(1)(1)( )(1)11xxxxxxxxxxxxG xx xxxxxxxxxn所对应的生成矩阵为：1101000011010000110100001101G例题：如果循环码(7,4)的生成多项式g(x)= x3+x+1求对应的所有码字n解

37、：可得生成矩阵为1011000010110000101100001011G10111000101111011000100111011000110001011000010001011000010001011000011011000010100101100010100101101001000101111111100011000110000110100101110011100100111101001111010011110100011101000111010000000111111116个码字构成4个循环组，前两组分别7个码字，后两组为自循环的单独码字。可见，循环码并不是只由一个码字循环就可以得到全

38、部码字。n将生成矩阵通过矩阵初等变换转换成IkPk*r的形式，即可得到系统生成矩阵。3.生成多项式和生成矩阵生成多项式g(x)生成矩阵多项式G(x)生成矩阵G系统生成矩阵Gn解：可以先得到两个生成矩阵，后经过矩阵初等变换得到系统生成矩阵11011000010110000101100001011G例题：已知循环码(7,4)的生成多项式g(x)有两种可能 x3+x+1或x3+x2+1，分别求其系统生成矩阵21101000011010000110100001101G10001010100111001011000010111000110010001100101110001101矩阵初等变换矩阵初等变换

39、100010001011100110001001100110001101110110000101010110000100010110000110001010100101001110100001011010100001011110111100111001100001101001011100111001001111010011110100111101000111010001110100000001111111通过比较，可以发现，对于生成矩阵G1及系统生成矩阵G1,最后所生成的码字相同，唯一不同的是消息位与码字的对应关系不同。由生成多项式g(x)直接产生系统循环码n步骤：n(1)将消息多项式m(x)

40、乘以xn-k；n(2)将xn-k m(x)除以g(x)得到余式r(x)；n(3)将r(x)加进xn-k m(x)，得到系统码。n解:(1)消息码为1101，所以消息多项式为m(x)=x3+x2+1，则 xn-km(x)=x3m(x)=x6+x5+x3 (2)求余式 (3)求系统码多项式 C(x)= xn-km(x) +r(x)= x6+x5+x3 +1 所以对应的系统循环码为1101001例题：如果循环码(7,4)的生成多项式g(x)= x3+x+1，消息码为1101，求对应的系统循环码653( )( )mod ( )mod ( )1mod ( )n kr xxm xg xxxxg xg x4

41、. 校验多项式和校验矩阵4. 校验多项式和校验矩阵4. 校验多项式和校验矩阵5.伴随多项式和伴随矩阵n伴随多项式S(x)与收到的码多项式R(x)同余( )( )mod ( )S xR xg xn伴随多项式S(x)与差错图样多项式E(x)之间也存在一一对应关系( )( )( )mod ( )( ) ( )( )mod ( )( )S xC xE xg xm x g xE xg xE x5.伴随多项式和伴随矩阵n循环码译码步骤n(1)利用 ，建立差错图样多项式E(x)和伴随多项式S(x)之间的映射表；n(2)收到R(x)后，利用 得到某个S(x)，然后利用步骤(1)中建立的映射表，即可查到所对应的

42、差错多项式E(x);n(3) 将差错多项式E(x)与R(x)相加，即可得到经过纠错的C(x)。 ( )( )mod ( )S xE xg x( )( )mod ( )S xR xg xn解，由 得到( )( )mod ( )S xE xg x例题：如果循环码(7,4)的生成多项式g(x)= x3+x+1，确定差错图样多项式与伴随多项式的映射表差错图样多项式E(x)伴随多项式S(x)0011xxx2x2x3x+1x4x2+xx5x2+x+1x6x2+1n若已知伴随多项式S(x)，可以容易求得对应的伴随矩阵S。例如，S(x)=x2+x+1,则伴随矩阵S=1 1 1n当然，由于循环码是线性分组码的子

43、类，所以，伴随矩阵仍可以由S=RHT求得。5.伴随多项式和伴随矩阵6. BCH码和RS码nBCH码是循环码中的一个大类，分为二进制BCH码和非二进制BCH码(例如RS码)。n二进制BCH码可记为(2m-1,k)，其中m为正整数且 ，即码长n=2m-1，且 (t为可纠正的差错数)，t由最小码距决定，即n二进制BCH码的优点是，具有纠正多个随机差错的能力。具有严谨的代数结构，可以按照码长n和纠错能力t直接将BCH码构造出来。该特点优于一般线性分组码，一般线性分组码在设计出来之后，需要计算最小距离dmin，才能知道纠错能力。若不符合要求，还要重复设计过程。3m nkmtmin21dt6. BCH码和

44、RS码n确定BCH码的生成多项式g(x)，取决于两方面：n(1) g(x)是xn+1因式中最高阶为n-k的多项式，这是任何循环码都必须满足的条件。由于BCH码的码长n=2m-1， ，所以其码长的取值只能是7,15,31,63,127,255,当n较大时，xn+1的因式分解就只能用计算机来计算。n(2) g(x)必须满足对纠错能力t的要求，即对最小码距的要求。n实际应用中，将满足上述两个条件的系数整理成“BCH码生成多项式系数”表，以便查用。3m 例题：求码长为15且能纠正3个差错的BCH码n解：码长n=2m-1=15，所以m=4；纠错能力t=3；将x15+1因式分解后， 得x15+1=(x+1

45、)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1) 查前述的“BCH码生成多项式系数”表，可得满足条件的BCH码为(15,5)，其相应的生成多项式的最高阶为n-k=10，则生成多项式为 g(x)=(x2+x+1)(x4+x+1)(x4+x3+x2+x+1) =x10+x8+x5+x4+x2+x+16. BCH码和RS码nRS(Reed-Solomn)码是一种非二进制BCH码。nRS码是极大最小距离码(MDC码)。n若某个码的最小距离dmin=n-k+1，则称线性分组码(n,k)为极大最小距离码。在(n,k)线性分组码中，极大最小距离码具有最大的检错、纠错能力。n由

46、于RS码是多进制，所以很容易与M进制调制技术相匹配；RS码特别适合纠正突发错误。内容提要n一、纠错码的基本概念n二、纠错编码的代数基础三、线性分组码四、循环码五、卷积码五、卷积码卷积码与线性分组码的比较卷积码线性分组码表示符号(n,k,K)，K为约束长度(n,k)记忆性有记忆，输出的n个比特不仅与当前输入的k比特有关，而且与以前输入的K个k比特有关无记忆，输出的n个比特仅与当前输入的k个比特有关(可视为K=0时的无记忆卷积码)代数结构无严格的代数结构，目前多采用计算机来搜索好码，缺乏有效的数学分析工具有严格的代数结构，借用数学工具研究较为透彻编码效率()LkLK nknkkkn输入k位当前时间

47、以前K个时间输入n位kn输入k位输入n位卷积码卷积码线性分组码线性分组码1. 卷积码的组织结构n卷积码(n,k,K)与线性分组码(n,k)的重要区别在于，卷积码是有记忆的，并用约束长度表示记忆长度，记为K。输出的n位比特不仅与当前时间输入的k比特有关，还与以前时间输入的多个k比特有关，到底与以前多长时间有关，就由约束长度K来度量。n卷积码可以视为多个线性分组码的线性叠加，只不过多个线性分组码是来源于同一个输入源的多个不同时间段(包括当前时间段和K个以前时间段)。显然，当K=0时，卷积码就退化为线性分组码。例题：设卷积码(2,1,2)，其组织结构如图(a)所示，假设输入序列为1011，通过求输出序列，来说明卷积码编码的全过程10011010011011011010011000010100000(a)(b)(