第四章多项式环及循环码精选PPT.ppt

《第四章多项式环及循环码精选PPT.ppt》由会员分享，可在线阅读，更多相关《第四章多项式环及循环码精选PPT.ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章多项式环及循环码第1页，此课件共79页哦1一种特殊的线性分组码一种特殊的线性分组码循环算子循环算子L：对：对n重码字重码字A=(an-1,an-2,an-3,a2,a1,a0)，有，有B=L(A)=(bn-1,bn-2,bn-3,b2,b1,b0)=(an-2,an-3,a2,a1,a0,an-1)循环特性：循环特性：对任意许用码字对任意许用码字C，则，则L(C)也是许用码字也是许用码字循环码：循环码：一个一个(n,k)线性码线性码C，如果每个码字的循环移位仍是一，如果每个码字的循环移位仍是一个码字个码字,称该码为循环码。称该码为循环码。第2页，此课件共79页哦2循环码的描述循环码的描述

2、问题：如何构造和描述一个循环码？满足什么样条件的问题：如何构造和描述一个循环码？满足什么样条件的循环码可以有较好的距离特性？循环码可以有较好的距离特性？第3页，此课件共79页哦3多项式的引入多项式的引入如果将码字描述成n阶多项式的形式，A(x)=an-1xn-1+an-2xn-2+an-3xn-3+a2x2+a1,x+a0，则循环算法就可以描述为L(A(x)=xA(x)mod(xn-1)便于描述：对任何一个多项式D(x)，有D(x)A(x)mod(xn-1)为许用码字，这里并没有限定D(x)的幂次，但可以肯定的一点是不同的D(x)A(x)mod(xn-1)是有限的，其个数由A(x)决定，这也决

3、定了码集的冗余度和纠错能力，什么样的A(x)可以得到什么样的冗余度？哪些A(x)是等价的？第4页，此课件共79页哦4第一节 多项式与多项式环第5页，此课件共79页哦5要求掌握的内容要求掌握的内容多项式剩余类环多项式剩余类环循环群循环群第6页，此课件共79页哦6一、复习几个概念一、复习几个概念同余、剩余类同余、剩余类群群环环域域第7页，此课件共79页哦7同余和剩余类(p23)同余同余：若整数a和b被同一正整数m除时，有相同的余数，则称a、b关于模m同余，记为剩余类剩余类(Residue)：给定正整数m，可将全体整数按余数相同进行分类，可获得m个剩余类，分别用第8页，此课件共79页哦8群(Grou

4、p)的定义(p26)设设G是一个非空集合，并在是一个非空集合，并在G内定义了一种代内定义了一种代数运算数运算“。”，若满足：，若满足：1)封闭性。对任意封闭性。对任意，恒有，恒有2)结合律。对任意结合律。对任意，恒有，恒有3)G中存在一恒等元中存在一恒等元e,对任意对任意，使，使4)对任意对任意，存在，存在a的逆元的逆元，使，使则称则称G构成一个群。若加法，恒等元用构成一个群。若加法，恒等元用0表示，表示，若为乘法，恒等元称为单位元若为乘法，恒等元称为单位元第9页，此课件共79页哦9环环(Ring)的定义的定义(p30)非空集合非空集合R中，若定义了两种代数运算加和中，若定义了两种代数运算加和

5、乘，且满足：乘，且满足：1)集合集合R在加法运算下构成阿贝尔群在加法运算下构成阿贝尔群 2)乘法有封闭性乘法有封闭性 3)乘法结合律成立，且加和乘之间有分配乘法结合律成立，且加和乘之间有分配律律第10页，此课件共79页哦10子环、理想和主理想子环、理想和主理想(P101)子环：若环子环：若环R中的子集中的子集S，在环，在环R中的定义的代数运算也构成中的定义的代数运算也构成环，则称环，则称S为为R的子环。的子环。理想：理想：S是是R的一个子环，若的一个子环，若S中的元素由某几个元素及其中的元素由某几个元素及其所有可能的倍数构成，则所有可能的倍数构成，则S是一个理想是一个理想 主理想：若理想中的元

