第五章循环码 陆以勤
第五章 循环码 陆以勤
引子 [7,3](第三章例1) 1001110 gr x6+x3+x2+x 81(x) x(x+1)g3(x) G=0100111 g2 ←分G(x)= x3+x2+x+1 82(x) (x+1)g3(x) 0011101 g3 x4+x3+x2+1 83(x) 83(x) c=mG=(mj m2 m3)G c(x)=mG(x)=(mj m2 m3)G(x) c(x) =m81x)+m282)+m383) ix(x+1)g3)+m2(x+1)g(x)+m383(x) =1 =(mx(c+)+m2x+)+m3g3) =(mx2+(m1+mx+(m1+m2+m3)g36x =m(6x)83x)69m6x)<=2 所有的码字多项式都是g(x)的倍式 因为是系统码，求校验位即可 cx)=m(x)xn-k+rxy=mx)x4+r)三0(modg3x),可得余式： rx)三mx)x4(modg3x) 校验多项式rc)是信息多项式mx)移4位除以g3)的余式，所以编码电路可用除以 83x)的电路（除法电路）实现
引子 + + = = + + + + + + + + + = = = ( ) ( 1) ( ) ( 1) ( ) ( ) ( ) ( ) 1 ( ) 1 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 0 0 1 1 1 0 3 3 3 3 2 1 4 3 2 5 2 6 3 2 g x x g x x x g x g x g x g x x x x x x x x x x x G G x 3 2 1 g g g [7，3]（第三章例1） c=mG=(m1 m2 m3 )G c(x)=mG(x)= (m1 m2 m3 ) G(x) c(x) = m1g1 (x)+m2 g2 (x)+m3 g3 (x) = m1x(x+1)g3 (x)+ m2 (x+1)g3 (x)+ m3 g3 (x) = (m1x(x+1) + m2 (x+1)+m3 )g3 (x) =(m1x 2+(m1 +m2 )x+ (m1 + m2 + m3 )) g3 (x) =m(x) g3 (x) m(x)<=2 所有的码字多项式都是g3 (x)的倍式 因为是系统码，求校验位即可 c(x)= m(x)xn-k+r(x)=m(x)x4+r(x) ≡0 （mod g3 (x))，可得余式： r(x) ≡ m(x)x4 （mod g3 (x)) 校验多项式r(x)是信息多项式m(x)移4位除以g3 (x)的余式，所以编码电路可用除以 g3 (x)的电路（除法电路 ）实现
引子 c(x)=m(x)g3x)mx)<=2,设为mx)=ar2+bx+G 所有的码字多项式都是g3(x)的倍式 g3x)的小于或等于2次的倍式是码字多项式 能否抽象成一个数学模型？ 主理想：由生成元的所有倍式组成。 如果想用g3x)生成的主理想作为码的模型，必须把g3x)无限个倍式映射为有 限个码元。 这时，可用剩余类。因为℃x)=6,所以必须把g3(x)的倍式模一个7次 多项式n(x)。 如何选取n(x),使fx)g3x)modn(x)后为一个码字？ 若把多项式映射为多重， c(x)=m(x)g3(x)=(ax2+b+c)g3(x)=ax2 g3(x)+bx g3(x)+cg3(x) 映射为7重，Xg3x)对应为把g左移1位，x2g3x)左移2位 cx)相当于g与把左移1、2位所得码字的线性组合
引子 c(x)=m(x) g3 (x) m(x)<=2，设为m(x)=ax2+bx+c ❖ 所有的码字多项式都是 g3(x)的倍式 g3(x)的小于或等于2次的倍式是码字多项式 能否抽象成一个数学模型？ ❖ 主理想：由生成元的所有倍式组成。 如果想用g3(x)生成的主理想作为码的模型，必须把g3(x)无限个倍式映射为有 限个码元。 这时，可用剩余类。 因为c(x) <=6，所以必须把 g3(x)的倍式模一个7次 多项式n(x)。 ❖ 如何选取n(x)，使f(x)g3(x) mod n(x)后为一个码字？ ❖ 若把多项式映射为多重， c(x)=m(x) g3(x)=（ ax 2 +b+c） g3(x)=ax 2 g3(x)+bx g3(x)+cg3(x) 映射为7重，x g3(x)对应为把g左移1位， x 2 g3(x)左移2位 c(x)相当于g与把左移1、2位所得码字的线性组合
引子 f(x)=fuxm+fa-x1t...+fix+fo g3(x)的倍式f(x)g3x)=fg3x)+fmxr183x)+.+fxg3(x)+fo8x) 相当于xg3(x)(i=O,1,…,m-1)的线性组合。 而xig3(x)相当于把多重g左移位。 当i2时，6”xg3x)>6,多重g已移出左边缘，为了保证fg为一个码 字，需要把移出边缘的部分作处理，方案有： 。 把移出部分截掉，即对fx83x取模x运算。 这时，截掉后的多重重量会不断减少，可能不再是一个码字，所 以这种处理方法不合理。 把移出部分循环回fg的尾部，即对fx)g3x)取模x7-1运算。 处理后可能保证多重重量不会减少，是否是一个码字？ 水 定理4.2.10(p111)F,[x]/f(x)中每个理想都是主理想，且该主理想 的生成元g(x)f(x)。 g3x川x7-1,满足(7,3)码是g3x)生成的主理想的必要条件，是否 满足充要条件？
引子 ❖ 设f(x)=fmx m + fm-1x m-1 +…+ f1x+f0, g3(x)的倍式f(x)g3(x)= fmx m g3(x)+ fm-1x m-1 g3(x)+…+ f1x g3(x) +f0 g3(x) 相当于x i g3(x) (i=0,1,…,m-1)的线性组合。 而x i g3(x)相当于把多重g左移i位。 ❖ 当i>2时， x i g3 (x)>6,多重g已移出左边缘，为了保证fg为一个码 字，需要把移出边缘的部分作处理，方案有： • 把移出部分截掉，即对f(x)g3 (x)取模x 7运算。 这时，截掉后的多重重量会不断减少，可能不再是一个码字，所 以这种处理方法不合理。 • 把移出部分循环回fg的尾部，即对f(x)g3 (x)取模x 7 -1运算。 处理后可能保证多重重量不会减少，是否是一个码字？ ❖ 定理4.2.10(p111) Fp[x]/f(x)中每个理想都是主理想，且该主理想 的生成元g(x)|f(x)。 g3 (x)| x 7 -1，满足（7，3）码是g3 (x)生成的主理想的必要条件，是否 满足充要条件？
引子 米下证(7,3)码是在F[x]/(x-1)中以g3(x)为生成元的主理想。 即证g3(x)的倍式模x7-1后仍是一个码字（即是g3(x)小于3次的倍式） 设x7-1=h(x)g3(x) f(x)=p(x)h(x)+r(x),or(x)<7-00gs (x)=7-4=3 f(x)g3(x)=(p(x)h(x)+r(x)g3(x)=p(x)(x-1)+r(x)g3(x) f (x)g3 (x)=r(x)g3 (x)mod x7-1 所以f(x)g3(x)是一个码字，亦即(7,3)是在F,[x]/(x7-1)中以g3(x) 为生成元的主理想。 0*g3 (x)mod x7-1 (0000000) g3(x) mod x7-1 (0011101) xg:(x) modx7-1 (0111010) x2g3(x）modx7-1 (1110100) x3g3 (x)mod x7-1 (1101001) x4g3 (x)mod x7-1 (1010011) x5ga(x) mod x7-1 (0100111) x6g3(x) mod x7-1 (1001110)
引子 下证（7，3）码是在Fp[x]/(x7-1)中以g3(x)为生成元的主理想。 即证g3(x)的倍式模x 7-1后仍是一个码字（即是g3(x)小于3次的倍式） 设x 7-1=h(x)g3(x) f(x)=p(x)h(x)+r(x), r(x)<7- g3 (x)=7-4=3 f(x)g3 (x)=(p(x)h(x)+r(x))g3 (x)=p(x)(xn-1)+r(x)g3 (x) f(x)g3 (x)≡r(x)g3 (x) mod x7-1 所以f(x)g3 (x)是一个码字，亦即（7，3）是在Fp[x]/(x7-1)中以g3(x) 为生成元的主理想。 0*g3(x) mod x7-1 (0 0 0 0 0 0 0) g3(x) mod x7-1 (0 0 1 1 1 0 1) xg3(x) mod x7-1 (0 1 1 1 0 1 0) x 2g3(x) mod x7-1 (1 1 1 0 1 0 0) x 3g3(x) mod x7-1 (1 1 0 1 0 0 1) x 4g3(x) mod x7-1 (1 0 1 0 0 1 1) x 5g3(x) mod x7-1 (0 1 0 0 1 1 1) x 6g3(x) mod x7-1 (1 0 0 1 1 1 0)
一、循环码的数学概念 1. 定义1（循环码）：若线性码C=[n,]满足 廿(Cn-1 Cn2,cc)∈C:(cn2,c,ccn-)∈C,则称为循环码。 若用线性空间描述，则n重子空间Vn,k∈Vm,若 Vv=(cn-n cn-2...,cn co)EVn,k:Vv=(cn-2...,cn co cn-)EVn,k 则称Vn,k为循环子空间，也称[n,k]循环码。 g(x) (0001101) 例[7,4]汉明码，p62,例3.3 xg(x) (0011010) x2g(x) (0110100) 0001111 xg(x) (1101000) H=0110011 x'g(x) (1010001) x5g(x) (0100011) 1010101 xg(x) (1000110) (x+1)g(x) (0010111) x(x+1)g(x) (0101110) x2(x+1)g(x) (1011100) x3(x+1)g(x) (0111001) x4(x+1)g(x) (1110010) x5(x+1)g(x) (1100101) x6(x+1)g(x) (1001011) (x3+x+1)g(x) (1111111 0*g(x) (0000000)
一、循环码的数学概念 1. 定义1 （循环码） ：若线性码C = [n,k]满足 （cn-1,cn-2,...,c1,c0）C:(cn-2,...,c1,c0,cn-1）C, 则称为循环码。 若用线性空间描述，则n重子空间Vn,k Vn,若 v=(cn-1,cn-2,...,c1,c0）Vn,k:v=(cn-2,...,c1,c0,cn-1）Vn,k 则称Vn,k为循环子空间，也称[n,k]循环码。 g(x) (0 0 0 1 1 0 1) xg(x) (0 0 1 1 0 1 0) x 2g(x) (0 1 1 0 1 0 0) x 3g(x) (1 1 0 1 0 0 0) x 4g(x) (1 0 1 0 0 0 1) x 5g(x) (0 1 0 0 0 1 1) x 6g(x) (1 0 0 0 1 1 0) (x+1)g(x) (0 0 1 0 1 1 1) x(x+1)g(x) (0 1 0 1 1 1 0) x 2(x+1)g(x) (1 0 1 1 1 0 0) x 3(x+1)g(x) (0 1 1 1 0 0 1) x 4(x+1)g(x) (1 1 1 0 0 1 0) x 5(x+1)g(x) (1 1 0 0 1 0 1) x 6(x+1)g(x) (1 0 0 1 0 1 1) (x3+x+1)g(x) (1 1 1 1 1 1 1) 0*g(x) (0 0 0 0 0 0 0) 例[7，4]汉明码，p62,例3.3 = 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 H
一、循环码的数学概念 --一一--一一--一一- 0001101gx) g(x) (0001101) ◆ 1000110 xg(x) (0011010) 0011010 x2g(x) (0110100) 0100011 xig(x) (1101000) 0110100 x4g(x) (1010001) x5g(x) (0100011) 1101000 1010001 x6g(x) (1000110) 0010111(x+1)g(x) (x+1)g(x) (0010111) x(x+1)g(x) (0101110) 1001011 (1011100) 0101110 x2(x+1)g(x) x3(x+1)g(x) (0111001) 1100101 x4(x+1)g(x) (1110010) 1011100 x5(x+1)g(x) (1100101) 1110010 x6(x+1)g(x) (1001011) 0111001 (x3+x+1)g(x) (1111111) 0*g(x) (0000000) 00000000●g(x) 1111111(x3+x+1)g(x)
一、循环码的数学概念 0100011 1000110 0001101 g(x) 1101000 0011010 0110100 1010001 0010111 (x+1)g(x) 0111001 0101110 1011100 1110010 1100101 1001011 0000000 0 • g(x) 1111111 (x 3+x+1)g(x) g(x) (0 0 0 1 1 0 1) xg(x) (0 0 1 1 0 1 0) x 2g(x) (0 1 1 0 1 0 0) x 3g(x) (1 1 0 1 0 0 0) x 4g(x) (1 0 1 0 0 0 1) x 5g(x) (0 1 0 0 0 1 1) x 6g(x) (1 0 0 0 1 1 0) (x+1)g(x) (0 0 1 0 1 1 1) x(x+1)g(x) (0 1 0 1 1 1 0) x 2(x+1)g(x) (1 0 1 1 1 0 0) x 3(x+1)g(x) (0 1 1 1 0 0 1) x 4(x+1)g(x) (1 1 1 0 0 1 0) x 5(x+1)g(x) (1 1 0 0 1 0 1) x 6(x+1)g(x) (1 0 0 1 0 1 1) (x3+x+1)g(x) (1 1 1 1 1 1 1) 0*g(x) (0 0 0 0 0 0 0)
一、循环码的数学概念 数学上，码字循环是码多项式乘x(左循环)或x1(右循环)取模x-的余式 类 定理1：设V,是模x-剩余类构成的线性空间，Vnkc'n,'n是一个循环 码的充要条件是：V是x-1剩余类中的理想 分析：理想的定义：交换环中的非空子集/称为中的理想，若： 1)Ha,b∈1：a-b∈I; 2)Ha∈，r∈R:ar=ra∈I 证明：（)证'是一个循环码，则'是x-1剩余类中的理想 n网ea,7=2ey,证7网网ey f网田=2r i=0 v(x)=(an an2a,ao)EVnk xv(x)=(an2,..an,do,an)EVnk +“+4 x'v(x)=(aiadoaan)EV.k ∴.fx)v(x)=v(x)•f(x)eVn
一、循环码的数学概念 数学上,码字循环是码多项式乘x(左循环)或x -1 (右循环)取模x n -1的余式. 定理1：设Vn是模x n -1剩余类构成的线性空间，Vn,k Vn, Vn,k是一个循环 码的充要条件是： Vn,k是x n -1剩余类中的理想 。 分析：理想的定义: 交换环R中的非空子集I称为R中的理想，若： 1) a, b I: a-b I; 2) a I, r R: ar =ra I 证明:(1)证Vn,k是一个循环码，则Vn,k是x n -1剩余类中的理想 n k n i n n i n k i n n n k n n n k n i i i n n k n i i n k i f x v x v x f x V x v x a a a a a V x v x a a a a V v x a a a a V f x v x f x v x v x V f x f x V f x v x V , 1 1 0 1 , 2 1 0 1 , 1 2 1 0 , 1 0 , 1 0 , ( ) ( ) ( ) ( ) ...... ( ) ( ,..., , , ,..., ) ...... ( ) ( ,..., , , ) ( ) ( , ,..., , ) ( ) ( ) ( ) ( ) , ( ) , ( ) ( ) • = • = = = • = = • − − − − − − − − − = − = 证
一、循环码的数学概念 (2)证'n是x-1剩余类中的理想，则V,是一个循环码 v(x)∈'nk:xv(x)=x(x)∈'nk 理想，某些元素的倍式组成，可以证明，V仅由一个元素生成， 是个主理想 定理2：GF(q)上的循环码'nk中，存在唯一的n-k次首一多项式 86)=xn-k+gn-kx-1++gx+g0,使： 1)vc(x):g(x)Ic(x); 2) cy∈Fg[x:oc(x)sn-1且gxlc(x)->c(x)∈Vnki 1)说明每一个码矢都是g(x)的倍式，即由g(x)循环移位的线 性组合 2)说明g(x)小于n-1次的倍式（即由g(x)循环移位的线性组合） 定是个码多项式。 gx)叫循环码的生成元（生成多项式），所以V是个主理想
一、循环码的数学概念 （2）证Vn,k是x n -1剩余类中的理想，则Vn,k是一个循环码 n k Vn k v x V xv x x v x , , ( ) : ( ) = ( ) ❖ 理想，某些元素的倍式组成，可以证明，Vn,k仅由一个元素生成， 是个主理想 ❖ 定理2：GF(q)上的循环码Vn,k中，存在唯一的n-k次首一多项式 g(x)=xn-k+gn-k-1x n-k-1+…+g1x+g0，使： 1) c(x) Vn,k: g(x)|c(x); 2) c(x) Fq [x]: c (x) n-1且g(x)|c(x) --> c(x) Vn,k; 1)说明每一个码矢都是g(x)的倍式， 即由g(x)循环移位的线 性组合 2)说明g(x)小于n-1次的倍式（即由g(x)循环移位的线性组合） 一定是个码多项式。 ❖ g(x)叫循环码的生成元（生成多项式），所以Vn,k是个主理想
一、循环码的数学概念 定理3：GF(q)上的[n,k]循环码的生成多项式g(x)|xn-1;反之，若g(x)|xn-1, 则g(x)一定生成一个[n,k]循环码，其中k=n-g(x) 证明：(1)证g(x)|xn-1 g(x)∈'nk 设xn-1=g(x)h(x)+r(x),°r(x)<°g(x)(欧几里德算法) 则 x”-1=g(x).h(x)+r(x)=0∈'nk r(x)=x”-1-g(x).h(x) 又g(x)h(x)∈Vnk ..r(x)EVnk 又a°r(x)<a°g(x) 而g(x)是生成元，次数最小，所以(x)=0
一、循环码的数学概念 定理3：GF(q)上的[n,k]循环码的生成多项式g(x)|xn-1;反之，若g(x)|xn-1， 则g(x)一定生成一个[n,k]循环码，其中k=n-g(x) 证明：(1)证g(x)|xn-1 g(x) Vn,k， 设x n-1=g(x)h(x)+r(x)， r(x)< g(x) （欧几里德算法） 则 ( ) ( ) 0 ( ) ( ) ( ) ( ). ( ) ( ) 1 ( ). ( ) 1 ( ). ( ) ( ) 0 , , , = = − − − = + = g x r x r x g x r x V g x h x V r x x g x h x x g x h x r x V n k n k n n k n 而 是生成元，次数最小，所以 又 又