循环码.ppt

1,6.3.5 循 环 码,循环码是线性分组码的一个重要子集. 循环码有严密的代数学理论基础，检错和纠错能力较强，而且编码和解码设备都不太复杂. 循环码除了具有线性分组码的一般性质外，还具有循环性：循环码中任一许用码矢经过循环移位后，所得到的码矢仍然是许用码矢 一、循环码的多项式描述 ⒈ 循环码的定义 定义：如果 (n,k) 线性分组码的任意码矢C=(Cn－1 ,Cn－2,…,C0)的 i 次循环移位，所得矢量 C(i)=(Cn－1－i ,Cn－2－i,…,C0,Cn－1,…,Cn－i) 仍是一个码矢，则称此线性码为 (n,k) 循环码2,⒉ 循环码的多项式描述 为了运算的方便，将码矢的各分量作为多项式的系数，设任意n维矢量C=（cn-1,cn-2,….,c1,c0），可以用一个次数不超过n-1的多项式唯一确定把码矢表示成多项式，称为码多项式其一般表示式为 C(x)=(Cn－1xn－1+Cn－2xn－2+…+ C1x +C0) 对于二进制码，码多项式的每个系数不是0就是1 x仅是码元位置的标记我们并不关心x的取值 码多项式 i 次循环移位的表示方法 C(x) 乘以 x(i=1)，再除以 (xn+1)，得,,模运算,,,3,上式表明：码矢循环一次的码多项式 C (1)(x) 是原码 多项式 C(x)乘以 x 除以 (xn+1) 的余式。

记作： C(x) 的 i 次循环移位 C (i)(x) 是 C(x) 乘以 xi 除以 (xn+1) 的余式，即： 结论：循环码的码矢的 i 次循环移位等效于将码 多项式乘 xi 后再取模 (xn+1)4,二、循环码的生成多项式和生成矩阵 ⒈ 循环码的生成阵 在(n，k)循环码的2k个码多项式中，取前k-1位皆为 0的码多项式g(x) (其次数r＝n-k)，再经k-1次循环移位，共得到k个码多项式：g(x),xg(x),…,xk－1g(x)这k个码多项式显然是相互独立的，可作为码生成矩阵的k个行，于是得到(n，k)循环码的生成矩阵G(x)为：,5,码的生成矩阵一旦确定，码就确定了； 这就说明： (n,k) 循环码可由它的一个 (n－k) 次码 多项式 g(x) 来确定； 所以说 g(x) 生成了 (n,k) 循环码，因此称 g(x) 为码 的生成多项式 定理1：(n,k)循环码C(x)中存在唯一的一个非零的， 首一的和最低次为r(r=n-k)的码多项式满足： 并且c(x)是码式，当且仅当c(x)是g(x)的倍式 定理2：g(x)是(n,k)循环码的生成多项式，当且仅当 g(x)是xn+1的r=n-k次因式。

6,结论：当求作一个(n,k)循环码时，只要分解多项式(xn+1) ，从中取出(n－k)次因式作生成多项式即可 举例：求 (7,3) 循环码的生成多项式 [解]： 分解多项式 x7+1，取其4次因式作生成多项式 x7+1= (x+1) (x3+x2+1) (x3+x+1) 可将一次和任一个三次因式的乘积作为生成多项式，因而可取 g1(x)= (x+1) (x3+x2+1) = x4+x2+x+1 或 g2(x)= (x+1) (x3+x+1) = x4+x3+x2+1,,,,,G1 (x) G2 (x),7,若已知消息矢量，则由 求得所有的码字：,8,⒉ 循环码的监督阵 设 g(x) 为 (n,k) 循环码的生成多项式，必为 (xn+1) 的因式，则有 xn+1=h(x)g(x)，式中h(x) 为 k 次多项式，称为 (n,k) 循环码的监督多项式 由等式 x7+1= h(x)g(x) 两端同次项系数相等得 将上面的方程组写成矩阵形式有：,9,10,,由此可见，监督矩阵的第一行是码的监督多项式 h(x) 的 系数的反序排列，第二、三、四行是第一行的移位； (n,k) 循环码的监督矩阵,h0=hk=1,11,,,,,例：已知(7,3) 循环码的生成多项式为： g(x)=x4+x2+x+1，求该码的监督多项式及监督阵 解：由x7+1=g(x)h(x)得 h(x)=(x7+1) ÷g(x)=x3+x+1,,,,,,,移动方向与g(x) 移动方向相反,,升序排列,,12,,6.3.6 循环码的编码和译码,一、系统循环码 ⒈ 循环码的标准阵 定理：令C是一个(n,k)循环码，具有生成多项式g(x)。

