循环码

6.3循环码循环码是一种特殊的线性分组码，属于线性分组码的一个重要子类，也是目前研究最为透彻的一类码，大多数有实用价值的纠错码都是循环码。循环码与一般的线性分组码相比具有以下优点：循环码的编码及译码易于用简单的具有反馈连接的移位寄存器来实现。定义6.3.1设有(n,k)线性分组码C，如果它的任意一个码字的每一次循环移位仍然是C中的一个码字，则称C为循环码。也即，如果C=(cncn-1…c2c1)是循环码C的一个码字，那么C=(cn-1cn-2…c1cn)等也都是C的码字时，则所有这些具有循环特性的码字的全体便构成了循环码C。循环码的主要特点是：①理论成熟：可利用成熟的代数结构深入探讨其性质；②实现简单：可利用循环移位特性在工程上进行编、译码；③循环码的描述方式有很多，但在工程上最有用的是采用多项式的描述方法。信息码元码字00000000000010011101010010011101101110101001001110101101001111011010011111110100表6.3.1循环码的例子6.3.1循环码的多项式描述设有循环码字C=(cncn-1…c2c1)，则可以用一个次数不超过n-1的多项式惟一确定，其相应的多项式可表示为：(6.3.1)由循环码的特性可知，若C=(cncn-1…c2c1)是循环码C的一个码字，则C(1)=(cn-1…c1cn)也是该循环码的一个码字，它的码多项式为：(6.3.2)比较式(6.3.1)和式(6.3.2)，得：121()nnCxcxcxc(1)111()nnnCxcxcxc该式说明，码字循环一次的码多项式C(1)(x)是原码多项式乘x后再除以xn+1所得的余式，即：由此可以推知，C(x)的i次循环移位C(i)(x)是原码多项式C(x)乘xi后再除以xn+1所得的余式，即：(6.3.3)1(1)11()()111nnnnnnnncxcxcxCxCxccxxx(1)()()mod(1)nCxxCxx()()()mod(1)iinCxxCxx表6.3.2(7,3)循环码的循环移位循环次数码字码多项式000000000011101x4+x3+x2+110111010x(x4+x3+x2+1)mod(x7+1)=x5+x4+x3+x21110100x2(x4+x3+x2+1)mod(x7+1)=x6+x5+x4+x231101001x3(x4+x3+x2+1)mod(x7+1)=x6+x5+x3+141010011x4(x4+x3+x2+1)mod(x7+1)=x6+x4+x+150100111x5(x4+x3+x2+1)mod(x7+1)=x5+x2+x+161001110x6(x4+x3+x2+1)mod(x7+1)=x6+x3+x2+x6.3.2循环码的生成矩阵在循环码的码多项式中，每一个能整除xn+1的(n-k)次首一多项式都是该码的生成多项式，记为g(x)。将g(x)经过k-1次循环移位，共得到k个码多项式：g(x)、xg(x)、…、xk-1g(x)。这k码多项式显然是相互独立的，于是得到循环码的生成矩阵G(x)：(6.3.4)12()()()()()kkxgxxgxGxxgxgx循环码可由它的一个n-k次首一多项式g(x)来确定，因此称它为码的生成多项式，即：(6.3.5)码的生成多项式具有如下性质：①在(n,k)循环码中，n-k次码多项式是最低次的码多项式。②在(n,k)循环码中，g(x)是惟一n-k次多项式。③在(n,k)循环码中，每个码多项式C(x)都是g(x)的倍式。④任意(n,k)循环码的生成多项式g(x)一定xn+1。10()nknkgxgxgxg例6.3.2求二进制(7,3)循环码的生成多项式。解：分解多项式x7+1，取其四次首一多项式作为生成多项式：x7+1=(x+1)(x3+x+1)(x3+x2+1)可将一次和任一个三次多项式的乘积作为生成多项式：g(x)=(x+1)(x3+x2+1)=x4+x2+x+1或g(x)==(x+1)(x3+x+1)=x4++x3+x2+1由于线性码的生成矩阵G与一致校验矩阵H满足关系GHT=0，而循环码也是线性码，如果设g(x)为(n,k)循环码的生成多项式，它必为xn+1的因式，则有：xn+1=g(x)h(x)(6.3.6)称h(x)为(n,k)循环码的校验多项式，且：h(x)=hkxk+…+h1x+h0(6.3.7)(n,k)循环码的一致校验矩阵H为**2*1*()()()()()nknkhxxhxHxxhxxhx011011011000000kkkkkkhhhhhhhhHhhhh式中h*(x)为h(x)的反多项式，即h*(x)=h0xk+h1xk-1+…+hk-1x+hk例6.3.3以二进制码(7,3)码为例，说明(n,k)循环码可由生成多项式或校验多项式完全确定。由多项式的因式分解知：其四次多项式为生成多项式：其三次多项式为校验多项式：由等式x7+1=g(x)h(x)，两端的同次系数应相等，得：73421(1)(1)xxxxxx42()1gxxxx3()1hxxxx3的系数x4的系数x5的系数x6的系数将上述方程组写成矩阵形式：302112030ghghghgh403122130ghghghgh4132230ghghgh42330ghgh012340123301232012310000000000000000hhhhghhhhghhhhghhhhgg上式中列矩阵的元素就是生成多项式g(x)的系数，它本身是一个码字，那么第一个矩阵即为(7,3)循环码的一致校验矩阵，即：可见，一致校验矩阵的第一行是码的校验多项式的系数的反序排列，而第二、三、四行分别是第一行的移位，由此得到用校验多项式的系数来构成的一致校验矩阵：01230123(7,3)01230123000000000000hhhhhhhhHhhhhhhhh(7,3)0001101001101001101001101000H6.3.3系统循环码系统循环码的生成矩阵系统的一致校验矩阵是例6.3.4以g(x)=(x3+x+1)为生成多项式生成一个(7,4)循环码，要求生成的循环码是系统码。解：由例6.3.1得对应给定g(x)的循环码的一般生成矩阵为：kGIPTnkHPIk1011000(1)0101100(2)0010110(3)0001011(4)G对矩阵G的行进行运算，将第⑴、⑶、⑷行相加后作为第1行，第⑵、⑷行相加后作为第2行，得：对应：这样，就得到系统循环码的生成矩阵和一致校验矩阵。01000101(1)(3)(4)0100111(2)(4)00101100001011G0111010001110101101001H6.3.7常用的循环码(1)循环冗余校验码在数据通信中，信息都是先划分成小块再组装成帧后(或叫分组、包等，仅名称不同而已)在线路上统计复用传送或存入共同物理介质的，帧尾一般都留有8、12、16或32位用作差错校验。如把一帧视为一个码字，则其校验位长度不变而信息位和码长是可变的，其结构符合缩短循环码的特点。只要以一个选定的循环码为基础，改变的值，就能得到任何信息长度的帧结构，而纠错能力保持不变。这种应用下的缩短循环码称为循环冗余校验码(CyclicRedundancyCheck，CRC)。nkkn(,)niki(,)nki循环冗余校验码是系统的缩短循环码，码的结构如图6.3.10所示。图6.3.10循环冗余校验码(CRC)结构图中，码字用码多项式表示，是除以后的余式，为次多项式，它们之间满足：。虽然循环冗余校验码指的是整个码字，但人们习惯上仅把校验部分称为CRC码。如果传输过程无差错，则接收码字应等于发送码字这时能被整除；如果，则说明在传输过程中出现了误码。()Cx()rx()nkxmx()gx()gxnk()()()nkCxxmxrx()Cx()rx()Cx()rx()gx()()rxCx例6.3.7某CRC的生成多项式为。如果想发送一串信息“110001”的前6位，并加上CRC校验，发送码字应如何安排，接收码字又如何校验？解：本题信息码字多项式，，从生成多项式的阶数得校验位数等于4，因此。将除以得余式：于是，发送码字多项式，对应的发送码字为(1100011100)。4()1gxxx()Cx()rx54()1mxxx6k()gx10n()nkxmx()gx()rx45432()()mod()(1)mod()nkrxxmxgxxxxgxxx()()()nkCxxmxrx98432xxxxx在接收端，CRC校验实际上就是做除法运算：如果传输过程无差错，则能被整除，余式为“0”；如果余式不为“0”，则说明一定有差错。例6.3.8假设，即信息码字为(1011001)，，求CRC校验码。由题得：，用去除，有：()rx()gx643()1mxxxx43()1gxxx410874()xmxxxxx()gx4()xmx经相除后得到的最后余数1010就是冗余校验码。所以，发送码字为：(10110011010)。需要注意的是，这里所涉及的运算与前面一样都是模2运算。如果例子中的发送码字(10110011010)经传输后受噪声的干扰，在接收端变成为(10110011100)。求余式的除法如下：()rx求得余式不为零，相当于在发送码字上加了差错图样“00000000110”。差错图样相应的多项式为。有差错时，接收端收到的不再是，而是+。由于：若，则这种差错就能检测出来，若，那么由于接收到的码字多项式仍然可被整除，错误就检测不出来，也即发生了漏检。理论上可以证明，循环冗余校验码的检错能力如下：①可检测出所有奇数个错；②可检测出所有单比特和双比特的错；2()exxx()Cx()Cx()ex()+()()()=+()()()CxexCxexgxgxgx()()ex0gx()()ex0gx()gx③可检测出所有小于、等于校验码长度的突发错误；④对于位的突发性错误，查出概率为；⑤对于多于位的突发性错误，查出概率为。由此可以看出，只要选择足够的冗余校验位，可以使得漏检率减到任意小的程度。循环冗余编码法在数据传输中得到了最广泛的应用。CRC本身具有纠错功能，但网络中一般不用其纠错功能，仅用其强大的检错功能，检出错误后要求重发。目前广泛使用的CRC码已成国际标准，生成多项式主要有下述四种：nk1nk(1)12r1nk12rCRC-12，其生成多项式：CRC-16，其生成多项式：CRC-CCITT，其生成多项式：CRC-32，其生成多项式：循环冗余校验码的编译码过程通常用采用硬件来实现，因为除法运算易于用移位寄存器和模2加法器来实现，可以达到比较高的处理速度。随着集成电路工艺的发展，循环冗余码的产生和校验均有集成电路产品，发送端能够自动生成CRC码，接收端可自动校验，速度大大提高。121132()1gxxxxxx16152()1gxxxx16155()1gxxxx322623221612111087542()1gxxxxxxxxxxxxxxx(2)BCH码BCH码是一类最重要的循环码，能纠正多个随机错误。这种码可以是二进制码，也可以是非二进制码。BCH码具有纠错能力强，构造方便，编、译码易于实现