最新更新

本类热点图文资讯

月度热点

推荐给好友 上一篇：Socket编程相关数据类型定义   下一篇：【软考】java socket资料

校验码辅导讲座

字号:  小  中  大  | 打印 发布: 2007-05-01   作者:    来源: 本站原创    查看:

一、码距
a2a1
a3a2a1a0
二、奇偶校验奇性=a0⊕a1⊕a2⊕…⊕an 偶校验位an =a0⊕a1⊕a2⊕…⊕an-1， 奇校验位an =NOT（a0⊕a1⊕a2⊕…⊕an-1）。
a1a2am-1amHP1b1b2bm-1HP2c1c2cm-1cmHP3n1n2nm-1nmVP1VP2VPm-1HPn+1
X1X2Y1X3X4Y2X5X6X7X8X9X10X11X12
则X1X2X3X4处的比特分别为__(36)__；  X5X6X7X8处的比特分别为____；  X9X10XI1X12处的比特分别为__(38)__；Y1和Y2处的字符分别为__(39)__和__(40)__。从第1列可知X4=0；从第3行可知水平也是偶校验。从第2行可知X3=1；从第7列可知X8=0；从第8列可知X12=1；从第7行可知X11=1；从第6列可知X10=0；从第6行可知X9=1；从第2列可知X1=1；从第1行可知X2=1；从第3列可知X5=1；从第4行可知X6=0；从第4列（或第5行）可知X7=0；整理一下：(36)X1X2X3X4=1110(37)X5X6X7X8=1000(38)X9X10X11X12=1011(39)由字符Y1的ASCII码1001001=49H知道，Y1即是“I”（由“D”的ASCII码是1000100=44H推得）(40)由字符Y2的ASCII码0110111=37H知道，Y2即是“7”（由“3”的ASCII码是0110011=33H推得）三、海明校验推求海明码时的一项基本考虑是确定所需最少的校验位数k。考虑长度为m位的信息，若附加了k个校验位，则所发送的总长度为m+k。在接收器中要进行k个奇偶检查，每个检查结果或是真或是伪。这个奇偶检查的结果可以表示成一个k位的二进字，它可以确定最多2k种不同状态。这些状态中必有一个其所有奇偶测试试都是真的，它便是判定信息正确的条件。于是剩下的（2k-1）种状态，可以用来判定误码的位置。于是导出下一关系：2k-1≥m+k码字格式
B1B2B3B4B5B6B7P1P2D1P3D2D3D4
校验位的确定其中：P1位负责校验海明码的第1、3、5、7、…（P1、D1、D2、D4、…）位，（包括P1自己）P2负责校验海明码的第2、3、6、7、…（P2、D1、D3、D4、…）位，（包括P2自己）P3负责校验海明码的第4、5、6、7、…（P3、D2、D3、D4、…）位，（包括P3自己）
　　 　　　 　
A=B1⊕B3⊕B5⊕B7=0得P1=D1⊕D2⊕D4B=B2⊕B3⊕B6⊕B7=0得P2=D1⊕D3⊕D4C=B4⊕B5⊕B6⊕B7=0得P3=D2⊕D3⊕D4若四位信息码为1001，利用这三个公式可求得三个校验位P1、P2、P3值。和海明码，如图7则表示了信息码为1001时的海明码编码的全部情况。而图8中则列出了全部16种信息（D1D2D3D4=0000～1111）的海明码。
B1B2B3B4B5B6B7P1P2D1P3D2D3D4
P1P2D1P3D2D3D4
A=B1⊕B3⊕B5⊕B7=0；B=B2⊕B3⊕B6⊕B7=0；C=B4⊕B5⊕B5⊕B7=0。若三个校验方程都成立,即方程式右边都等于0，则说明没有错。若不成立即方程式右边不等于0，说明有错。从三个方程式右边的值，可以判断那一位出错。例如，如果第3位数字反了，则C=0(此方程没有B3），A=B=1（这两个方程有B3）。可构成二进数CBA，以A为最低有效位，则错误位置就可简单地用二进数CBA=011指出。这是关于海明码的经典说法，即码距为3，可以发现2位，或者纠正1位错。应满足2k-1≥m+k。但在清华的王爱英主编的《组成与结构》（该书已成为国内的权威）中还提出了一种码距为4的海明码，可以发现2位，并且纠正1位错。应满足2(k-1)≥m+k。四、循环冗余校验码校验码的具体生成过程为：假设发送信息用信息多项式C(X)表示，将C(x)左移R位，则可表示成C(x)*2R，这样C(x)的右边就会空出R位，这就是校验码的位置。通过C(x)*2R除以生成多项式G(x)得到的余数就是校验码。几个基本概念如生成多项式为G(x)=x4+x3+x+1，可转换为二进制数码11011。而发送信息位1111，可转换为数据多项式为C(x)=x3+x2+x+1。
x3+x+1x3+x2+1x4+x3+x2+1x4+x2+x+1x4+x+1x8+x7+x6+x4+1x5+x2+1
x10+x9+x8+x6+x5+x3+1
x6+x+1
x12+x10+x5+x4+x2+1
x16+x15+x2+1
CRC码的生成步骤2、将信息码左移R位，相当与对应的信息多项式C(x)*2R【例】假设使用的生成多项式是G(x)=x3+x+1。4位的原始报文为1010，求编码后的报文。1、将生成多项式G(x)=x3+x+1转换成对应的二进制除数1011。CRC的和纠错
A7A6A5A4A3A2A1
如果循环码有一位出错，用G(x)作模2除将得到一个不为0的余数。如果对余数补0继续除下去，我们将发现一个有趣的结果；各次余数将按图10顺序循环。例如第一位出错，余数将为001，补0后再除（补0后若最高位为1，则用除数做模2减取余；若最高位为0，则其最低3位就是余数），得到第二次余数为010。以后继续补0作模2除，依次得到余数为100，0ll…，反复循环，这就是“循环码”名称的由来。这是一个有价值的特点。如果我们在求出余数不为0后，一边对余数补0继续做模2除，同时让被检测的校验码字循环左移。图10说明，当出现余数(101)时，出错位也移到A7位置。可通过异或门将它纠正后在下一次移位时送回A1。这样我们就不必像海明校验那样用译码电路对每一位提供纠正条件。当位数增多时，循环码校验能有效地降低硬件代价，这是它得以广泛应用的主要原因。图10的CRC码（G(x)＝1011，C(x)＝1010），若接收端收到的码字为1010111，用G(x)＝1011做模2除得到一个不为0的余数100，说明传输有错。将此余数继续补0用G(x)＝1011作模2除，同时让码字循环左移1010111。做了4次后，得到余数为101，这时码字也循环左移4位，变成1111010。说明出错位已移到最高位A7，将最高位1取反后变成0111010。再将它循环左移3位，补足7次，出错位回到A3位，就成为一个正确的码字通信与网络中常用的CRC在数据通信与网络中，通常k相当大，由一千甚至数千数据位构成一帧，而后采用CRC码产生r位的校验位。它只能检测出错误，而不能纠正错误。一般取r=16，标准的16位生成多项式有CRC-16＝x16+x15+x2+1和CRC-CCITT＝x16+x15+x2+1。一般情况下，r位生成多项式产生的CRC码可检测出所有的双错、奇数位错和以及（1-2-(r-1)）的突发长度为r+1的突发错和（1-2-r）的突发长度大于r+1的突发错。例如，对上述r=16的情况，就能检测出所有突发长度小于等于16的突发错以及99．997%的突发长度为17的突发错和99．998%的突发长度大于17的突发错。所以CRC码的检错能力还是很强的。这里，突发错误是指几乎是连续发生的一串错，突发长度就是指从出错的第一位到出错的最后一位的长度(但是，中间并不一定每一位都错)。【例1】某循环冗余码（CRC）的生成多项式G(x)＝x3+x2+1，用此生成多项式产生的冗余位，加在信息位后形成CRC码。若发送信息位1111和1100则它的CRC码分别为＿A＿和＿B＿。由于某种原因，使接收端收到了按某种规律可判断为出错的CRC码，例如码字＿C＿、＿D＿、和＿E＿。（1998年试题11）
供选择的答案A：G(x)＝1101，C(x)＝1111C(x)*23÷G(x)＝1111000÷1101＝1011余111得到的CRC码为1111111B：G(x)＝1101，C(x)＝1100C(x)*23÷G(x)＝1100000÷1101＝1001余101得到的CRC码为1100101【例2】中常用的一种检错码是CRC，即_A_码。在进行编码过程中要使用_B_运算。假设使用的生成多项式是G(X)=X4+X3+X+1，原始报文为11001010101，则编码后的报文为_C_。CRC码_D_的说法是正确的。在无线电通信中常采用它规定码字长为7位．并且其中总有且仅有3个“1”。这种码的编码效率为_E_。供选择的答案：A：①水平垂直奇偶校验  ②循环求和③循环冗余④正比率B：①模2除法 ②定点二进制除法 ③二－十进制除法 ④循环移位法C：①1100101010111 ②110010101010011③110010101011100 ④110010101010101D：①可纠正一位差错  ②可检测所有偶数位错 ③可检测所有小于校验位长度的突发错  ④可检测所有小于、等于校验位长度的突发错E：①3/7      ②4/7      ③log23/log27    ④(log235)/7解：从前面有关CRC的论述中可得出： A：③循环冗余 B：①模2除法 D：从前面有关通信与网络中常用的CRC的论述中可得出：④可检测所有小于、等于校验位长度的突发错，所谓7中取3定比码，就是整个码字长度为7位，其中1的位数固定为3。所有128个7位代码（0000000～1111111）中只有1的位数固定为3的才是其合法码字。可以用求组合的公式求出其合法码字数为：C73＝7!/(3!*(7-3)!)＝7*6*5/(1*2*3)＝35编码效率＝合法码字所需位数/码字总位数＝(log235)/7


TAG:

我来说两句