第5章 数据链路层(1)

1、北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/第第5 5章章 数据链路层数据链路层数据链路层功能数据链路层功能组帧组帧差错控制差错控制流量控制与可靠传输机制流量控制与可靠传输机制介质访问控制介质访问控制局域网局域网广域网广域网数据链路层设备数据链路层设备北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/在两台主机通过互联网通信时，从源主机在两台主机通过互联网通信时，从源主机H1开始，经过一系列路由器（开始，经过一系列路由器（R1、R2、R3），到目的主机），到目的主机H2结束。结束。 从协议的层次看，主机从协议的层次看，主机H1和和H2有完整的协议层次，路由

2、器的协议栈只有下面三有完整的协议层次，路由器的协议栈只有下面三层。数据进入路由器后先从物理层上到网络层，在网络层的转发表中找到下一跳层。数据进入路由器后先从物理层上到网络层，在网络层的转发表中找到下一跳的地址后，再下到物理层转发数据。的地址后，再下到物理层转发数据。北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/只考虑数据在数据链路层流动只考虑数据在数据链路层流动 当主机当主机H1向向H2发送数据时，我们可以想象数据是在数发送数据时，我们可以想象数据是在数据链路层从左向右水平传送。即通过这样的四段链路：据链路层从左向右水平传送。即通过这样的四段链路：H1链路层链路层R1链路层

3、、链路层、R1链路层链路层R2链路层、链路层、R2链链路层路层R3链路层和链路层和R3链路层链路层H2链路层。链路层。 北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.1数据链路层功能数据链路层功能一些术语一些术语 结点结点把主机和路由器统称为结点把主机和路由器统称为结点 物理链路物理链路 沿着通信路径连接相邻结点的通信信道。链路的中间没有任何沿着通信路径连接相邻结点的通信信道。链路的中间没有任何其他的交换结点。两个主机通信时，通信路径上要经过许多独其他的交换结点。两个主机通信时，通信路径上要经过许多独立的链路。立的链路。 逻辑链路逻辑链路 把实现数据传输协议的硬件和软件

4、加到链路上，就构成了数据把实现数据传输协议的硬件和软件加到链路上，就构成了数据链路，有人将其称为逻辑链路。链路，有人将其称为逻辑链路。 网络适配器就是实现这些协议的硬件和软件。一般的适配器包网络适配器就是实现这些协议的硬件和软件。一般的适配器包含了数据链路层和物理层这两层的功能。链路层协议交换的数含了数据链路层和物理层这两层的功能。链路层协议交换的数据单元称为帧。据单元称为帧。 北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.1数据链路层功能数据链路层功能所有的数据链路层的基本功能都是将数据帧通过单条链路从一个结点移所有的数据链路层的基本功能都是将数据帧通过单条链路从一个

5、结点移动到相邻结点，但具体细节依赖于该链路上应用的具体数据链路层协议。动到相邻结点，但具体细节依赖于该链路上应用的具体数据链路层协议。 链路层协议包括如以太网、链路层协议包括如以太网、802.11802.11无线局域网、令牌环和无线局域网、令牌环和PPPPPP。 链路层的一个重要特点是在通信路径的不同链路上可能由不同的链链路层的一个重要特点是在通信路径的不同链路上可能由不同的链路层协议来处理。需要着重注意的是不同的数据链路层协议的提供路层协议来处理。需要着重注意的是不同的数据链路层协议的提供功能是不同的。功能是不同的。例如一个数据链路层协议可能提供可靠的交付、另一个数据链例如一个数据链路层协议

6、可能提供可靠的交付、另一个数据链路层协议可能不提供可靠的交付。路层协议可能不提供可靠的交付。 数据链路层可能提供的服务包括：组帧、差错控制、流量控制、可靠传数据链路层可能提供的服务包括：组帧、差错控制、流量控制、可靠传输和介质访问控制。输和介质访问控制。北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.1数据链路层功能数据链路层功能1.1.组帧组帧 在网络层分组在链路上传输前，链路层协议用数据链路层的在网络层分组在链路上传输前，链路层协议用数据链路层的帧将其封装。帧将其封装。一一个帧有数据字段和首部字段组成，网络层的分组就插在数据字段个帧有数据字段和首部字段组成，网络层的分

7、组就插在数据字段中。一个帧可能包含尾部字段，我们把首部字段和尾部字段合并起中。一个帧可能包含尾部字段，我们把首部字段和尾部字段合并起来称为首部字段。接收端在收到物理层上交的比特流后，能根据首来称为首部字段。接收端在收到物理层上交的比特流后，能根据首部字段的标记，从收到的比特流中识别帧的开始和结束。帧的结构部字段的标记，从收到的比特流中识别帧的开始和结束。帧的结构由数据链路层协议规定。由数据链路层协议规定。北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.1数据链路层功能数据链路层功能2.差错控制差错控制由于通信链路中存在信号的衰减和电磁干扰，帧中的由于通信链路中存在信号的衰