6、素由一个元素的所有倍数及其线性组合生主理想：若理想中的元素由一个元素的所有倍数及其线性组合生成，则称这个理想为主理想。成，则称这个理想为主理想。第11页，此课件共79页哦11二、多项式剩余类环二、多项式剩余类环(P103)有关多项式的几个概念有关多项式的几个概念多项式的加法和乘法多项式的加法和乘法多项式剩余类环的定义多项式剩余类环的定义第12页，此课件共79页哦12多项式多项式 f(x)=fnxn+fn-1xn-1+f1x+f0其中i=0,1,n，该多项式称为域Fp上的多项式多项式次数多项式次数 degf(x)系数不为零的x的最高次数称为多项式f(x)的次数首一多项式首一多项式 最高次数的系数

7、为1的多项式有关多项式的几个概念有关多项式的几个概念第13页，此课件共79页哦13 既约多项式既约多项式 设f(x)是次数大于零的多项式，若除常数和常数与本身的乘积以外，再不能被域Fp上的其他多项式整除，则称f(x)为域Fp上的既约多项式 有关多项式的几个概念有关多项式的几个概念第14页，此课件共79页哦14f(x)=fnxn+fn-1xn-1+f1x+f0g(x)=gnxn+gn-1xn-1+g1x+g0若对所有若对所有i,fi=gi,则则f(x)=g(x)多项式加法多项式加法f(x)+g(x)=(fn+gn)xn+(fn-1+gn-1)xn-1+(f1+g1)x+(f0+g0)多项式乘法多

8、项式乘法结论：按上述定义的加法和乘法运算，Fpx构成一个具有单位元、无零因子的可换环多项式的加法和乘法多项式的加法和乘法第15页，此课件共79页哦15定义定义：以一个Fp上的多项式f(x)=fnxn+fn-1xn-1+f1x+f0为模的剩余类全体构成一个多项式剩余类环 Fp上的所有次数小于n-1的多项式构成n次多项式的剩余类全体 剩余类之间的加法和乘法运算规则多项式剩余类环多项式剩余类环第16页，此课件共79页哦16 1、GF(2)上的多项式 f(x)=x2+1的剩余类全体为：2、GF(2)上的多项式 f(x)=x2+x+1的剩余类全体为：对所定义的加法和乘法运算，前者构成剩余类环，后者构成域

9、结论：若n次首一多项式f(x)在域Fp上既约，则f(x)的剩余类环构成一个有pn个元素的有限域Examples第17页，此课件共79页哦17两个结论两个结论多项式环多项式环Fpx的一切理想均是主理想的一切理想均是主理想多项式剩余类环多项式剩余类环Fpx/f(x)中的每一个理想都中的每一个理想都是主理想。是主理想。第18页，此课件共79页哦18第第2节节 循环码的描述循环码的描述第19页，此课件共79页哦19要求掌握的内容要求掌握的内容定义定义循环码的代数性质循环码的代数性质循环码的生成多项式和校验多项式循环码的生成多项式和校验多项式循环码的生成矩阵和校验矩阵循环码的生成矩阵和校验矩阵循环码的系

10、统码形式循环码的系统码形式第20页，此课件共79页哦20 定义定义1：设设CH是一个是一个n.k线性分组码，线性分组码，C1是其中的一个码字，是其中的一个码字，若若C1的左的左(右右)循环移位得到的循环移位得到的n维向量也是维向量也是CH中的一个码字，中的一个码字，则称则称CH是循环码。是循环码。定义定义2：设：设是是n维空间的一个维空间的一个k维子空间，维子空间，若对任一若对任一恒有恒有则称则称Vn,k为循环子空间或循环码为循环子空间或循环码一、循环码定义一、循环码定义第21页，此课件共79页哦21将码字将码字 看成如下多项式的系数看成如下多项式的系数:循环码码字与多项式之间的关系循环码码字

