第五章循环码 陆以勤
第五章 循环码 陆以勤
引子 [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)