8、减和电磁干扰，帧中的比特在传输过程中可能产生差错，比特在传输过程中可能产生差错，1接收方判断为接收方判断为0，0接收方判断为接收方判断为1。转发有差错的数据是没有意义的，数据链路层的许多转发有差错的数据是没有意义的，数据链路层的许多协议提供检测是否存在差错的机制。这是通过在帧中协议提供检测是否存在差错的机制。这是通过在帧中设置差错检测冗余位，让接收结点对收到的帧进行差设置差错检测冗余位，让接收结点对收到的帧进行差错检测来完成的。错检测来完成的。差错纠正不仅能检测是否帧中出现了差错，而且能够差错纠正不仅能检测是否帧中出现了差错，而且能够判决帧中的差错出现在哪里并纠正这些错误。一些协判决帧中的差错

9、出现在哪里并纠正这些错误。一些协议如议如ATM只为分组的首部提供链路层差错纠正。只为分组的首部提供链路层差错纠正。北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.1数据链路层功能数据链路层功能3.流量控制流量控制由于链路的每一结点具有有限的帧缓存，接收结点在由于链路的每一结点具有有限的帧缓存，接收结点在某个时间段收到帧的速率比其处理的速度快，没有流某个时间段收到帧的速率比其处理的速度快，没有流量控制，接收方的缓存会溢出，帧会丢失。量控制，接收方的缓存会溢出，帧会丢失。链路层协议提供流量控制机制，当接收方来不及处理链路层协议提供流量控制机制，当接收方来不及处理发送方发送的数

10、据时，及时控制发送方发送数据的速发送方发送的数据时，及时控制发送方发送数据的速率，旨在使收发方协调一致。率，旨在使收发方协调一致。北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.1数据链路层功能数据链路层功能4.可靠传输可靠传输当数据链路层提供可靠传输服务时，它保证将网络当数据链路层提供可靠传输服务时，它保证将网络层的分组无差错地通过数据链路层。层的分组无差错地通过数据链路层。链路层可靠传输的服务时通过确认和重传机制来获链路层可靠传输的服务时通过确认和重传机制来获得的。得的。链路层可靠地传输服务常用于容易产生高差错率的链路层可靠地传输服务常用于容易产生高差错率的链路，如无

11、线链路。链路，如无线链路。而低差错率的链路，包括光纤、双绞线和同轴电缆，而低差错率的链路，包括光纤、双绞线和同轴电缆，链路层的可靠传输被认为是不必要的开销。因此许链路层的可靠传输被认为是不必要的开销。因此许多有线的链路层协议不提供可靠的交付。多有线的链路层协议不提供可靠的交付。北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.1数据链路层功能数据链路层功能5.介质访问控制介质访问控制介质访问控制协议定义了帧在链路上传输的规则。介质访问控制协议定义了帧在链路上传输的规则。对于在链路的一端有一个发送方、另一端有一个接对于在链路的一端有一个发送方、另一端有一个接受方的点对点链路，

12、介质访问控制协议比较简单，受方的点对点链路，介质访问控制协议比较简单，甚至不存在。甚至不存在。对于多个结点共享单个广播链路，就是被称为多址对于多个结点共享单个广播链路，就是被称为多址访问的问题，介质访问控制协议用来协调多个结点访问的问题，介质访问控制协议用来协调多个结点的帧传输。的帧传输。北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.2组帧组帧 封装成帧封装成帧(framing)就是在一段数据的前后分别添加首就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。确定帧的界限。部和尾部，然后就构成了一个帧。确定帧的界限。 首部和尾部的一个重要作用就是进行首部和尾部的

13、一个重要作用就是进行帧定界帧定界。 帧结束帧首部IP 数据报帧的数据部分帧尾部 MTU数据链路层的帧长开始发送帧开始北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.2组帧组帧1.字节计数法字节计数法 这种帧同步方法以一个特殊字符表征一帧的起始，这种帧同步方法以一个特殊字符表征一帧的起始，并以一个专门字段来标明帧内的字节数。并以一个专门字段来标明帧内的字节数。 接受方可以通过对该特殊字符的识别从比特流中接受方可以通过对该特殊字符的识别从比特流中区分出帧的起始，并从专门字段中获知该帧中随区分出帧的起始，并从专门字段中获知该帧中随后跟随的数据字节数，从而可确定出帧的终止位后跟随

14、的数据字节数，从而可确定出帧的终止位置。置。北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.2组帧组帧 面向字节计数的同步规程的典型实例是面向字节计数的同步规程的典型实例是DEC公司的数字公司的数字数据通信报协议数据通信报协议DDCMP。 控制字符控制字符SOH标志数据帧的起始。标志数据帧的起始。 Count字段共有字段共有14位，用以指示帧中数据段中数据的位，用以指示帧中数据段中数据的字节数，数据段最大长度为字节数，数据段最大长度为8(214-1)=131064位，长位，长度必须为字节度必须为字节(即即8位位)的整倍数，的整倍数，DDCMP协议就是靠协议就是靠这个字节计