11、与多项式之间的关系因此，循环码的每个码字对应一个次数小于等于因此，循环码的每个码字对应一个次数小于等于n-1的多项式。的多项式。若若 ，则，则V(x)为为n-1次多项式，若次多项式，若vn-1=0。则。则V(x)为次为次数小于数小于n-1的多项式。的多项式。并且，码字与多项式之间是一一对应的。并且，码字与多项式之间是一一对应的。第22页，此课件共79页哦22二、循环码的代数性质二、循环码的代数性质 假设有两个码多项式假设有两个码多项式 则有则有第23页，此课件共79页哦23二、循环码的代数性质二、循环码的代数性质 定理定理4.1 循环码循环码C中次数最低的非零码多项式是唯一的。中次数最低的非零

12、码多项式是唯一的。由于循环码是线性码，因此由于循环码是线性码，因此 证明：令证明：令 为循环码中次数最低的一个非零多项式。假设该多项式不唯一，即存在另为循环码中次数最低的一个非零多项式。假设该多项式不唯一，即存在另一个次数为一个次数为r的多项式的多项式 是一个次数比是一个次数比r更低的码多项式。更低的码多项式。第24页，此课件共79页哦24二、循环码的代数性质二、循环码的代数性质 定理定理4.1 循环码循环码C中次数最低的非零码多项式是唯一的。中次数最低的非零码多项式是唯一的。即即 证明：若证明：若 则则 是一个次数比是一个次数比r更低的非零码多项式。更低的非零码多项式。因此，因此，g(x)是

13、唯一的。是唯一的。这与假设相矛盾，因此必有这与假设相矛盾，因此必有第25页，此课件共79页哦25二、循环码的代数性质二、循环码的代数性质 定理定理4.2 令令 为循环码为循环码C中最低次数的非零码多项式，中最低次数的非零码多项式，则常数项则常数项g0一定等于一定等于1。证明：假设证明：假设 这与之前假设这与之前假设g(x)是次数最低的非零码多项式相矛盾。是次数最低的非零码多项式相矛盾。则则 上式表明，如果将上式表明，如果将g(x)循环左移一位，可以得到一个次数循环左移一位，可以得到一个次数低于低于r的非零码多项式的非零码多项式 因此，必有因此，必有第26页，此课件共79页哦26由定理由定理4.

14、2可知，次数最低的非零码多项式具有如下形式可知，次数最低的非零码多项式具有如下形式考虑多项式考虑多项式 ，它们，它们的次数分别为的次数分别为 ，且是，且是g(x)的循环移的循环移位。位。因此，由循环码的定义，它们一定是循环码的码多项式，且它们的线性组合因此，由循环码的定义，它们一定是循环码的码多项式，且它们的线性组合也一定是一个码多项式，即也一定是一个码多项式，即是一个码多项式，其中是一个码多项式，其中第27页，此课件共79页哦27定理定理4-3 设设 是是(n,k)循环码的最低次数循环码的最低次数非零码多项式，次数小于或等于非零码多项式，次数小于或等于n-1的多项式为码多项式，当且仅的多项式

15、为码多项式，当且仅当它是当它是g(x)的倍式。的倍式。证明证明：令：令 是次数小于等于是次数小于等于n-1的二进制多项式，且为的二进制多项式，且为g(x)的的倍式。倍式。由于由于 是码多项式是码多项式 的线性的线性组合，因此它一定是一个码多项式。组合，因此它一定是一个码多项式。第28页，此课件共79页哦28 证明证明：假设：假设 是循环码中的码多项式，我们可得到是循环码中的码多项式，我们可得到 因此有因此有 由于由于 和和 都是码多项式，因此都是码多项式，因此b(x)必为码多项式。必为码多项式。若若 ，则，则b(x)必为次数小于必为次数小于g(x)的非零码多项式，与的非零码多项式，与g(x)为

