State Key Laboratory of Integrated Services Networks 第五章第五章 循环码循环码要求掌握的内容根据多项式会写循环码的生成矩阵和校验矩阵会写循环码生成和校验矩阵的系统形式会画循环码的编码电路由生成多项式的根定义循环码第一节 循环码定义循环码的生成多项式和校验多项式循环码的生成矩阵和校验矩阵循环码的系统码形式State Key Laboratory of Integrated Services Networks 一、循环码定义一、循环码定义 定义定义1：设设CH是一个是一个n.k线性分组码，线性分组码，C1是其是其中的一个码字，若中的一个码字，若C1的左的左(右右)循环移位得到的循环移位得到的n维向量也是维向量也是CH中的一个码字，则称中的一个码字，则称CH是循环码。是循环码。定义定义2：设设是是n维空间的一个维空间的一个k维子空间，维子空间，若对任一若对任一恒有恒有则称则称Vn,k为为循环子空间循环子空间或或循环码循环码State Key Laboratory of Integrated Services Networks 问题一如何寻找k维循环子空间？如何设计n,k循环码？ 利用多项式和有限域的概念注：注： 1、GF(p)上的上的n维向量与维向量与GF(p)上的多项式之间有一一对上的多项式之间有一一对应的关系应的关系 2、模、模n 多项式多项式F(x)的剩余类构成一个多项式剩余类环的剩余类构成一个多项式剩余类环Fpx/F(x)，若在环中再定义一个数乘运算，即，若在环中再定义一个数乘运算，即 则模则模F(x)的剩余类构成一个的剩余类构成一个n维线性空间，定义为剩余类线维线性空间，定义为剩余类线性结合代数。性结合代数。State Key Laboratory of Integrated Services Networks 问题一转化为如何从模多项式xn-1的剩余类结合代数中寻找循环子空间？定理 以多项式以多项式xn-1为模的剩余类线性结合代数中，其一为模的剩余类线性结合代数中，其一个子空间个子空间Vn, k为循环子空间为循环子空间(或循环码或循环码)的充要条件的充要条件是：是：Vn,k是一个理想。是一个理想。 循环码是模循环码是模xn-1的剩余类线性结合代数中的一个的剩余类线性结合代数中的一个理想。理想。State Key Laboratory of Integrated Services Networks 问题二问题二如何从多项式剩余类环中如何从多项式剩余类环中寻找理想？寻找理想？ 由于由于 1、多项式剩余类环中任何一个理想都是主理、多项式剩余类环中任何一个理想都是主理想想主理想中的所有元素可由某一个元素的主理想中的所有元素可由某一个元素的倍式倍式构成构成 2、在主理想的所有元素中，至少可找到一个、在主理想的所有元素中，至少可找到一个次数最低的首一多项式次数最低的首一多项式g(x),即即生成多项式生成多项式定义：生成多项式定义：生成多项式g(x)是模是模xn-1剩余类代数中，剩余类代数中，一个理想的次数最低的非零首一多项式，它是一个理想的次数最低的非零首一多项式，它是理想或循环码的生成元。理想或循环码的生成元。State Key Laboratory of Integrated Services Networks 问题三问题三如何寻找生成多项式如何寻找生成多项式g(x)？循环码循环码模多项式模多项式xn-1剩余类线性结合代数中的理想剩余类线性结合代数中的理想生成多项式生成多项式State Key Laboratory of Integrated Services Networks 二、生成多项式和校验多项式二、生成多项式和校验多项式两个定理两个定理 定理定理1:GF(q)(q为素数或素数的幂为素数或素数的幂)上的上的n,k循环循环码中，存在唯一的码中，存在唯一的n-k次首一多项式次首一多项式g(x)，每一个，每一个码多项式码多项式C(x)必是必是g(x)的倍式，每一个小于等于的倍式，每一个小于等于(n-1)次的次的g(x)的倍式一定是码多项式的倍式一定是码多项式两个定理两个定理 定理定理2:GF(q)(q为素数或素数的幂为素数或素数的幂)上上n,k循环码的循环码的生成多项式生成多项式g(x)一定是一定是xn-1的的n-k次因式：次因式： xn-1= g(x) h(x)。 反之，若反之，若g(x)为为n-k次多项式，且次多项式，且xn-1能被能被g(x)整除，整除，则则g(x)一定能生成一个一定能生成一个n,k循环码循环码两个结论 结论1:找一个n,k循环码，即是找一个n-k次首一多项式g(x)，且g(x)必是xn-1的因式。结论结论2:若若C(x)是一个码多项式，则是一个码多项式，则反之，若反之，若，则，则C(x)必是一个码多项式必是一个码多项式Examples GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1) 试求一个7,4循环码。g(x)、 xg(x)、x2 g(x)、 x3g(x)、State Key Laboratory of Integrated Services Networks 三、循环码的生成矩阵和校验矩阵g(x)决定生成矩阵，决定生成矩阵，h(x)决定校验矩阵决定校验矩阵State Key Laboratory of Integrated Services Networks 四、循环码的系统码 模g(x)的除法问题由于生成矩阵由于生成矩阵G中的中的k行要求线性无关，因此行要求线性无关，因此在求余式时，可选择在求余式时，可选择k个线性无关的信息组个线性无关的信息组 (1,0,0,0) xk-1， (0,1,0,0,0) xk-2, (0,0,0,0,1) 1表示ri(x)的系数循环码的编码原理(1)基本步骤基本步骤(n,k)1、分解多项式、分解多项式xn-1=g(x)h(x)2、选择其中的、选择其中的n-k次多项式次多项式g(x)为生成多项式为生成多项式3、由、由g(x)可得到可得到k个多项式个多项式g(x), xg(x),xk-1g(x)4、取上述、取上述k个多项式的系数即可构成相应的生成矩阵个多项式的系数即可构成相应的生成矩阵5、取、取h(x)的互反多项式的互反多项式h*(x),取取h*( x), xh*( x), xn-k-1h*( x) 的系数即可构成相应的校验矩阵的系数即可构成相应的校验矩阵可选择可选择k个线性无关的信息组个线性无关的信息组 (1,0,0,0) xk-1， (0,1,0,0,0) xk-2, (0,0,0,0,1) 1循环码的编码原理(2)表示ri(x)的系数由生成多项式的根定义循环码设码的生成多项式 g(x)=xr+gr-1xr-1+g1x+g0, giGF(q)它必在某一个GF(q)的扩域上完全分解，即它的根必在此扩域上。考虑g(x)无重根的情况，即要求xn-1无重根。定理在GF(q)上多项式xn-1无重根的充要条件是(n,q)=1在GF(2)上要保证g(x)无重根的条件是xn-1中的n是奇数，因此二进制循环码中，码长是奇数。g(x)=(x-a1)(x-a2)(x-ar)， aiaj，aiGF(qm)每一码多项式必以a1,a2,ar为根。则 C(ai)=cn-1ain-1+cn-2ain-2+c1ai+c0=0g(x)=LCM(m1(x),m2(x),mr(x)回顾共轭根系的概念回顾共轭根系的概念设设f(x)=fkxk+fk-1xk-1+f0, fiGF(p)。若。若p特征域的元素特征域的元素w是方程是方程f(x)的根，的根，f(w)=0,则对于一切自然数则对于一切自然数n, wpn也必是也必是f(x)的根。的根。共轭根系共轭根系最小多项式：系数取自最小多项式：系数取自GF(p)上，且以上，且以w为根的所有首一多项式为根的所有首一多项式中，次数最低的多项式称为中，次数最低的多项式称为w的最小多项式，记为的最小多项式，记为m(x)循环码的编码多项式乘法和除法电路循环码的编码电路(乘法和除法)State Key Laboratory of Integrated Services Networks 一、多项式乘法和除法电路b0b1b2br-2b1br-1b1br输出C(x)输入A(x)a0,a1,ak 乘B(x)运算电路(利用校验多项式h(x)编码时会用到)b0b1b2br-2b1br-1b1br输出C(x)输入A(x)a0,a1,ak乘B(x)运算电路akb0akb1akbr-2akbr-1-b1b1br-1输出商q(x)输入A(x)-b2-br-1-b0除B(x)运算电路a0,a1,ak除式B(x)构成电路，被除式A(x)的系数依次送入电路h0h1h2hr-2b1hr-1b1hr输入A(x)a0,a1,ak-g1gr-1输出商q(x)-g2-g0-gr-1-gr-1乘H(x),除g(x)运算电路多项式相乘相除电路多项式相乘相除电路当当H(x)、G(x)次数不同时次数不同时输入输入输出输出1x21x3xState Key Laboratory of Integrated Services Networks 二、循环码编码电路循环码编码电路循环码编码电路循环码编码电路循环码编码电路n-k 级编码器级编码器基本原理：利用生成多项式基本原理：利用生成多项式g(x)若要求编成若要求编成非系统码非系统码形式，则利用形式，则利用乘法电路乘法电路若要求编成若要求编成系统码系统码形式，则利用形式，则利用除法电路除法电路n-k级乘法电路级乘法电路(非系统码形式非系统码形式)取g(x), xg(x),xk-1g(x)的系数可构成生成矩阵Gn-k级乘法电路级乘法电路(非系统码形式非系统码形式)若信息序列 m=(m0, m1,mk-1),则mG对应的n维向量为：该n维向量正是多项式m(x)g(x)的系数g0g1g2gn-k-2b1gn-k-1b1gn-k输出C(x)输入m(x)m0,m1,mk乘g(x)运算电路mk-1 gn-k-1mk-1 gn-k输入m(x)是信息序列，g(x)为生成多项式mk-1 g0mk-1 g1GF(2)上，上，x7-1=(x+1)(x3+x+1)(x3+x2+1) ，g(x)=x3+x+1，试画一个，试画一个7,4循环码的循环码的n-k级乘级乘法编码电路。法编码电路。Example输入输入m(x)输出输出c(x)由于生成矩阵由于生成矩阵G中的中的k行要求线性无关，因此在求行要求线性无关，因此在求余式时，可选择余式时，可选择k个线性无关的信息组个线性无关的信息组 (1,0,0,0) xk-1 (0,1,0,0,0) xk-2 (0,0,0,0,1) 1循环码的系统码循环码的系统码表示ri(x)的系数循环码的系统码循环码的系统码n-k级乘法电路（系统码形式）级乘法电路（系统码形式）对任意信息多项式对任意信息多项式m(x), xn-km(x)除除g(x)可得余式可得余式r(x)，m(x)的系数为信息序列的系数为信息序列m，r(x) 的系数为的系数为m对应的校验比特对应的校验比特若信息序列若信息序列 m=(mk-1, mk-2,m0)；对应的多项式；对应的多项式m(x)=mk-1xk-1+ mk-2xk-2+m0因此，循环码的系统码电路是信息多项式因此，循环码的系统码电路是信息多项式m(x)乘乘xn-k,除除g(x)的实现电路的实现电路输入m(x)m0,m1,mk-1-g1gn-k-1-g2-g0-gn-k-1-gn-k-2乘乘xn-k除除g(x)运算电路运算电路门1n-k级乘法电路（系统码形式）级乘法电路（系统码形式）门门2GF(2)上，上，x7-1=(x+1)(x3+x+1)(x3+x2+1) ，g(x)=x3+x+1，试画一个，试画一个7,4循环码的循环码的n-k级系级系统码形式的乘法编码电路。统码形式的乘法编码电路。Example输入输入m(x)输出输出c(x)门门1门门2k 级编码器级编码器基本原理：利用校验多项式基本原理：利用校验多项式h(x)；为系统码编；为系统码编码电路码电路若信息序列若信息序列 m=(mk-1, mk-2,m0)对应的多项式对应的多项式m(x)=mk-1xk-1+ mk-2xk-2+m0码多项式码多项式C(x)= m(x)g(x),且且C(x)为系统码为系统码 h(x)C(x)= h(x)m(x)g(x) = m(x)(xn-1) = m(x)xn-m(x) = mk-1xn+k-1+ mk-2xn+k-2+m0xn -(mk-1xk-1+mk-2xk-2+m0)k 级编码器级编码器h0 cn-1 +h1 cn-1-1 + +hk cn-1-k=0h0 cn-2 +h1 cn-2-1 + +hk cn-2-k=0h0 cn-3 +h1 cn-3-1 + +hk cn-3-k=0h0 ck +h1 ck-1 + +hk c0=0h(x)C(x)的乘积中，的乘积中，xn-1, xn-2, xk次的系数为零次的系数为零xn-1的系数的系数xn-2的系数的系数xn-3的系数的系数xk的系数的系数k 级编码器级编码器cn-1-k = - (h0 cn-1 +h1 cn-1-1 + +hk-1 cn-1-(k-1)cn-2-k = - (h0 cn-2 +h1 cn-2-1 + +hk-1 cn-k-1)cn-3-k = - (h0 cn-3 +h1 cn-3-1 + +hk-1 cn-k-2)cn-k-(n-k) = - (h0 ck +h1 ck-1 + +hk-1 c1) 由于由于hk=1-h0-h1-h2-hk-2b1-hk-1输入信息门cn-1cn-2cn-k-1cn-k循环码循环码k级编码电路级编码电路k 级编码器级编码器GF(2)上，上，x7-1=(x+1)(x3+x+1)(x3+x2+1) ，g(x)=x3+x+1， h(x)= x4+x2+x+1。试画一个。试画一个7,4循环码的循环码的k级系统码形式的编码电路。级系统码形式的编码电路。Example输入输入m(x)输出输出c(x)门门1xx4x2第三节第三节 几类特殊的循环码几类特殊的循环码最小循环码最小循环码缩短循环码缩短循环码准循环码准循环码双环循环码双环循环码特殊的循环码特殊的循环码最小循环码最小循环码一个理想中不再含有任何的非零理想，此理想对应的循环码称为一个理想中不再含有任何的非零理想，此理想对应的循环码称为最最小循环码小循环码或或既约循环码既约循环码缩短循环码缩短循环码对循环码缩短得到的码对循环码缩短得到的码取取n, k循环码中前循环码中前i位信息位为位信息位为0的码字，得到一个的码字，得到一个n-i, k-i缩短循缩短循环码环码准循环码准循环码一个一个mn0, mk0线性分组码，若它的任一码字左移或右移循环移位线性分组码，若它的任一码字左移或右移循环移位n0次后，得到的码仍是该码的一个码字，则称这类码为次后，得到的码仍是该码的一个码字，则称这类码为准循环码准循环码双环循环码双环循环码由两个循环矩阵由两个循环矩阵Ik和和P阵组成的阵组成的G=Ik P生成的码生成的码Example8, 4码双循环码形式码双循环码形式8, 4码准循环码形式（码准循环码形式（n0=2）Examples:设设7,4循环码的生成多项式为循环码的生成多项式为 g(x)=x3+x2+1，试，试1)写出它的校验多项式写出它的校验多项式h(x)2)求出的生成矩阵和校验矩阵求出的生成矩阵和校验矩阵3) 求出系统码的生成矩阵和校验矩阵求出系统码的生成矩阵和校验矩阵4) 画出画出(n-k)级系统码编码电路和级系统码编码电路和k级编码电路级编码电路1) h(x)=(xn-1)/g(x)=x4+x2+x+12) h*(x)=x4+x3+x2+1