第三章eafdsa

第三章循环码一、循环码的特点（没有分节）1、循环码是一种分组码，可设计成系统码2、循环码不仅是线性分组码的封闭性，还具有循环特性。循环性：（0121...aaaann）为非零循环码组，则（1032...nnnaaaa）、（2143...nnnnaaaa）···也为许用码组，不论右移或左移结果都一样，均为循环码组。3、循环码的码多项式表示：许用码A=(0121...aaaann))(DA=012211...aDaDaDannnn左移i位后的码组)(iA=121(...)ninininiaaaa其码多项式为：)()(DAi=ininninninaDaDaDa12211...)()(DAi=iD)(DAmod)1(nD例1：循环码为（1100101）则)(DA=1256DDD)()1(DA)(DDAmod)1(7D)(DDA=DDDD367所以)()1(DA=136DDD对应码组为（1001011），正好是将（1100101）直接循环左移一位的结果。二、生成多项式1、循环码的要素：循环码完全由其码长度n及生成多项式)(Dg所决定。2、生成多项式)(Dg：一个能除尽1nD的n-k阶多项式称为循环码(n,k)生成多项式。3、循环码的构成：阶数低于n并能被)(Dg除尽的一组多项式就构成一个(n,k)循环码。阶数小于等于n-1能被)(Dg除尽的多项式都是循环码的许用码组。设)(DA是循环码（n,k）的许用码组多项式，)(Dg为(n,k)循环码的生成多项式，显然有)(DA=)()(DGDM其中)(DM为次数不大于k-1的多项式由于)(DA的形式或变化取决于)(DM的变化(())MD1k故)(DM多项式的个数=k2)(DA多项式的个数=k2，即(n,k)循环码的许用码组k2个例2：令n=7,)(Dg=1234DDD是17D的一个因式，求(7,3)循环码码组。解：n-k=4，k2=32=8可由)(Dg导出8个阶数不大于6的多项式是)(Dg的倍式，正好对应许用码组。0=)(Dg·0(0000000)1234DDD=)(Dg·1(0011101)DDDD345=)(Dg·D(0111010)521DDD=)(Dg·)1(D(0100111)2456DDDD=)(Dg·2D(1110100)1356DDD=)(Dg·)1(2D(1101001)DDDD236=)(Dg·)(2DD(1001110)641DDD=)(Dg·)1(2DD(1010011)这八个许用码组由两个循环链组成。其中一个为当然链。00000000001111例3、两类特殊的循环码：)1,(nn，)1,(n解：对n值有：1nD=)1(D)1D...(21nnDDa)若取)(Dg=1D1)1())((nnDg则：（n，k）=（n，n－1）显然可证，1D的任何倍式的码重必定保持偶数，且最小码重理当为2，故2mindb)若取)(Dg=1D...21nnDD则（n，k）=(n,1)故许用码组=12=2个。00000001111111这里有：0码字0多项式，全1码字)(Dg本身。这种循环码为重复码(n,1)，ndmin结论：当循环码的码长n为奇数时，二元循环码共有偶数个循环链。4．循环玛的演变：任何(n,k)循环玛，其生成多项式g(D)为n-k阶多项式g(D)*g(D+1)为新的生成多项式，从而构成循环玛(n,k-1)，其最小码距增加1。5．监督多项式：1nD=h(D)g(D),称g(D)为生成多项式，h(D)为监督多项式(n,k)生成多项式d纠检错能力监督多项式(7,6)1D2检1错332(1)(1)DDDD(7,4)321DD3纠1个错或检2个错32(1)(1)DDD(7,3)32(1)(1)DDD4纠1个错同时检2个错31DD(7,1)332(1)(1)DDDD7纠3个错1D（7,k）循环码表其中：321DD与31DD为互反多项式6．本原多项式：一个n次多项式F（x）若满足下列条件，则称为本原多项式：（1）F（x）是既约的，即不能再分解；（2）F（x）可整除1mx，这里21nm（3）F（x）不可能整除1qx，这里qm如上面73321(1)(1)(1)DDDDDD中两个3阶多项式都是本原多项式，因为他们都是既约多项式，而且不能除尽61D、51D、41D。结论：以本原多项式作为生成多项式得到的循环码(n,k)为循环汉明码。循环码汉明码线性分组码循环汉明码如（7，4）循环码即为循环汉明码。三、循环码的生成矩阵和监督矩阵设()gD为n－k阶多项式，且为（n，k）循环码的生成多项式1）121()()()()KKkDgDDgDGDgDG=（）kn（非系统码）--110---110---110,,(),nknknknknknkggggggggGDgggg输入信息元与码字的关系12012-120()(,,,)()()()()()kkkkkkADmmmGDmDmDmgDmDgD表明循环码多项式A（D）既可由信息元和生成矩阵多项式相乘得到，也能由信息元对应的多项式与生成多项式之积得到。2）系统循环码生成矩阵-111222-()()()()()()()nnnkkkDrDCDCDDrDGDCDDrD其中：1122()mod()r()mod()()mod()nnnkkrDDgDDDgDrDDgD显然：()()()(i=1,2,k)niiDqDgDrD或：()()()niiqDgDDrD由上式可知：q(D)g(D)为生成多项式的倍式，故为许用多项式，从右边观察k个许用多项式线性无关。故可构成生成矩阵1122n-k()()()()nnkDrDDrDGDDrD由1()()nDgDhD，若已知g（D）则可求h(D)。h(D)为监督多项式，10()kkhDhDhDh010101()0kkknknhhhhhhhhhH例4．已知（7，4）系统码的生成多项式为32()1gDDD，求G。解：由7162172527342374324()mod()()1mod()()1mod()()1mod()rDDDDDgDrDDDDgDrDDDDDgDrDDDDgD故62542321()11DDDDDGDDDDDDG=cdcc0001101001011101000111000110＝4,IQ，H=011100111100101011100共16个码字，分别来自4个循环链（G中出现的c、d循环链和全1链a，全0链b），显然为特殊的线性分组码。例5：已知（7，4）系统码的生成多项式为g（D）=12DD，求G。解：由r1(D)12617DDDmodg(D)r2(D)27D125DDDmodg(D)r3(D)37DDDD24modg(D)r4(D)47D13DDmodg(D)G=ccdc0001011001011001001111000101H=110100101110101110100有a，b，c，d四个循环链，与例4相同。3）互反多项式：两个同阶g1(D)、g2(D)若生成的循环码组集完全相同，则称这两个g1(D)、g2(D)为互反多项式。例6：已知前表中（7，3）码的生成多项式为g（D）=1234DDD，监督多项式为h(D)=123DD，求生成多项式及监督矩阵。解：非系统码生成矩阵：111010001110100011101dGdd1011000010110000101100001011H观察（7，3）循环码发现它是（7，4）循环码中两个循环链（b，d）组成。结论：（n，k-1）循环码是（n，k）循环码的子集。4）对偶码以监督多项式h（D）作为生成多项式构造得到（n，n-k）循环码，它与以g(D)作为生成多项式生成的（n，k）循环码，互称为对偶码。四、循环码的编码器五、循环码的译码器P3-11