既约多项式：设f(x)是次数大于0的多项式，除了常数、常数与本身乘积以外，不能再被域F上其他多项式除尽，则f(x)为F域上的既约多项式。 定义8－1：给定一个多项式g(x)，把它称为模，如果两个多项式d1(x)和d2(x)满足：  则称多项式d1(x)和d2(x)对模g(x)同余。记为：d1(x)≡d2(x) ≡r(x) mod g(x) 性质：已给定多项式g(x)≠0为模，多项式d1(x)和d2(x)同余的充要条件是：  例：设模多项式为：g(x)=x3+x+1 则：d1(x)= x4+x3+1=(x+1)( x3+x+1)+ x2 d2(x)= x3+x2+x+1= x3 +x+1+x2 同余！（d1(x)－d2(x)＝x4+x2+x=xg(x)） 例：g(x)=x2+ 1  ⊕ 0 1 x x+1  0 1 x x+1 0 1 x x+1 1 0 x+1 x x x+1 0 1 x+1 x 1 0   ⊙ 0 1 x x+1  0 1 x x+1 0 0 0 0 1 0 x x+1 0 x x+1 1 0 x+1 1 x   例：g(x)=x3+x+1的剩余类多项式集合：｛0,1,x，x+1，x2，x2 +1，x2＋x，x2＋x+1｝ 与矢量集合：｛000，001，010，011，100，101，110，111｝同构。 定理8－1：设P(x)是GF(p)上的m次既约多项式，则所有次数小于m次的GF(p)上的多项式全体｛0，1，p0+p1x，…，p0+p1x＋p2x2＋…＋pm-1xm-1｝在模P(x)加和乘运算下组成一个有pm个元素的有限域GF(pm)。  定义8－2：具有循环移位特点的线性分组码叫循环码。 设[C]为（n，k）循环码，则∨C∈[C]有： C =（cn-1 cn-2…c1c0） C(1)=（cn-2 cn-3…c0 cn-1） C(2)=（cn-3 cn-4…c n-1 cn-2） ┆ C(n-1)=（c0 cn-1…c 2 c1） 定理8－2：若c(x)是n长循环码中的一个码字多项式，则xi c(x)按模xn+1运算的余式必为循环码中的码字多项式。 (７,４)码的码字多项式： V1(x)=x6+ x2+1=( x3+ x+1)2 V2(x)=xV1( x) mod(x7+1)=x3+ x+1 V3(x)=xV2( x) mod(x7+1) = x4+ x2+ x = x ( x3+ x+1) V4(x)=xV3( x) mod(x7+1) = x5+ x3+ x2 = x2 ( x3+ x+1) V5(x)=xV4( x) mod(x7+1) = x6+ x4+ x3 = x3 ( x3+ x+1) V6(x)=xV5( x) mod(x7+1) = x5+ x4+1 =( x2+ x+1) ( x3+ x+1) V7(x)=xV6( x) mod(x7+1) = x6+ x5+x =(x3 +x2+ x) ( x3+ x+1) V8(x)=x5+x2+x+1=( x2 +1) ( x3+ x+1) V9(x)=xV8( x) mod(x7+1) = x6+ x3+ x2+x =(x3 +x) ( x3+ x+1) V10(x)=xV9( x) mod(x7+1) = x4+ x3+ x2+1 =(x+1) ( x3+ x+1) V11(x)=xV10( x) mod(x7+1) = x5+ x4+ x3+x =(x2 +x) ( x3+ x+1) V12(x)=xV11( x) mod(x7+1) = x6+ x5+ x4+x2 =(x3 +x2) ( x3+ x+1) V13(x)=xV12( x) mod(x7+1) = x6+ x5+ x3+1 =(x3 +x2+ x+1) ( x3+ x+1) V14(x)=xV13( x) mod(x7+1) = x6+ x4+ x+1 =(x3 +1) ( x3+ x+1) V15(x)=x6+ x5+ x4+ x3+ x2+x+1 =(x3 +x2+ 1) ( x3+ x+1) V16(x)=0 =0(x3+ x+1) Vi(x)=m(x) V2(x) 定理8－3：GF(2)上（n，k）循环码中有唯一的非零最低次多项式g(x)，且其常数项为1。 （思考题：） 定义8－3：如果一个码的所有码多项式都是多项式g(x)的倍式，则称g(x)生成该码，且称g(x)为该码的的生成多项式。 定理8－4：任何一个n-k =r次多项式都可生成一个（n，k）线性分组码。 例2：（1）g(x)=x4+x+1  由C=MG，生成（7，3）线性分组码（系统码） （2）g(x)=x4+x3+ x2+1  由C=MG，生成（7，3）线性分组码 C： 定理8－5：如果g(x)是一个n-k =r次多项式，且是xn－1的一个因式，则g(x)生成（n，k）循环码。 证明： 设[C]是g(x)生成的（n，k）线性分组码； 若C∈[C],则c(x)=cn-1xn-1+ cn-2xn-2+…c1x+c0 xc(x)=cn-1xn+ cn-2xn-1+…c1x2+c0x =( cn-2xn-1+…c1x2+c0x+ cn-1)+ cn-1(xn+1) = c(1)(x)+ cn-1(xn+1) ∴c(1)(x)= m’(x)g(x) 即C(1) ∈[C] [C]为具有循环移位特点的线性分组码！ 证毕！ 定理8－6：任何循环码的全体码字都可由一个n-k =r次多项式生成。 设： 生成矩阵：   例3：（7，3）循环码，生成多项式为： g(x)=x4+x3+ x2+1 输入M=(101)，求：输出码字C（系统码）。 解：∵，∴V=(v3v2v1v0) m(x)= x2+1 1) 信息元前移r位：x4m(x)= x6+ x4 2) 按模取余：V(x)=Rg(x)[ x4m(x)] = x+1 3) 合成码字：C(x)=x4m(x)+ V(x) = x6+ x4+ x+1 系统码的生成矩阵：  例4：已知（7，3）循环码生成多项式： g(x)=x4+x3+ x2+1 (1) 求G0 法一：（利用系统码特点求）r=4，k=3 r1(x)=xn-1=x6 mod g(x) =x3+x2+x r2(x)=xn-2=x5 mod g(x) =x2+x+1   法二：（G→G0）  h(x)~H c(x)h(x)=m(x)g(x)h(x)= m(x)(xn+1) = m(x) xn+ m(x) ∴c(x)h(x)中xn-1，…，xk项系数为0。 c(x)h(x)=（cn-1xn-1+ cn-2xn-2+…c1x+c0） （hkxk+ hk-1xk-1 +…h1x+h0） cn-1h0+ cn-2h1+…+ cn-k-1hk=0 cn-2h0+ cn-3h1+…+ cn-k-2hk=0 ┋ ckh0+ ck-1h1+…+ c0hk=0  HCT=0T h*(x)=h0xk+ h1xk-1+…hk   例4(续)： (2) 求H0 法一：（利用互反多项式）   法二：（G0→H0） ，  定理8－7：令C是生成多项式为g(x)的（n，k）循环码，它的互为对偶码是一个（n，n-k）循环码，且由多项式h*(x)生成。 生成多项式 g(x) h*(x) h (x)  循环码集 （n，k） （n，r） （n，r）  生 成 矩 阵     一 致 校 验 矩 阵      各种码的编码器比较：  例：构造g(x)= x3+ x+1的（7，4）循环码的编码器。并设M=(1101)，求码字C。 解： 编码电路： 工作过程： 节拍 输入 D0 D1 D2 C  0 0 0 0 0 0  1 1 1 1 0 1  2 1 1 0 1 1  3 0 1 0 0 0  4 1 1 0 0 1  5 0 0 1 0 0  6 0 0 0 1 0  7 0 0 0 0 1