7交大通信技术基础课件6b54

1、1第五节 循环码循环码是线性分组码中一类重要的码，它是以现代代数理论作为基础建立起来的。循环码的编码和译码设备都不太复杂，且检错纠错的能力较强，目前在理论和实践上都有较大的发展。一、循环码的循环特性循环码是一种线性分组码，且为系统码，即前位为信息码，后位为监督码，它除了具有线性分组码的封闭性外，还具有循环性：即循环码中任一许用码组经过循环移位后（将最后端的码元移至左端，或相反）所得到的码组仍为它的一许用码组。2(7,3)循环码：信息位监督位码组编号6a5a4a3a2a1a0a100000002001011130101110401110015100101161011100711001018111

2、00103一般来说，若 是一个(n,k)循环码的码组，则下列也都是该循环码的码组。),(0121aaaann ),(1032 nnnaaaa),(2143 nnnnaaaa),(1210aaaan 41、码多项式为了便于用代数理论来研究循环码，把长为n的码组与(n-1)次多项式建立一一对应的关系，即把码组中各码元当作是一个多项式的系数。若码组则相应的多项式表示为（7，3）循环码中的任一码组可以表示为),(0121aaaaAnn 012211)(axaxaxaxAnnnn 012233445566)(axaxaxaxaxaxaxA5这种多项式中，x只是码元位置的标记。例如上式表示第7码组中，a6

3、、 a5、 a2和 a0为“1”，其它均为零。我们对x的取值并不关心，多项式中的存在只表示该对应码位上是“1”码，否则为“0”码，我们称这种多项式为码多项式。例如表中第7码组可表示为：由此可知码组和码多项式本质上是一回事，只是表示方法不同而已。1010011)(23456xxxxxxxA1256xxx62、码多项式的按模运算（1）整数的模n运算如果一整数m可以表示成：Q为整数，则称在模n运算下有：如：可见：在模n运算下，一整数等于其被n除得的余数。npnpQnm，），（模npm ），（模2011），（模213217（2）码多项式的模运算由于码多项式的系数为二进制，所以按模2运算，在模2运算中，

4、用加法代替减法。)()()()(xRxQxNxF），（模)()()(xNxRxF），（模1133xx），（模1113224xxxxx81024 xx13xxxx 0412 xx913x113x13x10在循环码中，若T(x)是一个长度为n的许用码组，则xiT(x)在模(xn+1)运算下，也是一个许用码组。），（模1)()(nixxTxTx012211)(axaxaxaxTnnnn 112211)( ninnininninnixaxaxaxaxTxiininxaxaxa01122 11)() 1)()() 1)()()(22110112211221101122112211221101122112

5、21101122112211inininiininninninininiininnininininninininiininninninininiininninnininninniaxaxaxaxaxaxaxaxaxaxaxaxaxaaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxTx 12结论：一个长为n的循环码，它必定是按模(xn+1)运算的一个余式。1)(256xxxxTT(x)是T(x)代表的码组向左循环移位i次的结果。举例：举例： 是(7,3)循环码的一个许用码组，则x3T(x)在模(x7+1)运算下，也是一个许用码组。inininiininaxaxax

6、axaxaxT 221101111)(133、循环码的生成矩阵G在讨论线性分组码时已经指出：若找到了码的生成矩阵G，就可以由k个信息位得出整个码组，而且生成矩阵的每一行都是一个码组。如(7,4)线性分组码：当a6a5a4a3=1000，则码组A就等于G的第一行；当a6a5a4a3 =0100，则码组A等于G的第二行，等等。由于G是k行n列矩阵，因此，如能找到k个已知码组，就能构成矩阵G。这k个已知码组必须是线性不相关的，否则，给定的信息位与编出的码组就不是一一对应的。1101010111111000010000100001GGaaaaA345614循环码具有封闭性，即码中任意两码组按位模2和后

7、形成的新序列仍为一（许用）码组，由于两个相同的码组相加得一个全0序列，所以循环码一定包含全0码组。(n,k)循环码共有2k个不同码组，从中找到一个码组：其前面其前面的（的（k kl l）位都是）位都是0 0，而第，而第k k位及第位及第n n位为位为l l，即幂次大于，即幂次大于n-kn-k的的系数为系数为0 0，x xn-kn-k及及x x0 0的系数为的系数为l l，而其他系数为，而其他系数为O O或或1 1的码多项式的码多项式。用表示这一码多项式，即1000)(1110 xaxaxxgknknkn码全101000121aaakn 15第k位及第n位必须为“1”，是因为：若第n位不为1，该

8、码组右移后将成为前k位都是0，而后（n-k）位不都为0，这是不可能的（按全0是一码组的要求，信息位全为0，则监督位也必定全为0），所以，第n位必定是“1”。同理，也可证明，第k位也必须是“l”。称g(x)为生成多项式。由g(x)可得到生成矩阵G(x) )()()()()(21xgxxgxgxxgxxGkk16在前面介绍的(7,3)循环码中，n-k=4，因此，表中唯一的一个4次码多项式代表的码组是第2组001011，相对应的码多项式（即生成多项式）为：1)(24xxxxg1000000000)()()()(2423523462xxxxxxxxxxxxgxxgxgxxG11101000111010

9、0011101G17G它不符合IkQ形式，所以此生成矩阵不是典型的。不过G可通过线性变换成为典型的生成矩阵，如将G矩阵中第一行与第三行相加（101ll000010111=1001011）后取代第一行，此时便成为典型的生成矩阵。111010001110101101001G18循环码的许用码组可表示为：)()()()()(2456456xgxxgxgxaaaxGaaaxT)()(4526xgaxaxa由此可见：任一循环码多项式都是g(x)的倍式，即都可被g(x)整除，而且任一次数不大于(k-1)的多项式乘g(x)都是码多项式。195、如何寻找(n,k)循环码的生成多项式任一循环码多项式T(x)都是

10、g(x)的倍式。这样，循环码组也可写成：循环码的生成多项式也是一个码组，即有：T(x)为一(n-k)次多项式，则xkT(x)为一n次多项式。)()()(xgxhxT1)()(1)(nnkxxTxQxxTx)()(xgxT1)(xQ20码多项式必定是(xn+1)的一个因式。循环码的生成多项式g(x)应该是(xn+1)的一个（n-k）次因子。)() 1()(xTxxTn)()(1xhxxgxkn21例如：例如： (x7+1)可以分解为： x7+1=(x+1)(x3+x2+1)(x3+x+1)为了求出（7,3）循环码的生成多项式g(x)，就要从上式中找到一个n-k=4次的因式。从上式不难看出，这样的

11、因式有两个，即：1) 1)(1(2423xxxxxx1) 1)(1(2343xxxxxx22二、循环码的编码方法编码的任务是在已知信息位的条件下求得循环码的码组，而我们要求得到的是系统码，即码组前k位为信息位，后n-k位是监督位。设信息位的码多项式用(n,k)循环码的码多项式的最高幂次为n-1次，而信息位是在它的最前面k位，因此信息位在循环码的码多项式中应表现为 xn-km(x)多项式（最高幂次为n-1）。显然它从幂次xn-k-1起至x0的(n-k)位的系数都为0。012211)(mxmxmxmxmkkkk knknnknkknxmxmxmxmxmx 0112211)(23其中q(x)为幂次小

12、于k的商多项式，而r(x)为幂次小于n-k的余式。上式表明，多项式xn-km(x)为g(x)的倍式。xn-km(x)必定是由g(x)生成的循环码中的码字，而r(x)即为该码字的监督码元所对应的多项式。)()()()()(xgxrxqxgxmxkn)()()()(xgxqxrxmxkn241、循环码的编码规则(1)根据给定的(n,k)值选定生成多项式g(x)，即从(xn+1)的因子中选取一个(n-k)次多项式作为g(x)；(2)用xn-k乘m(x)。这一运算的物理意义是把信息位后附加上(n-k)个“0”。例如，信息位为110，它相当于m(x)=x2 + x，当n-k=7-3=4时， xn-km(

13、x)= x4(x2 + x )= x6 + x5，它相当于1100000。（3）用g(x)除xn-km(x)，得到商q(x)和余式r(x)，即：)()()()()(xgxrxqxgxmxkn25例如，如选用 作为生成多项式，则1)(24xxxxg1)()(2456xxxxxxgxmxkn101111011111011111000001112422xxxxxx26(4)编出的码组T(x)为本例中， 这就是表中的第7码组。可见，这样编出的循环码就是系统码了。)()()(xrxmxxTkn11001011011100000)(xA27由此可得到以多项式表示的系统循环码的生成矩阵为其中rn-i是g(x

14、)除xn-i所得的余式，由该式中多项式的系数就可得到码的系统形式的生成矩阵G和H矩阵。 )()()()(2211xrxxrxxrxxGknknnnnn282、多项式除法电路多项式除法电路由r级线性移位寄存器组成。包括r个模2加法器、最多r+1个模2常数乘法器和r级移位寄存器。给定两个多项式m(x)和g(x)。则多项式除法电路如图所示012211)(mxmxmxmxmkkkk 0111)(gxgxgxgxgrrrr 1g02g13g2rgr-1.商输出输入m(x)gr29多项式除法电路举例356)(xxxxm1)(3xxxg123商输出输入0 0 01011实际电路30除法过程节拍输入序列寄存器

15、内容输出000010110001000101100020001011003000101104000011150011116010117100111113323356xxxxxxxxxx3113 xx3560 xxx123xxx3460 xxx45xx 2350 xxx234xxxxxx240 xx03103xx1第4 次 移位后的反馈第4 次 移位后的寄存器内容第5 次 移位后的反馈第6 次 移位后的反馈第6 次 移位后的寄存器内容第7 次 移位后的反馈第7 次 移位后的寄存器内容第5 次 移位后的寄存器内容323、循环码编码的硬件实现方法一：使用上述的除法电路例如：(7,3)循环码+D0+D

16、1+数据输入1D2D3xx2x4S数据输出1)(24xxxxg33(7,3)循环码共需要移位 n=7 次。从信息码到达输入端至输出端产生余数，其间有 r=n-k=4 个单位时间迟延。先编码后发送（不能同时进行）。 输入 移位寄存器 移位次数 m D0 D1 D2 D3 i 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 2 0 0 1 1 0 3 0 0 0 1 1 4 0 1 1 1 1 5 0 1 0 0 1 6 0 1 0 1 0 734方法二、：改进型电路（ 发送信息与编码同时进行进行。）35对于(n,k)循环码，移位k次后便得到余数。提前了 r=n-k 个单位时间

17、。364、编码的软件实现（1）方法一（对应硬件电路一） n位信息码元后面补（n-k）个0g(x)对应的（n-k+1）位码元寄存器1寄存器237（高位）余数（低位）g(x)对应的码元寄存器1寄存器2mi信息码元异或（）方法二（对应硬件电路二） 38三、循环码的解码方法接收端解码的要求有两种：检错和纠错。(1)检错译码达到检错目的解码原理十分简单：利用码组多项式T(x)是g(x)的倍式的编码原理进行解码。编码器输出：接收码多项式： E(x)为差错多项式（对应于错码矩阵E）。)()()(xrxmxxTkn)()()(xExTxR39可见：当接收到的码组没有差错（即 E(x)=0 ）时， R(x)=T

18、(x) ，R(x)能被g(x)整除。)()()(xgxqxT)()()()()()()()()()(xgxExqxgxExgxgxqxgxR从循环码的编码原理可知，T(x)是g(x)的倍式，即：)()()()()(xgxExTxgxR40qE(x)是商，rE(x)是余式。因此：接收端可以根据余式rE(x)是否为零来判断接收码组是否有错。检错译码步骤：计算R(x)的余式r(x)（伴随式S(x)）；根据r(x)是否为零来判断接收码组R(x)是否有错。)()()()()(xgxrxqxgxREE当接收到的码组出现差错（即 E(x) 0），且差错的数目在码的检验范围之内时，将有：41循环码检错解码的硬

19、件实现主要部分是一个除法器和缓冲移位寄存器。42解码电路的除法器与发送编码器的电路相同。43(2) 纠错译码在接收端为纠错而采用的解码方法要比检错复杂得多。为了能够纠错，要求每个可纠正的错误图样必须与一个特定的余式（伴随式）有一一对应关系。纠错译码步骤：计算R(x)的余式r(x)（伴随式S(x)）；根据S(x)得到差错多项式E(x)（错误图样）；计算 R(x) - E(x) = T(x)。纠错译码设备的复杂程度主要取决于由伴随式找到错误图样的识别电路或组合逻辑电路的复杂性。44)()()(xExTxR），（模），（模），（模)()()()()()()()(xgxExgxExTxgxRxS45（

20、7,4）循环汉明码能纠正一个错误。设接收码为 a6a5a4a3a2a1a01)(3xxxg 错码位置 错误图样E 伴随式S a0 0000001 001 a1 0000010 010 a2 0000100 100 a3 0001000 011 a4 0010000 110 a5 0100000 111 a6 1000000 101 46定理： 若 则：译码时，只有知道一个代表图样的伴随式，其他错误图样的伴随式由此代表图样伴随式在伴随式计算电路中得到。代表伴随式：是指第一位开头为非0的错误图样对应的伴随式。），（模)()()(xgxRxS），（模)()()(xgxRxxSii），（模)()()(

21、xgxSxxSii），（模)()()()(xgxSxaxSa），（模)()()()(xgxRxaxSa47(7,4)循环汉明码译码电路译码过程共需要 2n=14 个节拍。纠错信号“1”也反馈到伴随式计算电路输入端，对伴随式进行修正，以消去该错误对伴随式的影响（此后伴随式为0）。484950有错码的接收码组也有可能被整除，这时的错码就不能检出了，这种错误称为不可检错误。不可检错误中的码组错码数必定超过了这种编码的检错能力。)()()()()()()()()()(xgxExqxgxExgxgxqxgxR51四、缩短循环码已知循环码的生成多项式应该是（xn+1）的一个（n-k）次因子，但有时（xn+1）多项式的因子个数比较少，因此在给定长度n下码的数目也较少。为了增加（n,k）码的数目，以便选择，循环码经常采用缩短形式。在（n,k）循环码的2k个码组集合中，