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

课题：错误检测与纠正目的要求：掌握差错检测与纠正的方法CRC码、海明码教学重点：CRC码求法教学难点：海明码教学课时：2教学方法：讲授、演示数据链路层错误检测与纠正共22页，您现在浏览的是第1页!奇偶校验码

奇偶校验码是一种通过增加冗余位使得码字中“１”的个数为奇数或偶数的编码方法，它是一种检错码。一个二进制码字，如果它的码元有奇数个1，就称之为具有奇性。对于一个n位字，奇性=a0⊕a1⊕a2⊕…⊕an。很明显，用同样的方式，也能够根据每一个码字的零的个数来构成奇偶校验。单个的奇偶校验码可描述为：给每一个码字加一个校验位，用它来构成奇性或偶性校验。因此，若有一个码元是错的，就可以分辨得出。在一个传输系统里，传输以前，由奇偶发生器把奇偶校验位加到每个字中。原有信息中的数字在接收机中被检测，如果没有出现正确的奇、偶性，这个信息标定为错误的，这个系统将把错误的字抛掉或者请求重发。注意，用单个的奇偶校验码仅能检出奇数个码元的错误。奇偶校验可以用在数字系统的主要接口设备中，由于在每个信息中增加了冗余度，仅当出现错误的概率和错误的危害足够大时，才采用奇偶校验码。在实际的应用中，按码字的形成方向可以分为垂直奇偶校验、水平奇偶校验和垂直水平奇偶校验三种奇偶校验方式。数据链路层错误检测与纠正共22页，您现在浏览的是第2页!垂直奇偶校验

垂直奇偶校验又称纵向奇偶校验，它能检测出每列中所有奇数个错，但检测不出偶数个的错，如图2-23所示，因而对差错的漏检率接近1/2。位\数字0123456789C10101010101C20011001100C30000111100C40000000011C51111111111C61111111111C70000000000偶C00110100110奇1001011001图2-23垂直奇偶校验方式数据链路层错误检测与纠正共22页，您现在浏览的是第3页!水平垂直校验

水平垂直校验(LRC)又叫报文校验、方块校验。这种方法是在奇偶校验的基础上，为了提高奇偶校验码对突发错误的检测能力，将若干奇偶校验码排成若干行，然后对每列进行奇偶校验，放在最后一行，该检验字符的编码方法是使每一位纵向代码中1的个数成为奇数(或偶数)。传输时按照列顺序进行传输，在一批字符传送之后，另外增加一个检验字符，在接收端又按照行的顺序检验是否存在差错。由于突发错误是成串发生的，经过这样的传输后错误被分散了。它能检测出所有3位或3位以下的错误、奇数个错、大部分偶数个错以及突发长度<=p+1的突发错，如图2-25所示。可使误码率降至原误码率的百分之一到万分之一，还可以用来纠正部分差错，有部分偶数个错不能测出。它适用于中、低速传输系统和反馈重传系统。图2-25水平垂直奇偶校验方式数据链路层错误检测与纠正共22页，您现在浏览的是第4页!循环冗余检验的原理在数据链路层传送的帧中，广泛使用了循环冗余检验CRC的检错技术。假设待传送的数据M=1010001101（共kbit）。我们在M的后面再添加供差错检测用的nbit冗余码一起发送。数据链路层错误检测与纠正共22页，您现在浏览的是第5页!冗余码的计算举例设n=5,P=110101，模2运算的结果是：商Q=1101010110，余数R=01110。将余数R作为冗余码添加在数据M的后面发送出去，即发送的数据是101000110101110，或2nM+R。数据链路层错误检测与纠正共22页，您现在浏览的是第6页!帧检验序列FCS在数据后面添加上的冗余码称为帧检验序列FCS(FrameCheckSequence)。循环冗余检验CRC和帧检验序列FCS并不等同。CRC是一种常用的检错方法，而FCS是添加在数据后面的冗余码。FCS可以用CRC这种方法得出，但CRC并非用来获得FCS的惟一方法。

数据链路层错误检测与纠正共22页，您现在浏览的是第7页!应当注意仅用循环冗余检验CRC差错检测技术只能做到无差错接受(accept)。“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于

1

的概率认为这些帧在传输过程中没有产生差错”。也就是说：“凡是接受的帧都没有传输差错”（有差错的帧就丢弃而不接受）。要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。数据链路层错误检测与纠正共22页，您现在浏览的是第8页!UseofaHammingcodetocorrectbursterrors数据链路层错误检测与纠正共22页，您现在浏览的是第9页!已知：海明码的监督关系式为：

