3.1基本概念 第3章 连路:一条无源的点到点的物理线路段 数据链路层 数据链路:链路+规程(控制数据传输) 数据链路层的作用 通过一些数据链路层协议(即链路控制规程) 在不太可靠的物理链路上实现可靠的数据传输 数据链路层的主要功能 为网络层提供的服务 ①链路管理:数据链路的建立、維持和释放; ②帧同步:收方能从收到的比特流中区分一帧开始和 ①无确认的无连接的服务 结束的地方 适用于误码率很低的通信信道;或语音通信; ③差错控制:收方收到有差错的数据帧时,能检错重 传或纠错; ②有确认的无连接的服务 ④流量控制:发方发送數据的速率必须使收方来得及 用于误码率很高的通信信道;如无线通信 ⑤透明传输:不管所传数据是什么样的比特组合,收 方都能正确接收。并能将数据与控制信息分开; ③有确认的面向连接的服务 ⑥寻址:保诬每一帧都能发送到目的站 适用于通信要求较高(可靠性、实时性)的情况 差错检测和纠正 差错评价指标 差错:接收的与发送的数据不一致 误码率:错传的码元数与所传输码元总数之比 随机差错:具有独立性,与前后码元无关 Pe= Ne/N 突发差错:相邻多个数据位出错 其中,N一传输的码元总数,Ne-错传的的码元数 差错产生的原因 误比特率: 通信信道的噪声 错传的比特数与所传输总比特数之比 ①热噪声:由传输介质导体的电子热运动产生。幅 在二进制码元时,误比特率=误码率 度较小,是产生随机差错的主要根源 ②冲击噪声:由外界电磁干扰产生,幅度较大 是产生突发差错的主要根源 普通电话线路:Pe=104~-1 冲击噪声是引起差错的主要原因 大多数通信系统:Pe=105~10°
1
差错控制的基本方式 误码控制基本原理 ①反馈纠错 为了能判断传送的信息数据是否有误,在传送 时增加必要的附加判断数据;在不发生误码的情况 在接收端能发现差镨,但不能确定错爲的位置,通过反 之下,附加判断数据是完全多余的,但如果发生 馈信息请求发送端重发,直到接收端肯定确认为止 适用于双工通信和非实时通信系统 来实现检错和纠错 ②前向纠错 即,为了使数据码具有检错和纠错能力,应当 在接收端不仅能发现错码,而且还能够确定错鸸的位 按一定的规则在数据码的基础上增加一些冗余码(又 置,并纠正错码。 称监督码) 适用于单工通信和实时通信系 ③混合纠错 码}编码 据码 少量差错在接收端自动纠正,若超出自行纠正能力 生成蔹醬码冗余码 通过反馈信息请求发送端重发 信息帻 码字的检错与纠错能力 码字编码的海明距离 对于一种码字編码,在这个码字集合中,可得到 码字(n位)-数据码(m位)冗余码(r位 所有任意两个码字的海明距离,其中最小的海明距离 海明距离:两个码字之间对应码元位的不同码元 称为该码字编码的海明距离d 的个数 定理1:如果d>2t+1,则該编码可纠正任何t个(或t个以 0001001 定理2: 1,则该编码可检测出任何e个(或e个 10100011 00101010 有3位不同。所以,海明距离 一般情况下,冗余位越多(即r越大),检错纠错 能力越强,但相应的编码效率也随之降低了 示例:偶校验的检错与纠错能力 误码控制编码的分类 例:对于偶校验(使每个码字中都有偶数个1) 按冗余码的控制功能分: 数据码为2位(有用数据为00、01、10、11) ①纠错码:在接收端能发现并自动纠正差错 冗余码为1位(偶校验位) ②检错码:在接收端能发现差错 有用数据经过偶校验編码,其码字集合 0、0ll、10l、110; 该编码的海明距离d=2, 纠错检错的常用方法 海明码:可纠错和检错,实现复杂,效率低 根据定理1,该编码不能纠正任何错误 艮据定理2,该編码可检测出任何1个错 ②奇偶校验码:方法简单,检错能力差 循环冗余编码(CRC):实现容易,检错能力强,广 寄校验的检错能力与偊校验一样
2
纠错码:海明码 确定校验关系 明在1950年提出的可纠正一位错的编码方法 用r个校验位构造出r个校验关系式来指示一位错 凸"豐 码的n(m+r)种可能位置及表示无差错 码字排列:从最左边位开始依次编号(1、2、…n); XXi r个校验位:在2的位置(1、2、4、8、…) m个数据位:在其余位(3、5、6、7、9、…) r的确定:r2-r>m+1;(∵r2>n+1-m+r+1) 发送1P2b3eb6b7 例如:4个信息位D1D2D3D4,3个校验位P1P2P3. P]=b5 6 b6 e b7 采用偶校验 段BB的的 -SIa ebe b56 b7 $2=b26 6 b66 b7 s4=b⊕bs⊕b6⊕b7 校验位 海明示例:接收端 海明示例:发送端 收到的发送码一[010011差错位 增 S2=b2eb3⊕b⊕b7 发送 LOLLLOTOLL CP3-bsab⊕b7 s4=b4ebs⊕b6b7=1 S4S2 SIll≠000, 有差错!差错位是b7(D4) 获取数据:去掉校验位,数据=1011, 海明编码解码一简便法 海明示例:数据=1100001(m=7,r=4) 例:数据 将码字中为1的各 时,, 位码字位号表示为二进制码,再口 按模2求和,所得结果就是校 1_P■P1 P3P2P1= 发送的码字:一龆 即p3p11 收到的码字:一[o00 差错位 解码简便法:将码字中为1的各 接收:口11@oo 位码字位号表示为二进制码 b3=011 按模2求和,若和为0,则无 b6=110 错。若和不为0,则指明差错的S4
3
检错码:循环冗余码一CRC码 例:若数据码=110011 可表示为:M(x)=1x5+1x+0x3+0x2+1x+1 特点:实现容易,检错能力强,广泛使用 即;M(x)=x3+x4+x+1. 常结合反馈重传法来保证信息的可靠传输 生成多项式G(x) 码字组成 G(x)=gx+…+x2+…+gx+ge 发送的码宇【bbb1br;nn1rn 其中,g=0或lr>}>0,g,≠0,gn≠共r+1位 G(x)被通信双方事先共同选定使用 編码与解码的计算采用二进制比特序列多项式。 发送端:通过GAx)生成校验码 二进制比特序列多项式: 接收端:通过G(x)校验接收的码字, M(x)=bmp1+…+bx+…+bx+be 对于多项式的运算:采用模2计算(加法不进 位,减法不借位);加减法是一样的 其中,b=0或1,m-1>>0,共m位 模2计算即是异或运算 在发送端 在接收端 1.生成校验码R(x 把要发送的数据码M(去除G(x,所得的余 接收到(x)-x+R(x)后,按如下操作进行校 数值R(x)就是循环冗余码(简称CRC校验码) H(x)-x Msb2x日 E(x为余数 G(x)R(x为余数(CRC校验码) =0无错 G(x共r+1个bit位, ≠0有错 x)x一R(x) 2.发送M(x)x+R(x 数据码十编 码」数据码 际上,把CRC校验码R(x附加到数据码 的后面,就构成编码多项式M(x)x+R(x),然 CRC示例1:发送端 CRC示例1:接收端一无差错 例:设数据码M(x=110011 接收端:采用生成多项式G()=x+x3+l(即11001) 采用生成多项式G(x)=x2+x3+l(即11001),r=4 发送端:求CRC校验码 M(x)x'+R(xL=o(x) G(x)→11001/1100 若E(Ax 多项式运算采用 1101011 发送码M(x)x"+R(x 发送码:M(x)-x+Rx=1100111001 数据位校验位 0←余数E(x)无差错!
4
CRC示例1:接收端一有差错 CRC示例2:发送端 例:设数据Mx)=1110110,G(x=11001,r=4 发送端发出的码字=1100111001 求CRC校验码R(x 接收端收到的码字=110010001 突发差错 Gay→11017111 ←MAxx 01←收到的码字M(x)-x2+R(x) 11001 发送码 00←余数E(x M(xx+R/x) =111001100110 E(x)≠0,检测到差错 数搪位校验位 0110←余数Rx 流行的生成多项式有: 32停止等待协议 CRC-8 G(x)=xtx +r+ 数据链路协议主要考虑的问题 CRC-12 G/x)=x2+x+x+x2+x+ ①避免所传送的数据可能出现差错和丢 G(x)=x16+x15+x2+l ②使发方发送数据的速率适应收方的接收能力 CRC-CCITT: G(x)=x+x2+x'+I 检测能力: 发送端 接收端 所有单个错、奇数个错和离散的二位错。 所有长度≤r位的突发差错 CRC的实现: 数据链路 ①硬件:采用多段移位寄存器及异或门组成CR 校验电路来实现 ②软件:通过快速CRC校验软件来实现 物理链路 理想化的数据传输 最简单流量控制的停止等待协议 假设1:所传送的数据即不会出现差错和也不会丢 保留假设1:去掉假设2。考虑流量控制问题→流量控制协议 失;(不考虑差错控制问 使发送端发送数据的速率适应接收端的接收能力 假设2:接收端的数据接收速率足够快,有能力 最简单流量控制协议 在发送节点 发送螭接收端 收发送端的数据发送率 (不考虑流量控制问题) 发送端接收端 ①从数裾链路层的发送缓存中取一个数据桢 ②发送这个数据桢 在理想化的条件下,数据链路 ③等待 ④若收到由接收端的应答信息,转到① 在接收节点 ①差错控制协议; ①等待; ②流量控制协议; ②接收由发送端发来的数据桢 就可保证数据的正确传输 ①将其存入数据链路层的接收缓存 ④发送应答信息,表示数据桢已接收;转到①
5