16、次数最低码多项式相矛盾，因此为次数最低码多项式相矛盾，因此b(x)=0。因此，码多项式必为因此，码多项式必为g(x)的倍式。的倍式。第29页，此课件共79页哦29定理定理4-4(p147)(n,k)循环码中，有且仅有一个次数为循环码中，有且仅有一个次数为n-k的码多项式的码多项式每一个码多项式是每一个码多项式是g(x)的倍式，且每个次数不大于的倍式，且每个次数不大于n-1且为且为g(x)的倍式的倍式的多项式必为一码多项式。的多项式必为一码多项式。由于码多项式由于码多项式 是是g(x)及其倍式的线性组合，即及其倍式的线性组合，即 可知可知 共有共有 个元素，构成维数为个元素，构成维数为n-r的线

17、性空间，而的线性空间，而n,k循环码中共有循环码中共有 个码字。因此有个码字。因此有 即即第30页，此课件共79页哦30注：注：由上述定理，由上述定理，(n,k)循环码的每一个码多项式可表示为循环码的每一个码多项式可表示为生成多项式的次数等于码中校验位的个数，即等于生成多项式的次数等于码中校验位的个数，即等于n-k.其中其中 是待编码的信息比特，是待编码的信息比特，v(x)是对应的码多是对应的码多项式。项式。因此，可利用因此，可利用 乘以消息多项式乘以消息多项式 来完成编码，即一个来完成编码，即一个n,k循环码的码字可由非零最小次数多项式完全确定，称该多循环码的码字可由非零最小次数多项式完全确

18、定，称该多项式为循环码的生成多项式。项式为循环码的生成多项式。第31页，此课件共79页哦31问题：如何寻找生成多项式问题：如何寻找生成多项式g(x)？第32页，此课件共79页哦32三、生成多项式三、生成多项式 定理定理4-5(p148):GF(q)(q为素数或素数的幂为素数或素数的幂)上上n,k循环码循环码的生成多项式的生成多项式g(x)一定是一定是xn-1的的n-k次因式：次因式：xn-1=g(x)h(x)。反之，若反之，若g(x)为为n-k次多项式，且次多项式，且xn-1能被能被g(x)整除，则整除，则g(x)一定能生成一个一定能生成一个n,k循环码循环码第33页，此课件共79页哦33三、

19、生成多项式三、生成多项式 结论结论1:找一个找一个n,k循环码，即是找一个循环码，即是找一个n-k次首一多项式次首一多项式g(x)，且，且g(x)必是必是xn-1的因式。的因式。结论结论2:若若C(x)是一个码多项式，则是一个码多项式，则反之，若反之，若，则，则C(x)必是一个码多项式必是一个码多项式第34页，此课件共79页哦34g(x)决定生成矩阵，决定生成矩阵，h(x)决定校验矩阵决定校验矩阵四、循环码的生成矩阵和校验矩阵四、循环码的生成矩阵和校验矩阵第35页，此课件共79页哦35第36页，此课件共79页哦36第37页，此课件共79页哦37Examples GF(2)上，上，x7-1=(x

20、+1)(x3+x+1)(x3+x2+1)试求一个试求一个7,4循环码。循环码。g(x)、xg(x)、x2 g(x)、x3g(x)、第38页，此课件共79页哦38五、循环码的系统码五、循环码的系统码(P151)第39页，此课件共79页哦39由于生成矩阵由于生成矩阵G中的中的k行要求线性无关，因此在求余式时行要求线性无关，因此在求余式时，可选择，可选择k个线性无关的信息组个线性无关的信息组 (1,0,0,0)xk-1，(0,1,0,0,0)xk-2,(0,0,0,0,1)1第40页，此课件共79页哦40表示ri(x)的系数第41页，此课件共79页哦41第42页，此课件共79页哦42循环码的编码原理