S2=a2+a4+a5+a6

S1=a1+a3+a5+a6

S0=a0+a3+a4+a6

接收码字为：“0011101”(n=7)

求：发送端的信息码。

1)由海明码的监督关系式计算得S2S1S0=011。

2)由监督关系式可构造出下面错码位置关系表：3)由S2S1S0=011查表得知错码位置是a3。

4)纠错--对码字的a3位取反得正确码字："0010101"

5)把冗余码a2a1a0删除得发送端的信息码："0010"

数据链路层错误检测与纠正共22页，您现在浏览的是第10页!3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)：

A=∑(0,1,1,0,1,0)=1

B=∑(0,1,0,0,1,0)=0

C=∑(0,1,0,0,0)

=1

D=∑(0,1,1,0,0)

=0

4)海明码为:"101110001100"数据链路层错误检测与纠正共22页，您现在浏览的是第11页!作业：生成多项式为G(x)=x4+x+1，若接收方接收到的二进制流为101101010101100110，请问传输过程是否出错？数据链路层错误检测与纠正共22页，您现在浏览的是第12页!水平奇偶校验

水平奇偶校验又称横向奇偶校验，它不但能检测出各段同一位上的奇数个错，而且还能检测出突发长度<=p的所有突发错误，如图2-24所示。其漏检率要比垂直奇偶校验方法低，但实现水平奇偶校验时，一定要使用数据缓冲器。位\数字0123456789偶校验C101010101011C200110011000C300001111000C400000000110C511111111111C611111111111C700000000000图2-24水平奇偶校验方式数据链路层错误检测与纠正共22页，您现在浏览的是第13页!恒比码

码字中1的数目与0的数目保持恒定比例的码称为恒比码。“恒比码”仅是单个奇偶校验的推广。五中取三的恒比码常常用于传输二进形式的十进数。如我国邮电部门使用的五单位数字保护电报码，就是一种五中取三的恒比码，编码方式见图2-26所示。在这种表示方法中采用8-4-2-1的权数来表示十进数，然后选择所增加的恒比位使每个字恰好有两个0和三个1。当接收到的任何信息其1的个数少于三或多于三，就可以知道这个信息是错误的。恒比码能够检测出全部的单一错误和40%的两个错误。数字编码数字编码101011610101211001711100310110801110411010910011500111001101图2-26五中取三恒比码数据链路层错误检测与纠正共22页，您现在浏览的是第14页!冗余码的计算用二进制的模

2

运算进行2n乘M的运算，这相当于在M后面添加n个0。得到的(k+n)bit的数除以事先选定好的长度为(n+1)bit的数P，得出商是Q而余数是R，余数R比除数P至少要少1个比特。数据链路层错误检测与纠正共22页，您现在浏览的是第15页!

1101010110

←

Q

商

除数

P→

110101101000110100000

←

2nM被除数

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余数循环冗余检验的原理说明数据链路层错误检测与纠正共22页，您现在浏览的是第16页!检测出差错只要得出的余数R不为0，就表示检测到了差错。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。一旦检测出差错，就丢弃这个出现差错的帧。只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到的差错的概率就很小很小。数据链路层错误检测与纠正共22页，您现在浏览的是第17页!海明码的实现和特点海明码：海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式：

２r>=n+1

或

2r>=k+r+1

海明码的编码效率为：

R=k/(k+r)

式中k为信息位位数，r为增加冗余位位数

数据链路层错误检测与纠正共22页，您现在浏览的是第18页!已知：信息码为："0010"。海明码的监督关系式为：

S2=a2+a4+a5+a6

S1=a1+a3+a5+a6

S0=a0+a3+a4+a6

求：海明码码字。

1)由监督关系式知冗余码为a2a1a0。

2)冗余码与信息码合成的海明码是："0010a2a1a0"。

设S2=S1=S0=0,由监督关系式得：

a2=a4+a5+a6=1

a1=a3+a5+a6=0

a0=a3+a4+a6=1

因此，海明码码字为："0010101"数据链路层错误检测与纠正共22页，您现在浏览的是第19页!已知：信息码为：“11001100”

(k=8)

求：海明码码字。1)把冗余码A、B、C、…，顺序插入信息码中，得海明码

码字:“AB1C100D11

0

0”

码位:

123456789101112

其中A,B,C,D分别插于2k位(k=0,1,2,3)。码位分别为1,2,4,8。2)冗余码A,B,C,D的线性码位是：(相当于监督关系式)

A->1,3,5,7,9,11