《通讯差错校验.doc》由会员分享，可在线阅读，更多相关《通讯差错校验.doc（9页珍藏版）》请在金锄头文库上搜索。
1、本专题概述(第5周)数据链路层的帧-差错控制-循环冗余校验帧的传输控制标准之流量控制滑动窗口协议协议种类与事实标准回首往事 数据链路层数据链路层主要是保证数据帧的传输。帧，一段（块、团）由比特流组成的数据。为了保证帧传输的准确进行，规定了：帧的定义（构造组成标准）、帧的传输控制标准（差错控制、流量控制）等。二帧传输差错的发现1.传输差错的来源：电磁干扰、接触不良。2.传输差错的检测要求：A.简单快速 B. 易于实现 C.附加的位少 D.最好能纠错3.传输差错的检测方法（1）奇偶校验A.奇校验B. 偶校验为了得到偶校验位，发送方把校验位置1，并使1的总数（包括校验位）是偶数。发送方：原数据为11
2、10110（奇数个1） ， 转变后实际发送的数据为11110110（偶数个1），在前面插1原数据为0110110（偶数个1） ， 转变后实际发送的数据为00110110（偶数个1），在前面插0接受方：检测数据中1的总个数，为偶数个1则认为传输正确，为奇数个1则认为传输发生错误。优点：A.简单快速 B. 易于实现 C.附加的位少 缺点：不可靠。如传输数据中有两位同时发生错误，则无法判断是否传输出错。例：发送方：原数据为1110110（奇数个1） ， 转变后实际发送的数据为11110110（偶数个1）。如果传输发生错误 11110110 突变为 11110000接受方：检测数据中1的总个数，为偶数
3、个1则认为传输正确，为奇数个1则认为传输发生错误。解决办法：采用其他方法。（2） 用校验和检测差错算法描述： step1: 把所有的数据看成是二进制（16进制）整数序列，并把这些整数序列累加。Step2: 把整数序列累加产生的进位再次累加到结果中。例如： H e l l o w o r l d .48 656C 6C 6F 2077 6F72 6C64 2E4865+6C6C+6F20+776F+726C+642E+进位=71FC(4865+6C6C+6F20+776F+726C+642E = 271FA ,进位为2，71FA+2=71FC)优点：A.简单快速 B. 易于实现 C.附加的位少
4、缺点：不能检测所有错误。如传输数据中有两位同时发生错误，则无法判断是否传输出错。例：原数据： 出错后变为： 0001 0003 0002 0000 0003 0001 0001 0003校验和均为7 （3） 用循环冗余校验（Cyclic Redundancy Check ,CRC）检测差错g(X)=X16+X12+X5+1优点：可以检测出小范围内出错。例如，突发性错误。A、校验原理循环冗余码校验英文名称为Cyclical Redundancy Check，简称CRC。它是利用除法及余数的原理来作错误侦测（Error Detecting）的。实际应用时，发送装置计算出CRC值并随数据一同发送给接
5、收装置，接收装置对收到的数据重新计算CRC并与收到的CRC相比较，若两个CRC值不同，则说明数据通讯出现错误。B.工作原理 (a). 把位串看成是系数为0或1的多项式。一个K位帧看成是系数为0或1的K次多项式（从XK-1 到 X0）的系数序列.例：110001 共6位 K=6 表示成多项式1*X5+1*X4+0*X3+0*X2+0*X1+1*X0多项式系数1，1，0，0，0，1(b). 模2加法或减法运算=异或运算（相异为1，相同为0）0- 0=0 0 -1=1 1- 0=1 1-1 =0 0+0=0 0+1=1 1+0=1 1+1=00异或0=0 0异或1=11异或0=1 1异或1=0(c)
6、.发送方和接收方事先商量好一个生成多项式g(X)=X16+X12+X5+1。(d).基本思想：将CRC校验位加在帧的末尾，使这个带校验位的帧的多项式能被g(x)除尽（整除）。当接收收到带CRC校验位的帧时，用多项式g(x)去除它（即带校验的帧的多项式/多项式g(x) ） ，如果有余数，则说明数据通讯出现错误。C.计算CRC校验算法：step1:用乘法。设多项式g(x)为r阶，在帧的末尾附加r个0，使这个帧为m+r位，相应的多项式为xr*M(x)step2:用除法。多项式xr*M(x)的系数位串 /多项式g(x) 的系数位串step3: 用模2减法（异或运算）。从多项式xr*M(x)的系数位串-
7、余数。结果就是要传送的带校验位的帧.叫多项式T(x).明显地，T(x)能被 g(x)整除。因为：（被除数-余数）/除数 ，结果肯定为整数（即被整除，无余数）。例如： 10/3=3，余1，（10-1）/3= ？，结果肯定为整数（即被整除，无余数）。例：帧： 1101011011 M(x)除数：10011 g(x)=x4+x+1 r阶 r=4在帧的末尾附加r=4个0后形成的串 11010110110000 xr*M(x)商 1100001010 10011 ) 11010110110000 10011 -1001110011- 00000结果：商1100001010 余 1110要传送的带校验位的
8、帧多项式T(x) 11010110111110T(x)=Xr*M(x)+余数 当接收收到校验位的帧时，用多项式g(x)去除它（即带校验位的帧的多项式/多项式g(x) ） ，如果有余数，则说明数据通讯出现错误。11010110111110/10011=? 余 ？问题：当多项式g(x)的整数倍差错时，无法检测。效果：1、一个坏帧查不出来的概率大致为 1/2r2、 CRC-16码或CRC-CCITT码，可以查到所有的单位和双位出错，所有的奇数位错，所有的长度16位可以查到99.9%的出错。D. CRC标准根据应用环境与习惯的不同，CRC又可分为以下几种标准：CRC-12码；CRC-16码； g(X)
9、=X16+X15+X2+1CRC-CCITT码；g(X)=X16+X12+X5+1CRC-32码。CRC-12码通常用来传送6-bit字符串。CRC-16及CRC-CCITT码则用是来传送8-bit字符，其中CRC-16为美国采用，而CRC-CCITT为欧洲国家所采用。CRC-32码大都被采用在一种称为Point-to-Point的同步传输中。E .实现 (a) 硬件实现尽管CRC在数学上是复杂的，当可以用简单且便宜的硬件来实现。并且绝大多数都是硬件实现。下面以常用的CRC-CCITT 16位码 g(X)=X16+X12+X5+1为例来说明其生成过程。CRC-CCITT码由两个字节构成，在开始
10、时CRC寄存器的每一位都预置为0，然后把CRC寄存器与8-bit的数据进行异或，之后对CRC寄存器从高到低进行移位，在最高位（MSB）的位置补零，而最低位（LSB，移位后已经被移出CRC寄存器）如果为1，则把寄存器与预定义的多项式码进行异或，否则如果LSB为零，则无需进行异或。重复上述的由高至低的移位8次，第一个8-bit数据处理完毕，用此时CRC寄存器的值与下一个8-bit数据异或并进行如前一个数据似的8次移位。所有的字符处理完成后CRC寄存器内的值即为最终的CRC值。下面为CRC的计算过程：step1设置CRC寄存器，并给其赋值0000(hex)。step2将数据的第一个8-bit字符与1
11、6位CRC寄存器的低8位进行异或，并把结果存入CRC寄存器。step3CRC寄存器向右移一位，MSB补零，移出并检查LSB。step4如果LSB为0，重复第三步；若LSB为1，CRC寄存器与多项式码相异或。step5重复第3与第4步直到8次移位全部完成。此时一个8-bit数据处理完毕。step6重复第2至第5步直到所有数据全部处理完成。step7最终CRC寄存器的内容即为CRC值。(b) 软件（程序）实现其优点是可移植性好。其缺点为计算量大。编写CRC校验程序，就是依据CRC校验码的产生原理来设计程序。*3.3.2防止数据过载的流量控制计算机并不都以相同的速度运行，当一台计算机通过网络发送数据
12、的速度比目的计算机接收数据的速度快时，就出现了数据过载，这样就会发生数据丢失的情况。有几种流量控制（flow control）机制可用于处理数据过载。流量控制最简单的形式是一个定期停等（stop-and-go）系统：每发出一个包便等待确认。当接收方准备好接收另一个包时，发送一个控制消息，通常这是一种确认形式的消息。虽然定期停等协议避免了过载，却降低了网络带宽的利用率。要理解这一点，考虑一个包大小为1000个字节、传输速度为2Mb/s、延迟时间为50ms的网络的运行情况。网络硬件以2Mb/s的速度把数据从一台计算机传送到另一台计算机。但是每发送一个包后，发送方必须等100ms才能发送另一个包（即
13、包到达接收方需50ms，传回确认也需50ms）。因此，使用定期停等协议传送数据的最大速率为每100ms一个包。若以位传送速率表示，定期停等协议的最大速率可达80 000b/s，这只是硬件容量的4%。为了获得较高的吞吐量，协议使用称为滑动窗口（sliding windows）的流量控制技术。程序设置发送方和接收方使用固定的窗口大小（window size），这是在收到确认前可以发送的最大数据量。例如，发送方和接收方同意窗口大小为四个包。发送方在开始使用需发送的数据时，提取数据填入第一个窗口，并发送副本。如果有可靠性要求，发送方应保留一份副本以备万一需要时重发。接收方必须准备好缓冲区空间以接收整个
14、窗口。当包顺序到达时，接收方把时，接收方把包传给应用程序并返回一个确认给发送方。当确认到达后，发送方丢弃已确认的副本并发送一个包。图5-1说明了所谓滑动窗口的过程。图5-1 一个四个包大小的窗口滑过发送数据，窗口显示为（a）当开始传送时，（b）两个包被确认后，（c）8个包被确认后。发送方可以传送窗口中的所有包滑动窗口能显著地增加吞吐量。要理解这一点，考虑图中使用定期停等真议和滑动窗口协议的传送顺序。图5-2 对大小为四个包的传送进行了比较。图5-2 （a）表示了一个定期停等协议的传送顺序，在已发送出一个包后，发送另一个包之前要等待确认。如果沿着网络的一条路径发帝一个包的延迟时间为N，发送四个所需要时间为8N。图5-2（b）表示了一个滑动窗口协议的传送顺序，协议在等待前发送出窗口中的所有包。图中显示了在后继包的发送之前有一段小的延迟。虽然这一延迟小得几乎不能察觉，但传送并不是立即发生的需要一段很短的时间（通常是若干微秒）让硬件完成包的发送，中断cpu，然后开始传送下一个包。因此，发送四个包所需要的全部时间是2N，这里指
