《第4部分数据链路控制部分PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第4部分数据链路控制部分PPT讲稿.ppt（135页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第4部分数据链路控部分数据链路控制部分制部分第1页，共135页，编辑于2022年，星期一4.数据链路控制数据链路控制4.1基本概念1、物理链路的基本结构由计算机和通信的各自发展进程可知，直接连接一词是指两台设备之间的传输信道为直接连接的通信形式。例如，两台计算机的直接连接如图4.1(a)所示，常称点-点连接；多台计算机的直接连接如图4.1(b)所示，常称多点连接。第2页，共135页，编辑于2022年，星期一图4.1物理链路的结构(a)点-点连接；(b)多点连接第3页，共135页，编辑于2022年，星期一物理链路的基本结构可分为两种：点-点链路和多点链路。数据链路两端的DTE可以是计算机或终端
2、，也可是路由器或交换设备。从链路逻辑功能的角度来看，这些设备可称为站;从网络拓扑结构的观点来看，则常称之为节点(Node)。1)点-点链路在点-点链路中，发送信息或命令的站常称为主站(Primary，可简写成P)，接收信息和命令而发出确认信息或响应的站称为从站(Secondary，可简写成S)；兼有主、从站功能，可发送命令或响应的站称为复合站。第4页，共135页，编辑于2022年，星期一2)多点链路在多点链路中，往往有一站为控制站，主管数据链路的信息流，并处理链路上出现的不可恢复的差错情况；其余各站则为受控站。多点链路早先用于面向终端的计算机系统，随着计算机通信技术的发展，现已广泛用于计算机局
3、域网、无线分组网和卫星分组网。第5页，共135页，编辑于2022年，星期一2、数据链路控制的功能数据链路最重要的作用就是：通过一些数据链路控制规程(即数据链路层协议)，在不太可靠的、有外来干扰的物理链路上实现可靠的、几乎无差错的数据传输。依照OSI参考模式，可将数据链路层的主要功能归纳为以下7类。第6页，共135页，编辑于2022年，星期一1）.帧同步(FrameSynchronous)在数据链路层，数据的传送单元是帧(Frame)。数据一帧一帧地依次传送，这样在传输中一旦出现差错，只需将有差错的帧再重传一次，而无须将全部数据都进行重传，尤其适合于传输长的数据文件。帧同步是指收方应能从收到的比
4、特流中准确地判断出一帧的开始和结束，以便协调收发方之间的工作。第7页，共135页，编辑于2022年，星期一2）.寻址(Addressing)在点-点链接的环境中，如X.25帧级的寻址方式，寻址方式比较单一；但在多点链接的情况下，必须设置保证每一帧正确送到的收方地址及发方地址，以便收方知道是哪一个站点发送的帧。3）.流量控制(FlowControl)流量控制应确保通信的基本要求，即发方的发送数据速率必须不能超过收方及时接收和处理的能力。当收方来不及接收时，就必须采取相应的措施来控制发方发送数据的速率。第8页，共135页，编辑于2022年，星期一4）.差错控制(ErrorControl)在计算机一
5、类数据通信中，一般都要求有极低的比特差错率，为此广泛采用了编码技术。编码技术有两大类：一类是纠错编码，即前向纠错;另一类是检错编码,即检错重发。前向纠错:收方收到有差错的数据帧时，能够发现差错并能自动加以改正。这种方法的开销较大，适合于使用卫星中继的计算机通信。检错重发:收方一旦检测出收到的帧中有差错(但并不关心是哪几个比特有错)，就要求发方重复发送这一帧，以便收方能正确接收。这种方法在计算机通信中是最常用的。本章所要讨论的协议主要采用检错重发这种差错控制方法本章所要讨论的协议主要采用检错重发这种差错控制方法。第9页，共135页，编辑于2022年，星期一5）.数据和控制信息的识别(Identi
6、fication)由于数据和控制信息都是在同一信道中传送的，在许多情况下，数据和控制信息处在同一帧中，因此，一定要有相应的办法使收方能够将它们区分开来，这就是数据和控制信息的识别。6）.透明传输(TransparentTransmission)所谓透明传输，就是不管所传数据是什么样的比特组合，都应当能够在物理链路上传送。当所传数据中的比特组合恰巧与某一个控制信息完全一样时，就必须采取适当的措施，使收方不会将这样的数据误认为是某种控制信息，即保证了数据链路的传输具有透明性。第10页，共135页，编辑于2022年，星期一7）.链路管理(LinkManagement)当网络中的两个节点要进行通信时，
7、数据的发方必须确知收方是否已在准备接收的状态。为此，通信的双方必须先交换一些必要的控制信息,或者说，必须先建立一条数据链路。同样地，在传输数据时应当维持数据链路，而在通信完毕时要释放数据链路。数据链路的建立、维持和释放过程就叫做链路管理。第11页，共135页，编辑于2022年，星期一上述的数据链路控制功能与其数据链路控制协议(规程)密切相关，不同的网络具有不同的通信协议(规程)。本章讨论的重点是广域网的数据链路控制协议(规程)，而局域网的数据链路控制协议(规程)比广域网的更为复杂，我们将在介绍局域网时再进行讲述。第12页，共135页，编辑于2022年，星期一4.2 数据链路控制协议机理与分析数
8、据链路控制协议机理与分析 4.21停止等待协议在广域网数据链路层上，最简单、最基本的数据链路控制协议是停止等待(StopandWait)协议。为叙述方便起见，我们假设数据以帧(Frame)为单元传输，并且数据链路为半双工传输方式，如图4.2所示，仅由节点A向节点B发送数据，节点B向节点A回送确认。第13页，共135页，编辑于2022年，星期一图4.2停止等待协议的通信过程t7第14页，共135页，编辑于2022年，星期一1.停止等待协议的特征描述停止等待协议的特征是：当节点A发出一个数据帧后，必须停止发送，等待节点B的应答(Acknowledgement,ACK)。如果节点B收到数据帧后，经检
9、验无差错，则回送一应答(确认)帧通知节点A，节点A才能发送下一个数据帧，这种处理称之为正证实。1)正常情况所谓正常情况，是指在传输过程中，任何帧都不会出错或被丢失，这是一种理想情况。如图4.2所示，主机A将原文送到节点A，以数据帧格式通过数据电路传到节点B。节点B收到数据帧后，经验证无误，应立即执行下列操作：第15页，共135页，编辑于2022年，星期一(1)把数据帧送往主机B。(2)向节点A回送一个应答帧(ACK)确认。下面从时间顺序对传输一个数据帧的简单过程来分析停止等待协议的特征。设t1为数据帧传输第1比特的开始时刻，t2为第1比特到达节点B的时刻，t3为数据帧最后1比特到达的时刻，则数
10、据帧的传播时间tp为(4.1)式中，l为节点AB间的传输距离(km)；v为电波速度，一般在线媒质中取为2105km/s。第16页，共135页，编辑于2022年，星期一数据帧的传输时间tF为(4.2)式中，设F为数据帧长度(bit)，C为数据传输速率(b/s)。又设每个帧F由控制信息和数据信息两个部分组成，即式中，H为控制信息的比特数，D为每帧数据信息的比特数。节点A和B处理帧的时间tproc为 tproc=t4-t3=t7-t6第17页，共135页，编辑于2022年，星期一应答帧(ACK)的传输时间tA为式中，A为应答帧长度。因此，停止等待协议传输一个数据帧中D比特数据的信道利用率U为(4.3
11、)第18页，共135页，编辑于2022年，星期一如果在纯理想的条件下，即既不考虑数据传输时间又忽略传播时延，不计确认帧的开销，则信道利用率U仅与帧的结构F=H+D有关。例如，设帧F的D长度为128字节，而H为6字节，由此可算得U=95.5%。与异步通信方式传输一个字符的信道利用率U=70%相比较，可见以帧为单元的同步通信的信道利用率有了较大的改善。第19页，共135页，编辑于2022年，星期一2)非常情况现在，我们再来讨论节点A与B之间的数据传输有可能出现差错的情况。其差错具体表现在以下两方面：(1)节点A向节点B发送数据帧时，在传送中受到干扰出错或丢失数据。(2)节点B收到数据帧后，回送出A
12、CK帧，在BA的传输过程中，受到干扰出错或丢失数据。第20页，共135页，编辑于2022年，星期一这两方面的问题都致使节点A将一直等不到ACK确认帧，因此，节点A也就永远无法继续发送下一个帧，这就形成了死锁(DeadLock)。解决上述问题的办法是在节点A设置一个定时器T1，它的预定时间为t0。当发出一个数据帧后，立即启动定时器T1。若在预定时间t0内，节点A能收到ACK，则可继续正常传送下一个待发帧。若在预定时间内收不到ACK，即超时(TimeOut)，则节点A由此可判定应重发数据帧。第21页，共135页，编辑于2022年，星期一定时器的t0值必须不小于节点A与B之间来回传播的时间，即节点A
13、与B发、收帧的处理时间以及回送确认帧ACK的传输时间，也即t0(2tp+2tproc+tA)。很明显，如果t0(2tp+2tproc+tA)，则有可能在回送ACK的行程中，节点A的定时器已超时，误认有错而重发，这样在节点B将会收到第二份相同的数据帧，形成重复帧，这是在数据链路控制协议中要采取措施解决的又一问题。第22页，共135页，编辑于2022年，星期一要解决重复帧的问题，行之有效的方法是对每一个发出的数据帧都编上号。若接收端收到相同编号的帧，可认为出现了重复帧,这时应当丢弃这一重复帧,与此同时，节点B仍需向节点A发送确认帧ACK，表明上一次发送的ACK已受干扰或丢失，并未送到节点A。第23
14、页，共135页，编辑于2022年，星期一接着要考虑的问题是如何选用编号方案。对于停止等待协议，节点A每次只能发一个数据帧，所以只需用1bit的两个状态0、1加以编号即可。在正常的数据帧交换过程中，帧的序号0、1交替出现。每发送一个新的数据帧，编号值与上一次不同，收方就能区分出新的或重复的数据帧。第24页，共135页，编辑于2022年，星期一2.停止等待协议的定量分析现在我们来对上述的停止等待协议作定量分析。考虑到传输差错的影响，若某帧被干扰或丢失，设定时器的时限为T，则不成功传输所占用的传输容量Q1为F+CT。如果每帧重发平均次数为R，那么含R个废帧、一个正确帧的信道总容量Q0为 Q0=R(F
15、+CT)+(F+A+2CI)式中,I=tp+tproc。那么，考虑到传输差错影响的信道利用率U0为第25页，共135页，编辑于2022年，星期一现在再计算每帧重发的R。设p1为丢失某一数据帧的概率，p2为丢失1个ACK的概率。当数据帧和ACK帧两者均被正确接收，即帧发送成功的概率为(1-p1)(1-p2)时,显然有故障的概率p为1-(1-p1)(1-p2)，在k次试验中有k-1次重发的概率为(1-p)pk-1，则每帧传送的平均数R为(4.4)第26页，共135页，编辑于2022年，星期一所以，每个数据帧重发的平均次数R为将式上代入式(3.4)，可得(4.6)为简化分析，假设定时器的超时值T近似
16、等于(A/C+2I)，那么信道利用率U0可化简为(4.7)(4.5)第27页，共135页，编辑于2022年，星期一上式表明停止等待协议的实际信道利用率U0与以下三个因素有关：(1)第一项D/(H+D)，表明帧内附加控制信息标题的大小H会直接影响U0的值，即使在正常情况下，为传送数据位D也要考虑附加H时所引起的开销。(2)第二项(1-p)，表明在传送过程中出现差错的概率p决定着重发过程。也就是说，差错概率越大，重发可能性越大，致使U0降低。第28页，共135页，编辑于2022年，星期一(3)最后一项是协议的控制过程所引起的开销，每发送一数据帧，要等待T才能发送下一个数据帧，因此T值越大，其U0越
17、低。当式(3.7)中的HD，且CTF时，该式就简化为U(1-p)，说明信道利用率U取决于故障的概率p。由以上分析可知，停止等待协议很简单，但信道利用率不高。第29页，共135页，编辑于2022年，星期一3.停止等待协议的算法下面用程序语言来阐述停止等待协议的算法。为了讨论方便，仍设数据链路为半双工通信方式，仅由节点A发送数据帧，节点B接收数据帧，并假定只回送ACK确认帧。发送节点A内设发送状态变量V(S)，接收节点B内设接收状态变量V(R)。V(S)的值表示下一个待发送的帧序号，V(R)的值表示期望接收的帧序号。停止等待协议基本的收发过程如图4.3所示。其工作过程解释如下：第30页，共135页
18、，编辑于2022年，星期一图4.3停止等待协议(半双工传输方式)基本的收发过程第31页，共135页，编辑于2022年，星期一(1)经数据链路初始化后，V(S)、V(R)分别置于0。(2)对停止等待协议的V(S)、V(R)，若用1bit编号，只能是0、1两个值。(3)节点A每发送一个新帧，在其控制字段中填上N(S)值，此值取自V(S)。图中节点A发送第一个数据帧I格式内含N(S)，其值为0，因为N(S)=V(S)。第32页，共135页，编辑于2022年，星期一(4)在节点B，每收到一个数据帧，将其N(S)与节点B内的V(R)相比。若相等，表明该帧序号为期望值，则把数据帧的信息内容送往主机；修改V
19、(R)，取V(R)V(R)+1(模2)，赋值V(R)=1；同时对节点A回送确认帧ACK，内含节点B期望收到的下一个帧序号N(R)，此值为修改后的V(R)。如不相等，表明发送出错。第33页，共135页，编辑于2022年，星期一(5)当节点A收到节点B的确认帧时，RRN(R)=1，RR表示接收端准备妥(ReceiveReady)。取出N(R)=1，节点A判定N(S)为0的数据帧已被节点B正确接收了，可以发下一个数据帧，其V(S)应为V(S)+1=0+1=1。为了对上述停止等待协议(半双工传输方式)基本的收发过程有一个深入的理解，教材上给出用C语言编写的算法程序。第34页，共135页，编辑于2022
20、年，星期一4.2.2滑动窗口的流量控制方法实用的数据链路通信一般要求双向传输，即每个节点都能发送和接收数据；同一帧中既有数据信息又含有控制信息；发送节点发出的每一个帧均应有序号。本节将引入“滑动窗口(SlideWindow)”机制来说明如何循环重复使用已收到确认的帧的序号，提供可靠的流量控制手段，保证信息传输的准确性，有效地提高信道利用率。第35页，共135页，编辑于2022年，星期一1.滑动窗口的概念“滑动窗口”机制是实现数据帧的顺序控制的逻辑过程，它要求通信两端节点设置发送存储单元(缓冲区)，用于保存已发送但尚未被确认的帧，这些帧对应着一张连续序号列表。实质上，这些帧也可等效成一个先进先出
21、的队列，如图4.4所示。第36页，共135页，编辑于2022年，星期一图4.4滑动窗口的概念图第37页，共135页，编辑于2022年，星期一图中所示的已发送但未收到确认的序号队列的界称为发送窗口,其上界和下界分别称为发送窗口的上沿H(W)和下沿L(W)，上沿与下沿的区间定义为窗口尺寸W。设WT为发送窗口的尺寸，表示要占用存储单元的数量。同理，在接收端也可设置类似的接收窗口，设WR为接收窗口尺寸，指示期待接收的帧序号。第38页，共135页，编辑于2022年，星期一窗口尺寸W的选择与信道的数据速率以及传输时延都有关，还与编号的bit数有关。若用nbit编号，可以编2n个序号，从0到2n-1，其中最
22、大序号值Smax=2n-1。经常选用的n值为3或7。当n=3时，序号可为(07)模8循环使用；当n=7时，序号可为(0127)模128循环使用。第39页，共135页，编辑于2022年，星期一假定现用3bit进行编号，则窗口尺寸W的最小值为1，最大值为模数值-1即2n-1=7。对于模8的应用，数据帧的顺序编号总是07这8个数字循环，于是可以把窗口看作(注意仅仅是看作而言)是由一个圆的多个连续的八等分扇形面所组成的，如图4.5所示，每个扇形面代表一个序号，并按顺时钟方向编号。第40页，共135页，编辑于2022年，星期一图4.5滑动窗口机制的流量控制H(W)=L(W)+W-1第41页，共135页，
23、编辑于2022年，星期一发送窗口是用来对发送端进行流量控制的，发送窗口尺寸WT表示在没有收到对方确认的条件下发送端可连续发送的帧数。就停止等待协议而言，按照窗口尺寸的概念，其WT=1。这意味着停止等待协议在发出一个数据帧后，若没有收到对方确认，就不能连续发下一个数据帧。第42页，共135页，编辑于2022年，星期一2.滑动窗口机制的流量控制方法现在来解释图4.5中滑动窗口的流量控制方法。假定其发送窗口尺寸WT=3，按定义这表明在没有收到对方确认的情况下，发送端可连续最多发3个数据帧。在节点初始化后，图4.5的发送窗口内包含3个序号，即02。当发送端依次发完了02号数据帧，而尚未收到确认信息，那
24、么发送窗口已满，就应停止发送进入等待状态。第43页，共135页，编辑于2022年，星期一此时窗口的下沿L(W)=0，而窗口的上沿H(W)=2。设最后收到的确认帧的N(R)=3，按上一节的解释，则表示发送的编号为0、1及2号的帧已全部正确被对方所接收。这时将收到帧的N(R)作为窗口的下沿L(W)=3，则窗口上沿H(W)=W+N(R)-1(模8)=5，表示现在可以发送的数据帧编号为3、4、5，整个扇形面按顺时针方向滑动了一个区域。第44页，共135页，编辑于2022年，星期一若此时V(S)值为4，表示编号为3的帧已经发送，还允许继续发送4、5号帧。如果发送帧的N(S)等于窗口的上沿，则窗口关闭，应
25、停止发送，等待确认。待接收到新的数据帧或确认帧，它的N(R)大于上次的N(R)，则窗口的下沿按顺时针方向移动，那样又可继续发送N(S)=V(S)的数据帧。正因为窗口按照上述规律不断地向前滑动，故称之为滑动窗口机制的流量控制方法。第45页，共135页，编辑于2022年，星期一接收窗口的设置与发送窗口类似，但接收窗口是表明接收端允许接收的数据帧的序号范围。因此，只有在接收窗口内的数据帧才是期望接收的，换句话说，接收窗口之外的帧被看作是非法的而丢弃。滑动窗口机制的流量控制方法可用于包括数据链路控制协议在内的各层次控制协议，例如，它在网络层、传输层中都有应用。第46页，共135页，编辑于2022年，星
26、期一4.2.3连续ARQ协议连续ARQ协议的工作原理是应用滑动窗口机制的流量控制方法，改进了停止等待协议的缺点；在发送一个数据帧后，不是停止发送，而是允许继续发送多个数据帧，使通信的效率得到了提高。在连续ARQ协议中，所用的发送窗口尺寸WT应大于1，且接收端是有序接收的。允许连续发送数据帧的个数取决于窗口尺寸的大小，一般WT2n-1，其中n为编号的bit数。第47页，共135页，编辑于2022年，星期一现举例解释连续ARQ协议的工作过程，如图4.6所示。假设节点A向节点B发数据帧，设发送窗口的尺寸WT=5，表明节点A可连续发送5个数据帧，其序号为04。当节点A发完0号帧后，可以继续发送后续的1
27、号帧、2号帧等，对于每一帧分别按顺序编号。而接收窗口的尺寸WR=1。第48页，共135页，编辑于2022年，星期一图4.6连续ARQ协议的工作过程第49页，共135页，编辑于2022年，星期一(1)设节点B在收到一帧后立即应答，则应指明是对哪个帧号予以确认或否认。(2)现在假设2号数据帧在传输中出了差错(图中用E表示)，于是节点B发送否认帧NAK2(实际上用REJ表示帧拒绝)。NAK2到达节点A时，节点A正在发送4号帧。节点A根据收到的REJ中附带的N(R)=2，就可知道应当重发2号帧，但应在4号帧发送完后才能进行2号帧的重发。第50页，共135页，编辑于2022年，星期一(3)节点B应答NA
28、K2后，接着陆续收到3、4号帧，尽管这些帧号是帧正确到达的序号，但节点B也要将其丢弃(图中用D表示)。由于有序接收的约束，节点B只能等待2号帧。由此可知，对连续ARQ协议，节点一旦发现出错的数据帧后，其状态变量V(R)值保持不变，等待该帧序号的到达。此例中的V(R)=2，因此任何不等于2的N(S)都不加以处理。第51页，共135页，编辑于2022年，星期一(4)节点A在发完4号帧后，还要向回走，重传从2号帧开始的所有帧，因此连续ARQ协议又称为GobackNARQ，它指的是出现差错必须重传时，要向后走N个帧，然后开始重传。由以上分析可知，连续ARQ协议应允许连续发送多个数据帧。这虽然提高了吞吐
29、率,但重传的方法(即重传原来正确的帧)又增加了开销。在数据链路不太可靠(误码率大)的网络环境中，连续ARQ协议的通信效率并不会得到改善。第52页，共135页，编辑于2022年，星期一下面来寻求连续ARQ协议的吞吐量关系式。由图4.6可见，在无差错时，成功地发送一个数据帧所需的时间为tF；当出现差错时，重发一个数据帧所需的时间为tT。图4.6中重发处理所需的时间应近似为3tF+2tp。由此可得出在连续ARQ协议情况下，正确传送一个数据帧所需的平均时间t为式中a=tT/tF。第53页，共135页，编辑于2022年，星期一当发送节点处于饱和状态时，吞吐量的最大值(每秒成功发送的最大帧数)max为而归
30、一化的吞吐量为(4.10)(4.9)第54页，共135页，编辑于2022年，星期一式中，为每秒到达的帧数，小于max。若式(3.10)中a=1(即传播时间和超时时限值都远小于一个数据帧的传输时间tF)，则=(1-p)=S，即为停止等待协议的吞吐量。例在一个广域网上传送数据(参见图4.6)，设数据帧为1096bit，数据速率为64kb/s，链路长度为2000km。试求停止等待协议的归一化吞吐量S与连续ARQ协议的归一化吞吐量C(设p=0.01)。第55页，共135页，编辑于2022年，星期一解第56页，共135页，编辑于2022年，星期一此例结果表明，在题中的条件下，采用连续ARQ协议的归一化吞
31、吐量C可达95.9%，而同样情况下，停止等待协议的归一化吞吐量S只有23.7%。值得注意的是，在连续ARQ协议中，为了减少接收端开销，不必像图4.6所示的那样,每收到一个正确的数据帧就立即回送一个确认帧或否认帧，而是等连续收到好几个正确数据帧后，只对最后那个帧发一个确认信息即可。用N(R)表示接收端期望接收的帧序号，也表明N(R)-1号的帧及此号以前的各个数据帧均已正确无误收到。第57页，共135页，编辑于2022年，星期一例如，在图4.6所示发送窗口中，WT=5，发送端节点连续发送04号帧，然后窗口关闭，等待确认；而接收端节点每收到一个正确序号的帧，用V(R)与N(S)相比。如果相等，V(R
32、)V(R)+1(模n)。由于接收是有序的，每当V(R)加1，则表示前一帧已判为正确帧。若不相等，收端节点应立即回送一个否认帧。第58页，共135页，编辑于2022年，星期一当接收端节点接收了所有应该收到的序号，如果接收端恰有数据帧传送到节点A，则可由数据帧将N(R)信息捎带传到节点A。如果接收端无数据帧要传送，则应送出确认帧带上N(R)值。为确保应答及时，可设置一应答定时器T2，其预定时间应小于T1的预定时间。每接收一数据帧，经判断为正确帧后，就启动T2。若节点B有数据帧发送，则可复位T2，并发出捎带N(R)的数据帧。如一时无数据要发，则等待T2超时后即送出确认帧。第59页，共135页，编辑于
33、2022年，星期一4.2.4选择重传ARQ协议为了进一步提高信道利用率，减少重传的帧数，可以设法只重传有错的帧或者是定时器超时的帧，这就是选择重传ARQ协议。在该协议中，接收窗口的尺寸WR必须加大，使得接收序号不连续的但仍在接收窗口内的那些帧可暂存一下，以便等待所缺序号的帧重传到之后再一并送交主机。由此可见，这种协议所允许的发送窗口的尺寸WT和接收窗口的尺寸WR均可大于1，但应满足下式：WT+WR2n (4.11)第60页，共135页，编辑于2022年，星期一接收窗口WR的约束条件是不能大于发送窗口，因此，WR的最大值等于2n-1。若用3bit编号，取WRmax=2n-1=4时，可求得WT=4
34、。这种选择重传ARQ协议可以避免重传那些已经正确到达对方的数据帧，但要求占用更多的缓冲空间。第61页，共135页，编辑于2022年，星期一4.3 差错控制差错控制 计算机通信中的差错控制主要用来提高数据传输的可靠性与传输效率，它涉及纠、检错编码理论与方法，数据信道中差错分布的统计特性，以及选择相应的差错控制方式。计算机通信中的差错控制方式基本上可分为以下三类：(1)自动请求重发(ARQ)：接收端检测到接收信息有错时，通过重发发送端保存的副本以达到纠错的目的。第62页，共135页，编辑于2022年，星期一(2)前向纠错(FEC)：接收端检测到接收信息有错后，通过计算，确定差错的位置，并自动加以纠
35、正。(3)混合方式：接收端采取纠错混合(在ATM中应用)，即对少量差错予以自动纠正，而超过其纠正能力的差错则通过重发原信息的方法加以纠正。第63页，共135页，编辑于2022年，星期一不论哪种控制差错方式，都是以降低实际传输效率来提高其传输可靠性的。因此，在信道特性已经确定的条件下，差错控制的基本任务是寻求简单、有效的方法，确保系统的可靠性。目前，编码方式按码的构型可分为分组码和卷积码。常用的分组码有恒比码、垂直水平奇偶校验码、记数校验码、斜校法校验码、循环冗余校验码。其中，循环冗余校验码在数据链路控制中的应用最为普遍，而卷积码则在前向纠错系统中应用较多。本节着重介绍奇偶校验码和循环冗余校验码
36、(简称循环冗余码)。第64页，共135页，编辑于2022年，星期一4.3.1奇偶校验码奇偶校验码可分为奇校验码和偶校验码，两者的校验原理相同。在偶校验码中，校验位为1位(比特)；其校验规则为：加入校验位后的码字所包含的总的“1”的个数为偶数，即D1D2D3D7D8=0第65页，共135页，编辑于2022年，星期一例如，ASCII码字中大写字母A的二进制7比特为1000001(左为D7，右为D1)，1的个数为偶数，因此为确保加入校验位D8后的码字所含总的“1”应为偶数，则校验位D8必为0。同理，奇校验码的校验规则是：加入校验位后的码字所包含的总的“1”的个数为奇数，即D1D2D3D7D8=1如仍
37、将上例说明，为确保加入校验位D8后的码字所含总的“1”应为奇数，则校验位D8必为1。第66页，共135页，编辑于2022年，星期一如仍将上例说明，为确保加入校验位D8后的码字所含总的“1”应为奇数，则校验位D8必为1。奇偶校验码简单实用，但检错能力有限，一般只能检出奇数个出错码元，不适宜检测突发性差错。在此基础上，人们又进而提出了垂直水平奇偶校验码、记数校验码、斜校法校验码等，它们都属于二维奇偶校验码，适用于检测突发差错。第67页，共135页，编辑于2022年，星期一4.3.2海明码海明码是由RHamming在1950年提出的一种特殊的线性分组码，它可以纠正1位出错的比特。其基本编码规则是：若
38、码长为n，信息位为k，则附加r位冗余信息(也称监督位或校验位)，其中每个校验位与某几个特定的信息位构成偶校验的关系。接收端对这r个奇偶关系进行校验，即将每个校验位和与它关联的信息位进行相加(异或)，相加的结果称为校正因子。如果没有错误的话，这r个校正因子都为0；如果有一个错误，则校正因子不会全为0。根据校正因子的不同取值，可以知道错误发生在码字的哪一个位置上。第68页，共135页，编辑于2022年，星期一若要求用r个校验位构造出r个校验关系式来指出一位出错码的n种可能的位置，必须满足下列条件：2rn+1，即2rk+r+1(4.12)现以k=4为例来说明海明码的构造方法。如要满足不等式(4.12
39、)，则有r3。如取r=3，则n=k+r=7，常记作(n，k)。现以c6c5c4c0表示例中的7个码元，用S1、S2、S3表示三个校验关系式中的校正因子，则海明码中S1、S2、S3的值与出错码位置的对应关系如表4.1所示(也可定成另一种对应关系，不会影响其一般性)。第69页，共135页，编辑于2022年，星期一表4.1校正因子与出错码位置的对应关系第70页，共135页，编辑于2022年，星期一从上表可知，仅当一个出错码位于c 6、c 5、c 4和c 2时，校正因子S1为1，否则S1为0。可求得c 6、c 5、c 4、c 2四个码元形成的偶校验关系；同理，可得c 6、c 5、c 3、c 1和c 6
40、、c 4、c 3、c 0两组四个码元形成的偶校验关系(参见式(4.13)如下：第71页，共135页，编辑于2022年，星期一在发送端的信息位c6、c5、c4和c3的值取决于输入数据，是随机的，而校验位c2、c1、c0则根据信息位的值按校验位关系式确定。若编成的码组中无差错，那么校验位应使式(3.13)中的S1、S2、S3值均为0，可得：(4.13)(4.14)第72页，共135页，编辑于2022年，星期一例如，对于一段信息1000，按式(4.15)校验位生成式可得：c2=1，c1=1，c0=1，于是发送端发送的码字是1000111。上式经移项后，可求出校验位生成式：(4.15)第73页，共13
41、5页，编辑于2022年，星期一假如在接收端收到码字0000111，按以上校正因子的计算式(4.13)可得：S1=1，S2=1，S3=1，三个校正因子不全为0，说明码字有错，错误位置为S=S1S2S3=111=7，即信息位c6有错。将c6上的0变为1，即可纠正错误。最后去掉校验位，得到正确信息为1000。第74页，共135页，编辑于2022年，星期一上述海明码的码长为7比特，其中信息为4比特，因此(7,4)海明码其编码效率为47。如果取信息位数为7，可求得r4，取r=4，则码字长度为11。根据上面介绍的方法同样可以求得(11,7)海明码的码表，(11,7)海明码的编码效率为711。可见，信息位越
42、长，编码效率越高。第75页，共135页，编辑于2022年，星期一4.3.3循环冗余码1.循环冗余码的特性循环冗余码(CRC)是一种分组码。在一个长度为n的码组中有k个信息位和r个校验位，校验位的产生只与该组内的k个信息位有关。通常称这种结构的码为(n，k)码，此值k/n称为这种码的编码效率。第76页，共135页，编辑于2022年，星期一循环冗余码有以下两个特性：(1)一种码中的任何两个码字按模2相加后，形成的新序列仍为一个码字；若两个相同码字相加则得一个全0序列，因此，循环码一定包含全0码字。具有这种特性的循环冗余码称为线性码。(2)一码字的每次循环移位一定也是码集合中的另一个码字。设有一个(
43、n，k)线性码，其中每一个码字表示为U=U0，U1，U2，Ui，Un-2，Un-1式中，Ui为“0”或“1”。第77页，共135页，编辑于2022年，星期一如果U循环右移1位所得码字为 U=Un-1，U0，U1，U2，Ui，Un-2则循环后的码字也为码集合中的码字，称这种特性为循环特性。根据以上两个特性，循环冗余码可把码字表示为n-1次幂的多项式：U(x)=Un-1xn-1+Un-2xn-2+U2x2+U1x+U0式中，系数Un-1，Un-2，U1，U0为码组中相应码元的值(0或1)；x为延迟因子，表示单位时延。向左移1位，相当于多项式各项乘以x，并且满足xn=1，则原来最高幂次项Un-1xn
44、-1左移后成了幂次最低的一项。第78页，共135页，编辑于2022年，星期一一个循环冗余码(n，k)有且仅有一个生成多项式G(x)。上述两个特性可概括为每一码字多项式U(x)都可以表示码生成多项式的倍式，即 U(x)=i(x)G(x)模(xn-1)(4.16)式(4.16)中，i(x)表示倍式因子。第79页，共135页，编辑于2022年，星期一2.循环冗余码的编码/译码设k信息位的多项式可写成M(x)=mk-1xk-1+mk-2xk-2+m2x2+m1x+m0(4.17)式中，mi系数值为“0”或“1”。所谓编码，就是找出其对应码字的表达式。通常码字的前k位为信息位，后n-k位为校验位，因此，
45、其信息位的多项式为xn-kM(x)，幂次小于n。当用G(x)去除xn-kM(x)时，可得(4.18)第80页，共135页，编辑于2022年，星期一式中，Q(x)为幂次小于k的商式，R(x)为幂次小于(n-k)的余式。由式(4.18)可知xn-kM(x)R(x)=Q(x)G(x)即多项式xn-kM(x)+R(x)是G(x)的倍式，因此，它必是一个G(x)生成为循环冗余码中的码字。第81页，共135页，编辑于2022年，星期一由此可知，循环冗余码的编码步骤如下：(1)求M(x)所对应的码字，可先求M(x)，并乘以xn-k。(2)然后将所得式被G(x)除，求其余式。(3)得xrM(x)R(x)，即为
46、所求码字。M(x)乘xr可用移位寄存器的移位来实现;而被G(x)除，则可用G(x)的除法电路来实现。G(x)=xr+gr-1xr-1+g1x+1的一般除法电路如图4.5.1(a)所示，符号gi表示需连接或不连接，依据多项式中系数的“1”或“0”而定。第82页，共135页，编辑于2022年，星期一图4.7循环冗余码编码器第83页，共135页，编辑于2022年，星期一现假设由生成多项式G(x)=x3+x+1构成(7，4)循环冗余码，又设待编码的信息二进制序列为1101(左边为高序)，它对应的信息多项式为M(x)=x3+x2+1。利用多项式的长除法，可求得余式R(x)序列为001，则码组多项式为x3
47、M(x)R(x)=x6+x5+x3+1其对应的二进制序列为1101001(左边为高序)。由图4.7(b)所示的x3+x+1的除法电路可知，信息码输入经过三个单位时间的延迟才从输出端产生余式。实用的编码电路可改成图4.8所示形式。第84页，共135页，编辑于2022年，星期一图4.8改进的(7,4)循环编码电路第85页，共135页，编辑于2022年，星期一图4.8中,A信号在移位脉冲14期间使门a、c 开通，B信号在此期间使门b关闭；而在移位脉冲57期间，门a、c 关闭，门b开通。移位寄存器初始状态为000，修改后的编码电路的寄存器状态如表4.2所示。可以看出，经输入4位二进制信号序列，即可得移
48、位寄存器的状态为“100”，即为余式。余式在移位脉冲期间依次输出，得1101001。第86页，共135页，编辑于2022年，星期一在接收端，循环冗余码的译码电路也是用图4.5.1(b)所示的除法电路构成的。校验的方法是用生成多项式G(x)除接收下来的xrM(x)R(x)，如能整除，则表明传输无差错。例如，接收端收到的xrM(x)R(x)序列为1101001，而G(x)为1011，则运算后除尽。若由于传输中出错，使接收序列变为1111001，则经长除运算可得余式R(x)，如图4.9所示，表明传输有误，但并不能指明错在哪个比特位。第87页，共135页，编辑于2022年，星期一表4.2编码电路的寄存
49、器状态第88页，共135页，编辑于2022年，星期一图4.9循环冗余码的检错第89页，共135页，编辑于2022年，星期一4.3.4纠/检错能力分析数据通信中，由于信道热噪声或环境噪声的干扰，在介质上传输的数字信号可能会从“1”变为“0”或从“0”变成“1”，称作发生了差错。这类差错可分两种：一种称为单个错，一种称为突发错。单个错通常是由随机的信道热噪声引起的，一次只影响一位，且错误之间不存在相互关联。突发错通常是由瞬间的脉冲噪声引起的，如雷电等，它所影响的最大连续数据位数称为突发长度。第90页，共135页，编辑于2022年，星期一任何一种检错码或纠错码的检错和纠错能力都是有限的，不能保证检出
50、所有的错误。假设有信息长度为k比特，在发送端按照上述某种差错编码算法附加上r位冗余信息，这样实际传输的长度为n=k+r位的码字。其中有效码字数为2k个(k个信息位有2k种不同组合)，而总码字数为2n个，显然有2k2n，因此必有一部分是无效码字。当一个有效码字由于差错变成了一个无效码字时，立即就能判断出有错；反之，当一个有效码字错成了另一个有效码字时，因为没有理由认为它出错，这时错误就检测不出来了。第91页，共135页，编辑于2022年，星期一两个码字的对应位数取值不同的个数称为这两个码字的海明距离，如10001001和10110001这两个码字，它们的第3、4、5位取值不同，因此这两个码字的海