15、数来确定帧的终止位置的。这个字节计数来确定帧的终止位置的。 CRC1、CRC2分别对首部和数据部分进行双重校验分别对首部和数据部分进行双重校验 。 CRC2DataCRC1AddrSegAckFlagCountSOH16(位位)8-131064168882148北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.2组帧组帧2. 使用字符填充的首尾定界符法使用字符填充的首尾定界符法 该法用一些特定的字符来定界一帧的起始与终止。该法用一些特定的字符来定界一帧的起始与终止。为了不使数据信息位中出现的与特定字符相同的字为了不使数据信息位中出现的与特定字符相同的字符被误判为帧的首尾定界

16、符，可以在这种数据字符符被误判为帧的首尾定界符，可以在这种数据字符前填充一个转义控制字符以示区别，从而达到数据前填充一个转义控制字符以示区别，从而达到数据的透明性。的透明性。北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/用控制字符进行帧定界的方法举例用控制字符进行帧定界的方法举例 SOH装在帧中的数据部分帧帧开始符帧结束符发送在前EOT北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/透明传输SOHEOT出现了“EOT”被接收端当作无效帧而丢弃被接收端误认为是一个帧数据部分EOT完整的帧发送在前北京化工大学北方学院信息院北京化工大学北方学院信息院 http:

17、/解决透明传输问题 发送端的数据链路层在数据中出现控制字符发送端的数据链路层在数据中出现控制字符“SOH”或或“EOT”的前面插入一个转义字符的前面插入一个转义字符“ESC”(其十六进制编码其十六进制编码是是 1B)。 字节填充字节填充(byte stuffing)或或字符填充字符填充(character stuffing)接收端的数据链路层在将数据送往网络层之前删除插入的接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。转义字符。 如果转义字符也出现数据当中，那么应在转义字符前面插如果转义字符也出现数据当中，那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符时，入

18、一个转义字符。当接收端收到连续的两个转义字符时，就删除其中前面的一个。就删除其中前面的一个。 北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/SOHSOHEOTSOHESCESCEOTESCSOHESCESCESCSOH原始数据EOTEOT经过字节填充后发送的数据字节填充字节填充字节填充字节填充发送在前帧开始符帧结束符用字节填充法解决透明传输的问题 SOH北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.2组帧组帧3.使用比特填充的首尾定界符法使用比特填充的首尾定界符法 该法以一组特定的比特模式该法以一组特定的比特模式(如如01111110)来标志一来标志

19、一帧的起始与终止。帧的起始与终止。本节稍后要详细介绍的本节稍后要详细介绍的HDLC和和PPP协议就采用该协议就采用该法。为了不使信息位中出现的与该特定模式相似的法。为了不使信息位中出现的与该特定模式相似的比特串被误判为帧的首尾标志，可以采用比特填充比特串被误判为帧的首尾标志，可以采用比特填充的方法。的方法。 比如，采用特定模式比如，采用特定模式01111110，则对信息位中的任，则对信息位中的任何连续出现的何连续出现的5个个“1”，发送方自动在其后插入一个，发送方自动在其后插入一个“0”，而接受方则做该过程的逆操作，即每收到连，而接受方则做该过程的逆操作，即每收到连续续5个个“1”，则自动删去

20、其后所跟的，则自动删去其后所跟的“0”，以此恢复，以此恢复原始信息，实现数据传输的透明性。比特填充很容原始信息，实现数据传输的透明性。比特填充很容易由硬件来实现，性能优于字符填充方法。易由硬件来实现，性能优于字符填充方法。 北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.2组帧组帧4.违法编码法违法编码法该法在物理层采用特定的比特编码方法时采用。该法在物理层采用特定的比特编码方法时采用。 例如，曼彻斯特编码方法，是将数据比特例如，曼彻斯特编码方法，是将数据比特“1”编码编码成成“高高-低低”电平对，将数据比特电平对，将数据比特“0”编码成编码成“低低-高高”电平对。而电平

21、对。而“高高-高高”电平对和电平对和“低低-低低”电平对在数电平对在数据比特中是违法的。据比特中是违法的。可以借用这些违法编码序列来定界帧的起始与可以借用这些违法编码序列来定界帧的起始与终止。终止。 局域网局域网IEEE 802标准中就采用了这种方法。标准中就采用了这种方法。违法编码法不需要任何填充技术，便能实现数违法编码法不需要任何填充技术，便能实现数据的透明性，但它只适用采用冗余编码的特殊据的透明性，但它只适用采用冗余编码的特殊编码环境。编码环境。 北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.3差错控制差错控制信号在物理信道中传输时，线路本身电器特性造成的信号在物

22、理信道中传输时，线路本身电器特性造成的随机噪声、信号幅度的衰减、频率和相位的畸变、电随机噪声、信号幅度的衰减、频率和相位的畸变、电器信号在线路上产生反射造成的回音效应、相邻线路器信号在线路上产生反射造成的回音效应、相邻线路间的串扰以及各种外界因素（如大气中的闪电、开关间的串扰以及各种外界因素（如大气中的闪电、开关的跳火、外界强电流磁场的变化、电源的波动等）都的跳火、外界强电流磁场的变化、电源的波动等）都会造成会造成信号的失真信号的失真。在数据通信中，将会使接受端收。在数据通信中，将会使接受端收到的二进制数位和发送端实际发送的二进制数位不一到的二进制数位和发送端实际发送的二进制数位不一致，从而造

