循环码与近世代数补充

1、第四讲循环码与近世代数补充回顾 编码设计就是在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

2、(C)也是许用码字 循环码： C及它的任意次循环得到的码字之间任意线性组合都是许用码字。 注意：这里提到线性组合，就意味着要定义符号间的加法和乘法，为了简化分析，我们只考虑码字序列中的符号只取自于有限域的情况（定义了两种运算的符号集不一定要求是有限域）。循环码的生成元 显然，任取一个码字，集合C, L(C), L2(C), L3(C), .及其线性组合，构成了一个线性循环子码，C就称为这个线性循环子码的生成元 问题：能否用生成元完全描述循环码？满足什么样条件的循环码可以有较好的距离特性？多项式的引入 如果将码字描述成n阶多项式的形式，A(x)= an-1xn-1+an-2xn-2 +an-3x

3、n-3+ +a2x2+a1,x+a0，则循环算子就可以描述为L(A(x)=xA(x) mod (xn-1) 便于描述：对于循环码定义，给定生成元所对应的多项式为A(x)，则对任何一个多项式D(x)，有D(x)A(x) mod (xn-1)为许用码字多项式的引入（续） 这里并没有限定D(x)的幂次，但可以肯定的一点是不同的D(x)A(x) mod (xn-1)是有限的，因为幂次小于n的有限域上的多项式是有限的。 许用码字个数由A(x)决定，这也决定了码集的冗余度和纠错能力，什么样的A(x)可以得到什么样的冗余度？哪些A(x)是等价的？这些都是下面要研究的多项式的引入（续） 便于分析 当A(x)与

4、(xn-1)的最高次公因式为g(x)时，A(x)=g(x)b(x)， (xn-1)=g(x)h(x)，当D(x)=q(x)h(x)+r(x)，r(x)幂次小于h(x)的幂次时，有：D(x)*A(x)mod (xn-1) =q(x)h(x)g(x)b(x)+r(x)A(x)mod (xn-1) =r(x)A(x)mod (xn-1) 。也就是说对幂次高于h(x)幂次减1的D(x)，所得的码多项式必与幂次低于h(x)的多项次所生成的码相同。 即许用码字个数不大于幂次低于h(x)的多项式个数。多项式的引入 而如果有两个幂次小于h(x)的多项式r1(x)和r2(x)，它们与A(x)作模(xn-1) 相

5、乘有相同的结果，则有r1(x)- r1(x)g(x)b(x) =q(x)g(x)h(x) = r1(x)- r2(x)b(x)modh(x)=0 = r1(x)- r2(x) =0。 因此许用码字个数必等于幂次低于h(x)的多项式个数。近世代数的引入 事实上，用多项式表示的循环码可以充分利用近世代数的知识，形成一套较完整的描述和研究方法 为了深入了解循环码的原理与研究方法，有必要补充一些近世代数特别是有限域的知识。下面将不加证明地引入一系列重要的定义和定理，具体证明和相关推论可参考有关书籍代数基础 群 子群 陪集 环 子环 理想：如果I是R的子环，在R中任取r，在I中任取a，均有ar=ra属于

6、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的级。 有限循环群的阶数：生成元的级域的乘法结构（

7、续） 阶为n的循环群中每个元素的级都是n的因子，因此当n为素数时任何非零元的级都是n，即都是生成元 域的乘法群必为某一个元素生成的循环群，即q元域中必能找到一个，其阶为q-1。即所有有限域元素都能表示成生成元的幂次的形式，此时的生成元称为本原元。因此当q-1为素数时，任何非零元都是生成元和本原元域的加法结构 域的特征：满足ne=0的最小n值为域的特征，注意这里e为乘法单位元，0为域的零元，n取自正整数 元素的周期：对域中元素a，满足na=0的最小n值为a的周期。（注意对于域而言，在加法上用周期，在乘法上用级）域的加法结构（续） 域中非0元的周期都相同，且与域的特征相等 有限域的域整数：即单位元

8、的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)的共轭根系。共轭根系中的各根均不相等npw2pw1mpwmpw域的多项式结构（续） 系数取自GF(p)的，以w为根的所有首一多项式中，次数最低的称为w的最小多项式m(x)，w的最小多项式的次数m称为w的次数，称w为m次域元素 m(x)在GF(p)上不可约 若w也是f(x)

9、的根，则m(x)可整除f(x) 若w取自GF(pm)，则有m(x)可整除xxmp最小多项式与本原多项式 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