对 i=0,1, …，k-1，，G2,i是长度为n的矢量，它的生成函数 是G2,i(x)=xr+i+xr+i mod g(x)则k×n阶矩阵： 是码C的一个生成矩阵类似地，如果H2,j，是长度为r 的矢量，它的监督函数是H2,j(x)=xj mod g(x)，则r ×n阶 矩阵：,G,H的标准阵形式,,,,13,,是码C的一个一致校验矩阵此外，如果矢量m=(mk-1, … , m1,m0)编码为C=mG2，则m(x)与C(x)的关系为： C(x)=xrm(x)+[xrm(x)] mod g(x) 并且，如果矢量R=(Rn-1, …,R1,R0)的伴随式计算公式为 ST=H2RT，则R(x)与S(x)的关系为： S(x)=R(x) mod g(x) ⒉ 循环码的系统码 由上述定理，即可得到循环码产生系统码的方法： C=mG2 C(x)=xrm(x)+[xrm(x)] mod g(x),将信息码移至最高位， 且最低的次数为r次,,,,求xrm(x)的余数，且最高次数 小于r,应为码字的监督元部分14,例：已知(7,3)循环码的g(x)=x4+x3+x2+1， 试求其标准生成阵，一致校验阵及全部码字。

解：⑴ 由定理 G2,i(x)=xr+i+xr+i mod g(x) 得： X6+X6 mod g X5+X5 mod g X4+X4 mod g,,,1 0 0 1 1 1 0,0 1 0 0 1 1 1,0 0 1 1 1 0 1,,,X6+X3+X2+X (r=4,i=2),X5+X2+X+1 (r=4,i=2),,X4+X3+X2+1 (r=4,i=0),,X6 X5 X4 X3 X2 X 1,15,⑵ h(x)=(x7+1) ÷ g(x)=x3+x2+1， 由定理 H2,j(x)=xj mod g(x)，得： X6 mod g = X3+X2+X (j=6) X5 mod g = X2+X+1 (j=5) X4 mod g = X3+X2+1 (j=4) X3 (j=3) X2 X 1,1 1 1 0,0 1 1 1,1 1 0 1,1 0 0 0,0 1 0 0,0 0 1 0,0 0 0 1,X3 X2 X 1,,转置,,,16,⑶ 求全部码字：由定理得： C(x)=xrm(x)+[xrm(x)] mod g(x) m(x)=X2+X+1 X4m(x)=X6+X5+X4 [X4m(x)] mod g=X2 ∴ C(x)= X6+X5+X4+ X2 C={1110100} m(x)=X2+1 X4m(x)=X6+X4 [X4m(x)] mod g=X+1 ∴ C(x)= X6+X4+ X+1 C={1010011},消息码,C1码,C2=mG2,111,1110100,1110100,,,三行矢模二加,101,1010011,1010011,000,011,100,110,001,010,0111010,0000000,,,1101001,1101001,0111010,1001110,1001110,0100111,0100111,0000000,0011101,0011101,17,二、多项式运算电路 多项式加法运算 多项式乘单项式 多项式乘多项式 多项式求模g(x)运算(除法电路，即求余数) 移位寄存器的级数=除式的次数 移位寄存器的反馈抽头，由除式的各项系数定 gi(x)=0, 反馈抽头断开 gi(x)=1, 反馈抽头连通 完成除法所需的移位次数=等于被除式的次数+1 三、循环码的编码电路 ⒈ 非系统码的编码电路 例：,18,⒉ 系统码编码电路 系统码的编码电路可以分为两大类： 基于码的生成多项式g(x)的编码电路 基于码的一致校验多项式h(x)的编码电路 ⑴ 循环系统码r级除法编码电路 除式：g(x) 级数：r级，（因g(x)的最高次为r次，故得名) 依据：C(x)=xrm(x) ＋[xrm(x)] mod g(x)，即由移位（得到信息 位）、求余（得到监督位）和加法电路三部分组成。

