多项式环及循环码

多项式环及循环码1第一页，共七十九页，编辑于2023年，星期日一种特殊的线性分组码循环算子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第二页，共七十九页，编辑于2023年，星期日循环码的描述问题：如何构造和描述一个循环码？满足什么样条件的循环码可以有较好的距离特性？3第三页，共七十九页，编辑于2023年，星期日多项式的引入如果将码字描述成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)决定，这也决定了码集的冗余度和纠错能力，什么样的A(x)可以得到什么样的冗余度？哪些A(x)是等价的？4第四页，共七十九页，编辑于2023年，星期日第一节多项式与多项式环5第五页，共七十九页，编辑于2023年，星期日要求掌握的内容多项式剩余类环循环群6第六页，共七十九页，编辑于2023年，星期日一、复习几个概念同余、剩余类群环域7第七页，共七十九页，编辑于2023年，星期日同余和剩余类(p23)同余：若整数a和b被同一正整数m除时，有相同的余数，则称a、b关于模m同余，记为剩余类(Residue)：给定正整数m，可将全体整数按余数相同进行分类，可获得m个剩余类，分别用8第八页，共七十九页，编辑于2023年，星期日群(Group)的定义(p26)设G是一个非空集合，并在G内定义了一种代数运算“。”，若满足：1)封闭性。对任意，恒有2)结合律。对任意，恒有3)G中存在一恒等元e,对任意，使4)对任意，存在a的逆元，使则称G构成一个群。若加法，恒等元用0表示，若为乘法，恒等元称为单位元9第九页，共七十九页，编辑于2023年，星期日环(Ring)的定义(p30)非空集合R中，若定义了两种代数运算加和乘，且满足：

1)集合R在加法运算下构成阿贝尔群

2)乘法有封闭性

3)乘法结合律成立，且加和乘之间有分配律10第十页，共七十九页，编辑于2023年，星期日子环、理想和主理想(P101)子环：若环R中的子集S，在环R中的定义的代数运算也构成环，则称S为R的子环。理想：S是R的一个子环，若S中的元素由某几个元素及其所有可能的倍数构成，则S是一个理想主理想：若理想中的元素由一个元素的所有倍数及其线性组合生成，则称这个理想为主理想。11第十一页，共七十九页，编辑于2023年，星期日二、多项式剩余类环(P103)有关多项式的几个概念多项式的加法和乘法多项式剩余类环的定义12第十二页，共七十九页，编辑于2023年，星期日多项式

f(x)=fnxn+fn-1xn-1+…+f1x+f0其中i=0,1,…n，该多项式称为域Fp上的多项式多项式次数degf(x)

系数不为零的x的最高次数称为多项式f(x)的次数首一多项式最高次数的系数为1的多项式有关多项式的几个概念13第十三页，共七十九页，编辑于2023年，星期日既约多项式设f(x)是次数大于零的多项式，若除常数和常数与本身的乘积以外，再不能被域Fp上的其他多项式整除，则称f(x)为域Fp上的既约多项式

有关多项式的几个概念14第十四页，共七十九页，编辑于2023年，星期日f(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)多项式乘法结论：按上述定义的加法和乘法运算，Fp[x]构成一个具有单位元、无零因子的可换环多项式的加法和乘法15第十五页，共七十九页，编辑于2023年，星期日定义：以一个Fp上的多项式f(x)=fnxn+fn-1xn-1+…+f1x+f0为模的剩余类全体构成一个多项式剩余类环

Fp上的所有次数小于n-1的多项式构成n次多项式的剩余类全体

剩余类之间的加法和乘法运算规则多项式剩余类环16第十六页，共七十九页，编辑于2023年，星期日

1、GF(2)上的多项式f(x)=x2+1的剩余类全体为：2、GF(2)上的多项式f(x)=x2+x+1的剩余类全体为：对所定义的加法和乘法运算，前者构成剩余类环，后者构成域结论：若n次首一多项式f(x)在域Fp上既约，则f(x)的剩余类环构成一个有pn个元素的有限域Examples17第十七页，共七十九页，编辑于2023年，星期日两个结论多项式环Fp[x]的一切理想均是主理想多项式剩余类环Fp[x]/f(x)中的每一个理想都是主理想。18第十八页，共七十九页，编辑于2023年，星期日第2节循环码的描述19第十九页，共七十九页，编辑于2023年，星期日要求掌握的内容定义循环码的代数性质循环码的生成多项式和校验多项式循环码的生成矩阵和校验矩阵循环码的系统码形式20第二十页，共七十九页，编辑于2023年，星期日定义1：设CH是一个[n.k]线性分组码，C1是其中的一个码字，若C1的左(右)循环移位得到的n维向量也是CH中的一个码字，则称CH是循环码。定义2：设是n维空间的一个k维子空间，若对任一恒有则称Vn,k为循环子空间或循环码一、循环码定义21第二十一页，共七十九页，编辑于2023年，星期日将码字看成如下多项式的系数:循环码码字与多项式之间的关系因此，循环码的每个码字对应一个次数小于等于n-1的多项式。若，则V(x)为n-1次多项式，若vn-1=0。则V(x)为次数小于n-1的多项式。并且，码字与多项式之间是一一对应的。22第二十二页，共七十九页，编辑于2023年，星期日二、循环码的代数性质假设有两个码多项式则有23第二十三页，共七十九页，编辑于2023年，星期日二、循环码的代数性质