23、成由致，从而造成由“0”变成变成“1”或由或由“1”变成变成“0”的差的差错。错。北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.3 差错控制差错控制与语音、图像传输不同，计算机通信要求极低的差与语音、图像传输不同，计算机通信要求极低的差错率。错率。产生差错的原因：产生差错的原因： 信号衰减和热噪声信号衰减和热噪声 信道的电气特性引起信号幅度、频率、相位的信道的电气特性引起信号幅度、频率、相位的畸变；畸变； 信号反射，串扰；信号反射，串扰； 冲击噪声，闪电、大功率电机的启停等。冲击噪声，闪电、大功率电机的启停等。北京化工大学北方学院信息院北京化工大学北方学院信息院 htt

24、p:/5.3.1 5.3.1 基本概念基本概念什么是差错？什么是差错？q在通信中接收端收到的二进制数位（码元）在通信中接收端收到的二进制数位（码元）和发送端实际发送的数据不一致。和发送端实际发送的数据不一致。差错检测：判断数据经传输后是否有错的手段和差错检测：判断数据经传输后是否有错的手段和方法。方法。差错控制：确保传输数据正确的方法和手段。差错控制：确保传输数据正确的方法和手段。北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/ 在数据通信中，最常用的差错控制方法是在数据在数据通信中，最常用的差错控制方法是在数据中加入差错控制编码。中加入差错控制编码。我们将要发送的数据称为信

25、息位。在向信道发送信息位我们将要发送的数据称为信息位。在向信道发送信息位之前，先按照某种规则加上一定的冗余位（称为差错控之前，先按照某种规则加上一定的冗余位（称为差错控制编码过程），构成一个码字再发送。制编码过程），构成一个码字再发送。接收端收到码字后查看信息位和冗余位，并检查他们之接收端收到码字后查看信息位和冗余位，并检查他们之间的关系是否正确，即进行校验，以确定传输过程中是间的关系是否正确，即进行校验，以确定传输过程中是否有差错发生。否有差错发生。 差错控制方法通常有差错控制方法通常有自动请求重发自动请求重发技术、技术、 前向纠前向纠错错技术。技术。5.3.1 5.3.1 基本概念基本概念

26、北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/5.3.2 差错控制方法差错控制方法差错控制方法：差错控制方法：ARQARQ和和FECFECq自动请求重发自动请求重发ARQARQ：Automatic Request for Automatic Request for RepeatRepeatq接收方检测错误，通知发送方重传接收方检测错误，通知发送方重传q双向信道，发送方缓存发送的数据双向信道，发送方缓存发送的数据q前向纠错前向纠错FECFEC：Forward Error CorrectionForward Error Correctionq接收方不仅可以检测错误，而且知道错误

27、的位置，接收方不仅可以检测错误，而且知道错误的位置，从而改正错误从而改正错误q采用纠错码，无需反向信道，无需重发，但编码采用纠错码，无需反向信道，无需重发，但编码效率低效率低, ,纠错设备复杂纠错设备复杂北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/噪声噪声信源信源发送器发送器信道信道接收器接收器信宿信宿 发送端信源送出信息序列，一方面经检错码编码器编码由发送机送入信息，另一方面把它存入存储器以备重传。接收端经检错码译码接收端经检错码译码器对接收到的数据进行器对接收到的数据进行译码，判断是否有错。译码，判断是否有错。如无错，则给出无错信号，如无错，则给出无错信号，经反馈信道

28、送至发送端，同经反馈信道送至发送端，同时通知信宿接收译码后的信时通知信宿接收译码后的信息序列。息序列。如有错，则给出有错信号，如有错，则给出有错信号，经反馈控制器通知信宿拒收经反馈控制器通知信宿拒收信息，并通过反馈信道送至信息，并通过反馈信道送至发送端发送端发送端的判定信号检发送端的判定信号检测器检测后，控制信测器检测后，控制信源暂时停发新信息，源暂时停发新信息，并打开存储器将传输并打开存储器将传输中出错的信息重发一中出错的信息重发一遍遍(1)(1)自动请求重发自动请求重发ARQARQ北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/停等式停等式ARQ：发送后等待应答，然后发送

29、下一个帧；：发送后等待应答，然后发送下一个帧；回退回退N帧帧ARQ：接收到应答后，从出错的地方开始重新发：接收到应答后，从出错的地方开始重新发送以后的数据；送以后的数据；选择性重传选择性重传ARQ：接收到错误的帧的应答时，只需要重新：接收到错误的帧的应答时，只需要重新发送错误的帧。发送错误的帧。(1)(1)自动请求重发自动请求重发ARQARQ北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/(2)(2)前向纠错技术前向纠错技术FECFEC 前向纠错是发送端发送能够纠错的数据，接收端收前向纠错是发送端发送能够纠错的数据，接收端收到这些数据以后，通过错码译码器不仅能自动发现到这些数