除式部分规则：同前除式电路，3点Pr-1,P2,P1,P0,＋,,gr-1,g1,g0=1,g2,m(x),C(x),19,例：已知(7,4)汉明循环码的生成多项式g(x)=x3+x2+1, 试画出其r级编码电路，并求出各时刻寄存器值及输出的码字 解：电路的工作过程： 3级移位寄存器的初始状态全部清零，门1打开，门2关闭 高次位系数首先进入电路，一方面经或门输出，另一方面自动乘以xr=3后进入除法电路，从而完成xn-k=3m(x)的移位作用 4次移位后m(x)全部进入电路，完成了除法的作用，此时在移位寄存器内保留了余式r(x)的系数，在二进制情况下就是校验元 此时门2打开，门1关闭，再经过3次移位把移位寄存器中的校验元全部移出20,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,G2,C(x),+,P1,P2,b,c,P0,a,G1,m(x),a=m+P2,b=a+P1,P0’=a,P1’=P0,P2’=b,原则：移位后再进行逻辑运算， m(x),C(x)均是高位在前，且m(x) 后面补足零当G1关闭时，与门输出为0，0⊕p1=p1, 所以，异或门相当于直通21,,,0,0,0,,,1,a,1,b,1,1,CP2,,,,0,1,1,0,a,1,b,1,0,CP3,1,1,1,1,0,1,1,1,0,1,0,0,1,0,0,,依次串出,CP5,1,0,CP4,移入,逻辑运算,22,⑵ 循环系统码k级除法编码电路 当n-kk，为了节省存储器，通常采用h(x)来构造一 个k级移位寄存器的编码电路。

编码电路： 例：已知二进制(7,4)循环码的h(x)=x4+x2+x1+1,试 画出它的编码电路及输入为1001时寄存器的工作过程 初始时，4级寄存器全清零，G1打开，G2关闭接着移 动k=4次，4个信息元一方面移入4级寄存器，另一方面 输出 4次移位后， G2打开，G1关闭，此时信息元全部进入 移位寄存器，停止送入信息元第5次移位后得到第一 个校验元C2，它一方面跟在c3信息元后，另一方面移入P3依次类推，直至输出全部码字23,,,,,,,,,,,,,,,,,C(x),m(x),P0,P1,P2,P3,a,b,c,d,,,,,,,,,,,G2,,,G1,c=P0 d=c+P1 a=d+P2 b=a+m,24,1,,d,1,a,0,1,,1,1,1,0,0,,,,,CP5,,0,d,0,a,1,,1,CP6,,,,,1,1,1,0,0,0,1,0,0,0,1,1,1,1,1,CP7,1,0,1,1001,逻辑运算,25,四、循环码的伴随多项式及检纠错 ⒈ 循环码的伴随多项式 由前定理可知： 接收矢量R=(Rn-1, …,R1,R0)的伴随式计算公式为： S(x)=R(x) mod g(x) ∵ R(x)=C(x)+e(x); 又∵C(x)=0 mod g(x) ∴ S(x)=e(x) mod g(x),26,结论： ⑴ 循环码接收多项式的伴随式是接收多项式R(x) 除以g(x)的余式。

⑵ 与线性分组码一样，伴随式由错误图样确定 ⑶ 上式还表明循环码的伴随式计算电路就是一个 g(x)的除法电路 ⑷ 若余式为0，S(x)=0,e(x)=0,收到的就是一个 码字,(当然也可能是一个不可纠的错误图。