定理4.1循环码C中次数最低的非零码多项式是唯一的。由于循环码是线性码，因此证明：令为循环码中次数最低的一个非零多项式。假设该多项式不唯一，即存在另一个次数为r的多项式是一个次数比r更低的码多项式。24第二十四页，共七十九页，编辑于2023年，星期日二、循环码的代数性质

定理4.1循环码C中次数最低的非零码多项式是唯一的。即证明：若则是一个次数比r更低的非零码多项式。因此，g(x)是唯一的。这与假设相矛盾，因此必有25第二十五页，共七十九页，编辑于2023年，星期日二、循环码的代数性质

定理4.2令为循环码C中最低次数的非零码多项式，则常数项g0一定等于1。证明：假设这与之前假设g(x)是次数最低的非零码多项式相矛盾。则上式表明，如果将g(x)循环左移一位，可以得到一个次数低于r的非零码多项式因此，必有26第二十六页，共七十九页，编辑于2023年，星期日由定理4.2可知，次数最低的非零码多项式具有如下形式考虑多项式，它们的次数分别为，且是g(x)的循环移位。因此，由循环码的定义，它们一定是循环码的码多项式，且它们的线性组合也一定是一个码多项式，即是一个码多项式，其中27第二十七页，共七十九页，编辑于2023年，星期日定理4-3

设是(n,k)循环码的最低次数非零码多项式，次数小于或等于n-1的多项式为码多项式，当且仅当它是g(x)的倍式。证明：令是次数小于等于n-1的二进制多项式，且为g(x)的倍式。由于是码多项式的线性组合，因此它一定是一个码多项式。28第二十八页，共七十九页，编辑于2023年，星期日证明：假设是循环码中的码多项式，我们可得到因此有由于和都是码多项式，因此b(x)必为码多项式。若，则b(x)必为次数小于g(x)的非零码多项式，与g(x)为次数最低码多项式相矛盾，因此b(x)=0。因此，码多项式必为g(x)的倍式。29第二十九页，共七十九页，编辑于2023年，星期日定理4-4(p147)

(n,k)循环码中，有且仅有一个次数为n-k的码多项式每一个码多项式是g(x)的倍式，且每个次数不大于n-1且为g(x)的倍式的多项式必为一码多项式。由于码多项式是g(x)及其倍式的线性组合，即可知共有个元素，构成维数为n-r的线性空间，而[n,k]循环码中共有个码字。因此有即30第三十页，共七十九页，编辑于2023年，星期日注：由上述定理，(n,k)循环码的每一个码多项式可表示为生成多项式的次数等于码中校验位的个数，即等于n-k.其中是待编码的信息比特，v(x)是对应的码多项式。因此，可利用乘以消息多项式来完成编码，即一个[n,k]循环码的码字可由非零最小次数多项式完全确定，称该多项式为循环码的生成多项式。31第三十一页，共七十九页，编辑于2023年，星期日问题：如何寻找生成多项式g(x)？32第三十二页，共七十九页，编辑于2023年，星期日三、生成多项式

定理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第三十三页，共七十九页，编辑于2023年，星期日三、生成多项式结论1:找一个[n,k]循环码，即是找一个n-k次首一多项式g(x)，且g(x)必是xn-1的因式。结论2:若C(x)是一个码多项式，则反之，若，则C(x)必是一个码多项式34第三十四页，共七十九页，编辑于2023年，星期日g(x)决定生成矩阵，h(x)决定校验矩阵四、循环码的生成矩阵和校验矩阵35第三十五页，共七十九页，编辑于2023年，星期日36第三十六页，共七十九页，编辑于2023年，星期日37第三十七页，共七十九页，编辑于2023年，星期日ExamplesGF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1)

试求一个[7,4]循环码。g(x)、xg(x)、x2

g(x)、x3g(x)、38第三十八页，共七十九页，编辑于2023年，星期日五、循环码的系统码(P151)39第三十九页，共七十九页，编辑于2023年，星期日由于生成矩阵G中的k行要求线性无关，因此在求余式时，可选择k个线性无关的信息组(1,0,0,…,0)xk-1，(0,1,0,0,…0)xk-2,

