信息论和编码.pptx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《信息论和编码.pptx》由会员分享,可在线阅读,更多相关《信息论和编码.pptx(86页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
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互素。互素。这就解释了为什
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息论 编码
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内