华南理工大学_袁华老师
以下为笔记
保证数据传输的有效和可靠 传输过程不免会发生差错
那么数据链路层就需要做差错检测和控制和流量控制
流量控制有两种方法 基于速率;基于反馈 一般采取基于反馈的方法
在数据链路层经常采取基于反馈的模式,
即 由接收方告诉发送方: 处理能力大小为多少 ; 发送方根据接受方的反馈提供对应流量
数据链路层处理的协议数据单元： 帧 = 帧头(定位需要的物理地址) + 载荷 + 帧尾(校验)
物理层为数据链路层提供服务 物理层: 位流(bits) 数据链路层: 帧(frame)
成帧: 将原始的位流分散到离散的帧中
1.发送方: 在每个帧头部中的第一个字段，标识该帧的长度共有多少字符
2.接收方: 通过第一个字段，就知道这个帧有几个字符，在哪里结束该帧
3.优点: 实现简单
4.缺点: 没有考虑重新同步问题，一旦出错，无法恢复，工程中极少使用
考虑了重新同步问题，每一帧采用一个特殊字节做帧界，即当前帧的开始与上一个帧的结束
将这个特殊字节称为标志/标记字节（flag byte）存在问题
当传输数据中也存在标志字节时,会和真正的帧界混淆
解决方案
标记字节法 当数据中存在标记字节时,在数据的标记前添加转义字符
特点
用于PPP协议(点对点协议)
缺点
1.数据中存在帧界或转义符时会造成帧界混淆,大量的标志字节或转义字符会造成低效率的成帧（最坏情况50%）。
2. 任意比特数的帧不适用,必须是8位整数倍
任意比特数的帧怎么解决? 改进: 比特填充的比特标记法
这是一种面向二进制位的帧格式，把所有需传输的数据以比特位一字排开，并以特殊的位模式01111110作为帧标志，即一个帧的开始（这也意味着标志前一个帧的结束）
当帧内容出现与帧标志相同位串01111110时:
在5个1后插入一个0，即变成01111101，接收方将自动删除第5 个1后的0,恢复原来的数据 这称为位填充法（零比特填充法）,也称为透明传输。
当扫描过程中出现错误导致部分帧没有被正确接收:
接收方会继续扫描直到读取到下一个帧标志,开始重写转换同步数据
优点
可以传输任意比特数的帧,同时传输效率更高
将冗余信号用作帧界
例如: 在4B/5B编码模式中，将4比特映射到5比特上，能够承载32位却只利用了16位，剩下的位就可以用作帧界
又如: 在以太网中大量使用的曼彻斯特编码中
[规定1用高电位跳变到低电位表示,0用低电位跳变到高电位表示]没有利用 高电平到高电平 和 低电平到低电平 这两个冗余的跳变没有使用 可以用作帧界
优点
利用的是冗余信号,不会混淆,也不会填充,传输效率较高
数据链路层位于物理层之上、网络层之下
数据链路层提供有效的、可靠的帧传输
成帧方法
字符计数法
字节填充的标志字节法
比特填充的比特标记法
物理层编码违例法
纠错: 恢复出正确的数据
检错: 仅仅检出错误，不恢复，通常伴随重传
单个错误: 分散在各个数据块中
突发错误: 集中于一个数据块，整个数据块都是错误
突发错误比单个错误更难处理
发现错误,从错误中恢复出正确的来。
由于纠错码需要纠错,这个过程中需要太多的冗余位,所以开销较大。
在有线网络中极少使用,主要应用于无线网络中
只能发现错误,不能从错误中恢复,但可采用重传恢复
主要应用于局域网
几个差错处理相关的概念
海明距离: 包含数据位和校验位的n位单元（模式）
与码字相关的是海明距离
海明距离: 两个码字的海明距离指，两个码字间不同位的数目
例如:
10001001与10110001的海明距离就是3 从第三位开始不同 共3个不同数字
也可以两者进行异或运算
异或结果 00111000 1的个数即海明距离
指在全部码字中任意两个码字间海明距离的最小值
如果海明距离为d,则一个码字要变成另一个码字,至少需要跳变d位（发生d个一位错误）才能实现。
海明距离越大,纠错能力越强
但是,当一个系统中的海明距离增加的时候,合法码字就减少了; 即传输效率降低！
海明距离为2d+1的编码能检测出d位的差错
奇偶校验码: 一个校验位可以追加到传输数据中,分为奇校验和偶校验
它的海明距离为2,能检验出1位错误
校验位的值是0还是1取决于数据中1的个数
举例:
Data:10111000 数据中1的个数为4个
偶校验:加入校验码后1为偶数个 后面补0 101110000
奇校验:加入校验码后1为奇数个 后面补1 101110001
Data:100011 数据中1的个数为3个 偶校验:后面补1 1000111 奇校验:后面补0 1000110
如果1个比特发生跳变错误 可以检测出来
如果2个比特发生跳变错误,接受方无法检测出错误,认为码字正确
举例:
一个系统要传输的原始码字:00,01,10,11 。 经过偶校验,编码后变为000,011,101,110
发送方发送00 接收方收到011,就会判定为非法码字,出错
而接受方收到000,就会判定为合法码字,正确 但不一定是发送方发送的00,有可能发送方发送11经过偶校验后码字为110,但是经过2次跳变 变成11→00
成为了合法码字
接收方无法成功检错,无法通过奇偶校验处理2次及以上跳变
要传输的数据是m位，冗余位r应该是多少，才能纠正1位错来呢？
设一个系统中，编码后的码字位数是n，则n=m+r。因为要传输的数据位是m位，该系统需要传输的正确的码字个数(合法码字个数)应该是2^m ,
全部码字的个数是2^n，而n位码字每一位都可能发生跳变，且跳变之后不能变成另一个正确的码字，所以每个码字至少需要n+1个码字来表示它(别忘了还有它本身)
则有公式: (n+1)2^m <= 2^n , n = m+r → (m+r+1) <= 2^r
根据这个公式,可以计算出传输m位数据,至少需要的冗余位数r
eg : 传输m = 5位,需要的冗余位 r = 4
海明纠错码1950年提出:
每一个码字(包括 传输位和冗余位)从左到右编号，最左边为第1位....n位 校验位: 凡是编号为2的乘幂的位
第1,2,4,8,16……为校验位，其它3,5,6,7,9,11....为数据位(直接传进去)
而校验位可以设置。依据为包括自身在内的一些位的集合的奇偶值(偶校验/奇校验)
如何决定每个数据位的校验位呢？ 将某一位数据位的编号展开成2的乘幂的和,那么每一项所对应的位即为该数据位的校验位(收方使用) 反过来,校验位的校验集合也包含这个数据位。
编号11 = 1+2+8 编号29 = 1+4+8+16
校验位1的校验集合为所有奇数位,校验位2的校验集合: 2,3,6,7,10,11,...(展开都包含2)
eg: 传输数据m=7,(m+r+1) <= 2^r → 冗余位r=4
n=7+4=11 每一位传输的数据的编号都展开成校验位的集合
发方进行编码
待传输的数据1001000 m=7 计算公式: (m+r+1) <= 2^r
计算出结果r=4 编码后的位数 n=7+4=11 采用偶校验海明纠1位错编码
将数据填入3,5,6,7,9,10,11(传输数据位)
1,校验位1的校验集合为所有奇数位 3 5 7 9 11 10100 1的个数是2个 所以编号1只能填0
校验位2的校验集合: 2,3,6,7,10,11 10100 1的个数是2个 所以编号2也只能填0
校验位4的校验集合 4,5,6,7 对应的值是001 1的个数是1个 所以编号4填1
校验位8的校验集合 8,9,10,11 对应的值是000 1的个数是0个 所以编号8填0 则发送方得到编码后的码字0011 0010 000
接受方如何纠错
将差错计数器置为0 Counter = 0 当码字到达接收端的时候 接收端逐个检查校验位的奇偶性 如果发现某一个校验位和他检查集合的奇偶性不正确,就将该校验位的编号加到差错计数器Counter;最后所有的校验位都检查完成之后,检查计数器Counter的值 Counter=0,无差错 Counter≠0,出错 Counter的值是多少就是哪一位出错(累加出错)
纠1位错的海明码可以纠正突发错误:
eg: 连续K个码字按行排列成矩阵;发送数据时按列发送,每列K位
能够纠正的突发错误的个数小于等于发送矩阵的行数K
纠错码需要较多的冗余位 信道的利用率不高。
在出错率不高更关注传输效率的局域网内，主要采用检错码
有:奇偶校验码（海明距离为2 检1位错） 互联网校验和 循环冗余校验码
奇偶位取值等同于对数据位进行模2和运算
eg: 采用偶校验: 发方1110000 → 11100001
1. 11100101: 5个1,奇数个,检出错
2. 11011001 5个1,奇数个,检出错
3. 11101101 6个1,偶数个,不能检出错误,判定为正确 正确判断概率50%
循环冗余检错码CRC
检错码CPC工作原理: 任何一个k位的帧看成为一个k-1次的多项式
例如: M(x)：1011001 看成 x^6+x^4+x^3+1（k项k-1阶多项式 6阶7项多项式）
设定一个多项式编码生成多项式G(x)，G(x)为r阶，G(x)任意， r为冗余位
设置一个m为帧的多项式 m>r，M(x) > G(x)
计算x^rM(x)/G(x) = Q(x)+R(x)，其中Q(x)为商、R(x)为余数
这样(x^rM(x)-R(x))一定能被G(x)整除，即余数为0，否则说明出现错误
(发方) (x^rM(x)-R(x)) / G(x) = Q(x)
(收方) R(x) / G(x) 的余数 = 0 , 传输无误 不为0,传输发生错误
举一个十进制类比的例子 前提条件：被“3”整除
发送方: 23/3=7余2 23-2=21 ∴发送21,如果被“3”整除则证明无误 发送编码为21 如果是22/3=7余1就出错
局限: 发送编码为21,发送途中变成24,收方收到24,也能被“3”整除,不能证明无误
校验和
进行模2加运算 什么是模2运算,模2运算等同于异或运算
模2加以及模2减 即相同得0，不同得1 如:
0+0=0，0+1=1，0-1=1，0-0=0
采用循环冗余校验码CRC的系统,需要约定一个生成多项式(除数)
样例： 1101011011 （m=10） 给出M(x) , G(x)
M(x) = x^9+x^8+x^6+x^4+x^3+x+1
G(x) = x^4+x+1 （r=4 4阶）
T(x) = x^4M(x)= x^4(x^9+x^8+x^6+x^4+x^3+x+1) =
x^13+x^12+x^10+x^8+x^7+x^5+x^4 (相当于在原码后面补r个0)
帧：1101011011
移位后: 11010110110000
除数：10011（也就是G(x)） 11010110110000/10011余1110
余数: R(x) = 1110
传输帧：11010110111110（帧数据后面先添加4个0(r是4阶) + 余数1110）
11010110110000-1110 = 11010110111110
∴编码后的码字：CRC码为 11010110111110
当这个码字到达接收方时，如CRC码在接收端能被10011整除则说明接收正确，如果不能被整除，则被检测到已出错
生成多项式国际标准
CRC-12 x^12+x^11+x^3+x^2+x+1 用于字符长度为6位
CRC-16 x^16+x^15+x^2+1 用于字符长度为8位
CRC_CCITT x^16+x^12+x^5+1 用于字符长度为8位
CRC32 ：x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^10+x^8+x^7+x^5+x^4+x^3+x+1
CRC32 用在以太网计算循环冗余校验码
发出去的码字
检验位
检验位: 追加到报文尾部 常见： 16位互联网校验和
发送方: 码字就是被除数减去模2除法的余数
接收方: 判定余数是否为0,为0则无错误;不为0则有错误