21、循环码的编码原理(1)基本步骤基本步骤(n,k)1、分解多项式、分解多项式xn-1=g(x)h(x)2、选择其中的、选择其中的n-k次多项式次多项式g(x)为生成多项式为生成多项式3、由、由g(x)可得到可得到k个多项式个多项式g(x),xg(x),xk-1g(x)4、取上述、取上述k个多项式的系数即可构成相应的生成矩阵个多项式的系数即可构成相应的生成矩阵5、取、取h(x)的互反多项式的互反多项式h*(x),取取h*(x),xh*(x),xn-k-1h*(x)的系数即可构成相应的校验矩阵的系数即可构成相应的校验矩阵第43页，此课件共79页哦43可选择可选择k个线性无关的信息组个线性无关的信息组

22、 (1,0,0,0)xk-1，(0,1,0,0,0)xk-2,(0,0,0,0,1)1循环码的编码原理循环码的编码原理(2)第44页，此课件共79页哦44表示ri(x)的系数第45页，此课件共79页哦45第第3节节 循环码的编码电路循环码的编码电路(P165,174)多项式乘法和除法电路多项式乘法和除法电路循环码的编码电路循环码的编码电路(乘法和除法乘法和除法)第46页，此课件共79页哦46一、多项式乘法和除法电路一、多项式乘法和除法电路第47页，此课件共79页哦47第48页，此课件共79页哦48b0b1b2br-2br-1br输出C(x)输入A(x)a0,a1,ak 乘B(x)运算电路(利用

23、校验多项式h(x)编码时会用到)第49页，此课件共79页哦49b0b1b2br-2br-1br输出C(x)输入A(x)a0,a1,ak乘B(x)运算电路akb0akb1akbr-2akbr-1第50页，此课件共79页哦50-b1br-1输出商q(x)输入A(x)-b2-br-1-b0除B(x)运算电路a0,a1,ak除式除式B(x)构成电路，被除式构成电路，被除式A(x)的系数依次送入电路的系数依次送入电路第51页，此课件共79页哦51h0h1h2hr-2hr-1输入A(x)a0,a1,ak-g1gr-1输出商q(x)-g2-g0-gr-1-gr-1乘乘H(x),除除g(x)运算电路运算电路h

24、r第52页，此课件共79页哦52二、循环码编码电路二、循环码编码电路(P174)第53页，此课件共79页哦53第54页，此课件共79页哦54n-k 级编码器级编码器基本原理：利用生成多项式基本原理：利用生成多项式g(x)若要求编成非系统码形式，则利用乘法电路若要求编成非系统码形式，则利用乘法电路若要求编成系统码形式，则利用除法电路若要求编成系统码形式，则利用除法电路第55页，此课件共79页哦55n-k级乘法电路级乘法电路(非系统码形式非系统码形式)取g(x),xg(x),xk-1g(x)的系数可构成生成矩阵G第56页，此课件共79页哦56n-k级乘法电路级乘法电路(非系统码形式非系统码形式)若

25、信息序列 m=(mk-1,mk-2,m0),则mG对应的n维向量为：该n 维向量正是多项式m(x)g(x)的系数第57页，此课件共79页哦57g0g1g2gn-k-2gn-k-1gn-k输出C(x)输入m(x)m0,m1,mk-1乘g(x)运算电路mk-1 gn-k-1mk-1 gn-k输入m(x)是信息序列，g(x)为生成多项式mk-1 g0mk-1 g1第58页，此课件共79页哦58Examples GF(2)上，上，x7-1=(x+1)(x3+x+1)(x3+x2+1)试画一个试画一个7,4循环码的循环码的n-k级乘法编码电路。级乘法编码电路。第59页，此课件共79页哦59n-k级除法电