…(0,0,0,…,0,1)140第四十页，共七十九页，编辑于2023年，星期日表示ri(x)的系数41第四十一页，共七十九页，编辑于2023年，星期日42第四十二页，共七十九页，编辑于2023年，星期日循环码的编码原理(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第四十三页，共七十九页，编辑于2023年，星期日可选择k个线性无关的信息组(1,0,0,…,0)xk-1，(0,1,0,0,…0)xk-2,

…(0,0,0,…,0,1)1循环码的编码原理(2)44第四十四页，共七十九页，编辑于2023年，星期日表示ri(x)的系数45第四十五页，共七十九页，编辑于2023年，星期日第3节循环码的编码电路(P165,174)多项式乘法和除法电路循环码的编码电路(乘法和除法)46第四十六页，共七十九页，编辑于2023年，星期日一、多项式乘法和除法电路47第四十七页，共七十九页，编辑于2023年，星期日48第四十八页，共七十九页，编辑于2023年，星期日b0b1b2br-2br-1br输出C(x)输入A(x)a0,a1,…ak乘B(x)运算电路(利用校验多项式h(x)编码时会用到)49第四十九页，共七十九页，编辑于2023年，星期日b0b1b2br-2br-1br输出C(x)输入A(x)a0,a1,…ak乘B(x)运算电路akb0akb1akbr-2akbr-150第五十页，共七十九页，编辑于2023年，星期日-b1br-1输出商q(x)输入A(x)-b2-br-1-b0除B(x)运算电路a0,a1,…ak除式B(x)构成电路，被除式A(x)的系数依次送入电路51第五十一页，共七十九页，编辑于2023年，星期日h0h1h2hr-2hr-1输入A(x)a0,a1,…ak-g1gr-1输出商q(x)-g2-g0-gr-1-gr-1乘H(x),除g(x)运算电路hr52第五十二页，共七十九页，编辑于2023年，星期日二、循环码编码电路(P174)53第五十三页，共七十九页，编辑于2023年，星期日54第五十四页，共七十九页，编辑于2023年，星期日n-k

级编码器基本原理：利用生成多项式g(x)若要求编成非系统码形式，则利用乘法电路若要求编成系统码形式，则利用除法电路55第五十五页，共七十九页，编辑于2023年，星期日n-k级乘法电路(非系统码形式)取g(x),xg(x),…xk-1g(x)的系数可构成生成矩阵G56第五十六页，共七十九页，编辑于2023年，星期日n-k级乘法电路(非系统码形式)若信息序列m=(mk-1,mk-2,…m0),则mG对应的n维向量为：该n维向量正是多项式m(x)g(x)的系数57第五十七页，共七十九页，编辑于2023年，星期日g0g1g2gn-k-2gn-k-1gn-k输出C(x)输入m(x)m0,m1,…mk-1乘g(x)运算电路mk-1gn-k-1mk-1

gn-k输入m(x)是信息序列，g(x)为生成多项式mk-1g0mk-1g158第五十八页，共七十九页，编辑于2023年，星期日ExamplesGF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1)试画一个[7,4]循环码的n-k级乘法编码电路。59第五十九页，共七十九页，编辑于2023年，星期日n-k级除法电路(系统码形式)(1,0,0,…,0)xk-1，(0,1,0,0,…0)xk-2,

…(0,0,0,…,0,1)160第六十页，共七十九页，编辑于2023年，星期日表示ri(x)的系数61第六十一页，共七十九页，编辑于2023年，星期日n-k级除法电路(系统码形式)对任意信息多项式m(x),xn-km(x)除g(x)可得余式r(x)，m(x)的系数为信息序列mr(x)的系数为m对应的校验比特62第六十二页，共七十九页，编辑于2023年，星期日n-k级除法电路(系统码形式)若信息序列m=(mk-1,mk-2,…m0)对应的多项式m(x)=mk-1xk-1+mk-2xk-2+…+m063第六十三页，共七十九页，编辑于2023年，星期日n-k级除法电路(系统码形式)综上，循环码的系统码电路是信息多项式m(x)乘xn-k,除g(x)的实现电路64第六十四页，共七十九页，编辑于2023年，星期日输入m(x)m0,m1,…mk-1-g1gn-k-1-g2-g0-gn-k-1-gn-k-2乘xn-k除g(x)运算电路门165第六十五页，共七十九页，编辑于2023年，星期日k

级编码器基本原理：利用校验多项式h(x)为系统码编码电路66第六十六页，共七十九页，编辑于2023年，星期日k

级编码器若信息序列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)=m(x)(xn-1)=m(x)xn-m(x)=mk-1xn+k-1+mk-2xn+k-2+…+m0xn

-(mk-1xk-1+mk-2xk-2+…m0)67第六十七页，共七十九页，编辑于2023年，星期日k

级编码器h(x)C(x)的乘积中，xn-1,xn-2,…

xk次的系数为零xn-1的系数h0

cn-1+h1

cn-1-1+

…+hkcn-1-k=0xn-2的系数h0

cn-2+h1

cn-2-1+

…+hkcn-2-k=0xn-3的系数h0

cn-3+h1

cn-3-1+

…+hkcn-3-k=0xk的系数h0

ck

+h1

ck-1+

…+hkc0=068第六十八页，共七十九页，编辑于2023年，星期日k

级编码器由于hk=1cn-1-k

=-

(h0

cn-1+h1

cn-1-1+

…