30、据以后，通过错码译码器不仅能自动发现错误，并且能自动纠正传输中的错误，然后再把已错误，并且能自动纠正传输中的错误，然后再把已纠正的数据送给接收者。纠正的数据送给接收者。北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/ 由差错控制的上述两种方法引出来两种不同的差错由差错控制的上述两种方法引出来两种不同的差错控制编码：控制编码：检错码检错码和和纠错码纠错码。 其中，其中， 检错码检错码是能够自动发现错误的编码；是能够自动发现错误的编码； 纠错码纠错码是既能发现错误，又能自动纠正错误的编码。是既能发现错误，又能自动纠正错误的编码。 5.3.3 差错控制编码差错控制编码北京化工大学北

31、方学院信息院北京化工大学北方学院信息院 http:/常用检错码：常用检错码： （1）奇偶校验）奇偶校验（Parity Checking） 在原始数据字节的最高位增加一个奇偶校验位，使在原始数据字节的最高位增加一个奇偶校验位，使结果中结果中1的个数为奇数的个数为奇数(奇校验奇校验)或偶数或偶数(偶校验偶校验)。 例如例如1100010增加偶校验位后为增加偶校验位后为11100010 若接收方收到的字节奇偶校验结果与规则结果不符，若接收方收到的字节奇偶校验结果与规则结果不符，就知道传输中发生了错误。就知道传输中发生了错误。 只能用于面向字符的通信协议中。只能用于面向字符的通信协议中。5.3.3 差

32、错控制编码差错控制编码北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/实际数据传输中所采用的奇偶校验码分为：实际数据传输中所采用的奇偶校验码分为：垂直奇偶校验垂直奇偶校验水平奇偶校验水平奇偶校验水平垂直奇偶校验水平垂直奇偶校验5.3.3 差错控制编码差错控制编码北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/l垂直奇偶校验垂直奇偶校验是一字符为单是一字符为单位的校验方法。例如，传输数位的校验方法。例如，传输数据信息为据信息为“1010001”，采用偶，采用偶校验时，附加位为校验时，附加位为“1”，则发，则发送信息变为送信息变为“11010001”；采；采用奇

33、校验时，附加位为用奇校验时，附加位为“0”，发送信息变为发送信息变为“01010001”； I11 I12 贩 I1q I21 I22 贩 I2q2 Ip1 Ip2 贩 Ipq 贩 贩 贩 r1 r2 贩 rq 冗余位冗余位 信息位 发送顺序发送顺序 垂直奇偶校验 1ppR 编码效率：编码效率：5.3.3 差错控制编码差错控制编码北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/ 水平奇偶校验水平奇偶校验是将是将若干字符组成一个若干字符组成一个信息块，对该信息信息块，对该信息块的字符中对应的块的字符中对应的位分别进行奇偶校位分别进行奇偶校验，下表给出了水验，下表给出了水平奇偶校

