通信原理电子版讲义--信道编码（5）

1循环码(Cycliccode)•循环码概念及特点•码多项式表示•循环码的性质•码多项式与循环码移位后的关系•循环码的生成多项式及其构造•寻找生成多项式•生成矩阵和监督矩阵•非系统码系统码•循环码的编码器•循环码的译码器2循环码概念及性质特点•概念•如果是C的码组，则它的左右移位都是C的码组，具有这种特性的线性分组码称为循环码。•性质特点–线性分组码–循环性——任一许用码字经过循环移位后，得到的码组仍为一个许用码组•如是循环码的一许用码组•则也是一许用码组)(0123456ccccccc)(1234560ccccccc3生成多项式g(x)产生循环码•由前Theo.一个(n,k)的二进制循环码可以看成是唯一由它的生成多项式产生，即例如(7,3)循环码，n=7,k=3,r=4如果信息位为010，u(x)=x（信息多项式）生成码为0111010)()()(xgxuxc1)(234xxxxgxxxxxgxuxc345)()()(4生成矩阵G(x)•由于k位信息位共有个码组，都可用此法产生，如果现有信息码生成k个码字，且这k个码字都线性无关，用这k个码字作为一个矩阵G的k行构成生成矩阵G(x)1)()()(021xxuxxuxxukk)(1)()()(21xgxgxxgxxGkkk2GUC5例：由(7,3)循环码生成多项式，构成生成矩阵•(7,3)循环码1)(234xxxxg1)1(1)1()1()(23434524562342342342xxxxxxxxxxxxxxxxxxxxxxxG010110001011100010111G这样构成的循环码并非是系统码6非系统码系统码（1）Ex：(7,4)码，已知信息位为1001时，求：编码器输出。or（系统码输出）)(1)()()(21xgxgxxgxxGkk所得的余式除是ininknknnnnnxxgxrxrxxrxxrxxG)()()()()()(22111)(23xxxg7非系统码系统码（2）•系统码的码多项式为•例如，(7,4)码，1011•（1)(2）)()()(xrxxuxckn1)(23xxxg1)(3xxxu3463)(xxxxxu)()()()()(xgxrxqxgxuxkn22454535623346231xxxxxxxxxxxxxxxx2)()3(xxr监督位为101110010118生成矩阵和监督矩阵•系统码的生成矩阵典型形式•非系统码系统码–生成矩阵–监督矩阵QIGkrTIQH100010011100100111001010110001011100010111)(DGkIQ101011001001110011101H9生成矩阵和监督矩阵•可验证•由于g（x）能除尽•即或•生成多项式为•监督多项式为•可得到0TGH1nx)()(1xhxgxn01...)(gxgxgxgknkn01...)(hxhxhxhkk0...0...0......001111102110110021120011000kknkknknknknknknknkkhghghghghghghghghghghghghgghgh)1mod(0)()(nxxhxg10•如果生成矩阵是•则监督矩阵为•两者满足nkknknknggggggG000......0.....................00......nknkkkhhhhhhH)(000...0...0.....................0...00...0...)(0knkTGH互反多项式与零空间•由于xn+1可被g(x)整除，xn+1=g(x)h(x)•若h(x)=hkxk+hk-1xk-1+…+h1x+h0，•则h*(x)=h0xk+h1xk-1+…+hk-1x+hk为h(x)的互反多项式•g(x)和h*(x)均可生成长度为n的循环码，且互为零空间•Ex：P9912循环码的编码器•原理：按系统码的生成方式（除法器电路）以(7,4)码为例)()()(xrxxuxckn1)(23xxxg)()()()()(xgxrxqxgxuxknD1D2+D3+输入校验位码字输出13循环码的译码器•译码比编码复杂得多•检错、纠错•译码三步–伴随式S的计算–由S得到错误图样–纠正14伴随式的计算•发送码组•接收码组•误差码组•校正子只与E有关，根本是计算校正子][021cccCnn][021yyyYnnECY][021eeeEnniiiiiiyceyce则则如果,1,0ECYTTTTT)(EHEHCHHECHYS15检错•用于检错：•将接受到的码组进行出发运算，如果除尽，则说明传输无误；•如果未除尽，则表明传输出现差错，要求发送端重发。•用于这种目的的循环码经常被成为循环冗余校验码，即CRC校验码。16校正子S的计算•生成多项式g(x)去除接收码字Y(x))(Mod)()(xgxYxS17CRC码（循环冗余校验码）•是一种循环码，用于检错。•具有很强的检错能力，而且编码器及译码器都很容易实现。•在数据通信中得到广泛应用。（通过MODEM传输文件的协议，如ZMODEM协议中均用到了CRC校验技术）•可以检测出的错误如下：（1）突发长度n-k的突发错误；（2）大部分突发长度＝n-k+1的错误；（3）大部分突发长度n-k+1的错误；（4）所有与许用码组的码距dmin-1的错误；（5）所有奇数个随机错误。18•将任意k个信息码组用类似p100图9.3.1的编码器编成系统码，•得到一个长为的码，这就是CRC。rkn1913464xxxx1245781011121622232632xxxxxxxxxxxxxx1812142324xxxxx121516xxx125611141516xxxxxxxx11416xxx151216xxx1489101112xxxxxxx1231112xxxxx134678910xxxxxxx124678xxxxx13478xxxxx1234xxxxPolynomialParitybitsCRC-6464CRC-3232CRC-2424CRC-1616CRC-1212CRC-1010CRC-88CRC-6x6+x5+x2+x+16CRC-4413464xxxx20BCH码（Bose-Chaudhuri-Hocquenghem码）•是线性分组码中循环码的一种重要子类，有严密的代数结构，是目前研究较多、应用较广的一种线性分组码。•具有纠正多个随机错误的能力。•根据对纠错能力的要求，选择参数，并根据代数结构构造编译码算法。•如：n=7,k=4,t=1;n=15,k=7,t=2;n=31,k=16,t=3;n=127,k=50,t=13。21BCH码（Bose-Chaudhuri-Hocquenghem码）•是线性分组码中循环码的一种重要子类，有严密的代数结构，是目前研究较多、应用较广的一种线性分组码。•具有纠正多个随机错误的能力。•根据对纠错能力的要求，选择参数，并根据代数结构构造编译码算法。•如：n=7,k=4,t=1;n=15,k=7,t=2;n=31,k=16,t=3;n=127,k=50,t=13。22RS码（Reed-Solomon码）•是一种非二进制的BCH码。即：在（n,k）RS码中，输入信息被分成km比特一组，每组包括k个符号，每个符号由m比特组成。•纠正t个符号错误的RS码参数如下：码长n=2m-1符号，或m(2m-1)比特信息段k符号，或km比特监督段n-k=2t符号，或m(n-k)比特最小码距d=2t+1符号，或m(2t+1)比特