26、路级除法电路(系统码形式系统码形式)(1,0,0,0)xk-1，(0,1,0,0,0)xk-2,(0,0,0,0,1)1第60页，此课件共79页哦60表示ri(x)的系数第61页，此课件共79页哦61n-k级除法电路级除法电路(系统码形式系统码形式)对任意信息多项式m(x),xn-km(x)除g(x)可得余式r(x)，m(x)的系数为信息序列mr(x)的系数为m对应的校验比特第62页，此课件共79页哦62n-k级除法电路级除法电路(系统码形式系统码形式)若信息序列 m=(mk-1,mk-2,m0)对应的多项式m(x)=mk-1xk-1+mk-2xk-2+m0第63页，此课件共79页哦63n-k

27、级除法电路(系统码形式)综上，循环码的系统码电路是信息多项式m(x)乘xn-k,除g(x)的实现电路第64页，此课件共79页哦64输入m(x)m0,m1,mk-1-g1gn-k-1-g2-g0-gn-k-1-gn-k-2乘xn-k除g(x)运算电路门1第65页，此课件共79页哦65k 级编码器级编码器基本原理：利用校验多项式h(x)为系统码编码电路第66页，此课件共79页哦66k 级编码器级编码器若信息序列 m=(mk-1,mk-2,m0)对应的多项式m(x)=mk-1xk-1+mk-2xk-2+m0码多项式C(x)=m(x)g(x),且C(x)为系统码h(x)C(x)=h(x)m(x)g(x

28、)=m(x)(xn-1)=m(x)xn-m(x)=mk-1xn+k-1+mk-2xn+k-2+m0 xn -(mk-1xk-1+mk-2xk-2+m0)第67页，此课件共79页哦67k 级编码器级编码器h(x)C(x)的乘积中，xn-1,xn-2,xk次的系数为零xn-1的系数h0 cn-1+h1 cn-1-1+hk cn-1-k=0 xn-2的系数h0 cn-2+h1 cn-2-1+hk cn-2-k=0 xn-3的系数h0 cn-3+h1 cn-3-1+hk cn-3-k=0 xk的系数h0 ck+h1 ck-1+hk c0=0第68页，此课件共79页哦68k 级编码器级编码器由于hk=1

29、cn-1-k=-(h0 cn-1+h1 cn-1-1+hk-1 cn-1-(k-1)cn-2-k=-(h0 cn-2+h1 cn-2-1+hk-1 cn-k-1)cn-3-k=-(h0 cn-3+h1 cn-3-1+hk-1 cn-k-2)cn-k-(n-k)=-(h0 ck+h1 ck-1+hk-1 c1)第69页，此课件共79页哦69-h0-h1-h2-hk-2hk-1-输入信息门cn-1cn-2cn-k-1cn-k循环码k级编码电路第70页，此课件共79页哦70Examples:设7,4循环码的生成多项式为 g(x)=x3+x2+1，试1)写出它的校验多项式h(x)2)求出生成矩阵和校验

30、矩阵3)求出系统码的生成矩阵和校验矩阵4)画出(n-k)级系统码编码电路和k级编码电路第71页，此课件共79页哦711)h(x)=(xn-1)/g(x)=x4+x3+x2+12)h*(x)=x4+x2+x+1第72页，此课件共79页哦72第73页，此课件共79页哦73第74页，此课件共79页哦74设7,4循环码的生成多项式为g(x)=x3+x+1，试1)写出它的校验多项式h(x)2)求出生成矩阵和校验矩阵3)求出系统码的生成矩阵和校验矩阵4)画出(n-k)级系统码编码电路和k级编码电路第75页，此课件共79页哦751)h(x)=(xn-1)/g(x)=x4+x2+x+12)h*(x)=x4+x3+x2+1第76页，此课件共79页哦76第77页，此课件共79页哦77第78页，此课件共79页哦78第四节第四节 几类特殊的循环码几类特殊的循环码缩短循环码：缩短循环码：对循环码缩短得到的码对循环码缩短得到的码(p159)准循环码准循环码双环循环码双环循环码第79页，此课件共79页哦79