34、验示例。平奇偶校验示例。编码效率：编码效率：1qqR5.3.3 差错控制编码差错控制编码北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/l水平垂直奇偶校验水平垂直奇偶校验是是把水平和垂直两个方向把水平和垂直两个方向的奇偶校验结合起来构的奇偶校验结合起来构成的，即纵向每个字符成的，即纵向每个字符校验一次，水平方向每校验一次，水平方向每个信息块发送完后其对个信息块发送完后其对应位也校验一次（发送应位也校验一次（发送一个校验码）。一个校验码）。 编码效率编码效率) 1)(1(qppqR10001010字符字符1b1b2b3b4b5b6b7check11001011字符字符21101

35、1010字符字符310101011字符字符410001010字符字符510001010字符字符611101010字符字符700100001校验校验字符字符5.3.3 差错控制编码差错控制编码北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/（2）循环冗余校验）循环冗余校验 (CRC, Cyclic Redundancy Check) 差错检测原理：差错检测原理：将传输的位串看成系数为将传输的位串看成系数为0或或1的多项式。收发双的多项式。收发双方约定一个生成多项式方约定一个生成多项式G(x)，发送方在帧的末尾，发送方在帧的末尾加上加上校验和校验和，使带校验和的帧的多项式能被，使

36、带校验和的帧的多项式能被G(x)整除。接收方收到后，用整除。接收方收到后，用G(x)除多项式，若有余除多项式，若有余数，则传输有错。数，则传输有错。 校验和是校验和是16位或位或32位的位串。位的位串。 CRC校验的关键是如何计算校验和。校验的关键是如何计算校验和。5.3.3 差错控制编码差错控制编码北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/将要发送的二进制数序列看成是只有将要发送的二进制数序列看成是只有0 0和和1 1两个系数的一个多两个系数的一个多项式。项式。n n位的数据序列对应位的数据序列对应n-1n-1次多项式。如：二进制数序次多项式。如：二进制数序列为列为“

37、10100011010001”，7 7位的数据序列对应位的数据序列对应6 6次多项式：次多项式：M(x)=xM(x)=x6 6+x+x4 4+1+1 选定除式选定除式G(x)G(x)，被选作除式的多项式称为生成多项式，以下，被选作除式的多项式称为生成多项式，以下三个多项式已成为国际标准三个多项式已成为国际标准 CRC-12CRC-12： G(x)=xG(x)=x1212 +x +x1111 +x +x3 3 + x + x2 2 + x + 1 + x + 1 CRC-16CRC-16： G(x)=xG(x)=x1616 +x +x1515 + x + x2 2 + 1 + 1 CRC-CCI

38、TTCRC-CCITT： G(x)=xG(x)=x1616 +x +x1212 + x + x5 5 + 1 + 1 CRC-32 CRC-32 G（x）= x32+x26+x23+x22+x16+x12+x11+ x10 +x8+x7+x5+x4 + x2+x+1北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/将将M(x)M(x)乘以乘以 G(x)G(x)的最高幂次作为被除式，的最高幂次作为被除式， G(x)G(x)作多项式除作多项式除式式X Xr rM(x)=G(x)M(x)=G(x)* *商商+R(x)+R(x)（相应系数相除）（相应系数相除） 。除法采用。除法采用“加

39、法不进位，减法不借位加法不进位，减法不借位”的规则，即相当于异或操作的规则，即相当于异或操作R(x)R(x)作为冗余码，加在原传送数据后面作为冗余码，加在原传送数据后面: : T(x)= X T(x)= Xr rM(x) +R(x)= G(x) M(x) +R(x)= G(x) * *商商+R(x) +R(x) + R(x)R(x)，构成发送，构成发送序列。序列。接收方收到后，将接收序列用同样的生成多项式去除接收方收到后，将接收序列用同样的生成多项式去除 即即T(x)/G(x)T(x)/G(x)。若余式为零，则表示无差错；否则，说。若余式为零，则表示无差错；否则，说明传输过程中出现了错误。明传

40、输过程中出现了错误。01100001 1101001010110011 01100001 1101001010110011 北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/要发送的二进制数序列为要发送的二进制数序列为“10100011010001”，7 7位的数据位的数据序列对应序列对应6 6次多项式：次多项式： M(x)=xM(x)=x6 6+x+x4 4+1+1 选定的生成多项式为：选定的生成多项式为： G(x)=xG(x)=x4 4 +x +x2 2 +x+ 1 +x+ 1 （最高次数为（最高次数为4 4，相当于，相当于1011110111）被除多项式为：被除多项式为：

41、 M(x)xM(x)x4 4 x x1010+x+x8 8+x+x4 4 （相当于（相当于1010001101000100000000）北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/多项式除法后得到冗余码为多项式除法后得到冗余码为11011101，所以相应的数据发送，所以相应的数据发送序列为序列为1010001 11011101101000100000000101111011111011111010 0 001111110101011110111110101011110111101111011111010101111011111011101例例1.1.已知：已知：信息码信息

42、码MM：110011 110011 信息多项式：信息多项式：M(X)=XM(X)=X5 5+X+X4 4+X+1+X+1生成码生成码P P：1101 1101 生成多项式：生成多项式：P(X)=XP(X)=X3 3+X+X2 2+1 (n=3)+1 (n=3)求：冗余码和码字。求：冗余码和码字。 解：解：1 1）被除数是信息码）被除数是信息码M M 后添加后添加n=3n=3个个0 0，即，即110011000110011000。2 2）除数是）除数是P P即即11011101。3 3）用模）用模2 2运算。由计算结果知冗余码是运算。由计算结果知冗余码是001001，码，码字就是字就是11001

43、1001110011001。北京化工大学北方学院信息院北京化工大学北方学院信息院 .1检错编码检错编码接收端接收端：在在接收端把收到的数据以帧为单位进行接收端把收到的数据以帧为单位进行CRCCRC检验检验。用。用CRCCRC进行差错检验的过程很简单：接进行差错检验的过程很简单：接收方用收方用G(x)G(x)去除接收到得去除接收到得k+nk+n位比特。如果余数为位比特。如果余数为0 0，则认为正确而被收下得到信息码；如果余数为非则认为正确而被收下得到信息码；如果余数为非0 0，则接收方认为发生错误，就丢弃该帧，请求对方重则接收方认为发生错误，就丢弃该帧，请求对方重发。

44、发。.1检错编码检错编码例例2 2已知：接收码字已知：接收码字:1100111001:1100111001 多项式多项式:T(X)=X:T(X)=X9 9+X+X8 8+X+X5 5+X+X4 4+X+X3 3+1+1 生成码生成码P:P:1100111001 生成多项式生成多项式:P(X)=X:P(X)=X4 4+X+X3 3+1(n=4)+1(n=4)求：码字的正确性。若正确，则指出冗余码和信息码。求：码字的正确性。若正确，则指出冗余码和信息码。解：解：1)1)用码字除以生成码，用码字除以生成码，余数为余数为0 0，如图，如图5.65.6所示，所所示，所以码字正确。以码字正

45、确。 2)2)因因n=4n=4，所以冗余码是：，所以冗余码是：10011001，信息码是，信息码是:110011:110011北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/ 纠错码与检错码相比其功能更强，它不但能检错纠错码与检错码相比其功能更强，它不但能检错还能纠错。还能纠错。汉明码汉明码就是一种能够纠正一位错误的就是一种能够纠正一位错误的纠错码。汉明码是海明纠错码。汉明码是海明(H.W.Hamming)于于1950年年提出的一种码制。在发送数据之前将数据按照汉提出的一种码制。在发送数据之前将数据按照汉明码制形成汉明码，然后发送汉明码，到达对方明码制形成汉明码，然后发送汉明

