第5章 循环码.ppt

第二级,第三级,第四级,第五级,第5章,循环码,第5章 循环码,5.1 循环码与理想,5.2 由生成多项式的根定义循环码,5.3 幂等多项式和最小循环码,5.4 缩短循环码与准循环码,5.5 平方剩余码,5.6 多项式及域元素运算电路,5.7 循环码的编码电路,5.8 循环码的谱表示与,MS,多项式,5.9 序列线性复杂度与勃拉哈特(,Blahut,),定理,习题,5.1 循环码与理想,一、基本概念,7，4汉明码,C,H,的,H,矩阵为,由第二章可知，交换,H,矩阵各列，并不会影响码的纠错能力。把上述,H,矩阵的列进行交换后变为,由此矩阵可明显看出，第二行是第一行循环右移一位得到，第三行是第二行循环右移一位。由此矩阵编出的16个码字为：1000110，0100011，1010001，1101000，0110100，0011010，0001101；1001011，1100101，1110010，0111001，1011100，0101110，0010111；,1111111；0000000。,由这些码字看出，若,C,1,C,H,，,则它的右(左)移循环移位所得到的,n,重也是一个码字，具有这种特性的,n,，,k,分组码称为循环码。由于,n，k,线性分组码是,n,维线性空间,V,n,中的一个,k,维子空间，因此,n，k,循环码是,n,维线性空间中的一个,k,维循环子空间。,定义 5.1.1 一个,n,重子空间,V,n,，,k,V,n,，,若对任何一个,V=(,a,n,-1,，,a,n,-2,，,a,0,)V,n,，,k,，,恒有,v,1,=(,a,n,-2,，,a,n,-3,，,a,0,，,a,n,-1,)V,n,，,k,，,则称,V,n,，,k,为 循环子空间或 循环码。,二、码的多项式描述,从第二章可知，,GF(,p,),上的所有,n,重构成一个线性空间,V,n,，,其中每个矢量是分量取自,GF(,p,),上,n,重，若将每个,n,重和系数取自,GF(,p,),上的多项式相对应：,n,重：,(,a,n,-1,，,a,n,-2,，,a,1,，,a,0,),a,i,GF(p,),多项式：(,a,n,-1,x,n,-1,+,a,n,-2,x,n,-2,+,a,1,x,+,a,0,)=,f,(,x,),则它们之间建立了一一对应关系。在第四章中已指出，所有次数小于,n,次的多项式一定在模,n,次多项式,F,(,x,),F,p,x,的不同剩余类中，即,f,(,x,),a,n,-1,x,n,-1,+,a,n,-2,x,n,-2,+,a,1,x,+,a,0,(mod,F,(,x,),因此，,V,n,中每一个,n,重都与,G,F,(,p,),上的次数低于,n,次的一个多项式相对应，并必在模,F,(,x,),的某一剩余类中。第四章中已证明，在模,F,(,x,),运算下，模,F,(,x,),的剩余类构成一多项式剩余类环,F,p,x,F,(,x,)，,若在该环中再定义一个数乘，即,ca,(,x,)=,ca,n,-1,x,n,-1,+,ca,n,-2,x,n,-2,+,ca,0,c,G,F,(,p,),则可以证明模,F,(,x,),的剩余类构成一个,n,维线性空间，称为 剩余类线性结合代数。,定理 5.1.1 以多项式,x,n,-1,为模的剩余类线性结合代数中，其一个子空间,V,n,，,k,是一个循环子空间(循环码)的充要条件是：,V,n,，,k,是一个理想。,定义 5.1.2 生成多项式,g,(,x,),是模,x,n,-1,剩余类代数中，一个理想的次数最低的非零首一多项式，它是理想或循环码的生成元。,定理 5.1.2,G,F,(,q,)(,q,为素数或素数的幂)上的,n,，,k,循环码中，存在有唯一的,n,-,k,次首一多项式,g,(,x,)=,x,n,-,k,+,g,n,-,k,-1,x,n,-,k,-1,+,g,1,x,+,g,0,，,每一码多项式,C,(,x,),都是,g,(,x,),的倍式，且每一个(,n,-1),次的,g,(,x,),倍式一定是码多项式。,定理 5.1.3,GF(,q,),上,n,，,k,循环码的生成多项式,g,(,x,),一定是,x,n,-1,的因式：,x,n,-1=,g,(,x,),h,(,x,)。,反之，若,g,(,x,)为,n,-,k,次，且,g,(,x,)(,x,n,-1)，,则该,g,(,x,),一定生成一个,n,，,k,循环码。,例 5.1 在,GF(2),上，,x,7,-1=(,x,+1)(,x,3,+,x,+1)(,x,3,+,x,2,+1)，,求7，4循环码。找一个能除尽,x,7,-1,的,n,-,k,=3,次首一多项式,g,(,x,)，,可在,x,3,+,x,+1,与,x,3,+,x,2,+1,中任选一个，现在选,g,(,x,)=,x,3,+,x,2,+1，,则,xg,(,x,)：,xg,(,x,)=,x,4,+,x,3,+,x,x,2,g,(,x,)：,x,2,g,(,x,)=,x,5,+,x,4,+,x,2,x,3,g,(,x,)：,x,3,g,(,x,)=,x,6,+,x,5,+,x,3,它们相应的,n,重为：(0001101)，(0011010)，(0110100)，(1101000)，把它们作为生成矩阵的行，就得到了，4码的生成矩阵。,三、循环码的生成矩阵、校验矩阵,由前知，,x,n,-1=,g,(,x,),h,(,x,)。,若,g,(,x,),为,n,-,k,次，则,h,(,x,),为,k,次多项式。以,g,(,x,),作为生成多项式所组成的,n,，,k,循环码中,g,(,x,)，,xg,(,x,)，,x,k,-1,g,(,x,),等,k,个码多项式必是线性无关的，设可以由这些码多项式所对应的码字，构成循环码的生成矩阵,G,，,则,g,(,x,)=,g,n,-,k,x,n,-,k,+,g,n,-,k,-1,x,n,-,k,-1,+,g,1,x,+,g,0,xg,(,x,)=,g,n,-,k,x,n,-,k,+1,+,g,n,-,k,-1,x,n,-,k,+,g,1,x,2,+,g,0,x,x,k,-1,g,(,x,)=,g,n,-,k,x,n,-1,+,g,n,-,k,-1,x,n,-2,+,g,0,x,k,-1,所以,x,n,-1=,g,(,x,),h,(,x,),=(,g,n,-,k,x,n,-,k,+,g,1,x,+,g,0,)(,h,k,x,k,+,h,1,x,+,h,0,),由此可知等式右边的,x,n,-1,，,x,n,-2,，,x,的系数均为0，即,g,0,h,0,=-1,g,0,h,1,+,g,1,h,0,=0,g,0,h,1,+,g,1,h,i-1,+,g,n,-,k,h,i-(,n,-,k,),=0,g,0,h,n,-1,+,g,1,h,n,-2,+,g,n,-,k,h,k,-1,=0,g,n,-,k,h,k,=1,(5.1.2),上式可简写成,g,0,h,i,+,g,1,h,i,-1,+,g,n,-,k,h,i,-(,n,-,k,),=0,i,=1，2，,n,-1,g,0,h,0,+,g,n,-,k,h,k,=0,因此,n,，k,循环码的一致校验矩阵,(5.1.3),容易验证,G,H,T,=0,(5.1.4),所以，我们称,h,(,x,)=(,x,n,-1),g,(,x,),为码的 校验多项式，由式(5.1.3)可以看出，,H,矩阵的行完全由,h,(,x,),的系数决定。,如例5.1中7，4码的校验多项式,相应的,H,矩阵为,定理 5.1.4 令,C,1,和,C,2,分别由,g,1,(,x,),和,g,2,(,x,),生成的两个不同的循环码，则当且仅当,g,2,(,x,),g,1,(,x,),时，,C,1,C,2,。,证明 若,g,2,(,x,),g,1,(,x,)，,则,g,1,(,x,)=,a,(,x,),g2,(,x,)，,也就是由,g,1,(,x,),的所有倍式生成的循环码,C,1,必在由,g,2,(,x,),生成的码,C,2,中，所以,C,2,C,1,。,反之，若,C,2,C,1,，,则,C,1,的每一个码字不但是,g,1,(,x,),的倍式，也必是,g,2,(,x,),的倍式，,g,2,(,x,),g,1,(,x,),m,1,(,x,)。,若,g,2,(,x,),m,1,(,x,)，,则,m,1,(,x,),是,C,2,码的一个码字，因而,C,1,码的每一码字,g,1,(,x,),m,1,(,x,),必包含有,C,2,码的码字，,C,1,C,2,，,这与,C,1,C,2,的假设相矛盾，所以,g,2,(,x,),m,1,(,x,)，,可知,g,2,(,x,),g,1,(,x,)。,该定理给出了,C,1,是,C,2,码子码的充要条件。,四、系统码的构成,用式(5.1.1)矩阵生成的循环码，并不是系统码。系统码的,G,矩阵为,G,=,I,k,p,左边是,k,k,阶单位方阵。这相当于码字多项式的第,n,-1,次至,n,-,k,次的系数是信息位，而其余的为校验位，这相当于,C,(,x,)=,m,(,x,),x,n,-,k,+,r,(,x,)0 (mod,g,(,x,)(5.1.5),式中,m,(,x,)=,m,k,-1,x,k,-1,+,m,k,-2,x,k,-2,+,m,1,x,+,m,0,是信息多项式，(,m,k,-1,，,m,1,，,m,0,),是信息位，而,r,(,x,)=,r,n,-,k,-1,x,n,-,k,-1,+,r,n,-,k,-2,x,n,-,k,-2,+,r,1,x,+,r,0,是校验位多项式，相应的系数是码元的校验位。由上式可得,-,r,(,x,)=,C,(,x,)+,m,(,x,),x,n,-,k,m,(,x,),x,n,-,k,(mod,g,(,x,),(5.1.6),所以要构造用,g,(,x,),生成的系统码，首先必须将信息组乘以,x,n,-,k,变成,x,n,-,k,m,(,x,)；,然后，用,g,(,x,),除，得到余式,r,(,x,)；,再将其各项系数取加法逆元，就得到了所要求的校验位。因此，循环码系统码的编码问题就是以,g,(,x,),为模的除法,问题。,由,G,=,I,k,p,可知，信息组的基底矢量是：(1000)，(0100)，(0001)，相应的信息多项式分别为：,m,1,(,x,)=,x,k,-1,，,m,2,(,x,)=,x,k,-2,，,m,k,(,x,)=1。,与这些信息多项式相应的校验多项式分别为：,r,1,(,x,),x,n,-,k,x,k,-1,(mod,g,(,x,)，,r,2,(,x,),x,n,-,k,x,k,-2,(mod,g,(,x,)，,，,r,k,(,x,),x,n,-,k,(mod,g,(x,)。,一般写成,r,i,x,n,-,k,x,k,-,i,x,n,-,i,(mod,g,(,x,),i,=1，2，,k,与此相应的码多项式为,g,(,x,),q,i,(,x,)=,C,i,(,x,)=,x,n,-,i,-,r,i,(,x,),i,=1，2，,k,共,k,个，它们的系数就组成了系统码,G,矩阵的行。,(5.1.7),(5.1.8),(5.1.9),例 5.2 二进制7，4码的,g,(,x,)=,x,3,+,x,2,+1，,求系统码的,G,和,H,矩阵。,r,1,(,x,),x,6,x,2,+,x,(mod,g,(,x,),r,2,(,x,),x,5,x,+1(mod,g,(,x,),r,3,(,x,),x,4,x,2,+,x,+1(mod,g,(,x,),r,4,(,x,),x,3,x,2,+1(mod,g,(,x,),在,GF(2),上，元素的逆元就是它自己，所以,1 0 0 0 1 1 0,0 1 0 0 0 1 1,0 0 1 0 1 1 1,0 0 0 1 1 0 1,G,=,=,I,k,p,1 0 1 1 1 0 0,1 1 1 0 0 1 0,0 1 1 1 0 0 1,H,=,=-,p,T,I,n,-,k,5.2 由生成多项式的根定义循环码,循环码是模,x,n,-1,剩余代数中的一个以,g,(,x,),作生成元的理想，每一个码多项式都是,g,(,x,),的倍式。因此,g,(,x,),的根亦必是所有码字多项式的根，基于这点，我们可以从根来定义循环码。设码的生成多项式,g,(,x,)=,x,r,+,g,r,-1,x,r,-1,+,g,1,(,x,)+,g,0,g,i,GF(,q,),它必在某一个,GF(,q,),的扩域上完全分解，即它的全部根必在此扩域上。,关于,g,(,x,),的根有两种情况：一是,g,(,x,),无重根，一是有重根。由于有重根情况下用,g,(,x,),生成码，比无重根时生成的码除个别码外通常要差 7，故下面我,们仅讨论,g,(,x,),无重根的情况。为此，首先要找出,g,(,x,),无重根的条件。,g,(,x,)(,x,n1)，,或,g,(,x,),h,(,x,)=,x,n,-1。,若,g,(,x,),有,r,i,个重根，则,x,n,-1,也必含有,r,i,个重根。因此要保证,g,(,x,),无重根，首先必须要求,x,n,-1,无重根。,定理 5.2.1,在,GF(,q,),上多项式,x,n,-1,无重根的充要条件是(,n,，,q,)=1。,例 5.3 求,G,F(24),上以,，,2,，,4,为根的循环码。,设,GF(2,4,),是本原域元素，则它的最小多项式就是本原多项式,m,1,(,x,)=,x,4,+,x,+1，,，,2,，,4,，,8,是它的共轭根系。因此以,，,2,，,4,，,8,为根的循环码的生成多项式,g,(,x,)=,x,4,+,x,+1，,码长,n,就是,的级数，等于2,4,-1=15，故得到一个15，11码，这是一个循环汉明码。,设15，11码的码多项式,C,(,x,)=,c,14,x,14,+,c,13,x,13,+,c,0,，,c,i,GF(2)，,i,=0，1，2，14。,则,C,(,)=,c,14,14,+,c,13,13,+,c,1,+,c,0,=0,C,(,2,)=,c,14,(,2,),14,+,c,13,(,2,),13,+,c,1,2,+,c,0,=0,C,(,4,)=,c,14,(,4,),14,+,c,13,(,4,),13,+,c,1,4,+,c,00,C,(,8,)=,c,14,(,8,),14,+,c,13,(,8,),13,+,c,1,8,+,c,0,=0,或,(5.2.5),定理 5.2.1 若,H,矩阵的元素均在,GF(,q,m,),中，且第,j,行元素等于第,i,行相应元素的,q,次幂；则在,GF(,q,),中，由第,j,行元素所组成的,m,行，与第,i,行元素所组成的,m,行之间，每行均线性相关。,证明 设,H,的第,i,行元素为,0,，,1,，,2,，,n,-1,第,j,行元素为,q,0,，,q,1,，,q,2,，,q,(,n,-1),。,令,x,是,GF(,q,m,),中的任一元素，,是本原域元素，则,x,与,x,q可用域的自然基表示成,x,=,a,0,+,a,1,+,a,2,2,+,a,m,-1,(,m,-1),a,i,GF(,q,),(5.2.6),x,q,=,b,0,+,b,1,+,b,2,2+,b,m,-1,(,m,-1),b,i,GF(,q,)(5.2.7),由式(5.2.6)，并根据推论4.5.3可得,x,q,=(,a,0,+,a,1,+,a,2,2,+,a,m,-1,(,m,-1),q,=,a,q,0,+,a,q,1,q,+,a,q,2,2,q,+,a,q,m,-1,q,(,m,-1),=,a,0,+,a,1,q,+,a,2,2,q,+,a,m,-1,q,(,m,-1),(5.2.8),定义,iq,=,c,i,0,+,c,i,1,+,c,i,m,-1,m,-1,c,i,j,GF(,q,)，,i,=0，1，,m,-1,比较式(5.2.7)与式(5.2.8)并利用上式可知，,x,q,的系数(,b,0,，,b,1,，,b,m,-1,),完全可由,x,的系数(,a,0,，,a,1,，,a,m,-1,),的线性组合得到。,2,，,4,，,8,与,有完全相同的最小多项式,m,1,(,x,)，,因而它们有完全相同的零空间。而该定理也说明了这一点。所以在式(5.2.5)的,H,矩阵中，仅只考虑,14,，,13,，,，1,这一行的,G,F(2),上的四重表示即可。因而15，11循环汉明码的,H,为,式中，,14,，,13,，,和1的四重表示见表 4,-,2(下同)。,一般情况下，由于共轭根系有相同的最小多项式，因此由定理5.2.1及式(5.2.2)的,H,矩阵在,G,F(2,m,),域中可以简化为,例 5.4 求以,G,F(24),中的1，,，,2,，,4,元素为根的二进制循环码。,1=,0,的最小多项式是1+,x,，,所以,g,(,x,)=(1+,x,)(,x,4,+,x,+1)=,x,5,+,x,4,+,x,2,+1,n,=LCM(1，15)=15,得到一个15，10码，该码的,H,矩阵是,显然，这是一个增余删信汉明循环码。,一般情况下，,GF(2),上的循环汉明码是一个,2,m1，2,m,-1-,m,码，它的校验矩阵,(5.2.10),i,GF(2,m,),而增余删信汉明循环码是2,m,-1，2,m,-2-,m,码，,它的校验矩阵,(5.2.11),5.3 幂等多项式和最小循环码,一、幂等多项式,由前面讨论可知，一旦循环码的生成多项式,g,(,x,),确定，则码的校验多项式和码的参数,n,、,k,均确定。但是，要找,g,(,x,)，,必须对,x,n,-1,因式分解，当,n,较大时，这就变得很困难。为了避免这种情况，可在循环码中找到另一重要多项式 幂等多项式，它不需要对,x,n,-1,因式分解就能得到，并且能唯一地确定循环码。,定义 5.3.1 设,R,q,n,代表,GF(,q,),上以,x,n,-1,为模所构成的剩余类环。,E,(,x,),R,q,n,，,若,E,(,x,)=,E,2,(,x,)=,E,(,x,2,),则称,E,(,x,),为幂等多项式。,例如,E,(,x,)=,x,+,x,2,+,x,4,R,2,7,，,就是一个幂等多项式，因为,(,x,+,x,2,+,x,4,),2,=,x,2,+,x,4,+,x,=,x,+,x,2,+,x,4,显然，1是任何,R,q,n,环上的幂等多项式。,定理 5.3.1,(1)一个由,g,(,x,),生成的循环码或理想,C,g,(,x,),，,含有一个唯一的幂等多项式,E,(,x,)，,且,C,g,(,x,),=,C,E,(,x,)=,C,，,E,(,x,)=,p,(,x,),g,(,x,)。,当且仅当,g,(,i,)=0,时，,E,(,i,)=0。,(2),当且仅当,C,(,x,),E,(,x,)=,C,(,x,),时，,C,(,x,),C,g,(,x,),。,推论 5.3.1 若,E,(,x,),是码,C,的幂等多项式，则,C,的生成多项式,g,(,x,)=GCD(,E,(,x,),x,n,-1)。,例 5.7,GF(2),上的7，码。,g,(,x,)=,x,3,+,x,+1，,h,(,x,)=(,x,+1)(,x,3,+,x,2,+1)，,且由欧几里德算法,xg,(,x,)+,h,(,x,)=1,所以，7，4码的幂等多项式,E,(,x,)=,xg,(,x,)=,x,4,+,x,2,+,x,。,可以证明幂等多项式有如下性质：,(1),E,(,i,)=1，,或0,i,=0，1，,n,-1；,(2),若,E,(,x,),是一个幂等多项式，那么它的互反多项式,E,(,x,),也是一个幂等多项式。,码的幂等多项式,E,(,x,),与码的生成多项式,g,(,x,),之间有如下关系：,(1)码,C,信息位的个数，等于使,g,(,i,)0,的,i,的个数，也等于使,E,(,i,)=1,的,i,个数；,(2),g,(,x,)=GCD(,E,(,x,)，,x,n,-1)；,(3),若码,C,的幂等多项式为,E,(,x,),则码,C,对偶码,C,的幂等多项式为(1+,E,(,x,)。,二、最小循环码,定义 5.3.2 一个理想中若不再含有任何非零的理想，则称此理想为 最小(素)理想，相应的循环码称为 最小循环码或 既约循环码，而理想的幂等多项式称为 本原幂等多项式。,可以证明，每一个幂等多项式必是本原幂等多项式之和，而多项式环,R,q,n,中的每一个循环码，必是最小理想之和。,定理 5.3.2 若,x,n,-1=,p,0,(,x,),p,1,(,x,),p,2,(,x,),p,k,(,x,)，,这里,p,0,(,x,)=,x,-1，,p,i,(,x,),是,GF(,q,),上的既约多项式则当且仅当以,g,(,x,)=,P,i,(,x,),或,P,0,(,x,),作为码,C,的生成多项式时，码,C,才是一个最小循环码。这里，,P,i,(,x,),是,x,n,-1,中除,p,i,(,x,),之外的所有因子乘积。,5.4 缩短循环码与准循环码,一、缩短循环码,循环码生成多项式必是,x,n,-1,的因子，但在绝大部分,n,、,k,中,x,n,-1,的因子相对而言较少，限制了码的个数。为了增加,n,、,k,取值的数目增加码的个数，循环码经常用缩短形式，得到 缩短循环码。,缩短循环码是取,n,，,k,循环码中前,i,位信息位为0的码字作为码字，构成一个(,k,-,i,),维线性子空间，得到一个,n,-,i,，,k,-,i,(1,i,k,),缩短循环码。缩短循环码的校验位仍为,n,-,k,，,故该码的纠错能力至少不低于原来的,n,，,k,码，并且它的实现也并不比循环码复杂。,缩短循环码的生成多项式与原码相同，均为,g,(,x,)，,故编码电路与原码同。缩短循环码的,G,矩阵可以从原码的标准,G,阵中去掉前,i,行和前,i,列得到，,H,矩阵可以从原典型,H,阵中去掉前,i,列得到。,如由7，4循环汉明码缩短一位，便得到了6，3缩短码，它的,G,和,H,矩阵可直接由7，码得到：,由上述,G,6，3,矩阵可以明显看到，缩短循环码的码字之间，不一定存在有循环关系。但是这并不会影响译码器的复杂性，以后将看到缩矩循环码的译码器仅在原码译码器基础上，稍加修正即成。,二、准循环码与双环循环码,循环码,C,x,的每一码字，左移或右移循环一位仍是,Cx,的一个码字。也就是说，若,C,(,x,),C,x,，,则,xC,(,x,),Cx,(,m,od,xn,-1)，,即码在循环移位下具有 不变性。但是，对某些码而言，并不具有这种性质，例如，上面例举的7，4循环汉明码变成6，3缩短码，6，3码的每一码字循环移位一次不一定是该码的另一码字。对某些码而言，虽然码字循环移位一次得到的不是该码的码字，但若循环移位,n,0,(1),次，得到的仍是该码的一个码字,。,如某一6，3码，它的,G,矩阵为5.4.1),定义 5.4.1 一个,mn,0,，,mk,0,线性分组码，若它的任一码字左移或右移循环移位,n,0,次后，得到的仍是该码的一个码字，则称这类码为 准循环码。,由此可知，准循环码每个码字的码元位置号在,i,i,+,n,0,(mod,mn,0,),i,=1，2，,n,(5.4.2),置换下具有不变性。显然，循环码的,n,0,=1，,它是准循环码的一个特例。,由定理5.1.1知，循环码是模,x,n,-1,多项式剩余类环中的一个理想，由于准循环码不具有像循环码那样的循环移位一次下的不变性，因此很显然准循环码是模其它多项式,F(,x,),剩余类环中的一个理想，当,F(,x,)=,x,n,-1,时，准循环码就是循环码。可以证明 1缩短循环码就是准循环码。,下列矩阵,(5.4.3),在式(5.4.2)的置换下具有不变性，所以由此矩阵,G,生成的码是一个,mn,0,，,mk,0,准循环码。式中,I,是,k,0,k,0,阶单位方阵，0,是,k,0,k,0,阶0阵，,p,i,是,k,0,(,n,0,-,k,0,),矩阵。所以，准循环码的每一码字由,m,段组成，每段前面为,k,0,个信息元，后,n,0,-,k,0,个为校验元。与式(5.4.3)对应的准循环码的校验矩阵,(5.4.4),式中,I,和 0,分别表示(,n,0,-,k,0,)(,n,0,-,k,0,),阶单位方阵和全为0矩阵。,如果在式(5.4.3)和(5.4.4)中的,I,和 0,矩阵分别用,k,0,k,0,阶和(,n,0,-,k,0,)(,n,0,-,k,0,),阶任意方阵代替，则由此,G,和,H,矩阵产生的码称为 广义准循环码。,我们可把式(5.4.1),G,矩阵通过列交换变成准循环码系统码形式的,G,矩阵和,H,矩阵：,(5.4.5),(5.4.6),定义 5.4.2 由两个循环矩阵,I,k,(,单位方阵)和,p,阵组成的,G,=,I,k,p,生成的码称为 双环循环码。,显然，双环循环码等价于,n,0,=2,的准循环码。很多作者对这类双环循环码进行了研究，发现了一类性能很好的码。表 5,-,1列出了具有最大最小距离的二进,制,2,k,，,k,双环循环,码.,表 5,-,1 某些二进制2,k,k,双环循环码,表中，,p,阵生成元栏下的数字，表示码的生成矩阵,G,=,I,k,p,中，,p,矩阵第一行的八进制数表示。例如，8，4码的生成元为7，则,p,矩阵的第一行就是1110，因而码的,G,矩阵为,若化成式(5.4.3)准循环码形式则,虽然，这类2,k,，,k,双环循环码等价于,n,0,=2,的准循环码，但每个码字之间不一定存在准循环码码字之间的循环关系。,三、双环循环码和准循环码的多项式表示,考虑一个2,k,，,k,双环循环码或系统准循环码。,p,表示,G,矩阵中的循环矩阵，若,i,表示信息元，则码字,C,=,mG,=,m,I,k,p,=,m,mp,令,m,(,x,),表示信息元的信息多项式，,p,(,x,),表示,p,循环矩阵最上一行的多项式表示，则,p,矩阵的第二、三、行的多项式表示分别为：,xp,(,x,)(mod,x,k,-1),x,2,p,(,x,)(mod,x,k,-1),x,k,-1,p,(,x,)(mod,x,k,-1),很容易证明,k,k,阶循环码矩阵与模,x,k,-1,的多项式代数完全同构。因此，信息矢量,m,与循环矩阵,p,相乘,mp,的多项式表示为,m,(,x,),p,(,x,)(,m,od,x,k,-1)。,所以码字,v,的多项式表示为：(,m,(,x,)，m,(,x,),p,(,x,)(,m,od,x,k,-1),。,由此可知，系统准循环码或双环循环码的码字，可以看成是一个信息多项式,m,(,x,)，,后面跟随一个长为,k,的用,p,(,x,),产生的、模,x,k,-1,代数中的一个循环码。,5.5 平 方 剩 余 码,一、平方剩余的基本概念,定义 5.5.1 若对某一素数,p,，,存在有一个整数,x,，,使下式成立,x,2,i,(,m,od,p,),则称,i,是模,p,的 平方剩余；否则称为模,p,的 非平方剩余。,定理 5.5.1 若,p,是奇素数，则在 1 至,p,-1,的所有整数中，有(,p,-1)2,个是模,p,的平方剩余，有(,p1)2,个为模,p,的非平方剩余。,证明 这只要证明满足1,2,，2,2,，(,p,-1)2)2,的模,p,平方剩余的每一个均不相同即可。用反证法。若对一个,i,j,，,i,1，,i,，,j,(,p,-1)2,有相同的平方剩余：,i,2,j,2,(,m,od,p,),i,2,-,j,2,=(,i,+,j,)(,i,-,j,)0(,m,od,p,),由于,p,是素数，由第二章可知模,p,的剩余类是一个域，域中无零因子，所以，由上式可得,i,+,j,0,或,i,-,j,0(,m,od,p,),由于,i,1，,j,(,p,-1)2，,故,i,+,j,0，,所以只有,i,-,j,0(,m,od,p),或,i,j,(,m,od,p,)，,又因为,i,，,j,(,p,-1)2，,所以这意味着,i,=,j,，,与假设,i,j,相矛盾。因此，满足1,2,，2,2,，(,p,-1)2)2,的模,p,平方剩余中的每一个均不同，这说明在1，2，,p,中只有(,p,-1)2,个不同的平方剩余，其,余的(,p,-1)2,个为非平方剩余。,例如，,p,=7，,则满足1,2,，2,2,，3,2,的平方剩余为：1,2,1，2,2,4，3,2,2，它们每一个均不同，而其余的三个整数3，5，6为非平方剩余。这说明可以按照模,p,的平方剩余与平方非剩余对整数或模,p,的剩余类进行分类。模,p,的平方剩余还有以下性质(请读者证明之)：,(1)两个平方剩余的积，或两个非平方剩余的积仍是平方剩余。一个平方剩余与另一个非平方剩余之积为非平方剩余。,(2)若,p,=8,m,1，,则 2 是模,p,的平方剩余。若,p,=4,m,+1，,则-1(,p,-1)(,m,od,p,),是模,p,的平方剩余；若,p,=4,m,-1，,则-1是模,p,的非平方剩余。,二、平方剩余码,下面我们讨论,G,F(,q,),上的码长为素数,p,的平方剩余(,Q,R,),码。这里，,q,是模,p,的平方剩余，且为素数，对二进制,Q,R,码来说，,q,=2，,因而由性质(2)可知，码长为,p,=8,m,1,的 形式。,令,Q,表示模,p,的平方剩余集合，,N,表示模,p,的非平方剩余集合。若,是,G,F(,q,m,),域 的一个本原域元素，则由性质(1)知：当,i,是偶数时，,i,Q；,而,i,为奇数时,i,N，,且,0,=1Q，,因而,Q,是由,2,生成的一个循环子群。,由定理4.4.1可知，,GF(,q,m,),域中的所有非零元素都是,x,qm,-1=0,方程的根。因此若在,GF(,q,m,),中的某一子域内有一个,p,级根,，,则,p,=1，,，,2,，,3,，,p,-1,都是,x,p,-1,=0,方程的根。所以,x,p,-1=(,x,-1)(,x,-,)(,x,-,2,)(,x,-,p,-1,)=(,x,-1),q,(x,),n,(,x,),式中,(5.5.1),是系数在,GF(,q,),上的多项式。,定义 5.5.2,用下列多项式,q,(,x,)，(,x,-1),q,(,x,)，,n,(,x,)，(,x,-1),n,(,x,),生成的循环码，称为,GF(,q,),上的 平方剩余码，分别用,C,Q,，,C,Q,，,C,N,，,C,N,表示。,显然，,C,Q,和,C,N,码分别是,C,Q,和,C,N,码的增余删信码。因而,C,Q,C,Q,，,C,N,C,N,。,在二进制情况下，,C,Q,和,C,N,均为,C,Q,和,C,N,的偶重量子码。且,C,Q,和,C,N,码的信息位,k,=(,p,+1)2，,而,C,Q,和,C,N,码信息位的个数,k,=(,p,-1)2。,例 5.9,q,=2，,p,=81-1=7。,x,7,-1=(,x,-1)(,x,-,)(,x,-,2,)(,x,-,3,)(,x,-,4,)(,x,-,5,)(,x,-,6,),q,(,x,)=(,x,-,)(,x,-,2,)(,x,-,4,)=,x,3,+,x,+1,n,(,x,)=(,x,-,3,)(,x,-,5,)(,x,-,6,)=,x,3,+,x,2,+1,由,q,(,x,),与由,n,(,x,),生成的循环码都是7，4，3循环汉明码。而由(,x,-1),q,(,x,),和,(,x,-1),n,(,x,),生成的码都是增余删信汉明码。,定理 5.5.2,C,Q,和,C,N,码的最小距离,d,满足下列不等式：,(5.5.2),证明 设,a,(,x,),是,C,Q,中的一个重量最轻且等于,d,的码字，,n,是模,p,的一个非平方剩余,则,a,(,x,n,),是,C,N,中的一个重量最轻且为,d,的码字。那么,a,(,x,),a,(,xn,),既在,C,Q,又在,C,N,中，因为：,又由于：,可知，非零,a,(,x,),a,(,x,n,),有最小重量为,p,。,因为,a,(,x,),有最小重量为,d,，,则在,a,(,x,),a,(,x,n,),中的最大非0项数为,d,2,，,所以,d,2,p,，,d,。,若,QR,码CQR,是一个自对偶码，且最小距离是 4 的倍数，则可以证明,C,Q,R,码的最小距离,d,4,n,20+4,(5.5.3),如二进制的8，4，4，24，12，8，32，16，8，48，24，12，80，40，16，100，50，20等码均满足式(5.5.3)给出的限。,某些,QR,码与准循环码有密切关系。例如17，9,QR,码，,g,(,x,)=,x,8,+,x,7,+,x,6,+,x,+1，,d,=5，,删去一个信息位后，就得到一个16，8准循环码。可以证明二进制,C,Q,QR,码删去一个信息位，以及扩展,QR,码 都等效于一个,n,0,=2,的准循环码。,QR,剩余码在,x,x,r,(r,为平方剩余)置换下，可以证明是不变的，因而可以应用比较简单的置换译码方法进行译码，这将在以后谈到。表 5,-,2 给出了某些平方剩余码的生成多项式和最小距离。表中生成多项式栏下的数字，代表生成多项式各项的次数。例如，(3，1，0)代表,g,(,x,)=,x,3,+,x,+1。,表 5,-,2,某些二进制,QR,码,5.6 多项式及域元素运算电路,一、多项式相加电路,已知,G,F(,q,),上的两多项式,A,(,x,)=,a,n,-1,x,n,-1,+,a,n,-2,x,n,-2,+,a,1,x,+,a,0,a,i,GF(,q,),B,(,x,)=,b,n,-1,x,n,-1,+,b,n,2,x,n,-2,+,b,1,x,+,b,0,b,i,G,F(,q,),由第四章所定义的多项式相加,C,(,x,)=,A,(,x,)+,B,(,x,),=(,a,n,-1,+,b,n,-1,),x,n,-1,+(,a,1,+,b,1,),x,+(,a,0,+,b,0,),=,c,n,-1,x,n,-1,+,c,n,-2,x,n,-2,+,c,1,x,+,c,0,c,i,GF(,q,)，,c,i,=,a,i,+,b,i,，,i,=0，1，2，,n,-1,要完成上述多项式相加，可用图 5,-,1所示的电路完成。,图 5,-,1 多项式,A,(,x,)+,B,(,x,),并行运算电路,图 5,-,1 及以后各图中符号的意义 如下：,：,代表一个寄存,G,F(,q,),上元素的单元，可用触发器、磁芯或其它存贮单元组成；,：,代表模,q,相加器，无进位运算；,：代表两个输入端与门；,：代表乘,a,的模,q,常数乘法器，无进位运算；,：代表两个输入端的或门。,两个多项式相加之结果,C,(,x,),的系数存贮在,A,(,x,),寄存器中。图 5,-,2为串行相加电路，相加结果送入,A,(,x,),系数寄存器中。,图 5,-,2 多项式,A,(,x,)+,B,(,x,),串行运算电路,若为,A,(,x,)-,B,(,x,)，,则只要把,B,(,x,),系数以,G,F(,q,),中的加法逆元代替得到-,B,(,x,)，,再作-,B,(,x,)+,A,(,x,),运算即可。在二进制情况下“-”与“+”运算相同，因此相加电路与相减电路一样。,二、多项式相乘电路,设两多项式为：,A,(,x,)=,a,k,x,k,+,a,k,-1,x,k,-1,+,a,1,x,+,a,0,a,i,GF(,q,),B,(,x,)=,b,r,x,r,+,b,r,-1,x,r,-1,+,b,1,x,+,b,0,b,i,G,F(,q,),已知两多项式相乘为,C,(,x,)=,A,(,x,),B,(,x,),=,a,k,b,r,x,k,+,r,+(,a,k,b,r,-1,+,a,k,-1,b,r,),x,k,+,r,-