数据链路层错误检测与纠正ppt课件.ppt

课课 题：错误检测与纠正题：错误检测与纠正目的要求：掌握过失检测与纠正的方法目的要求：掌握过失检测与纠正的方法CRC码、海明码码、海明码教学重点：教学重点：CRC码求法码求法教学难点：海明码教学难点：海明码教学课时：教学课时：2教学方法：讲授、演示教学方法：讲授、演示奇偶校验码奇偶校验码 奇偶校验码是一种经过添加冗余位使得码字中“１〞的个数为奇数或偶数的编码方法，它是一种检错码一个二进制码字，假设它的码元有奇数个1，就称之为具有奇性对于一个n位字，奇性=a0⊕a1⊕a2⊕…⊕an很明显，用同样的方式，也可以根据每一个码字的零的个数来构成奇偶校验 单个的奇偶校验码可描画为：给每一个码字加一个校验位，用它来构成奇性或偶性校验因此，假设有一个码元是错的，就可以分辨得出在一个传输系统里，传输以前，由奇偶发生器把奇偶校验位加到每个字中原有信息中的数字在接纳机中被检测，假设没有出现正确的奇、偶性，这个信息标定为错误的，这个系统将把错误的字抛掉或者恳求重发留意，用单个的奇偶校验码仅能检出奇数个码元的错误奇偶校验可以用在数字系统的主要接口设备中，由于在每个信息中添加了冗余度，仅当出现错误的概率和错误的危害足够大时，才采用奇偶校验码。

在实践的运用中，按码字的构成方向可以分为垂直奇偶校验、程度奇偶校验和垂直程度奇偶校验三种奇偶校验方式 垂直奇偶校验 垂直奇偶校验又称纵向奇偶校验，它能检测出每列中一切奇数个错，但检测不出偶数个的错，如图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 垂直奇偶校验方式程度奇偶校验 程度奇偶校验又称横向奇偶校验，它不但能检测出各段同一位上的奇数个错，而且还能检测出突发长度<=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)又叫报文校验、方块校验。

这种方法是在奇偶校验的根底上，为了提高奇偶校验码对突发错误的检测才干，将假设干奇偶校验码排成假设干行，然后对每列进展奇偶校验，放在最后一行，该检验字符的编码方法是使每一位纵向代码中1的个数成为奇数(或偶数)传输时按照列顺序进展传输，在一批字符传送之后，另外添加一个检验字符，在接纳端又按照行的顺序检验能否存在过失由于突发错误是成串发生的，经过这样的传输后错误被分散了它能检测出一切3位或3位以下的错误、奇数个错、大部分偶数个错以及突发长度<=p+1的突发错，如图2-25所示可使误码率降至原误码率的百分之一到万分之一，还可以用来纠正部分过失，有部分偶数个错不能测出它适用于中、低速传输系统和反响重传系统 图2-25 程度垂直奇偶校验方式恒比码恒比码 码字中1的数目与0的数目坚持恒定比例的码称为恒比码恒比码〞仅是单个奇偶校验的推行五中取三的恒比码经常用于传输二进方式的十进数如我国邮电部门运用的五单位数字维护电报码，就是一种五中取三的恒比码，编码方式见图2-26所示在这种表示方法中采用8-4-2-1的权数来表示十进数，然后选择所添加的恒比位使每个字恰好有两个0和三个1当接纳到的任何信息其1的个数少于三或多于三，就可以知道这个信息是错误的。

恒比码可以检测出全部的单一错误和40%的两个错误数字编码数字编码101011610101211001711100310110801110411010910011500111001101图2-26 五中取三恒比码循环冗余检验的原理 n在数据链路层传送的帧中，广泛运用了循环冗余检验 CRC 的检错技术n假设待传送的数据 M = 1010001101〔共k bit〕我们在M的后面再添加供过失检测用的 n bit 冗余码一同发送 冗余码的计算 n用二进制的模 2 运算进展 2n 乘 M 的运算，这相当于在 M 后面添加 n 个 0n得到的 (k + n) bit 的数除以事先选定好的长度为 (n + 1) bit 的数 P，得出商是 Q 而余数是 R，余数 R 比除数 P 至少要少1 个比特 冗余码的计算举例 n设 n = 5, P = 110101，模 2 运算的结果是：商 Q = 1101010110，n 余数R = 01110n将余数 R 作为冗余码添加在数据 M 的后面发送出去，即发送的数据是101000110101110，或 2nM + R  1101010110 ← Q 商商 除数除数 P → 110101 101000110100000 ← 2nM 被除数被除数 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 ← R 余数余数循环冗余检验的原理阐明 帧检验序列 FCS n在数据后面添加上的冗余码称为帧检验序列 FCS (Frame Check Sequence)。