46、码，到达对方后根据接收到的汉明码进行解释分析、判错、纠后根据接收到的汉明码进行解释分析、判错、纠错。错。(3)(3)常用纠错码：常用纠错码： 汉明码汉明码5.3.3 差错控制编码差错控制编码北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/汉明码的组合规则汉明码的组合规则 汉明码是由数据与校验位组合而成的。其组汉明码是由数据与校验位组合而成的。其组合规则为：将数据与校验码（奇偶校验）自左合规则为：将数据与校验码（奇偶校验）自左至右进行编码，其中编号为至右进行编码，其中编号为2的幂的位均为校的幂的位均为校验位，其余为数据位。验位，其余为数据位。 5.3.3 差错控制编码差错控制编

47、码(3)(3)常用纠错码：常用纠错码： 汉明码汉明码北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/(1)(1)汉明码算法汉明码算法将码字数内的位从最左边开始按顺序依次编号将码字数内的位从最左边开始按顺序依次编号, ,第第1 1位是位是1 1号号, ,第第2 2位是位是2 2号号, , 第第n n位是位是n n号号. .编号为编号为2 2的幂的位的幂的位(1(1号号位位,2,2号位号位,4,4号位号位,8,8号位等号位等) )是校验位是校验位, ,其余的位填入其余的位填入m m 位位数据。数据。每个校验位的取值应使得包括自己在内的一些位的集合符每个校验位的取值应使得包括自己在

48、内的一些位的集合符合规定的奇偶性合规定的奇偶性.(.(主要用于奇偶性校验主要用于奇偶性校验) )1 2 3 4 5 6 7 8 9 10 11 12校验位校验位5.3.3 差错控制编码差错控制编码北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/(1)(1)汉明码算法汉明码算法为了知道编号为为了知道编号为K K的数据位对哪些检测位有影响的数据位对哪些检测位有影响, ,将将编号编号K K 改写成改写成2 2的幂的和的幂的和( (如如:11=1+2+8, :11=1+2+8, 29=1+4+8+1629=1+4+8+16),1),1个位只由扩展式中所示编号的位检个位只由扩展式中所示

49、编号的位检测测( (编号为编号为1111的位的位, ,只能由只能由1,2,8 1,2,8 检测位检测检测位检测) )由于在每个校验位的形成表达式中由于在每个校验位的形成表达式中, ,除自身编号外除自身编号外, ,其余都是信息位的编号其余都是信息位的编号, ,因此只要信息位是确定的因此只要信息位是确定的, ,校验位也可以唯一地确定校验位也可以唯一地确定. .5.3.3 差错控制编码差错控制编码北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/例例: :根据海明编码方法根据海明编码方法, ,对对ASCIIASCII字符字符Z(Z(二进制编码是二进制编码是1011010),10110

50、10),形成形成1111位码字位码字, ,要求简单地写出编码过程要求简单地写出编码过程. .并说明在传输过程中并说明在传输过程中, ,有一位错的情况下有一位错的情况下, ,如何能够检查出是哪一位是错的如何能够检查出是哪一位是错的? ?解解: m=7,n =11,r =4 编号编号: 1=1,2=2,3=1+2,4=4,5=1+4,6=2+4,7=1+2+4,8=8,9=1+8, 10=2+8,11=1+2+8 于是有于是有: (1) (3)+(5)+(7)+(9)+(11) (2) (3)+(6)+(7)+(10)+(11) (4) (5)+(6)+(7) (8) (9)+(10)+(11)被

51、检测位：数被检测位：数据位据位检测位检测位5.3.3 差错控制编码差错控制编码北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/1 2 3 4 5 6 7 8 9 10 11 0 0 1 0 0 1 1 1 0 1 0 编码编码码字码字最终的最终的汉明码汉明码为什么此为什么此处是处是1?1,2,4,8是校验位是校验位!其余位是信息位其余位是信息位. (9)(10)(11) (1) (3)(5)(7)(9)(11) 1 0 1 0 0 1 0 1 0 0奇数个奇数个1偶数个偶数个1采用偶采用偶检验哦检验哦!5.3.3 差错控制编码差错控制编码检验位的定位检验位的定位 将将4 4个

52、四个分别编号为个四个分别编号为R R1 1, R, R2 2, R, R3 3, R, R4 4 按海明码的编码规则，这按海明码的编码规则，这4 4个冗余位应分别插到数个冗余位应分别插到数据单元的据单元的2 20 0, 2, 21 1, 2, 22 2, 2, 23 3位置上，即位置上，即R R 1 1, R, R2 2, R, R3 3, R, R4 4将被将被分别插入到数据单元的分别插入到数据单元的D D1 1，D D2 2，D D4 4，D D8 8的位置上。的位置上。各冗余位在各冗余位在11 11位海明码中的位置位海明码中的位置 1 (20) 2(21) 3 4(22) 5 6 7 8

