《信息论和编码.pptx》由会员分享，可在线阅读，更多相关《信息论和编码.pptx（86页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、主要内容主要内容1234循环码的码多项式循环码的码多项式循环码的码多项式循环码的码多项式循环码编码循环码编码循环码编码循环码编码CRCCRC码码码码RSRS码码码码BCHBCH码码码码65乘法电路乘法电路乘法电路乘法电路第1页/共86页一、循环码的码多项式一、循环码的码多项式第2页/共86页第3页/共86页例例4.1.1汉明循环码C的生成矩阵G和校验矩阵H依次令m=(0000)(1111)代入方程CmG可得16个码字。经分析，将16个码字归结为4个循环环第一循环第二循环第三循环第四循环(1011000)(1110100)(0000000)(1111111)(0110001)(1101001)(
2、1100010)(1010011)(1000101)(0100111)(0001011)(1001110)(0010110)(0011101)(0101100)(0111010)第4页/共86页循环码的多项式描述循环码的多项式描述GF(2)上n维矢量空间Vn中的任一矢量V=(vn-1,v1,v0)viGF(2)可与GF(2)域上多项式V(x)一一对应如下：V=(vn-1,v1,v0)V(x)=vn-1 xn-1+v1 x+v0多项式的各系数就是矢量各元素的值，x的幂次指示对应元素所在位置。码空间是矢量空间Vn的一个子空间，因此n重矢量不一定是码矢量，n次多项式不一定是码多项式。位于码空间的矢量
3、叫码矢，对应的多项式为码多项式。我们约定：以下所说的码字、码组、码矢和码多项式等术语具有相同的物理意义，只是描述角度和表达方式不同而已。第5页/共86页第6页/共86页码码矢矢C0=(cn-1,c1,c0)右右循循环环一一位位C1=(cn-2,c1,c0,cn-1,)也是码矢。它们各自对应的码多项式是也是码矢。它们各自对应的码多项式是:C0(x)=cn-1 xn-1+cn-2 xn-2+c1 x+c0C1(x)=cn-2 xn-1+cn-3 xn-2+c0 x+cn-1比较两者，可知比较两者，可知C1(x)=xC0(x),mod(xn+1)(4-2)以以此此类类推推，循循环环码码循循环环移移2
4、位位、移移3位位、移移n-1位位后后仍然应是码字仍然应是码字,于是得到下面一系列等式：于是得到下面一系列等式：C2(x)=xC1(x)=x2C0(x),mod(xn+1)C3(x)=xC2(x)=x3C0(x),mod(xn+1):C n-1(x)=xC n-2(x)=xn-1C0(x),mod(xn+1)第7页/共86页由由码码空空间间的的封封闭闭性性，可可知知码码多多项项式式C0(x),C n-1(x)的的线性组合仍应是码多项式：线性组合仍应是码多项式：C(x)=an-1xn-1C0(x)+an-2xn-2C0(x)+a1xC0(x)+a0C0(x)=(an-1 xn-1+an-2 xn-
5、2+a1 x+a0)C0(x)=A(x)C0(x)mod(xn+1)(4-3)C0(x)是是码码多多项项式式，A(x)是是n-1次次多多项项式式，但但不不一一定定是是码码多多项项式式。式式(4-3)给给出出的的结结论论是是：码码多多项项式式与与任任意意n-1次多项式作运算后，结果一定回落到码空间。次多项式作运算后，结果一定回落到码空间。第8页/共86页二、循环码编码二、循环码编码第9页/共86页定定理理4.2在在一一个个GF(2)域域上上的的(n,k)循循环环码码中中，一一定定存在唯一的一个次数最低的存在唯一的一个次数最低的(n-k)次次首一码多项式首一码多项式g(x)=xn-k+gn-k-1
6、 x n-k-1+g1 x+1使使所所有有码码多多项项式式都都是是g(x)的的倍倍式式，且且所所有有小小于于n次次的的g(x)的倍式都是码多项式。的倍式都是码多项式。即即C(x)m(x)g(x)及及g(x)|C(x)“所有小于所有小于n次的次的g(x)的倍式都是码多项式的倍式都是码多项式”意味意味着着m(x)g(x)一定是码字，其中一定是码字，其中m(x)是是GF(2)上小于上小于k次的任意多项式，以致它与次的任意多项式，以致它与(n-k)次的次的g(x)相乘后所相乘后所得倍式的次数一定小于得倍式的次数一定小于n次。次。第10页/共86页定理定理4.3(n，k)循环码的生成多项式循环码的生成多
7、项式g(x)一定是一定是(xn-1)的因式，即一定存在一个多项式的因式，即一定存在一个多项式h(x)，满足，满足(xn-1)g(x)h(x)或或 g(x)|(xn-1)反之，如果反之，如果g(x)是是(xn-1)的（的（n-k）次因式，）次因式，g(x)一定是某一定是某(n，k)循环码的生成多项式。循环码的生成多项式。第11页/共86页上上述述定定理理告告诉诉了了构构造造(n，k)循循环环码码的的方方法法如下：如下：对对xn-1(在在二二元元域域中中等等效效于于对对xn+1)实实行行因式分解因式分解,找出其中的（找出其中的（n-k）次因式。）次因式。以以找找出出的的（n-k）次次因因式式为为循
8、循环环码码生生成成多多项项式式g(x)，与与信信息息多多项项式式m(x)相相乘乘，即即得码多项式：得码多项式：C(x)=m(x)g(x)。第12页/共86页例例4.2分析码长分析码长n=7的所有可能二进制循环码的所有可能二进制循环码解解：将将GF(2)上上多多项项式式(x71)因因式式分分解解，或或查查表表4.6m=3一行，得：一行，得：(x71)=(x1)(x3x1)(x3x21)因此因此(x71)因式的次数可以有以下四种因式的次数可以有以下四种1次次(x1)3次次(x3x1)或或(x3x21)4次次(x1)(x3x1)或或(x1)(x3x21)6次次(x3x1)(x3x21)(n-k)可取
9、可取1、3、4、6,因此断言：因此断言：存在存在(7,6)，(7,4)，(7,3)，(7,1)循环码，循环码，而不存在而不存在(7,2)，(7,5)循环码。循环码。第13页/共86页 i最小多项式最小多项式 i最小多项式最小多项式 i最小多项式最小多项式 i最小多项式最小多项式m=21(0,1,2)m=31(0,1,3)3(0,2,3)m=41(0,1,4)3(0,1,2,3,4)5(0,1,2)7(0,3,4)m=51(0,2,5)3(0,2,3,4,5)5(0,1,2,4,5)7(0,1,2,3,5)11(0,1,3,4,5)15(0,3,5)m=61(0,1,6)3(0,l,2,4,6)
10、5(0,l,2,5,6)7(0,3,6)9(0,2,3)11(0,2,3,5,6)13(0,1,3,4;6)15(0,2,4,5,6)21(0,1,2)23(0,1,4,5,6)27(0,1,3)31(0,5,6)m=71(0,3,7)3(0,1,2,3,7)5(0,2,3,4,7)7(0,1,2,4,5,6,7)9(0,1,2,3,4,5,7)11(0,2,4,6,7)13(0,1,7)15(0,1,2,3,5,6,7)19(0,1,6,7)21(0,2,5,6,7)23(0,6,7)27(0,1,4,6,7)29(0,1,3,5,7)31(0,4,5,6,7)43(0,l,2,5,7)47
11、(0,3,4,5,7)55(0,2,3,4,5,6,7)63(0,4,7)m=81(0,2,3,4,8)3(0,1,2,4,5,6,8)5(0,1,4,5,6,7,8)7(0,3,5,6,8)9(0,2,3,4,5,7,8)11(0,1,2,5,6,7,8)13(0,1,3,5,8)15(0,1,2,4,6,7,8)17(0,1,4)19(0,2,5,6,8)21(0,l,3,7,8)23(0,1,5,6,8)25(0,1,3,4,8)27(0,1,2,3,4,5,8)29(0,2,3,7,8)31(0,2,3,5,8)表表4-6二元扩域二元扩域GF(2m)中连续幂次根所对应的最小多项式中连续
12、幂次根所对应的最小多项式第14页/共86页要构成要构成(7,3)循环码，循环码，(n-k)=4的因式有的因式有(x1)(x3x1)或或(x1)(x3x21)两个，任选其中一个两个，任选其中一个,比如比如g(x)=(x+1)(x3+x+1)=(x4+x3+x2+1)作生成多项式作生成多项式,令令C(x)=m(x)g(x)=(m2x2+m1x+m0)(x4+x3+x2+1)可产生循环码集。例如可产生循环码集。例如m=(011)即即m(x)=(x+1)时时(x+1)(x4x3x21)=x5+x2+x1+1对应码矢对应码矢C=(0100111)类推，得全部码集。类推，得全部码集。经检验，符合经检验，符
13、合“码字的循环仍是码字码字的循环仍是码字”信息位信息位m000001010011100101110111码矢码矢C00000000011101011101001001111110100110100110011101010011第15页/共86页构码也有好坏之分。比如构造一个构码也有好坏之分。比如构造一个(15,10)循环码，循环码，x15+1=(x+1)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1)由于由于n-k=5方案方案1：g1(x)=(x+1)(x4+x+1)=x5+x4+x2+1方案方案2：g2(x)=(x+1)(x4+x3+x2+x+1)=x5+1g(
14、x)一般就是最轻码，一般就是最轻码，g1(x)、g2(x)的重量分别是的重量分别是和，因此和，因此g1(x)优于优于g2(x)。第16页/共86页用用上上述述方方法法可可得得循循环环码码，但但未未必必是是系系统统的的。若若想想得得到到系系统统循循环环码码，即即码码字字的的前前k位位原原封封不不动动照照搬搬信信息位而后息位而后(n-k)位为校验位，具有如下形式位为校验位，具有如下形式 C(x)=xn-k m(x)+r(x)(4-5)r(x)是是与与码码字字中中(n-k)个个校校验验元元相相对对应应的的(n-k-1)次次多多项式，可将式项式，可将式(4-5)写成写成 xn-k m(x)=C(x)+
15、r(x)等等式式两两边边除除以以生生成成多多项项式式g(x)，由由于于g(x)能能整整除除C(x)，degr(x)17的单个突发差错的单个突发差错6.所有长度所有长度2的两个突发差错的两个突发差错1.所有奇数个差错（此码重为偶数）所有奇数个差错（此码重为偶数）2.所有所有3个的随机差错个的随机差错3.所有长度所有长度16的单个突发差错的单个突发差错4.以以(1-2-17)的概率检出长度的概率检出长度17的单个突发差错的单个突发差错5.以以(1-2-16)的概率检出长度的概率检出长度17的单个突发差错的单个突发差错6.所有长度各所有长度各2的两个突发差错的两个突发差错同上同上CRC-ITU-T1
16、.所有奇数个差错（此码重为偶数）所有奇数个差错（此码重为偶数）2.所有所有14个的随机差错个的随机差错3.所有长度所有长度32的单个突发差错的单个突发差错4.以以(1-2-33)的概率检出长度的概率检出长度33的单个突发差错的单个突发差错5.以以(1-2-32)的概率检出长度的概率检出长度33的单个突发差错的单个突发差错6.所有长度各所有长度各2的两个突发差错的两个突发差错CRCITU-T第39页/共86页五、五、BCH码码第40页/共86页BCH码是纠错能力可控的纠随机差错码，是循环码是纠错能力可控的纠随机差错码，是循环码的子类。码的子类。该码有严格的代数结构，生成多项式该码有严格的代数结构
17、，生成多项式g(x)与最小距离与最小距离dmin有密切关系，使设计者可以根据对有密切关系，使设计者可以根据对d dminmin的要求，轻易地构造出具有预定纠错能力的码。的要求，轻易地构造出具有预定纠错能力的码。BCH编、译码电路比较简单，易于工程实现，在编、译码电路比较简单，易于工程实现，在中、短码长情况下的性能接近理论最佳值。因此中、短码长情况下的性能接近理论最佳值。因此BCH码不仅在编码理论上占有重要地位，而且也是实际使码不仅在编码理论上占有重要地位，而且也是实际使用最广泛的码之一。用最广泛的码之一。BoseChandhariBCHHocquenghemBCH码最初是定义在码最初是定义在G
18、F(2)域上的二进制码，后被推域上的二进制码，后被推广到多元域广到多元域GF(q)上。上。第41页/共86页xn-1因式分解因式分解(4-17)这里，既约因式这里，既约因式m mj j(x x)（j=0,j=0,l l-1-1）分成两部分，它们的乘积）分成两部分，它们的乘积分别是分别是g g(x x)和和 h h(x x)。循环码并不强调。循环码并不强调g g(x x)的既约性，它可以是的既约性，它可以是既约的，也可以是非既约的。若某既约因式既约的，也可以是非既约的。若某既约因式m mj j(x x)是非既约是非既约g g(x x)的一个因式，必有的一个因式，必有 m mj j(x x)|)|
19、g g(x x)|()|(x xn n-1)-1)(4-18)(4-18)换一个角度，如果将换一个角度，如果将(x xn n-1)-1)看成是一个看成是一个n n次多项式，那么它次多项式，那么它在复数域应该有在复数域应该有n n个根，记作个根，记作a ai i，i i=0,=0,n n-1-1，此时，此时(x xn n-1)-1)可表可表示成示成x xn n-1=(-1=(x x-a a0 0)()(x x-a a1 1)()(x x-a an n-1-1)(4-19)(4-19)比较式比较式4-174-17和式和式4-194-19，式，式4-174-17中的因式中的因式m mj j(x x)
20、既然已经达到既然已经达到“既约既约”，就不能再分解，那式，就不能再分解，那式4-194-19又从何而来呢？又从何而来呢？第42页/共86页例例4-7（x4-1）在不同域上的因式分解）在不同域上的因式分解在实数域的分解：在实数域的分解：x x4 4-1=-1=(x x2 2+1)(+1)(x x+1)(+1)(x x-1)-1)在复数域的分解：在复数域的分解：x x4 4-1=-1=(x x+i i)()(x x-i i)()(x x+1)(+1)(x x-1)-1)在二元域的分解：在二元域的分解：x x4 4-1=-1=x x4 4+1=(+1=(x x+1)(+1)(x x+1)(+1)(x
21、 x+1)(+1)(x x+1)+1)上例说明：域不同则分解亦不同，在一个域的既约不等于在另上例说明：域不同则分解亦不同，在一个域的既约不等于在另一个域的既约。一个域的既约。既约多项式既约多项式m mj j(x x)在在GF(2)GF(2)上不能再分解，其系数在数域取值于上不能再分解，其系数在数域取值于0,10,1；但它在二元扩域；但它在二元扩域GF(2GF(2m m)未必就不能再分解，因未必就不能再分解，因GF(2GF(2m m)是是多项式域，系数取值于多项式域，系数取值于 0 0、1 1、2 2、。于是问题变。于是问题变为为(x xn n-1)-1)能否在能否在GF(2GF(2m m)完全
22、分解？如何分解？分解后如何用于纠完全分解？如何分解？分解后如何用于纠错编码设计？编码和译码又如何实现？错编码设计？编码和译码又如何实现？第43页/共86页根根据据定定理理4.1，只只要要找找到到与与循循环环码码对对应应的的主主理理想想中中的一个的一个n 阶元素，就可以将阶元素，就可以将(xn-1)在在GF(2m)上完全上完全分解为分解为 xn-1=证：若证：若a是循环群是循环群n阶元素，必有阶元素，必有an=1即即(an-1)=0将将ai,i=0n-1代入代入(xn-1)验根，验根，得得(ai)n-1=(a n)i-1=(1)i-1=0 ai,i=0n-1是是(xn-1)的的n个根，以根为一次
23、项可将个根，以根为一次项可将(xn-1)完全分解为完全分解为xn-1=(x-a0)(x-a1)(x-an-1)问题问题1.码长码长n与扩域次数与扩域次数m有何关系？有何关系？2.GF(2m)上的根上的根ai与二元域多项式与二元域多项式mj(x)有何关系？有何关系？第44页/共86页二二元元扩扩域域GF(2m)是是由由一一m次次本本原原多多项项式式生生成成的的。当当n=2m-1时时，这这个个n阶阶域域元元素素a就就是是(2m-1)阶阶本本原原元元，资资料料中中通通常常用用 表表示示本本原原元元；当当n(2m-1)且且n|(2m-1)时时，这这个个n阶阶域域元元素素a为为非非本本原原元元，通通常常
24、用用 表表示示非非本本原原元元。这这里里不不强强调调域域元元素素是是否否本本原原，所所以以用用中中性性字母字母a来表示。来表示。=xn-1=GF(2m)扩域扩域|GF(2)域域系数系数1既是扩域又是二元域元素既是扩域又是二元域元素或改变顺序为或改变顺序为=xn-1第45页/共86页若若(xn-1)的某一个根的某一个根ai,i 0,1n-1又是某个既约因又是某个既约因式式mj(x),j 0,1l-1的根，也是的根，也是(n-k)次生成多项式次生成多项式g(x)的根，那么必有的根，那么必有a为为n阶本原元时：阶本原元时：(x-ai)|mj(x)|g(x)|(xn-1)=()(4-22)a为为n阶非
25、本原元时：阶非本原元时：(x-ai)|mj(x)|g(x)|(xn-1)|()(4-23)以上两式说明：生成多项式以上两式说明：生成多项式g(x)的（的（n-k）个根也是）个根也是(xn-1)的根，只要能够以适当的方法找出这些根，就的根，只要能够以适当的方法找出这些根，就可以从这些根得到生成多项式可以从这些根得到生成多项式g(x)。第46页/共86页研究表明，有重根的研究表明，有重根的g(x)不能产生好码。不能产生好码。而如果而如果(xn-1)无重根，则无重根，则g(x)肯定无重根。肯定无重根。在在GF(qm)上上(xn-1)无重根的充要条件是无重根的充要条件是n、q互素。互素。这就解释了为什
26、么二进制码（这就解释了为什么二进制码（q=2）码长都是奇数）码长都是奇数的原因。的原因。(xn-1)的的n个根中，个根中，(n-k)个根也是个根也是g(x)的根，剩下的的根，剩下的k个根一定也是个根一定也是h(x)的根。的根。因此如果因此如果(xn-1)无重根，无重根，h(x)肯定也无重根。肯定也无重根。第47页/共86页至此，实际上已找到了用至此，实际上已找到了用(xn-1)在在GF(2m)域上的根域上的根来构造循环码的方法，那就是：来构造循环码的方法，那就是：在在(xn-1)的的n个根中选取若干个个根中选取若干个r1、r2rj,其中其中rj ai,i=0,1n-1找出各根对应的既约多项式找
27、出各根对应的既约多项式r1m1(x)、r2m2(x)rjmj(x)。求出这些既约多项式的最小公倍式：求出这些既约多项式的最小公倍式：g(x)=LCMm1(x),m2(x)mj(x)LCM(LeastCommonMultiple)-最小公倍式最小公倍式若选取的根是连续幂次的根，则所得的若选取的根是连续幂次的根，则所得的g(x)可以产可以产生一个生一个BCH码，否则就是一般的循环码。码，否则就是一般的循环码。第48页/共86页1 BCH1 BCH码的定义码的定义GF(q)域循环码生成多项式域循环码生成多项式g(x)，若含有，若含有2t个连个连续幂次的根续幂次的根，则由，则由g(x)生成的生成的(n
28、,k)循环码称为循环码称为q进制进制BCH码。码。连续幂次起始值连续幂次起始值m0的的选取并无多大实际意义，通常固定取选取并无多大实际意义，通常固定取m0=1。若若q=2，称为二进制（二元），称为二进制（二元）BCH码。码。若根若根a是本原元是本原元，称该码为本原，称该码为本原BCH码，其码码，其码长长n=qm-1。若根若根a是非本原元是非本原元，称该码为非本原，称该码为非本原BCH码，码，其码长其码长n是是qm-1的因子，满足的因子，满足n|(qm-1)。第49页/共86页BCH码限定理码限定理：若若BCH码生成多项式码生成多项式g(x)中含有中含有2t个连续幂次的根，则该码的最小距离个连续
29、幂次的根，则该码的最小距离dmim 2t+1证明：BCH码多项式C(x)=m(x)g(x)g(x)的2t个连续幂次根、2t也是C(x)的根设C(x)=c0+c1x+c2 x2+cn-1 xn-1以根x=代入，得c0+c1+c2 2+cn-1 n-1=0以x=2代入，得c0+c12+c2(2)2+cn-1(2)n-1=0以x=2t代入，得c0+c12t+c2(2t)2+cn-1(2t)n-1=0第50页/共86页将上面将上面2t个方程写作矩阵形式，得个方程写作矩阵形式，得CAT=0(4-24)其中其中A=可见，可见，A是范得蒙矩阵。数学证明：范得蒙矩阵一是范得蒙矩阵。数学证明：范得蒙矩阵一定是满
30、秩矩阵，即定是满秩矩阵，即矩阵矩阵A的秩是的秩是2t或者说有或者说有2t列线性列线性无关。码的最小距离无关。码的最小距离dmin等于校验矩阵中线性无关等于校验矩阵中线性无关的列数加的列数加1，因此，因此BCH码的码的dmin=2t+1(4-26)12n-112(2)2(2)n-112t(2t)2(2t)n-112n-112(2)2(n-1)2 12t(2)2t(n-1)2t第51页/共86页 2 2 本原本原BCHBCH码构造法码构造法 由关系式由关系式n=2m-1算出算出m，查表，查表4-5，找到一个，找到一个m次次本原多项式本原多项式P(x)，产生一个，产生一个GF(2m)扩域。扩域。在在
31、GF(2m)上找一个本原元上找一个本原元，分别计算，分别计算2t个连续个连续幂次根幂次根、2、2t所对应的所对应的GF(2)域上的最小多域上的最小多项式项式m1(x)、m2(x)m2t(x)。m 8时连续幂次根时连续幂次根 i所所对应的最小多项式见表对应的最小多项式见表4-6。计算这些最小多项式的最小公倍式，得到生成多计算这些最小多项式的最小公倍式，得到生成多项式项式g(x)g(x)=LCMm1(x)m2(x)m2t(x)(4-27)由关系式由关系式C(x)=m(x)g(x)求求BCH码字。码字。第52页/共86页对于二元对于二元BCH码，无需列出全部码，无需列出全部2t个连续幂次的根，个连续
32、幂次的根，而只要列出其中一半（奇数幂次的根）就可以了。而只要列出其中一半（奇数幂次的根）就可以了。这是因为任何一个偶数这是因为任何一个偶数ie 可写成一个小于它的奇数可写成一个小于它的奇数io 与与2的的l次幂的乘积次幂的乘积 ie=io 2l,ioie(4-28)比如比如2=121，4=122，10=521，12=322因此任何一个偶次幂根都是奇次幂根的共轭元因此任何一个偶次幂根都是奇次幂根的共轭元对照节定理和定理，可知它们对应同一个最小多项对照节定理和定理，可知它们对应同一个最小多项式，在计算最小公倍式时将不起作用。式，在计算最小公倍式时将不起作用。第53页/共86页 i最小多项式最小多项
33、式 i最小多项式最小多项式 i最小多项式最小多项式 i最小多项式最小多项式m=21(0,1,2)m=31(0,1,3)3(0,2,3)m=41(0,1,4)3(0,1,2,3,4)5(0,1,2)7(0,3,4)m=51(0,2,5)3(0,2,3,4,5)5(0,1,2,4,5)7(0,1,2,3,5)11(0,1,3,4,5)15(0,3,5)m=61(0,1,6)3(0,l,2,4,6)5(0,l,2,5,6)7(0,3,6)9(0,2,3)11(0,2,3,5,6)13(0,1,3,4;6)15(0,2,4,5,6)21(0,1,2)23(0,1,4,5,6)27(0,1,3)31(0
34、,5,6)m=71(0,3,7)3(0,1,2,3,7)5(0,2,3,4,7)7(0,1,2,4,5,6,7)9(0,1,2,3,4,5,7)11(0,2,4,6,7)13(0,1,7)15(0,1,2,3,5,6,7)19(0,1,6,7)21(0,2,5,6,7)23(0,6,7)27(0,1,4,6,7)29(0,1,3,5,7)31(0,4,5,6,7)43(0,l,2,5,7)47(0,3,4,5,7)55(0,2,3,4,5,6,7)63(0,4,7)m=81(0,2,3,4,8)3(0,1,2,4,5,6,8)5(0,1,4,5,6,7,8)7(0,3,5,6,8)9(0,2,
35、3,4,5,7,8)11(0,1,2,5,6,7,8)13(0,1,3,5,8)15(0,1,2,4,6,7,8)17(0,1,4)19(0,2,5,6,8)21(0,l,3,7,8)23(0,1,5,6,8)25(0,1,3,4,8)27(0,1,2,3,4,5,8)29(0,2,3,7,8)31(0,2,3,5,8)表表4-6二元扩域二元扩域GF(2m)中连续幂次根所对应的最小多项式中连续幂次根所对应的最小多项式第54页/共86页比如比如t=4时时8个连续幂次根个连续幂次根 2 3 4 5 6 7 8中，中，2 4 8是共轭元，是共轭元，3 6是共轭元，于是是共轭元，于是g(x)=LCMm
36、1(x)m2(x)m3(x)m4(x)m5(x)m6(x)m7(x)m8(x)=LCMm1(x)m2(x)m4(x)m8(x)m3(x)m6(x)m5(x)m7(x)=LCMm1(x)m3(x)m5(x)m7(x)因此因此对于二进制码，构造本原对于二进制码，构造本原BCH码的步骤改为码的步骤改为:分别计算分别计算t个连续奇次幂之根个连续奇次幂之根、3 2t-1所对应所对应的最小多项式的最小多项式m1(x)、m3(x)m2t-1(x)。第55页/共86页当码长当码长n确定后，确定后，BCH码纠错能力码纠错能力t的选择并不是任意的选择并不是任意的，而要受到一定限制。的，而要受到一定限制。对于对于q
37、元元BCH码，码，2t个根对应个根对应2t个最小多项式，每个个最小多项式，每个最小多项式的次数不会超过最小多项式的次数不会超过m，于是，于是2t个最小多项式个最小多项式的最小公倍式的最小公倍式g(x)的次数的次数degg(x)=(n-k)2tm(4-29)对于二元对于二元BCH码，码，t个根对应个根对应t个最小多项式，因此个最小多项式，因此degg(x)=(n-k)tm(4-30)(xn-1)一共有一共有n个根，连续幂次根不能超过根的总数个根，连续幂次根不能超过根的总数2t n (4-31)式式(4-29)(4-30)给出了给出了t的下限，式的下限，式(4-31)给出了给出了t的上的上限。限。
38、第56页/共86页例例4.8设计一个码长设计一个码长n=15的二元本原的二元本原BCH码，在不码，在不同纠错能力下的生成多项式应是怎样的？同纠错能力下的生成多项式应是怎样的？解解：15=24-1本题本题m=4第一步：查表，找到一个第一步：查表，找到一个m=4的本原多项式的本原多项式P(x)=x4+x+1。令。令 是该本原多项式是该本原多项式P(x)的根，满足的根，满足 4+1=0。由式。由式(4-31)，本码纠错能力，本码纠错能力t 7。第二步：对于二元码，分别计算第二步：对于二元码，分别计算t=7个连续奇次幂个连续奇次幂之根之根 3 5 7 9 11 13所对应的最小多项式。本例所对应的最小
39、多项式。本例可参考例的表可参考例的表2-3，我们看到，我们看到 3、9是共轭元，是共轭元，7、11和和 13是共轭元（利用教材是共轭元（利用教材p124“共轭根系共轭根系”定义定义分析）。分析）。第57页/共86页根和根所对应的最小多项式（例）如下：根和根所对应的最小多项式（例）如下：根根 m1(x)=p(x)=x4+x+1根根 3m3(x)=(x+a3)(x+a(x+a6 6)(x+a)(x+a9 9)(x+a(x+a1212)=x4+x3+x2+x+1根根 5m5(x)=(x+a5)(x+a10)=x2+x+1根根 7m7(x)=x4+x3+1根根 9同同 3，根根 11、13同同 7。这
40、里，这里，m(x)的全部根为下列系列：的全部根为下列系列：并把并把w序列换成序列换成a的序列。的序列。第58页/共86页 第三步：求最小公倍式得到生成多项式第三步：求最小公倍式得到生成多项式g g(x x)。若若t t=1=1，g g1(1(x x)=LCM)=LCMm m1(1(x x)=)=x x4+4+x x+1+1g g1(1(x x)是是4 4次多项式，即次多项式，即n-kn-k=4=4，k k=15-4=11,=15-4=11,这就是这就是(15,11)BCH(15,11)BCH码，也是汉明码。码，也是汉明码。若若t t=2=2，g g2(2(x x)=LCM)=LCMm m1(1
41、(x x),),m m3(3(x x)=)=m m1(1(x x)m m3(3(x x)=)=x x8+8+x x7+7+x x6+6+x x4+14+1，degdegg g2(2(x x)=)=n-k n-k=8=8，k k=15-8=7=15-8=7，这是，这是(15,7)BCH(15,7)BCH码。码。第59页/共86页若若t=3，g3(x)=LCMm1(x),m3(x),m5(x)=m1(x)m3(x)m5(x)=x10+x8+x5+x4+x2+x+1，degg3(x)=n-k=10，k=15-10=5，这是，这是(15,5)BCH码。码。若若t=4，g4(x)=LCMm1(x),m3
42、(x),m5(x),m7(x)=m1(x)m3(x)m5(x)m7(x)=x14+x13+x12+x11+x10+x9+x8+x7+x6+x5+x4+x3+x2+x+1degg4(x)=n-k=14，k=15-14=1，这是，这是(15,1)BCH码。码。第60页/共86页若若t=5，g5(x)=LCMm1(x),m3(x),m5(x),m7(x),m9(x)=m1(x)m3(x)m5(x)m7(x)=g4(x)若若t=6，g6(x)=LCMm1(x),m3(x),m5(x),m7(x),m9(x),m11(x)=m1(x)m3(x)m5(x)m7(x)=g4(x)若若t=7，g7(x)=LC
43、Mm1(x),m3(x),m5(x),m7(x),m9(x),m11(x),m13(x)=m1(x)m3(x)m5(x)m7(x)=g4(x)可见，当可见，当t=4、5、6、7时的时的BCH码均是码均是(15,1)码，码，生成多项式生成多项式g4(x)拥有拥有x的所有各次幂，意味着编码的所有各次幂，意味着编码时将一位信息时将一位信息“0”或或“1”重复发送重复发送15次。因此，次。因此，实际上只有实际上只有t=1,2,3的的(15,11)、(15,7)、(15,5)BCH码码才有实用价值。才有实用价值。第61页/共86页 非本原非本原BCH码与本原码与本原BCH码的主要区别码的主要区别在于所用
44、的根是否本原元在于所用的根是否本原元。当码长当码长n和纠错能力和纠错能力t给定后，本原给定后，本原BCH码码的根的根 一定是一定是n=2m-1阶阶,n已知就是已知就是m已知，因已知，因而而GF(qm)好找。好找。非本原非本原BCH码的根码的根 是是n阶元素阶元素,满足满足n|(qm-1)，n已知不等于已知不等于m已知，需要多一道计已知，需要多一道计算。算。第62页/共86页已知已知n和和t后二元非本原后二元非本原BCH码的设计步骤：码的设计步骤：求出满足求出满足 n|(2m-1)关系的关系的m的最小值。的最小值。n是是(2m-1)的因子，可以借助的因子，可以借助2m-1的素因子分解表（如表的素
45、因子分解表（如表4-7）来寻找来寻找m值。值。查表查表4-5，找出一个，找出一个m阶的本原多项式阶的本原多项式P(x)，产生一个二元扩域产生一个二元扩域GF(2m)。以以P(x)的根的根 为中介找出一个为中介找出一个n阶的非本原元阶的非本原元。计算与计算与、3、5 2t-1对应的最小多项式对应的最小多项式m1(x)、m3(x)m2t-1(x)。求生成多项式求生成多项式g(x)=LCMm1(x)m3(x)m2t-1(x)。第63页/共86页表表4-72m-1的素因子分解（的素因子分解（m34）m 素因子分解素因子分解 m素因子分解素因子分解m素因子分解素因子分解12345678910111373
46、 5313 3 71273 5 177 733 11 3123 8912131415161718192021223 3 5 7 1381913 43 1277 31 1513 5 17 2571310713 3 3 7 19 735242873 5 5 1l 31 417 7 127 3373 23 89 683232425262728293031323347 1784813 3 5 7 13 17 24131 601 18013 2731 81917 73 2626573 5 29 43 113 127233 1103 20893 3 7 11 31 151 33121474836473 5
47、 17 257 655377 23 89 599479第64页/共86页例例4.9试设计一个码长试设计一个码长n=23，纠两个随机差错，纠两个随机差错(t=2)的二元的二元BCH码。码。解：解：由于码长由于码长n 2m-1比如比如15、31、255等值，可知等值，可知要求设计的是二元非本原要求设计的是二元非本原BCH码。检查能被码。检查能被n=23整除的整除的2m-1(表表4-7)，m的最小值是的最小值是11(211-1=2047=8923,能够整除能够整除23)，所，所以取以取m=11。查表查表4-5,得得11阶的本原多项式是阶的本原多项式是P(x)=x11+x2+1。令令 是本原多项式是本
48、原多项式P(x)的根，满足的根，满足 11+2+1=0。由于。由于 是本原是本原元，它的阶数是元，它的阶数是211-1=2047，满足，满足 2047=1。为了得到为了得到23阶域元素，将阶域元素，将 2047=1改写为改写为 2047=8923=(89)23=()23=1,式中式中=89。事实上，事实上，0,1,2,3,2047本身都是域元素，本身都是域元素，只是将域只是将域元素元素 89定义为域元素定义为域元素 而已。由于而已。由于(89)23=()23=1，因此可，因此可断言断言 是一个是一个23阶的非本原元。阶的非本原元。第65页/共86页 求求 连续奇幂次的根所对应的最小多项式。连续
49、奇幂次的根所对应的最小多项式。首先找出首先找出 的所有共轭元，然后再来计算最小多的所有共轭元，然后再来计算最小多项式。项式。的共轭元有：的共轭元有：,2,4,8,16,32=23 9=9,18,36=23 13=13,26=3,6,12,24=。因因 24=完成了一个周期，所以这个周期的完成了一个周期，所以这个周期的11个域元素个域元素都是共轭元。将它们重新按幂次顺序排列就是：都是共轭元。将它们重新按幂次顺序排列就是：,2,3,4,6,8,9,12,13,16,18。由此可断定该。由此可断定该BCH码的生成多项式码的生成多项式g(x)至少是至少是11次多项式，有次多项式，有11个根。个根。同理
50、可得另一组共轭元同理可得另一组共轭元 5,10,20,17,11,22,21,19,15,7,14，也是，也是11个。个。第66页/共86页第一组第一组 所对应的最小多项式为所对应的最小多项式为m1(x)=(x+)(x+2)(x+3)(x+4)(x+6)(x+8)(x+9)(x+12)(x+13)(x+16)(x+18)=x11+x9+x7+x6+x5+x+1在上式运算过程中用到在上式运算过程中用到 23=1,=89,11+2+1=0等关系式。等关系式。本题本题t=2，和和 3是共轭元是共轭元,m1(x)=m3(x)g(x)=LCMm1(x)m3(x)=m1(x)=x11+x9+x7+x6+x