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

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