n循环冗余检验 CRC 和帧检验序列 FCS并不等同nCRC 是一种常用的检错方法，而 FCS 是添加在数据后面的冗余码nFCS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的独一方法 检测出过失 n只需得出的余数 R 不为 0，就表示检测到了过失n但这种检测方法并不能确定终究是哪一个或哪几个比特出现了过失n一旦检测出过失，就丢弃这个出现过失的帧n只需经过严厉的挑选，并运用位数足够多的除数 P，那么出现检测不到的过失的概率就很小很小 该当留意 n仅用循环冗余检验 CRC 过失检测技术只能做到无过失接受(accept)n“无过失接受〞是指：“凡是接受的帧〔即不包括丢弃的帧〕，我们都能以非常接近于 1 的概率以为这些帧在传输过程中没有产生过失〞n也就是说：“凡是接受的帧都没有传输过失〞〔有过失的帧就丢弃而不接受〕n要做到“可靠传输〞〔即发送什么就收到什么〕就必需再加上确认和重传机制 海明码的实现和特点n海明海明码 ：海明：海明码是一种可以是一种可以纠正一位正一位过失的失的编码它是利用在信息位它是利用在信息位为k k位，添加位，添加r r位冗余位冗余位，构成一个位，构成一个n=k+rn=k+r位的位的码字，然后用字，然后用r r个个监视关系式关系式产生的生的r r个校正因子来区分无个校正因子来区分无错和在和在码字中的字中的n n个不同位置的一位个不同位置的一位错。

它必需它必需满足以足以下关系式：下关系式：　　　　　　　　　２　　　　　　　　　２r>=n+1  r>=n+1  或或    2r>=k+r+12r>=k+r+1　　海明　　海明码的的编码效率效率为：：　　　　　　　　　　　　　　　　　　　　　　　　R=k/(k+r)R=k/(k+r) 式中式中 k k为信息位位数，信息位位数， r r为添加冗余添加冗余位位数位位数 Use of a Hamming code to correct burst errorsn知：信息码为："0010"海明码的监视关系式为：　　　　　　　　S2=a2+a4+a5+a6　　　　　　　　S1=a1+a3+a5+a6　　　　　　　　S0=a0+a3+a4+a6　　　　　　　　　　求：海明码码字1)由监视关系式知冗余码为a2a1a02)冗余码与信息码合成的海明码是："0010a2a1a0"　　　　　设S2=S1=S0=0,由监视关系式得：　　　　　　　　a2=a4+a5+a6=1　　　　　　　　a1=a3+a5+a6=0　　　　　　　　a0=a3+a4+a6=1　　　　　　因此，海明码码字为："0010101" n知：海明码的监视关系式为：　　　　　　　　S2=a2+a4+a5+a6　　　　　　　　S1=a1+a3+a5+a6　　　　　　　　S0=a0+a3+a4+a6　　　　　　接纳码字为：“0011101〞(n=7)　　　　求：发送端的信息码。

1)由海明码的监视关系式计算得S2S1S0=0112)由监视关系式可构造出下面错码位置关系表：n3)由S2S1S0=011查表得知错码位置是a34)纠错--对码字的a3位取反得正确码字："0 0 1 0 1 0 1"5)把冗余码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,3)码位分别为1,2,4,8n2)冗余码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)=1　　　　　　B=∑(0,1,0,0,1,0)=0　　　　　　C=∑(0,1,0,0,0)　=1　　　　　　D=∑(0,1,1,0,0)　=0　　　　4)海明码为:"1 0 1 1 1 0 0 0 1 1 0 0"n知：接纳的码字为：“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)=1　err=err+20=1　　　　　　B=∑(0,0,0,0,1,0)=1　err=err+21=3　　　　　　C=∑(1,1,0,0,0)　=0　err=err+0 =3　　　　　　D=∑(0,1,1,0,0)　=0　err=err+0 =3　　　　　由err≠0可知接纳码字有错，3)码字的错误位置就是错误累加器(err)的值34)纠错--对码字的第3位值取反得正确码字：　　　　　　"1 0 1 1 1 0 0 0 1 1 0 0"5)把位于2k位的冗余码删除得信息码："1 1 0 0 1 1 0 0" n作作业业：：生生成成多多项项式式为为G(x)=x4+x+1，，假假设设接接纳纳 方方 接接 纳纳 到到 的的 二二 进进 制制 流流 为为101101010101100110，，请请问问传传输输过过程程能能否否出错？出错？n教学总结：本讲讲解错误检测与纠正下一讲讲解滑动窗口协议。