53、(23) 9 10 11 R1R2dR3dddR4ddd各检验位取值的计算各检验位取值的计算 海明码的每个检验位的值都是一组数据的奇偶校验海明码的每个检验位的值都是一组数据的奇偶校验位。位。检验比特位检验比特位R R 1 1, R, R2 2, R, R3 3, R, R4 4分别是分别是4 4组不同数据位的奇组不同数据位的奇偶校验位，偶校验位，采用二进制数据来表示海明码采用二进制数据来表示海明码11 11个数据位数个数据位数 有有00010001；00100010；00110011；01000100；01010101；01100110；01110111；10001000；10011001；1

54、0101010，10111011这这11 11种情况种情况对这对这11 11种情况中位数最低位为种情况中位数最低位为1 1的位置进行偶校验，的位置进行偶校验，即对即对00010001；00110011；01010101；01110111；10011001，10111011这这6 6个数个数据位做偶校验，得到的偶校验码为据位做偶校验，得到的偶校验码为R R 1 1的值的值即即R R 1 1为对从低位数起的第为对从低位数起的第1 1、3 3、5 5、7 7、9 9、1111这这6 6位作偶位作偶校验而得到的校验位。校验而得到的校验位。对这对这11 11种情况中位数的次低位为种情况中位数的次低位为1

55、 1、即倒数第、即倒数第2 2位为位为1 1的位进行偶校验，的位进行偶校验，即对即对00100010；00110011；01100110；01110111；0101001010；10111011（第（第2 2、3 3、6 6、7 7、1010、11 11）这）这6 6个数据位做偶校验，得到个数据位做偶校验，得到的偶校验校验位的值为的偶校验校验位的值为R R 2 2的值的值依此类推依此类推对这对这11 11种情况中倒数第种情况中倒数第3 3位为位为1 1（01000100；01010101；01100110；01110111）的位置，即第）的位置，即第4 4、5 5、6 6、7 7这这4 4位做

56、偶位做偶校验，得到的偶校验码为校验，得到的偶校验码为R R 3 3的值的值R R4 4是对倒数第是对倒数第4 4位为位为1 1的位置，即第的位置，即第8 8、9 9、1010、11 11 （10001000；10011001；10101010；10111011）这）这4 4位作偶校验得到的校验位作偶校验得到的校验位的值位的值示例示例1 1：数据：数据10011011001101变成海明码的编码过程变成海明码的编码过程 1 2 3 4 5 6 7 8 9 10 111 2 3 4 5 6 7 8 9 10 11在从低位数起的第1、3、5、7、9、11这6位作偶校验而得到的校验位R 1是0。在从低

57、位数起的第2、3、6、7、10、11这6位作偶校验而得到的校验位R 2是1。在从低位数起的第4、5、6、7这4位作偶校验而得到的校验位R 3是1。在从低位数起的第8、9、10、11这4位作偶校验而得到的校验位R 4是0。由数据1001101得到的海明码为01110010101R1R21R3001R41010R21R3001R4101011R3001R41010111001R4101011100101010001 0010 0011 0100 0101 0110 0111 1000 1001 1010 10110001 0010 0011 0100 0101 0110 0111 1000 100

58、1 1010 10110001 0010 0011 0100 0101 0110 0111 1000 1001 1010 10110001 0010 0011 0100 0101 0110 0111 1000 1001 1010 10110001 0010 0011 0100 0101 0110 0111 1000 1001 1010 10110001 0010 0011 0100 0101 0110 0111 1000 1001 1010 10110001 0010 0011 0100 0101 0110 0111 1000 1001 1010 10110001 0010 0011 0100

59、 0101 0110 0111 1000 1001 1010 1011北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/(2)(2)汉明码检错与纠错过程汉明码检错与纠错过程 将出错计数器置为将出错计数器置为0 0。 依次对每个校验位进行奇偶校验，如果有错依次对每个校验位进行奇偶校验，如果有错将校验位所对应的编码值加入计数器中。直到将校验位所对应的编码值加入计数器中。直到每个校验位检查完为止。每个校验位检查完为止。 如果出错计数器值为如果出错计数器值为0 0，则数据传输无错。反，则数据传输无错。反之如果计数器值不为之如果计数器值不为0 0，则数据传输有错，且，则数据传输有错，且出

60、错计数器值即为出错数据位的编码。出错计数器值即为出错数据位的编码。 将出错数据位的数据取反即可。将出错数据位的数据取反即可。注意注意: :汉明码只能纠正一位错，若多位出错则无能为力。汉明码只能纠正一位错，若多位出错则无能为力。5.3.3 差错控制编码差错控制编码北京化工大学北方学院信息院北京化工大学北方学院信息院 http:/【例例】 已知数据已知数据“11001100”在发送前，编码后得到的汉明码是在发送前，编码后得到的汉明码是“101110001100”（这里采用偶校验），经信道传输到达接收端后，（这里采用偶校验），经信道传输到达接收端后，设定由于噪声干扰或其它方面的原因，数据被改为设定由