32数据链路层错误检测与纠正

1、课课 题：错误检测与纠正题：错误检测与纠正目的要求：掌握差错检测与纠正的方法目的要求：掌握差错检测与纠正的方法crc码、海明码码、海明码教学重点：教学重点：crc码求法码求法教学难点：海明码教学难点：海明码教学课时：教学课时：2教学方法：讲授、演示教学方法：讲授、演示奇偶校验码奇偶校验码 奇偶校验码是一种通过增加冗余位使得码字中“”的个数为奇数或偶数的编码方法，它是一种检错码。一个二进制码字，如果它的码元有奇数个1，就称之为具有奇性。对于一个n位字，奇性=a0 a1 a2 an。很明显，用同样的方式，也能够根据每一个码字的零的个数来构成奇偶校验。 单个的奇偶校验码可描述为：给每一个码字加一个校

2、验位，用它来构成奇性或偶性校验。因此，若有一个码元是错的，就可以分辨得出。在一个传输系统里，传输以前，由奇偶发生器把奇偶校验位加到每个字中。原有信息中的数字在接收机中被检测，如果没有出现正确的奇、偶性，这个信息标定为错误的，这个系统将把错误的字抛掉或者请求重发。注意，用单个的奇偶校验码仅能检出奇数个码元的错误。奇偶校验可以用在数字系统的主要接口设备中，由于在每个信息中增加了冗余度，仅当出现错误的概率和错误的危害足够大时，才采用奇偶校验码。在实际的应用中，按码字的形成方向可以分为垂直奇偶校验、水平奇偶校验和垂直水平奇偶校验三种奇偶校验方式。 垂直奇偶校验 垂直奇偶校验又称纵向奇偶校验，它能检测出

3、每列中所有奇数个错，但检测不出偶数个的错，如图2-23所示，因而对差错的漏检率接近1/2。位数字0 1 2 3 4 5 6 7 8 9c10 1 0 1 0 1 0 1 0 1c20 0 1 1 0 0 1 1 0 0c30 0 0 0 1 1 1 1 0 0c40 0 0 0 0 0 0 0 1 1c51 1 1 1 1 1 1 1 1 1c61 1 1 1 1 1 1 1 1 1c70 0 0 0 0 0 0 0 0 0 偶c00 1 1 0 1 0 0 1 1 0奇1 0 0 1 0 1 1 0 0 1图2-23 垂直奇偶校验方式水平奇偶校验 水平奇偶校验又称横向奇偶校验，它不但能检测出

4、各段同一位上的奇数个错，而且还能检测出突发长度=p的所有突发错误，如图2-24所示。其漏检率要比垂直奇偶校验方法低，但实现水平奇偶校验时，一定要使用数据缓冲器。位数字0 1 2 3 4 5 6 7 8 9偶校验c10 1 0 1 0 1 0 1 0 11c20 0 1 1 0 0 1 1 0 00c30 0 0 0 1 1 1 1 0 00c40 0 0 0 0 0 0 0 1 10c51 1 1 1 1 1 1 1 1 11c61 1 1 1 1 1 1 1 1 11c70 0 0 0 0 0 0 0 0 00图2-24 水平奇偶校验方式 水平垂直校验 水平垂直校验(lrc)又叫报文校验、方

5、块校验。这种方法是在奇偶校验的基础上，为了提高奇偶校验码对突发错误的检测能力，将若干奇偶校验码排成若干行，然后对每列进行奇偶校验，放在最后一行，该检验字符的编码方法是使每一位纵向代码中1的个数成为奇数(或偶数)。传输时按照列顺序进行传输，在一批字符传送之后，另外增加一个检验字符，在接收端又按照行的顺序检验是否存在差错。由于突发错误是成串发生的，经过这样的传输后错误被分散了。它能检测出所有3位或3位以下的错误、奇数个错、大部分偶数个错以及突发长度=n+1 或 2r=k+r+1海明码的编码效率为：r=k/(k+r) 式中 k为信息位位数， r为增加冗余位位数 use of a hamming co

6、de to correct burst errorsn已知：信息码为：0010。海明码的监督关系式为：s2=a2+a4+a5+a6s1=a1+a3+a5+a6s0=a0+a3+a4+a6求：海明码码字。1)由监督关系式知冗余码为a2a1a0。2)冗余码与信息码合成的海明码是：0010a2a1a0。设s2=s1=s0=0,由监督关系式得：a2=a4+a5+a6=1a1=a3+a5+a6=0a0=a3+a4+a6=1因此，海明码码字为：0010101 n已知：海明码的监督关系式为：s2=a2+a4+a5+a6s1=a1+a3+a5+a6s0=a0+a3+a4+a6接收码字为：“0011101”(n

7、=7)求：发送端的信息码。1)由海明码的监督关系式计算得s2s1s0=011。2)由监督关系式可构造出下面错码位置关系表：n3)由s2s1s0=011查表得知错码位置是a3。4)纠错-对码字的a3位取反得正确码字：0 0 1 0 1 0 15)把冗余码a2a1a0删除得发送端的信息码：0010 n已知：信息码为：“ 1 1 0 0 1 1 0 0 ”(k=8)求：海明码码字。n1)把冗余码a、b、c、，顺序插入信息码中，得海明码码字:“ a b 1 c 1 0 0 d 1 1 0 0 ”码位:1 2 3 4 5 6 7 8 9 10 11 12 其中a,b,c,d分别插于2k位(k=0,1,2

8、,3)。码位分别为1,2,4,8。n2)冗余码a,b,c,d的线性码位是：(相当于监督关系式)a-1,3,5,7,9,11；b-2,3,6,7,10,11； c-4,5,6,7,12；(注 5=4+1；6=4+2；7=4+2+1；12=8+4)d-8,9,10,11,12。 n3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)：a=(0,1,1,0,1,0)=1b=(0,1,0,0,1,0)=0c=(0,1,0,0,0)=1d=(0,1,1,0,0)=04)海明码为:1 0 1 1 1 0 0 0 1 1 0 0n已知：接收的码字为：“1 0 0 1 1 0 0 0 1 1 0 0”(k=8)求：发送端的信息码。 n1)设错误累加器(err)初值=02)求出冗余码的偶校验和，并按码位累加到err中：a=(1,0,1,0,1,0)=1err=err+20=1b=(0,0,0,0,1,0)=1err=err+21=3c=(1,1,0,0,0)=0err=err+0 =3d=(0,1,1,0,0)=0err=err+0 =3由err0可知接收码字有错，3)码字的错误位置就是错误累加器(err)的值3。4)纠错-对码字的第3位值取反得正确码字：1 0 1 1 1 0 0 0 1 1 0 05)把位于2k位的冗余码删除得信息码：1 1 0