A. 数据链路层--概述，检错和纠错
处理传输错误：差错检测和控制
流量控制：基于速率和基于反馈
将比特变为帧，叫成帧
字符计数法
带字节/字符填充的标志字节法
比特填充的比特标志法
物理层编码违例法
如字符计数法
任何信道，即使是光纤，也会出错。
单个错误：分散在各块中
突发错误：集中在某个块中
注:突发错误比单个错误更加难于处理,通常利用处理单个处理的方法来应对突发错误。
纠错码：发现错误，从错误中恢复出正确的来。因其需要太多的冗余位，纠错开销太大，在有线网络中极少使用，主要用于无线网络中。
检错码：只能发现错误，不能从错误中恢复，但可采用重传
两种不同的处理方局局友法适用于不同的环境
1 码字：包含数据位和校验位的n位单元。
2 海明距离：两个码字的海明距离 : 两个码字之间不同位的数目。如：10001001 和10110001 的海明距离为3。通过异或（相同为0，不同为1）结果中1个个数。
3 全部码字的海明距离:全部码字中任意两个码字之间海明距离的最小值。
4 海明距离的意义在于：如果海明距离为d，则一个码字需要发生d个1位错误才能变成另外一个码字
5 海明距离与检错的关系
海明距离为d+1的编码能检测出d位差错。因为在距离为d+1的检验码中，只改变d位
的值，不可能产生另一个合法码。如奇偶校验码，海明距离为2，能查出单个错。
6 海明距离与检错的关系
海明距离为2d+1的编码，能纠正d位差错。因为此时，如果一个码字有d位发生差
错，它仍然距离原来的码字距离最近，可以直接恢复为该码。
注:
1 海明距离越大，检错和纠错能力越强。但合法码字就减少了，即传输效率降低。
每一个码字从左到右编号，桐槐最左边为第1位
校验位和数据位
凡编号为2的乘幂的位是校验位，如1、2、4、8、16等
其余是数据位，如3、5、6、7、9等
纠错需要较多的冗余位，信道利用率不高。
奇偶校验码（海明距离为2，检1位错）
互联网校验和
循环冗余校验码
一个校验位（Parity Bit）追加到数据后。
校验位的值取“0”还是“1”，取决于整个码字的总的“1”的个数。（奇数还是偶数）。等同于异或运算的结果1个个数。（异或:相同得0，腊卖不同得1）
接收方检查是否存在单个比特的错误
B. 数据链路层的问题之一——差错检测
第一部分 差错、 差错检测（比特错）
概括来说，传输中的差错都是由噪声引起的。
一、原因：
1、全局性
由于线路本身电气特性所产生的随机噪声（热噪声），是信道固有的，随机存在的。
解决办法：提高信噪比来减少或避免干扰。（对传感器下手）
2、局部性
外界特定的短暂原因所造成的冲击噪声，是产生差错的主要原因。
解决办法：通常利用编码技术来解决。
二、轮穗差错
1、位错：比特位出错，1变成0，变成1。
2、帧错（如：[#1]-[#2]-[#3]）
丢失（收到[#1]-[#3]）
重复（收到[#1]-[#2]-[#2]-[#3]）
失序（收到[#1]-[#3]-[#2]）
3、链路层为网络层提供服务
a、无确认无连接服务
通信质量好的有线传输链路
b、有确认无连接服务
c、有确认面向连接服务
第二部分 差错检测（检错编码）
一、奇偶校验码（n-1位信息元，1位校验元）
1、奇校验码
“1”的个数为奇数
2、偶校验码
“1”的个数亮链为偶数
二、循环冗余码CRC
1、例子
发送端：
5（要传的数据）/2（生成多项式）=2......1（FCS帧检验序列/冗余码）
最终发送数据=要传的数据+冗余码5（要传的数据）/2（生成多项式）=2......1（FCS帧检验序列/冗余码）
接收端：
6（接收的数据）/2（生成多项式，同上的）=3......0
余数为0，判定这个帧无错，就接受；反之，判定这个帧有差错（无法确定到位），就丢弃。
2、计算冗余码
a、加0：假设生成多项式G（x）的阶为r，则加r个0；
例如：10011表示成多项式为X4+X1+X0=X4+X1+1，阶为4。（多项式N位，阶为N-1位）
b、模2除法：数据腊键卜加0后除以多项式，余数为冗余码/FCS/CRC检验码的比特序列。
异或：同0异1
3、能够实现无比特差错的传输，但这还不是可靠传输。
C. 数据链路层的差错的检测和恢复(奇偶校验码，CRC校验，校验和)，各种运算
在原始的物理传输线路上传输数据信号是有差错的，存在一定的误码率，数据链路层存在的目的就是给原始二进制位流增加一些控制信息 ，实现如何在有差错的线路上进行无差错传输
数据设定为M位，冗余位设定为R位，如果位数满足即认为不出错，如果位数不满足即肯定出错
差错产生的原因
信道的电气特性引起信号幅度，频率，相位的畸变，信号反射，串扰，闪电，大功率电机的启停等
计算机网络中出现的差错是连续的还是离散的差错？ → 是连续的突发性的差错
比如传了一个这样的位串0001101001，连续的差错：比如一共出错了3位，连续的出错在一起。离散的差错：一共出错了3位，不是连续出的，是分散出的
保证帧正确，按序送交上层（顺序要对，不能重复也不能跳帧）。在接收方能够判断接收的数据是否正确，若错误还可能要恢复错误
纠错控制主要由接收方做，能检查出错并定位到是哪儿出错了
接收方通过反馈机制告诉发送方出错，发送方通过重发的方式恢复差错
☆自动纠错比检错反馈重发机制代价大，在发生数据丢失的情况下，只是自动纠错机制无法进行差错恢复，还是需要检错反馈重发机制
一个帧包括m个数据位，r个校验位（是冗余位，和m位的有效数据是无关的），称为n位码字（n=m+r），我们希望r尽量短，并且尽量有一个固定长度
加入了冗余位，使接收方知道有差错发生，但不知道什么差错，然后请求重发
加入了足够多的冗余位，使接收方不仅知道有差错发生，并知道哪些位发生差错
两个编码的海明距离： 两个编码不相同位的个数
例：0000000000与0000011111的海明距离是5
编码方案的海明距离： 编码方案中任两个编码海明距离的最小值
ASCII这样的连续编码的海明距离都是1
为检测d位错，编码方案的海明距离应至少为d+1
当发生d位错时，不会由一种合法编码变为另一种合法编码，也就是想要由一种合法编码变为另一种合法编码，需要d+1以上出错
对接收方来讲，它判定一个编码是否出错的唯一依据是这个编码是否是一个合法的编码。即使接收方收到了一个合法的编码，它也无法判断是否是一个合法编码，因为它不知道这个合法编码原本就是合法的，还是出错以后也依然是一个合法编码。因此需要海明距离应至少为d+1
在数据链路层一般是不用这种检错方法的，因为检错率太低
若接收方收到的字节奇偶结果不正确，就可以知道传输中发生了错误
增加奇偶校验位后海明距离由1变为2，因此根据“为检测d位错，编码方案的海明距离应至少为d+1”，可以检查出一位二进制位的差错
用这种方法，有一位出错时，就会由合法编码（奇校验时1的个数为奇数，偶校验时1的个数为偶数）变成一种非合法编码（奇数校验时1的个数为偶数，偶校验时1的个数为奇数）
为纠正d位错，编码方案的海明距离应至少为2d+1
当册差发生d位错时，出错编码仍然最接近于原始的正确编码
例：现在有一个编码方案，这个编码方案之中只有4种合法编码↓
0000000000
0000011111
1111100000
1111111111
它们之间的海明距离为5，按衫姿嫌照定理，能够纠正2位错
假设接收方收到了这样的编码：0001100000，很明显这是个非法编码，怎么样纠正
呢？我们知道出错的位数是≤ 2位的，它和第一种的海明距离为2，和第二种为7，和
第三种为3，和第四种为8，离它或手最近的是第一种编码。它采用这种就近恢复的原则将
出错的编码恢复到原始编码
数据链路层用的最多的一种检错方法
但是高层（网络层，传输层）是不用这种检错方法的，而用检验和的方法
生成多项式G（x）
发方，收方事前约定。这里的约定是数据链路层的协议已经定义该协议使用什么生成多项式
生成多项式的高位和低位必须为1
生成多项式必须比传输信息对应的多项式短
（现在最多用的是CRC-32，生成多项式是32位，能否保证生成多项式比传输的对应的多项式短呢？从原始数据来讲保证不了，但是到数据链路层时加了传输层的头，网络层的头之后肯定能保证大于32位。比如现在的Internet网络，例如在传输层使用TCP加20个字节，在网络层IP又加了20个字节，已经超过32位了，所以肯定能保证）
理论上来讲生成多项式的阶越高，检错率越高
硬件实现CRC校验
四个多项式已经成为国际标准
CRC码（增加的r位冗余位检错码，即校验和）加在帧尾（效率比较高），使带CRC码的帧的多项式能被G（x）除尽：接收方接收时，用G（x）去除它，若有余数，则传输出错
• 模2加法运算定义为：（对应于逻辑异或）
0+0=0 0+1=1 1+0=1 1+1=0
例如0101+0011=0110
• 模2减法运算定义为：（对应于逻辑异或）
0-0=0 0-1=1 1-0=1 1-1=0
例如0110-0011=0101
• 模2乘法运算定义为：
0x0=0 0x1=0 1x0=0 1x1=1
• 模2除法运算定义为：
0 ÷1=0 1÷1=1
利用模2减求余数，余数最高位为1，则商1，否则商0，每商1位则余数减少1位，
直到余数位数少于除数位数
按位与运算：
按位与运算符”&”是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位均为1时，结果位才为1，否则为0。参与运算的数以补码方式出现
例如： 9 & 5
00001001（9的二进制补码）
&
00000101 （5的二进制补码）
00000001
可见9 & 5 =1
最高位作为符号位，若符号位为0，则表示正数，若符号位为1，则表示负数
其余各位代表数值本身的绝对值（以二进制表示）
绝对值相同的正数和负数，它们除了符号位不同外，其他各位都相同
一个数如果值为正，则它的反码与原码相同
一个数如果值为负，则将其符号位置为1，其余各位为对原码相应数据位取反
（取反：二进制中有0和1两种状态，取反就是取与当前状态相反的状态，1取反等于0,0取反等于1）
正数的补码与反码，原码相同
负数的补码则将其最高位置为1，其余各位为对原码的相应数据位取反，再对整个数加1
即 X为负数时，【X】补 = 【X】反+1
（+0）补 = 00000000
（-0）反 = 11111111
（-0）补 = 11111111 + 1 = 100000000→进位1舍去→00000000
假设用一个字节表示一个数，补码的表示范围为：-128 ----- +127
用反码表示的最小值为：-128，其反码为：10000000
用反码表示的最大值为：+127，其反码为：01111111
按位或运算符”|”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的两个二进位有一个为1时，结果位就为1.参与运算的两个数均以补码出现
例如：9|5
00001001
| 00000101
00001101（十进制为13）
可见9|5=13
~为单目运算符，具有右结合性。其功能是对参与运算的数的各二进位按位求反
例如：~9
~（0000000000001001）结果为：1111111111110110
按位异或运算符” ^ ”是双目运算符。其功能是参与运算的两数各对应的二进位相异或。当两对应的二进位相异时，结果为1。参与运算数仍以补码出现
例如：9^5
00001001
^ 00000101
00001100（十进制为12）
左移运算符” ＜＜ ”是双目运算符。其功能是把 ” ＜＜ ”左边的运算数的各二进位全部左移若干位，由” ＜＜ ”右边的数指定移动的位数，高位丢弃，低位补0
例如：a=00000011（十进制3），a ＜＜ 4，结果为：00110000（十进制48）
右移运算符” ＞＞ ”是双目运算符。其功能是把” ＞＞ ”左边的运算数的各二进制全部右移若干位，” ＞＞ ”右边的数指定移动的位数
例如：a=15（00001111），a ＞＞2，结果为00000011（十进制3）
计算方法例：
※CRC码计算还有一个好处：
我们希望不管m是多少位的，但是冗余位r是越短越好，而且最好位数是固定的。用这CRC码的好处就是生成多项式是多少阶的，那么最后的余数（冗余位）的位数就是多少位。如果是n阶的，那么最后就是4位
循环冗余校验法检验不出来的错的情况：收到的位串虽然是错误的，但是恰巧能被生成多项式整除，这个时候检测不出来
适用于高层协议，如IP，TCP，UDP等
校验码放在前面或后面影响都不大，所以绝大多数是放在前面的
检错率低于循环冗余校验法
在↓例子中，如果第1位和第9位同时出错，或者第2位和第10位同时出错···出错，那么它们取反相加的数是不变的，这个时候是检查不出错的。但是网络当中连续突发的错占绝大部分，这种跳跃性的出错概率很小，所以检验和的检错率还是比较高的
高层不用冗余校验法的原因是，冗余校验法主要采用除的计算方式，比累加的（校验和）计算方式效率要低，而数据链路层用这种方法可以用硬件实现，但是网络层和传输层一般只能通过软件实现，那么效率就降低了。而且数据链路层已经提供了比较可靠的支持，所以高层就可以用这种检错率相对低一点的检错法
检验字段初值置0，数据拆分成与检验字段等长的分片，不足部分补0，将所有分片逐位取反，并连续累加，丢弃最高进位，计算结果置于检验字段。接收端执行相同的过程（分段处理，取反累加，把累加出的校验和与校验码字段当中保存的校验和进行比对，如果是完全一致就没错），并将计算结果和传输过来的检验和进行比较以确定是数据是否出现差错
D. 数据链路层的三个基本内容(帧定界、透明传输和差错检测)都包含哪些内容
帧的首部必须设有一些特殊的比特组合，使得接收端能够找出一帧的开始。这也称为帧定界。帧定界还包含确定帧的结束位置.
网络的各层协议都是相当复杂的。当我们在电脑上编辑好一封邮件后，只要用鼠标点击一下“发送”按钮，这封电子邮件就发送出去了。实际上，我们的电脑要使用好几个网络协议。可是这些复杂的过程我们都看不见。因此，这些复杂的网络协议对网络用户来说都是“透明的”。意思是：这些复杂的网络协议虽然都是存在于电脑中，但用户却看不见（如果要看，就要使用专门的网络软件）。
差错校验是在数据通信过程中能发现或纠正差错，把差错限制在尽可能小的允许范围内的技术和方法。
包括奇偶校验码是一种通过增加冗余位使得码字中“枝羡1”的个数为奇数或偶数的编码方法，它是一种检错码。
水平奇偶校验的特点及编码规则
特点：水平奇偶校验又称横向奇偶校验，它不但大模能检测出各段同一位上的奇数个错，而且还能检测出突发长度<=p的所有突发错误。其漏检率要比垂直奇偶校验方法低，但实现水平奇偶校验时，一定要使用数据缓冲器。
水平垂直奇偶校验的特点及编码规则
特点：水平垂直奇偶校验又称纵横奇偶校验。它能检测出所有3位或3位以下的错误、奇数个错、大部分偶数个错以及突发长度<=p+1的突发错。可使误码率降至原误码率的百分之一到万分之一。还可以用来纠正部分差错。有部分偶数个错不能测出。适猛仿拍用于中、低速传输系统和反馈重传系统。