1、循环码n主要内容n什么是循环码？n循环码的一些性质n循环码的构造n循环码的编译码n循环码的应用什么是循环码？n线性分组码的一种，满足线性性。n循环性n循环码C中的任意码字循环移位k后的码字仍属于C，即 若AC，则A(k)Cn例：(0000),(1111)是循环码码多项式n码字 的码多项式定义为121 0.nnCc ccc 11212100.nnninniic xcxcxc xcc x循环性n码字 的循环左移1位为 其码多项式n循环左移k位为121 0.nnCccc c 121 01.nnCcc c c 11 01.kn knn kCcc c cc 1122101.nnncxcxc xc xc
2、1111101.knkkkn knn kcxcxcxc xc xc 循环性n定理一、n证明：用归纳法nK=1时，mod1kkncxx c xx 11221011212101111101.1mod1nnnnnnnnnnnnnnncxcxc xc xccxcxc xc xccxx cxc xccxxc xxn设k时成立，则显然k+1成立。证毕循环码的性质n定理二、（n，k）循环码中存在且仅有一个非零的最低次多项式，该多项式称为生成多项式g(x)，其他所有许用码字均可以表示成c(x)=u(x)g(x)n证明：n假设（n，k）循环码中存在两个最低次多项式g1(x),g2(x)，则根据循环码的线性性g(
3、x)=g1(x)+g2(x)是（n，k）中的码多项式。但g(x)的次数小于g1(x),g2(x)，与假设矛盾。n设 则根据循环性和线性性也是（n，k）循环码中的许用码组。（n，k）中的任意码字c(x)可写成nb(x)是次数小于r-1的多项式，na(x)是次数不大于n-r的多项式 121210.rrrrg xg xg xgx g 01.n rn rfxff xfxg x c xa x g xb xnb(x)=c(x)+a(x)g(x)，由于c(x)，a(x)g(x)都是许用码组，因此b(x)也是许用码组，因此如果b(x)=0，则我们找到了一个比g(x)次数低的码字，这与假设g(x)是最低次数矛盾
4、，因此b(x)=0。即循环码中的任意c(x)，有c(x)=a(x)g(x)。定理二n告诉一个信息：即（n，k）循环码的构造就是要找到生成多项式g(x)。n推论：由于c(x)=a(x)g(x)，且(n,k)循环码的c(x)个数为2k个，因此a(x)的最高次数为k-1,g(x)的次数为n-k。定理三（生成多项式的构造）n（n,k）循环码的生成多项式g(x)是（xn+1)的次数为n-k的因子。n证明：由定理二推论知g(x)的次数为n-k。设则10().n kn kg xgxg xg 110.1 11()()mod1knnkn knnx g xxgxg xxb xb xx n由定理二，b(x)=a(x
5、)g(x)n因此，n即g(x)是xn+1的因子。()()1kna xxg xx循环码小节n循环码的重要参数生成多项式g(x)。n(n，k)循环码的g(x)幂次为nk，且g(x)是(n,k)中幂次最低的非0码多项式。n(n,k)循环码的任意码组可以通过g(x)得到，即c(x)=u(x)g(x)n(n,k)循环码的g(x)是xn+1的n-k次因子。循环码举例n设计一个（7，4）循环码。n分析：n-k=3,n=7n已知n则可以选择ng(x)=x3+x+1或x3+x2+173231111xxxxxx(7,4)循环码n设g(x)=x3+x+1n所有许用码组c(x)=u(x)g(x)（多项式乘法），即32
6、3321065433231320221100()1c xu xu xu xuxxu xu xuuxuuuxuuxuuxu（7，4）循环码（非系统码）3232103210()1011000010110000101100001011x g xx g xc xu u u uxxg xg xcu u u uuGuG（7，4）循环码（非系统码）000000000000001000101100100010110001100111010100010110001010100111011001110100111011000110001011000100110100111010100111010111000101
7、11001110100110111111111110110001011111101001循环性验证n0000000，1111111n0001011，0010110，0101100，1011000，0110001，1100010，1000101n0011101，0111010，1110100，1101001，1010011，0100111，1001110（7，4）系统循环码n1、由非系统G行变换得1000101010011100101100001011G（7，4）系统循环码n2、分析系统码的c(x)应具有如下形式：n则b(x)应该是 的余式（多项式除法）。12120().()()kkn kkkn
8、 kc xuxuxuxb xu x xb xa x g x/()n kxu xg x（7，4）系统循环码 11mod()22mod()120mod().nng xnng xkkn kn kg xxxxxc xu uuxx（7，4）系统循环码663R e553R e3210443R e333R e625232104231111111mmmmxxxxxxxxcxu u u uxxxxxxxxxxxxxu u u uxxxxxxu G（7，4）系统循环码00000000000000100010110010001011000110011101010001001110101010110001100110001011101110101000100010110011001110101010100111011101100011001100010110111010011110111010011111111111循环码编码与译码n编码器：n系统码编码器可以用移位寄存器实现除法。n非系统编码器可以用移位寄存器实现乘法。
