3-2数据链路层-差错控制

1.位错/比特错：比特位错误，如1变为0。本文所讲均为此类错误
2.帧错：帧的丢失、重复、失序
3.差错控制
（1）自动重传请求ARQ
接收方检测出差错，通知发送方重发，直到正确接收
（2）前向纠错FEC
不但能发现差错，还能确定比特串错误的位置，从而加以纠正
4.一般来说，数据的传输差错是由噪声引起的。通信信道的噪声可以分为两类：热噪声和冲击噪声。 热噪声一般是信道固有的，引起的差错是 随机差错， 可以通过提高信噪比来降低它对数据传输的影响。冲击噪声一般是由外界电磁干扰引起的，引起的差错是突发差错，它是引起传输差错的主要原因，无法通过提高信噪比来避免。

一.检错

（一）奇偶校验码

n-1位数据和1位校验位组成，校验位用于调节发送信息中的1的个数是偶数还是奇数。
1.奇校验码：附加一个校验元后，“1”的个数为奇数
2.偶校验码：附加一个校验元后，“1”的个数为偶数
3.因为偶数个0和1出错（0变1,1变0）不影响整个1个奇偶个数，所以只能检测出错误而无法对其进行修正，只能检测奇数位出错情况，无法检测出双位错误，并不知道哪些位错了，检错能力50%

eg.
如果一个字符s的ASCII编码从低到高依次为1100101，采用奇校验，在下述收到的传输后字符中，哪种错误不能检测?
A. 11000011 B.11001010 C.11001100 D.11010011

解：1100101共4个1，奇校验在后面添加一个1（在哪里加1看题目要求），使1的个数为奇，变为11001011（如果偶校验，已经4个1了，在后面加0，即11001010）
则传输后应该保持奇数个1才有可能正确，ABC都是4个1必然错误。D有奇数个1，可能正确（也可能偶数位跳变出错）

（二）循环冗余码CRC

凡是接收的都是无差错的（无限趋近于1的概率认为是无差错的），有差错的都丢弃了，因此不能叫做可靠传输（未全部接收）。能够查出99％以上的差错。可以检测出所有的奇数个错/单/双比特错误，带k个校验位的多项式编码可以检测到所有长度小于等于k的突发性错误。CRC校验可以使用硬件来完成。

如：
生成多项式G(x)=1101（即x³+x²+1），待传送数据M=101001
①M后面+r个0（r=G(x)的阶数3；或看做1101有四位，4-1=3），变为101001000
②101001000÷G(x)，得到商Q，余数R（余数为r位，不足的在前面补0）

余数叫做FCS帧检验序列/冗余码，FCS的生成以及接收端CRC检验都是由硬件实现，处理很迅速，因此不会延误数据的传输。

此处的÷是模2除，即异或：相同写0，不同写1

③待传送数据M=101001后面接上余数R（或视为取代补的r个0），得到101001001，即为最终发送的数据

④接收端将最终发送的数据÷生成多项式，即101001001÷1101，余数为0表示没错，就接收。如果接收端收到的数据为101001011，模2除1101，得到余数为010，表示从右往左第二位出错

二.纠错-海明码

可以发现错位，而且能指出错位的位置。可以检测双比特错误，但只能纠正一位差错（单比特错误）。

1.海明距离/码距/海明距
（1）两个合法编码的对应比特取值不同的比特数称为这两个码字的码距。如：0001和0000，有一位不同，码距是1。
（2）一个有效编码集中，任意两个合法编码的码距的最小值称为该编码集的码距。如：0000和0001和0011，两两之间码距的最小值为1，因此码距为1
（3）若要检测d位错，需要码距d+1。反之，若码距为n，则可以检测n-1位错。
（4）若要纠正d位错，需要码距2d+1

2.海明码工作流程
eg.要发送的数据D=1100
解：
（1）确定校验码的位数
n=4（待发送数据4位），根据公式n+k≤2^k-1，得k=3（满足等式的最小k值），表示校验码为3位，k也叫做需要增加的冗余信息位。结合n=4得到共7位
（2）将校验码分别放在1、2、4、8、…2ⁿ位上，其余由高到低填入数据1100

（3）求出校验码的值
根据表格，x₄对应二进制100，即1**，即以1开头的二进制7、6、5、4都由4号校验码负责校验。
同理，x₂为010，即*1*，1在中间的7、6、3、2都由2号校验码负责；
x₁为001，即**1，1在右边的7、5、3、1都由1号校验码负责。

（4）如果采用偶校验，即保证表中值为1的个数是偶数
x₄的7、6、5、4，值分别为1、1、0、x₄，因此x₄为0
x₂的7、6、3、2，值分别为1、1、0、x₂，因此x₂为0
x₁的7、5、3、1，值分别为1、0、0、x₁，因此x₄为1

表格变为

（5）检错和纠错
eg.接收方收到的数据为1110001
①标注序号

因为x₄负责7654位校验，对应的值为1110，奇数个1，说明7654位存在错误
x₂负责7632位的校验，对应的值为1100，偶数个1，说明7632位正确
x₁负责的7531位的校验，对应的值为1101，奇数个1，说明7531位存在错误
145

②找错法一
x₂说明错误出现在145，而x₁和x₄都有5，因此5号出错

②找错法二
x₁和x₄都有5、7，而x₂说明7没错，所以5号出错

③找错法三（推荐）：异或（相同为0，不同为1）
x₄⊕1⊕1⊕1⊕0=0，得x₄=1
x₂⊕1⊕1⊕0⊕0=0，得x₂=0
x₁⊕1⊕1⊕0⊕1=0，得x₁=1
x₄x₂x₁为101，对应5，即第五位出错