第四讲——循环码与近世代数补充.ppt

第四讲,循环码与近世代数补充,回顾,编码设计就是在n维有限域空间中找到抽取2k个许用码字的方法，方法数非常巨大为了简化好码搜索、便于分析及简化译码方法，引入了线性约束，即只研究线性分组码但只有线性分组约束还不够，例如对码距的分析仍很复杂，译码算法随n-k指数增涨因此需要引入进一步的约束,循环码一种特殊的线性分组码,循环算子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)也是许用码字循环码：C及它的任意次循环得到的码字之间任意线性组合都是许用码字。,循环码的生成元,显然，任取一个码字，集合C,L(C),L2(C),L3(C),.及其线性组合，构成了一个线性循环子码，C就称为这个线性循环子码的生成元问题：能否用生成元完全描述循环码？满足什么样条件的循环码可以有较好的距离特性？,多项式的引入,如果将码字描述成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)是等价的？这些都是下面要研究的便于分析,近世代数的引入,事实上，用多项式表示的循环码可以充分利用近世代数的知识，形成一套较完整的描述和研究方法为了深入了解循环码的原理与研究方法，有必要补充一些近世代数特别是有限域的知识。下面将不加证明地引入一系列重要的定义和定理，具体证明和相关推论可参考有关书籍,代数基础,群子群陪集环子环理想：如果I是R的子环，在R中任取r，在I中任取a，均有ar=ra属于I，则I为R的一个理想,环（续）,主理想：可换环中，I(a)=ra+na|rR,nZ为R的一个主理想（其中na表示n个a相加）。a为该主理想的生成元。多项式剩余类环：以一个多项式为模的剩余类环以f(x)为生成元，生成理想If(x)，以此理想把Fp(x)（GF(p)上的多项式全体）的陪集构成模f(x)的剩余类环（乘法为模f(x)的多项式乘法）,域的乘法结构,循环群，据群所定义的加法，对某一个元（生成元）任意次重复运算得到的群（包括零元）。（在域中我们所考虑的循环群指的是域中的乘法群）元素的级数：对元素a，满足na=0的最小的非0的n即为a的级。有限循环群的阶数：生成元的级,域的乘法结构（续）,阶为n的循环群中每个元素的级都是n的因子，因此当n为素数时任何非零元的级都是n，即都是生成元域的乘法群必为某一个元素生成的循环群，即q元域中必能找到一个，其阶为q-1。即所有有限域元素都能表示成生成元的幂次的形式，此时的生成元称为本原元。因此当q-1为素数时，任何非零元都是生成元和本原元,域的加法结构,域的特征：满足ne=0的最小n值为域的特征，注意这里e为乘法单位元，0为域的零元，n取自正整数元素的周期：对域中元素a，满足na=0的最小n值为a的周期。（注意对于域而言，在加法上用周期，在乘法上用级）,域的加法结构（续）,域中非0元的周期都相同，且与域的特征相等有限域的域整数：即单位元的n次相加构成的素子域，它与模p的整数域GF(p)同构GP(p)为GF(pm)的基域，GF(pm)为GF(p)的扩域,域的多项式结构,对GF(p)上的多项式f(x)，若有一个根为w，则也是该多项式的根，据此可望写出其一组根，甚至全部根而若wGF(pm)，则有=w。当w的级为pm-1时，w,wp,构成f(x)的共轭根系。共轭根系中的各根均不相等,域的多项式结构,系数取自GF(p)的，以w为根的所有首一多项式中，次数最低的称为w的最小多项式m(x)，w的最小多项式的次数m称为w的次数，称w为m次域元素m(x)在GF(p)上不可约若w也是f(x)的根，则m(x)可整除f(x)若w取自GF(pm)，则有m(x)可整除,最小多项式与本原多项式,m次域元素的最小多项式，在GF(p)上不可约，但在GF(pm)上可以完全分解成一次因式之积。在GF(pm)中，以本原元为根的最小多项式称为该域的本原多项式GF(pm)的本原多项式的根级数均为pm-1，且本原多项式必为m次多项式,最小多项式的根,w为最小多项式的根，若w是特征为p的有限域F上的m次元素，则所有小于m次的多项式f(x)将w代入，得到的集合构成pm阶子域。（以最小多项式为模）对于m次元素w，有1,w,w2,wm-1线性无关，可作为域空间的基,多项式的周期,多项式的周期，对多项式f(x)，它所能整除的xL-1中最小的L值称为f(x)的周期。对GF(p)上的m次本原多项式f(x)，其周期为pm-1,有限域的阶（元素个数）必为其特征（素子域的阶）之幂GF(p)上的d次即约多项式f(x)，其多项式剩余类集合Fpx/f(x)构成pd阶扩域GF(pd)，且