《《信道编码中》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《信道编码中》PPT课件.ppt（85页珍藏版）》请在三一办公上搜索。
1、第三章 信道编码 3.4 循环码,本节的主要内容,码多项式 循环移位的数学表达 循环码的生成多项式 循环码的编码 循环码的译码 编、译码的电路实现,循环码：cyclic code 码多项式：code polynomial 生成多项式：generator polynomial 求模运算：modular arithmetic 系统码：systematic（regular）code 循环移位运算：cycle shift operation,外语关键词,上节回顾：线性分组码,基本概念：表达方式：(n,k)码，k是信息位数，r是监督位数，n=k+r是码长。编码：已知信息K（k位二进序列），求相应码字的方
2、法是 C=KG，G叫生成矩阵，是k行n列的，一般G具有Ik Q的形式，Ik 是k行k列单位方阵，Q是k行r列的矩阵。生成矩阵的设计，应使许用码字之间的最小汉明距离尽量地大。,译玛：当收到码字R时，首先计算伴随子向量：S=RHT；若S=0，则R=C为正确码字；若S 0，则RC为错误码字。这里H叫一致监督矩阵，是r行n列的。一般H具有 P Ir 的形式，Ir 是r行r列单位方阵，P是r行k列的矩阵，P与Q互为转置关系。纠正1位错：当S 0时，由S=RHT 求出S，比较S 与HT，HT的那一行与S相同，相应的错误格式向量E的那一位就等于1，于是R的那一位就是错误的。最后根据 C=RE进行将其纠正。,
3、纠正多位错错：当S 0时，根据S=RHT=EHT，可以预先由S=EHT计算出各种错误格式E所对应的伴随子向量S，得到ES对照表。查表就能找到接收码字R（即S=RHT）所对应的E。纠错能力不等式：2r Cno+Cn1+Cn2+Cnt 这是因为伴随子S是1行r列的向量，它有2r 种不同的状态，除了用全零态表示正确码之外，最多只能区别开2r1种不同的错误格式。,引言：构造线性分组码关键是设计出一个好的生成矩阵，使所有码字之间的汉明距离尽量大。怎样找这样的矩阵呢？循环码的出现提供了一整套理论和方法，使人们能够借助数学工具来寻找更好的线性分组码，并由此引发出一大类很常用检、纠错编译码。,3.4 循环码,
4、上节讨论过(7,3)线性分组码:C0=(0000000);C1=(0011101);C2=(0100111);C3=(0111010);C4=(1001110);C5=(1010011);C6=(1101001);C7=(1110100);,不难发现它们具 有循环移位特性：C0=(0000000);C1=(0011101);C3=(0111010);C7=(1110100);C6=(1101001);C5=(1010011);C2=(0100111);C4=(1001110);,循环码是线性分组码中的一个子集。对于循环码，有了一个的码字，按循环移位规律就能写出n个码字。从中选出k个来构造生成矩
5、阵G，就能生成全部2k个许用码字。循环码与近代数学有密切联系。使我们可以借助数学工具来设计编码。,3.4.1 码多项式,二进制自然码可表达为以2为底的多项式表达，如：C=(1010111)=126+025+124+023+122+121+120；把底换为x，则得到“码多项式”：C(x)=1x6+0 x5+1x4+0 x3+1x2+1x1+1x0=x6+x4+x2+x+1 码长为n时，可写：C(x)=cn-1 xn-1+cn-2 xn-2+c1x1+c0 x0 如三位二元码的8个码字对应的码多项式为：000，001，010，011，100，101，110，111；0，1，x,x+1,x2,x2+
6、1,x2+x,x2+x+1,3.4.2 循环移位的数学表达,对二进数，左移一位相当于乘以2，而将最高位的进位(2n位)上的数码拿回到20位，叫做循环移位，相当于作模2n-1运算。如：1011010011 实际是 52 mod 7=3码多项式的循环移位，实际是乘x后作模 xn-1运算。如：1100010 11000100 1000101(x6+x5+x)x(x6+x5+x)mod(x7-1)=(x7+x6+x2)mod(x7-1)=x6+x2+1,（7,4）循环码及其码多项式的循环移位：,循环次数 循环码 码多项式 模x7-1运算后 0 0001011 x3+x+1 x3+x+1 1 00101
7、10 x(x3+x+1)x4+x2+x 2 0101100 x2(x3+x+1)x5+x3+x2 3 1011000 x3(x3+x+1)x6+x4+x3 4 0110001 x4(x3+x+1)x5+x4+1 5 1100010 x5(x3+x+1)x6+x5+x 6 1000101 x6(x3+x+1)x6+x2+1,3.4.3 循环码的生成多项式(1)生成多项式的定义和特点,循环码的码多项式中幂次最低的非零多项式叫做生成多项式，记做g(x)。如(7,4)码的x3+x+1。有了它，其它码字都可由xi g(x)的模 xn-1得到。生成多项式的常数项为1。否则，通过循环移位还能继续降低幂次，它
8、就不是幂次最低的多项式了。生成多项式的幂次为r。因为幂次最低的码多项式是信息为0001,后面跟上r个监督位的那个码字所对应的码多项式，它的最高位是 xr，是r次的多项式。,(2)生成多项式的两个性质：,1任意码多项式T(x)都是生成多项式 g(x)的倍式。证明：（n,k）循环码作为线性分组码，其生成矩阵G是k行n列的，可由k个不同的码字构成：,任给一个信息码K=(cn-1cn-2cn-k)，利用生成矩阵和公式C=KG，不难求出它对应的码字 T(x)=KG=(cn-1cn-2cn-k),=（cn-1xk-1+cn-2xk-2+cn-k）g(x)；即：T(x)=h(x)g(x)；表明任意码多项式T
9、(x)都应能被g(x)整除。,2生成多项式g(x)是 xn-1的一个因式。证明：因为g(x)循环左移k位,即g(x)乘以xk后再作模xn-1运算,应当仍为一个码多项式。xk g(x)为n次多项式，除以xn-1的商式必为1，设余式为T(x),于是有：,移项即证得：xn-1=g(x)xk h(x)；,即：xk g(x)=xn-1+T(x)=xn-1+h(x)g(x),（3）生成多项式g(x)的确定：由性质2知，g(x)是xn-1的一个因式。可根据设定的码长n和监督位r，将xn-1因式分解，从中选择一个r次的因子作为g(x)。,例如：(7,4)码，n=7，k=4，r=3；分解：x7-1=(x-1)(
10、x3+x+1)(x3+x2+1)g(x)应是x7-1 的一个r=3次的因子，可取为：g(x)=x3+x+1 或 g(x)=x3+x2+1；二者任选其一，一旦选定，就不再考虑另一个了。,插件1：查表分解xn-1的方法,（1）并非所有的xn-1都具有r次的既约(不能再分解)的因式。但只要满足n=2r-1，xn-1就具有r次的既约因式。因此 P194 页表4中只列出满足n=2m-1的xn-1的分解情况。（2）不论n取何值，xn-1总有一个m0(x)=x+1的因式。（3）xn-1其它因式是mi(x),i=1,3,5,7（4）mi(x)的表达由8进制数给出，将它换成二进制自然码就是mi(x)各位的系数。
11、如 m=5阶时，n=31，可分解x31-1为：第i=1类因式查表得到(45)8=(100101)2，表示m1(x)=x5+x2+1；第i=3类因式查表得到(75)8=(111101)2，m3(x)=x5+x4+x3+x2+1；第i=5类因式查表得到(67)8=(110111)2，m5(x)=x5+x4+x2+x+1；,（5）表中并未列出xn-1所有的因式，与已列出因式对偶的因式都被省略了。所谓对偶指的是将二进制自然码高低位倒置的表达，如：与(100101)2对称的是(101001)2，表示m15(x)=x5+x3+1；与(111101)2对称的是(101111)2，表示m7(x)=x5+x3+
12、x2+x+1；与(110111)2对称的是(111011)2，表示m11(x)=x5+x4+x3+x+1；值得注意的是，有的二进制自然码本身就是对称的，如：(11111)2与(10001)2，高低位倒置后不变,不会出现新的因式。（6）xn-1分解为以上因式之积，诸因式中幂次最高为r。（7）类序号i与n互素的那些因式mi(x)被称为本原多项式；类序号i与n可约的那些因式mi(x)被称为非本原多项式。如果n为素数，所有的因式都是本原多项式。,例查表分解x63-1 因为26-1=63，所以应查P194 页表4中m=6阶。i=1：(103)8=(1000011)2，得知m1(x)=x6+x+1；由对偶
13、式(1100001)2和187页表得知m31(x)=x6+x5+1；i=3：(127)8=(1010111)2，得知m3(x)=x6+x4+x2+x+1；由对偶式(1110101)2和187页表知m15(x)=x6+x5+x4+x2+1；i=5：(147)8=(1100111)2，得知m5(x)=x6+x5+x2+x+1；由对偶式(1110011)2和187页表知m23(x)=x6+x5+x4+x+1；i=7：(111)8=(1001001)2，得知m7(x)=x6+x3+1；对偶式还是自己。,i=9：(015)8=(1101)2，得知m9(x)=x3+x2+1；由对偶式(1011)2和187
14、页表知m27(x)=x3+x+1；i=11：(155)8=(1101101)2，得知m11(x)=x6+x5+x3+x2+1；由对偶式(1011011)2和187页表知m13(x)=x6+x4+x3+x+1；i=21：(007)8=(111)2，得知m21(x)=x2+x+1；其对偶式仍是自己；最终结果：1）x63-1=m0(x)m1(x)m3(x)m5(x)m7(x)m9(x)m11(x)m13(x)m15(x)m21(x)m23(x)m27(x)m31(x)；2)本原多项式是m1(x),m5(x),m11(x),m13(x),m23(x)和m31(x)；,(1)循环码的生成矩阵,求出了生成
15、多项式g(x)，等于得到了一个码字，通过循环移位不难得到其它码字。果然如此简单吗？实际上，通过循环移位最多可写出n个码字，得不到全部码字，因为(n,k)码应当共有2k个许用码字。例如(7,4)循环码共有16个许用码字。取g(x)=x3+x+1，等于知道了中信息K=(0001)所对应的那个码字：C1=(0001 011)。,3.4.4 循环码的编码,C1经过循环移位只能得到7个码字：序号 信息位 许用码字 C1 0001(0001 011)C2 0010（0010 110）C5 0101（0101 100）C11 1011（1011 000）C6 0110（0110 001）C12 1100（1
16、100 010）C8 1000（1000 101）,（7,4）共有16个许用码字，还缺 9个。,从循环组中随便取4个许用码字，比如前4个，用它们构成的生成矩阵为G1：,再利用C=KG1 就能求得全部许用码字。比如：(0100)G1=(0101100);(1000)G1=(1011000);然而发现码字不具备信息位在前，监督位在后的形式。原因是G1不具备G=Ik Q的形式，这样编码叫非系统码，非系统码在译码时是比较困难的。,实际上，为了构造G=Ik Q 形式的生成矩阵。需要如下的 4个码字：1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 才能排列出44的单位矩阵Ik。通过对C1=
17、(0001 011)的循环移位可以得到（0010 110）和（1000 101)，但是却无法得到(0100),0 1 1,1 1 0,1 0 1,原因何在？原来0100所对应的码字（0100 111)位于另一循环组中:第一循环组 第二循环组 序号 信息 许用码字 序号 信息 许用码字 C1 0001（0001 011)C4 0100（0100 111)C2 0010（0010 110）C9 1001（1001 110）C5 0101（0101 100）C3 0011（0011 101）C11 1011（1011 000）C7 0111（0111 010）C6 0110（0110 001）C14
18、 1110（1110 100）C12 1100（1100 010）C13 1101（1101 001）C8 1000（1000 101）C10 1010（1010 011）第三循环组 第四循环组 C0 0000（0000 000）C15 1111（1111 111）,直接写不出系统码生成矩阵，但可以经过线性变换，将G1最下行加到第二行上，将最下面两行加到第一行上，也能得到Ik Q的形式的系统码生成矩阵G:,非系统码生成矩阵,系统码生成矩阵,得到了系统码生成矩阵，就可以用C=KG得到所有码字。,（2）直接计算系统码的监督元:以(7,4)码为例，设信息位为k3 k2 k1 k0，对应的多项式为：k
19、(x)=k3x3+k2x2+k1x+k0；设监督位为r2 r1 r0，监督位对应的多项式为:r(x)=r2x2+r1x+r0；系统码码字C=(k3 k2 k1 k0 r2 r1 r0)对应的码多项式为:C(x)=k3x6+k2x5+k1 x4+k0 x3+r2 x2+r1 x+r0；=x3(k3x3+k2x2+k1x+k0)+(r2x2+r1x+r0)=x3 k(x)+r(x)推广到一般，码多项式可写为为：C(x)=x r k(x)+r(x)-(1),根据生成多项式性质1，任何码多项式一定能被g(x)整除：C(x)mod g(x)=0 即：x r k(x)mod g(x)+r(x)mod g(
20、x)=0；移项，并考虑到模2运算可把负号变正号，于是：r(x)mod g(x)=x r k(x)mod g(x)；因为 r(x)是r-1次多项式，g(x)是r 次多项式，所以 r(x)mod g(x)=r(x)得到直接计算系统码码字监督多项式的公式是：r(x)=x r k(x)mod g(x)-(2)再由公式(1)就得到了相应的码字。,例1求(7,4)循环码中信息位K=(0100)对应的码字：解：k(x)=x2,r=3,xr k(x)=x5,g(x)=x3+x+1；由(2):r(x)=x5 mod x3+x+1=x2+x+1；由(1):C(x)=xr k(x)+r(x)=x5+x2+x+1；C
21、=(0100111)；同法可得到所有16个信息(00001111)的码字。,小结：循环码的编码步骤：1、确定(n,k)循环码的生成多项式：将xn-1分解因 式，从中选择一个r次的因子作为g(x)。2、根据信息K，由 r(x)=x r k(x)mod g(x)计算出它的监督位。3、由 信息位+监督位 直接写出编码C；4、间接编码方法：由g(x)得到一个码字，循环移位得到k个码字，写出生成矩阵，通过线性变换得到系统码生成矩阵G，最后由生成方程C=KG 求出相应码字。,例2 求(7,3)循环码的生成多项式，并为信息 K=(110)编码。解：(1)n=7,k=3,r=4 由：x7-1=(x+1)(x3
22、+x+1)(x3+x2+1)取：g(x)=(x+1)(x3+x+1)=x4+x3+x2+1；(2)由:k(x)=x2+x,xr k(x)=x4(x2+x)=x6+x5 知:r(x)=x6+x5 mod x4+x3+x2+1=x3+1；(3)R=(1001)；C=(1101001)；或由：g(x)=x4+x3+x2+1(0011101)循环左移三次得到：C=(1101001)；,3.4.5 循环码的译码（纠错）,(1)由接收码字R，写出其接收码多项式R(x)；(2)求伴随子多项式S(x)=R(x)mod g(x)；(3)若 S(x)=0（即接收码多项式能被g(x)整除）,则表明接收码无误。(4)
23、若 S(x)0，表明接收码有误，此时定义 错误格式多项式：E(x)=en-1xn-1+en-2xn-2+e2x2+e1x+e0；,(5)由S(x)求对应的E(x)。因S(x)=C(x)+E(x)mod g(x)=E(x)mod g(x)；为了找到S(x)对应的E(x)，我们可以预先将纠错能力t 位 以内的各种错误格式E(x)除以g(x)的余式都计算出来，列成一张S(x)-E(x)对照表，由S(x)就能直接查出E(x)。(6)纠错译码：由C(x)=R(x)+E(x)就能写出译码C。,例3 已知(7,4)码的生成多项式是g(x)=x3+x+1；请为R=(0110010)译码。解：设接收码为R=(r
24、6 r5 r4 r3 r2 r1 r0)；由 S(x)=E(x)mod g(x)；可列出S(x)E(x)对照表：,当R=(0110010)时，R(x)=x5+x4+x；S(x)=（x5+x4+x）mod（x3+x+1）=x+1；查表知：E(x)=x3；纠错：C(x)=R(x)+E(x)=x5+x4+x3+x；即：C=(0111010)；译码结果是K=0111,计算机中对公式的计算其实仍归结为数值计算，对所有的赋值都能正确得到结果，就等于对公式的计算。笔算时是从被除数的高位开始，依次对除数求商、求积、求余，然后右移一位，继续前述过程，直至到被除数末尾。现在的道理相同，只不过把除数固定在电路上（就
25、是反馈的位置），让被除数逐位右移通动寄存器，通过反馈电路实现求商、求积、求余的运算。由于是二进制代码，商只有1和0两个可能值，积就是除数本身或是零。商为0时反馈为0，被除数不变；商为1时反馈为1，被除数与除数相减，但模二减等于模二加。最后留在寄存器中的就是余数,上轮余数的首位被输出，它的就是商。,3.4.6 编、译码的电路实现1.除法求余电路：,设被除数是x r k(x)=x5=0100000，除数是g(x)=x3+x+1=1011，相除的过程见表所示。,xr K(x)输入 D0D1D2 输出 x6位 0 0 0 0 0 x5位 1 1 0 0 0 x4位 0 0 1 0 0 x3位 0 0
26、0 1 0 x2位 0 1 1 0 1 x1位 0 0 1 1 0 x0位 0 1 1 1 1,电路原理:,现在的除数g(x)是3次多项式，余数至多2次，故可取3位寄存器来存放余数。余数初值为零，覆盖值是被除数减去商与除数之积。因此将被除数诸位推入寄存器中，寄存器兼有减法计算功能，每次移位后都只计算3位长的一段。寄存器最高位(x2位)为0时，移位后除以g(x)的商必然为0；寄存器最高位为1时商必然为1；因此该位的输出的就是商。该商被反馈回去，反馈位置是g(x)的非0位，就相当于用商去乘除数，其乘积不是0就是g(x)。模2加等价于模2减，就实现了与寄存器中原先余数的相减运算。如果商为1，1g(x
27、)的最高位在与原先余数相减的运算中总是相抵消的，所以只须考虑其余3位的反馈即可。,2.编码电路：,把输入的K(x)从D0端移到D2后面，就得到了如图所示的实用编码电路。,首先开关P置向上，开关Q闭合，得到上面四行的数据；输出的就是信息K。然后P置向下，Q开启，继续将寄存器中的余数输出；就是接在后面的监督。,电路工作原理：(1)在D2端加入K(x)，就等于在D0端加x r k(x)，这样 就省去了前置的乘以x3的乘法(移位)器。(2)将Q闭合，P置向上，就可以在进行除法运算的 同时，将信息K送到输出，形成编码的前半段。(3)无须移位7次，只要移位4次，就可以完成求模 运算的工作，接着把P置下，Q
28、开启，就可以把 D0D1D2中的余数，顺序接在编码的后半段上，形成完整的编码。,3、译码电路：,首先断开K2，接通K1，利用除法求余电路，把接收码字R(x)除以g(x)的余式，即伴随子S(x)计算出来，存于D0D1D2中；与此同时，R(x)也被缓存在R0R6中。,R0R1R2R3R4R5R6 K1 D0 D1 D2 K2,然后，断开K1，接通K2。与门设计是对输入（101）有响应。若e6位错，则求余结果S=101，恰使与门有输出，正好纠正R6位。此后，移位继续进行，D0D1D2值发生变化，与门关闭，不再影响R5R0的输出。若e5位错，则求余得出的S=(111)，与门无输出，但经过一个节拍后D0
29、D1D2变成(101)，与门变得有输出，正好轮到缓存器中R5位的输出，将它纠正；再继续移位，与门又关闭了。其它位有错时，同样引起类似于上述变化的纠错过程。巧就巧在正好轮到R有错的那一位输出时，寄存器恰变为101，与门便输出纠错信号“1”，将该位错码纠正。,如此巧妙的玄机在哪里呢?因为伴随子S(x)=R(x)mod g(x)=E(x)mod g(x)，所以分析电路对R(x)的作用与分析E(x)是等价的。当R(x)为正确码时，E(x)是全0，除法器求余结果为0，与门不会打开，R(x)从缓冲器中原样输出。当R(x)有一位不正确时，E(x)的相应位是1，其它全0；除法器求余逻辑是按照x3+x+1设计的
30、,初值为000,当有1输入时才变为100,此后由于输入全为0,寄存器则按照100010 001110011111101的规律变化,共7步变到101。E(x)为1的码位进入运算器的同时也进入缓冲器，经过7步才能缓冲才能输出，这时正好与门打开，将其纠正。,译码电路逐次移位的数据变化,本节要点,1.循环码的基本概念：(1)码字的循环移位(2)码多项式及其两个重要性质(3)循环码的生成多项式2.循环码的编码：根据信息K，直接由 r(x)=x r k(x)mod g(x)求出监督位，添在信息位后，即得到编码。,3.循环码的译码：（1）由接收码字R，写出其接收码多项式R(x)；（2）求伴随子多项式S(x)
31、=R(x)mod g(x)；（3）若 S(x)=0（即接收码多项式能被g(x)整除）,则表明接收码无误。（4）若 S(x)0，表明接收码有误，此时应将纠错能力t 位以内的各种错误格式E(x)除以g(x)的余式都计算出来，列成一张S(x)-E(x)对照表。（5）由S(x)直接查表得到E(x)。（6）由C(x)=R(x)+E(x)进行纠错。,思考：是否任意码长n和任意信息位k都能构成(n,k)循环码？（提示：考虑生成多项式）。作业：P114页：14、17题,第三章 信道编码 3.5 循环码的扩展,本节的主要内容,增余汉明码截短循环码循环冗余校验码二元本原BCH码二元非本原BCH码,增余汉明码：ex
32、tended Hamming code 截短循环码：shortened cyclic code 循环冗余校验码：Cyclic Redundancy Check Code(CRC)本原BCH码：primitive BCH code 非本原BCH码:non-primitive BCH code,外语关键词,上节回顾：循环码,基本概念：循环码的特点，码多项式，循环移位的数学表达。生成多项式：（1）码多项式中幂次最低（幂次为r）常数项为1的非 零多项式。（2）通过对g(x)的循环移位可获得其它一些码多项式。（3）任意码多项式T(x)都应能被g(x)整除。（4）g(x)是xn-1的一个因式。,循环码的编
33、码：（1）分解xn-1，以获得生成多项式g(x)；（2）求监督多项式：r(x)=x r k(x)mod g(x)；（3）写出相应码字：C(x)=x r k(x)+r(x)；循环码的译码：（1）根据S(x)=E(x)mod g(x)；算出纠错能力t 位 以内的各种错误格式E(x)的S(x)对照表；（2）求接收码的伴随子向量S*(x)=R(x)mod g(x)；（3）从对照表中查出S*(x)对应的E*(x)（4）C(x)=R(x)+E*(x),3.5.1 增余汉明码,汉明码是能纠正一位错的完备码，具有较高的编码效率。如果给它的每一个许用码字增加一位奇偶校验位，使其成为(n+1,k)码，其编码效率降
34、低不多，但监督能力却得到提高，不仅能纠正1位错，还能发现第2位错。如(7,4)码改为(8,4)码，第8列的码元满足偶校验关系：c7=c6+c5+c4+c3+c2+c1+c0；一致监督矩阵由H(7,3)变为H(8,4)：,校验矩阵增加全1的一行，当计算S=RHT时，该列的计算是s4=c7+c6+c5+c4+c3+c2+c1+c0,对于偶校验，如果是正确码字结果必然为0。当只有一位错时，s4必然为1，而伴随子S的其它各列 与HT 的某一行相同。如果出现两位错时，由S=RHT=EHT，而E中有两列为1，致使s4=e7+e6+e5+e4+e3+e2+e1+e0 必然为0，就表明有两个错。当然，它无法纠
35、正，只能要求系统重发。,3.5.2 截短循环码,求生成多项式，需要分解xn-1，但只有n=2m-1的数才能查表分解，这就限制了n的取值。其次，并不是任何xn-1中都能找到r次的因子。比如x 5-1 中就不含r=2和r=3的因子，难以构造(5,2)码。可以从效率较高的（7,4）汉明码出发，在(7,4)码的生成矩阵中去掉前两行和前两列，剩下的部分构成一个52的矩阵，可以用它来生成(5,2)码。,相对于原来的循环码，信息位与码长被同步地减小了。这样的编码称之为截短循环码。截短循环码的普遍表达是(n-i,k-i)，i是截短位数，监督位长度r=(n-i)-(k-i)=n-k不变。截短循环码的引入，扩大了
36、循环码的覆盖范围，使人们能根据所需要的n、k值灵活地设计各种(n-i,k-i)码。截短循环码具有循环码的许多结构特点，监督位没有变，纠错能力不变，纠错方法不变等。但由于“截短”，只取用了循环组中的部分许用码，会使码组失去循环移位性。,3.5.3 循环冗余校验码(CRC)Cyclic Redundancy Cheek,循环冗余校验码是截短循环码的一个典型应用。在数据通信和软盘、光盘存储器中，常常需要对较多信息（一个数据帧或一个记录轨道中的数据）进行差错监督。数据的长短往往不确定，但校验位的长度r却是固定的。根据n=2r-1设计出一个(n,k)循环码后，当信息长度小于k时，只要同时截短信息位和码字
37、的长度，而保持监督位不变，便得到一个(n-i,k-i)截短循环码，这就是循环冗余校验码（CRC)。,常取 r=16，这时 g(x)=x16+x12+x5+1=10001000000100001(B)=11021(H)g(x)作为最轻的码字，它的重量为4，表明该码组中最小汉明距离d 0=4，能纠正1位差错同时还能检查到第2位差错。例如信息为K(x)=4D6F746F(H)，则可以在信息后面添上CRC监督码：r(x)=x16K(x)mod g(x)=4D6F746F0000(H)mod 11021(H)=B944(H)有时也取32位的CRC校验码，生成多项式为：g(x)=(x16+x15+x2+1
38、)(x16+x2+x+1),循环冗余校验码不仅实现起来比较简单，而且具有很强的检测能力。它能检测出：（1）绝大部分连续长度不大于n-k+1的突发错误。（2）相当一部分连续长度大于n-k+1的突发错误。（3）所有与许用码字汉明距离不大于d0-1的错误。（4）所有奇数个错位。当错位较少时，它能自动纠正，当差错超过纠错能力时，根据校验位很容易进行检错，采用重发反馈(ARQ)方式保证数据的正确性。,1.复数域中的分解：分解 xn-1，相当于求方程 xn-1=0的根；如 x2-1=0的根是x=1和x=-1，则 x2-1=(x-1)(x+1)同理若 xn-1=0的n个根是 x=x1,x2,xn，则：xn-
39、1=(x-x1)(x-x2)(x xn)；显然，由 xn=1知，这n个根应当是1的n次方根。写 1=1e j 0，根据复数开方公式：,插件2：xn-1的因式分解原理,这n个根模长均为1，辐角等分单位园的圆周。,令：=e j 2/n；则：xk=k(k=0,1,，n-1)于是：,结论：复数域中xn-1分解为n个1次因式的乘积。,2.共厄类：当n=2m-1时，xn-1的n个根k(k=0,1,2,n-1)按平方关系：k=i,2i,4i,8i,16i；可以分成若干类。不妨以n=15,x15-1=0的15个根为例。i=1的类包含：1，2，4，8 这4个根；16=1，32=2，又会重复出现这4个根。i=3的
40、类包含：3，6，12，24=9这4个根；48=3，96=6，又会重复出现这4个根。,同理得到其它共厄类：,结论：x15-1=0 有 5个共厄类，各个类互不重复，且恰巧取尽了全部15个根。,3.xn-1在GF(2)域中的分解：因式分解与定义域是密切关联的。比如在复数域中 x2+1=(x+j)(x-j)，但在实数域中，x2+1已经不能再分解了。GF(2)域只有0和1两个数字，其它数是不存在的。我们来看x15-1=0的第i=5类中5与10 这2个1次因式：5=e j(52)/15=e j 2/3；10=e j(102)/15=e j 4/3=e-j 2/3；(x-5)(x-10)=(x-e j 2/
41、3)(x-e-j 2/3)=x2(e j 2/3+e-j 2/3)x+1=x2 2cos(2/3)x+1=x2+x+1,在 GF(2)域 x2+x+1已经最简，不能再分解了。我们把它叫做i=5类对应的最小多项式，记作：m5(x)=x2+x+1；同理，属于每个共厄类的各1次因式相乘，都可得到GF(2)域中一个相应的最小多项式，其幂次等于共厄类中根的个数：m1(x)=(x-)(x 2)(x 4)(x 8)=x4+x+1；m3(x)=(x 3)(x 6)(x 9)(x 12)=x4+x3+x2+x+1；m5(x)=(x-5)(x-10)=x2+x+1；m7(x)=(x 7)(x 11)(x 13)(
42、x 14)=x4+x3+1；m0(x)=(x 0)=x+1于是：x15-1=m0(x)m1(x)m3(x)m5(x)m7(x)=(x+1)(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)(x4+x3+1),4.本原与非本原：(1)本原根与非本原根：xn=1的n个根0=1,2,n-1 可分为本原根与非本原根两种，二者的区别是看能否由k 的一切幂次生成xn=1的全部根。下面以x15=1的部分根为例来说明：,幂次1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2 4 6 8 10 12 14 3 5
43、 7 9 11 13 1 3 6 9 12 1 3 6 9 12 1 3 6 9 12 1 5 10 1 5 10 1 5 10 1 5 10 1 5 10 17 14 6 13 5 12 4 11 3 10 2 9 8 1,可以看出,2,7 本原根，3,5 是非本原根。,(2)本原根与非本原根的循环性：因为k是xn=1的根，所以(k)n=1，不论本原与非非本原，任何一个根自乘n次必然等于1。然而，例中第i=3类中的根k(k=3,6,9,12)，因为i值是n值的因子，每个根k无须自乘n=15次，只要自乘m=n/i=5次，就能回到0=1；同理，第i=5类中的根k，只要自乘m=n/i=3次，就能回
44、到0=1。我们把通过自乘能回到0=1 的最小自乘次数m叫做该类元素的循环级。例中第i=1类和i=7类，k值与n值互素，因而每个根k因式都必须自乘n=15次才能回到0=1，表明这些根的循环级 m=15 结论：本原根的幂次与n互素，所以循环级等于n；非本原根的幂次与n可约，所以循环级是n的因子。,x15-1的根、共厄类及其最小多项式,注意：各既约因式幂次 r 等于该类中根的个数，它与该共厄类的循环级m的关系是：2r mod m=1,(3)本原类与非本原类：共厄类是以根的平方（即自乘）关系划分的，自乘不会改变幂次与n互素或可约的本性，所以同一共厄类中的根，本原属性相同。因此，本原根构成的类是本原类，
45、非本原根构成的类是非本原类。本原类的类序号i与n互素，非本原类的类序号i与n可约。(4)本原多项式与非本原多项式：同一类根的一次因式相乘得到该类的最小多项式。因此，本原类的最小多项式是本原多项式，非本原类的最小多项式是非本原多项式。这样就把xn-1分解得到的因式也分成了本原与非本原两种。,(5)非本原多项式的一个性质：,以x15=1为例，设：=2/15，=e j；则 i=3类的4个非本原根为：3 的辐角=6/15=2/5，6 的辐角=12/15=4/5，9 的辐角=18/15=6/5，12 的辐角=24/15=8/5连同0=1,它们五等份单位圆,构成x5=1的5个根。因此：,(x-3)(x-6
46、)(x-9)(x-12)=x4+x3+x2+x+1不仅是x15-1的因式，也是x5-1的因式。结论：非本原多项式是不仅是xn-1的因式，也xm-1的因式。(这里m是循环级，n是m的倍数）,小结：xn-1有n个复数根k，它们按平方关系分为若干个共厄类。同一个共厄类的诸根的1次因式相乘，得到GF(2)域的一个既约因式。每类都有自己的既约因式，各既约因式幂次 r 等于该类中根的个数，x n-1就可分解为这些既约因式之积。同一个共厄类的根有相同的循环级。循环级m等于n的根是本原根，循环级m等于n的某个因数(n/i)的根是非本原根。本原根所在共厄类的既约因式叫做本原多项式，非本原根所在共厄类的既约因式叫
47、做非本原多项式。反之也可以说，本原多项式的根是本原根，非本原多项式的根是非本原根。本原多项式与非本原多项式都是xn-1的因式，但是非本原多项式还是xm-1的因式，这里m是n的因子(m=ni),3.5.4 二元本原BCH码,因式分解的数学理论解决了循环码的存在问题，并为它奠定了坚实的基础。1.如何构造能纠正一位错的循环码多项式？根据因式幂次与循环级的关系，当n=2r 1时，x n-1 必存在最高幂次为r 的本原多项式。可构成纠一位错的汉明码。例如，r=3,4,5,6 时：n=23-1=7：x7-1有3次本原因式 x3+x+1，得到(7,4)码 n=24-1=15：x15-1有4次本原因式 x4+
48、x+1，得到(15,11)码 n=25-1=31：x31-1有5次本原因式 x5+x2+1，得到(31,26)码 n=26-1=63：x63-1有6次本原因式 x6+x+1，得到(63,57)码,2.能不能构造能纠正多位错的循环码多项式？理论上线性分组码纠错位数t与冗余位r的关系是 tr/2，为了纠错位数更多一些，监督位数r 就得更大一些,也就是说生成多项式的幂次r 需要更大一些。xn-1既然可分解为多个因式，我们不妨取几个因子的乘积作为生成多项式，就能增加它的幂次。而几个因子的乘积仍然还是xn-1的因式。比如 x7-1=（x+1)(x3+x+1)(x3+x2+1)；取生成多项式：g(x)=(
49、x3+x+1)(x3+x2+1)=x6+x5+x4+x3+x2+x+1 现在监督位增加到 r=6，就能构成（7,1）码(即七连重复码)，它可以纠正3位错(因为26=1+7+21+35)。,又如x15-1=(x+1)(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)(x4+x3+1)取生成多项式：g(x)=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)=x10+x8+x5+x4+x2+x+1 现在监督位增加到 r=10，就能构成（15,5）码，它可以纠正3位错。(因为2101+15+105+455)定义：取码长为n=2m 1，取包括本原多项式在内的若干个因式之积为生成多项
50、式的循环码叫做本原BCH码。BCH是能纠正多位错的循环码。,3.能不能根据纠错位数t来设计生成多项式？进一步的研究得知，给定t 就能决定在xn-1中选取哪些因式。设 t 是所设计的纠错位数，mi(x)是xn-1的因式，这里 i=1,3,5,7，则生成多项式：,式中：LCM 表示求最小公倍式。这种码长为n=2m-1，生成多项式由上述公式定义的循环码，叫做本原BCH码。这是更具实际意义的定义。P195页表5给出了n255的所有本原BCH码的码长、信息位、纠错位数，并以8进制方式给出了生成多项式。,例1 构造码长为15，分别能纠正1位、2位、3位和4位错的本原BCH码生成多项式。解：查最小多项式系数
