既约多项式:设f(x)是次数大于0的多项 式,除了常数、常数与本身乘积以外, 不能再被域F上其他多项式除尽,则f(x) 为F域上的既约多项式 定义8-1:给定一个多项式g(x),把它 称为模,如果两个多项式d(x)和az(x)满 足: d1(x)=q1(x)g(x)+r(x) d2(x)=q2(x)g(x)+r(x) 0≤0r(x)<0g(x) 则称多项式d1(x)和d2(x)对模g(x)同余 记为:d1(x)=d2(x)=r(x)modg(x) 性质:已给定多项式g(x)≠0为模,多项 式d1(x)和d2(x)同余的充要条件是: g(x)|d1(x)-d2(x) 例:设模多项式为:g(x)=x3+x+1 则:d1(x)=x4+x3+1=(x+1)(x32+x+1)+x2 d(x)=x3+x2+x+1=x3+x+1+x 同余!(d1(x)-d2(x)=x1+x2+x=xg(x)
既约多项式：设 f(x)是次数大于 0 的多项 式，除了常数、常数与本身乘积以外， 不能再被域 F 上其他多项式除尽，则 f(x) 为 F 域上的既约多项式。 定义 8－1：给定一个多项式 g(x)，把它 称为模，如果两个多项式 d1(x)和 d2(x)满 足： 0 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 2 2 1 1 r x g x d x q x g x r x d x q x g x r x o o = + = + 则称多项式 d1(x)和 d2(x)对模 g(x)同余。 记为：d1(x)≡d2(x) ≡r(x) mod g(x) 性质：已给定多项式 g(x)≠0 为模，多项 式 d1(x)和 d2(x)同余的充要条件是： ( )[ ( ) ( )] g x d1 x − d2 x 例：设模多项式为：g(x)=x 3+x+1 则：d1(x)= x 4+x 3+1=(x+1)( x 3+x+1)+ x 2 d2(x)= x 3+x 2+x+1= x 3 +x+1+x 2 同余！（d1(x)－d2(x)＝x 4+x 2+x=xg(x)）
例:g(x)=x2+1 0:0x2+1x(x2+1)(x+1)(x2+1) x2x3+x+1x3+x2+x x: x x2+x+1 x3 x3+x2+1 x+1:x+1 x x+1 x +x 00 xx+0 Xx x x+1 ++x10 x+1x+1 0 00000 0 x0x+ 0+1x x+1 x+1 例:g(x)=x3+x+1的剩余类多项式集合: {0,1,x+1,x2,x2+1,x2+x,x2+x+1} 与矢量集合:{000,001,010,011,100 101,110,111}同构
例：g(x)=x 2+ 1 2 3 3 2 2 3 3 2 2 3 3 2 2 2 2 1: 1 1 : 1 1 1 : 1 1 0 : 0 1 ( 1) ( 1)( 1) x x x x x x x x x x x x x x x x x x x x x x x x x + + + + + + + + + + + + + + + + + ⊕ 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)=x 3+x+1 的剩余类多项式集合： ｛0,1,x，x+1，x 2 ，x 2 +1，x 2＋x，x 2＋x+1｝ 与矢量集合：｛000，001，010，011，100， 101，110，111｝同构
定理8-1:设P(x)是GF(p)上的m次既 约多项式,则所有次数小于m次的GF(p) 上的多项式全体{0,1,P0+D1x,…,pt+px p2x2+…+pmn1xm4}在模P(x)加和乘运 算下组成一个有p个元素的有限域 GF(p")
定理 8－1：设 P(x)是 GF(p)上的 m 次既 约多项式，则所有次数小于 m 次的 GF(p) 上的多项式全体｛0，1，p0+p1x，…，p0+p1x ＋p2x 2＋…＋pm-1x m-1｝在模 P(x)加和乘运 算下组成一个有 p m 个元素的有限域 GF(p m )
(74A码:10。01。 CEMG V:oo01o1 V 8. 010011/ Ms? k:0o10141oo11o k:00101100D1o :0|01100WQn1oJo o||°kl101o 的:ooo01oo 0
定义8—2:具有循环移位特点的线性分 组码叫循环码。 设[C为(n,k)循环码,则C∈|C 有: C=(cm1Cn2…c1c0) Cn-2Cn-3°°C0Cn-1 C(2)=(Cn-3..Cn-I Cn-2) ∈ C(-=(Co Cm-1".C2 C1) 定理8—2:若c(x)是n长循环码中的 个码字多项式,则xc(x)按模x+1运算 的余式必为循环码中的码字多项式
定义 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…cn-1 cn-2） ┆ C(n-1)=（c0 cn-1…c 2 c1） 定理 8－2：若 c(x)是 n 长循环码中的一 个码字多项式，则 x i c(x)按模 x n+1 运算 的余式必为循环码中的码字多项式。 ∈[C]
(7,4)码的码字多项式 V(x)=x+x2+1=(x+x+1)2 V2(x)=xVi(x)mod(x'+1=x+x+1 V3(x)=xv2(x)mod(x'+1) x++rtx x(x3+x+1) V4(x)=v3(x)mod(x2+1) +x+ x2(x3+x+ 5(x)=xV4(x)mod(x2+1) rotex x(xtx+ V6(x)=xV5(x)mod(c+l +y-4 x2+x+ +x+ V7(x)=xv6(x)mod(c+1) x6+x5+x=(x3+x2+x)(x3+x+1) Vg(x)=x5+x2+x+1=(x2+1)(x3+x+1) Vo(x)=xv8(x)mod(c+1) x6+x3+x2+x=(x3+x)(x3+x+ Vio()=xvi(x)mod(x'+1) =x4+x3+x2+1=(x+1)(x3+x+1) Vil(r=xvid(x) mod(x +1) x5+x4+x3+x=(x2+x)(x3+x+1) V12(c)=xVii(x) mod(x'+1) =x0+x3+x4+ (x3+x2)(x3+x+1)
(７,４)码的码字多项式： V1(x)=x 6+ x 2+1=( x 3+ x+1) 2 V2(x)=xV1( x) mod(x 7+1)=x 3+ x+1 V3(x)=xV2( x) mod(x 7+1) = x 4+ x 2+ x = x ( x 3+ x+1) V4(x)=xV3( x) mod(x 7+1) = x 5+ x 3+ x 2 = x 2 ( x 3+ x+1) V5(x)=xV4( x) mod(x 7+1) = x 6+ x 4+ x 3 = x 3 ( x 3+ x+1) V6(x)=xV5( x) mod(x 7+1) = x 5+ x 4+1 =( x 2+ x+1) ( x 3+ x+1) V7(x)=xV6( x) mod(x 7+1) = x 6+ x 5+x =(x 3 +x2+ x) ( x 3+ x+1) V8(x)=x 5+x 2+x+1=( x 2 +1) ( x 3+ x+1) V9(x)=xV8( x) mod(x 7+1) = x 6+ x 3+ x 2+x =(x 3 +x) ( x 3+ x+1) V10(x)=xV9( x) mod(x 7+1) = x 4+ x 3+ x 2+1 =(x+1) ( x 3+ x+1) V11(x)=xV10( x) mod(x 7+1) = x 5+ x 4+ x 3+x =(x 2 +x) ( x 3+ x+1) V12(x)=xV11( x) mod(x 7+1) = x 6+ x 5+ x 4+x 2 =(x 3 +x2 ) ( x 3+ x+1) x 3+ x+1
V13(x)=xV12(x)mod(x+1) x6+x5+x32+1=(x3+x2+x+1)(x34+x+1) V14 r)=xV13(x)mod(x'+1) x6+x4+x+1=(x3+1)(x3+x+1) V1s(x)=x6+x5+x4+x3+x2+x+1 =(x3+x2+1)(x3+x+1) 1(x)=0=0(x3+x+1) Vi(x)=m(r)v2(x) 定理8-3:GF(2)上(n,k)循环码中有 唯一的非零最低次多项式g(x),且其常 数项为1。 (思考题:(x)=r=n-k) 定义8-3:如果一个码的所有码多项式 都是多项式g(x)的倍式,则称g(x)生成该 码,且称g(x)为该码的的生成多项式 定理8-4:任何一个n-k=r次多项式都 可生成一个(n,k)线性分组码
V13(x)=xV12( x) mod(x 7+1) = x 6+ x 5+ x 3+1 =(x 3 +x2+ x+1) ( x 3+ x+1) V14(x)=xV13( x) mod(x 7+1) = x 6+ x 4+ x+1 =(x 3 +1) ( x 3+ x+1) V15(x)=x 6+ x 5+ x 4+ x 3+ x 2+x+1 =(x 3 +x2+ 1) ( x 3+ x+1) V16(x)=0 =0(x 3+ x+1) Vi(x)=m(x) V2(x) 定理 8－3：GF(2)上（n，k）循环码中有 唯一的非零最低次多项式 g(x)，且其常 数项为 1。 （思考题： g x = r = n − k ( ) ） 定义 8－3：如果一个码的所有码多项式 都是多项式 g(x)的倍式，则称 g(x)生成该 码，且称 g(x)为该码的的生成多项式。 定理 8－4：任何一个 n-k =r 次多项式都 可生成一个（n，k）线性分组码
例2:(1)g(x)=x4+x+1 1001100 G=0100110 0010011 由C=MG,生成(7,3)线性分组码(系统码) [0010011,0110101,10111,111001,0000 0100110,1101010 1001100 (2)g(x)=x4+x3+x2+1 1110100 G=0111010 0011101 由C=MG,生成(7,3)线性分组码 C:00110100000 0111010 1110100 1101001 循环码 1010011 0100111 1001110
例 2：（1）g(x)=x 4+x+1 = 0010011 0100110 1001100 G 由 C=MG，生成（7，3）线性分组码（系统码） （2）g(x)=x 4+x 3+ x 2+1 = 0011101 0111010 1110100 G 由 C=MG，生成（7，3）线性分组码 C： 0010011， 0100110， 1001100 0110101， 1101010 1011111，1111001，0000000 0011101 0111010 1110100 1101001 1010011 0100111 1001110 0000000 C：
定理8-5:如果g(x)是一个nk=次多 项式,且是x-1的一个因式,则g(x) 生成(n,k)循环码 证明 设[C是g(x)生成的(n,k)线性分组码; 若C∈IC,则c(x)=cnxn+cm2xn2+…cx+co xc(x)=Cnx叶cmxn+…cx2+cox (Cn-2x-+oc1x+cox+ Cn-1)+ cn-1(x"+1) c"x)+cn1(x"+1) xm(rg(x) cn-iheeglx) (x)=m'(xig(x) 即C0)∈IC IC为具有循环移位特点的线性分组码! 证毕! 定理8-6:任何循环码的全体码字都可 由一个n-k次多项式生成
定理 8－5：如果 g(x)是一个 n-k =r 次多 项式，且是 x n－1 的一个因式，则 g(x) 生成（n，k）循环码。 证明： 设[C]是 g(x)生成的（n，k）线性分组码； 若 C∈[C],则 c(x)=cn-1x n-1+ cn-2x n-2+…c1x+c0 xc(x)=cn-1x n+ cn-2x n-1+…c1x 2+c0x =( cn-2x n-1+…c1x 2+c0x+ cn-1)+ cn-1(x n+1) = c (1)(x)+ cn-1(x n+1) ∴c (1)(x)= m’(x)g(x) 即 C(1) ∈[C] [C]为具有循环移位特点的线性分组码！ 证毕！ 定理 8－6：任何循环码的全体码字都可 由一个 n-k =r 次多项式生成。 xm(x)g(x) cn-1h(x)g(x)
设:g(x)=gx+g-1x-+…+g1x+80 生成矩阵: gx)8x+8,-1x++8x+8o n-3 g(x)8+8, …+g1x"+g G(r) gr 8r-i g gox g(r) grx+gr-1x+…+g1x+g0 8r g 0 G 8r 8 gr g k-1个0
设： 1 0 1 1 g(x) g x g x g x g r r r = r + + + + − − 生成矩阵： + + + + + + + + + + + + + + + + = = − − − + − − + − − − − − − − − − − − 1 0 1 1 0 1 1 1 1 2 0 1 1 3 1 2 1 1 0 2 1 1 2 1 ( ) ( ) ( ) ( ) ( ) g x g x g x g g x g x g x g x g x g x g x g x g x g x g x g x g x xg x x g x x g x G x r r r r n k k k r n k r n k k r n r n k k r n r k k = − − − 1 0 1 0 1 0 0 0 0 0 0 0 g g g g g g g g g G r r r r r r k-1个0