计算机网络：数据链路层之差错控制、奇偶校验码、CRC循环冗余码、海明码
带你度过期末难关
文章目录
- 一、差错控制
-
- 1、冗余编码
- 2、编码VS编码
- 二、检错编码
-
- 1、奇偶校验码
- 2、CRC循环冗余码
- 三、纠错编码————海明码
-
- 海明距离
- 1、确定校验码位数r
- 2、确定校验码和数据的位置
- 3、求出校验码的值
- 4、检错并纠错
-
- 纠错的方法一：
- 纠错方法二：
- 总结
一、差错控制
概括来说，传输中的差错都是由于噪声引起的。
全局性
1.由于线路本身电气特性所产生的随机噪声(热噪声)，是信道固有的，随机存在的。
解决办法:提高信噪比来减少或避免干扰。(对传感器下手)
局部性
⒉.外界特定的短暂原因所造成的冲击噪声，是产生差错的主要原因。
解决办法:通常利用编码技术来解决。
差错
- 位错：【比特位出错，1变成0，0变成1。】
- 帧错：
- 丢失：收到[#1]-[#3]
- 重复：收到[#1]-[#2]-[#2]-[#3]
- 失序：收到[#1]-[#3]-[#2]
链路层为网络层提供服务:
- 无确认无连接服务：通信质量好，有线传输链路
- 有确认无连接服务：通信质量差的无线传输链路
- 有确认面向连接服务：通信质量差的无线传输链路
1、冗余编码
在数据发送之前，先按某种关系附加上一定的冗余位，构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时，相应的冗余位也随之变化，使码字遵从不变的规则。接收端根据收到码字是否仍符合原规则，从而判断是否出错。
2、编码VS编码
数据链路层编码和物理层的数据编码与调制不同。物理层编码针对的是单个比特，解决传输过程中比特的同步等问题，如曼彻斯特编码。而数据链路层的编码针对的是一组比特，它通过冗余码的技术实现一组二进制比特串在传输过程是否出现了差错。
二、检错编码
1、奇偶校验码
奇校验：原始码流+校验位 总共有奇数个1
偶校验：原始码流+校验位 总共有偶数个1
校验位只有1个
奇偶校验码特点:
只能检查出奇数个比特错误，检错能力为50%。
2、CRC循环冗余码
例题：
要发送的数据是1101011011，采用CRC校验，生成多项式是10011，那么最终发送的数据应该是?
最终发送的数据:要发送的数据+帧检验序列FCS
计算冗余码:
(1)加0：假设生成多项式G(x)的阶为r，则加r个0。
(2）模2除法：数据加O后除以多项式，余数为冗余码/FCS/CRC检验码的比特序列。
其中生成多项式是10011，而10011可以看成1×X^4 +0×X^3 +0×X^2 +1×X^1 +1×X^0。
可以看出最高阶是4阶，所以就需要在发送的数据（1101011011）后补4个0
计算过程如下图所示：
计算得出余数/FCS/冗余码：1110
那么最终发送的数据就是发送的数据+余数：11010110111110
注意：
冗余码的位数是生成多项式的最高阶数，如果你算的冗余码位数不够，需要在前面补0。（如果最高阶是4阶，冗余码计算出来的结果是11，那么冗余码应该是0011）
接收端检错过程
把收到的每一个帧都除以同样的除数，然后检查得到的余数R。
1.余数为0，判定这个帧没有差错，接受。
⒉余数为不为0，判定这个帧有差错（无法确定到位），丢弃。
FCS的生成以及接收端CRC检验都是由硬件实现，处理很迅速，因此不会延误数据的传输。
三、纠错编码————海明码
海明码:发现双比特错，纠正单比特错。
工作原理:动一发而牵全身
工作流程：
海明距离
两个合法编码(码字)的对应比特取值不同的比特数称为这两个码字的海明距离(码距)，一个有效编码集中,任意两个合法编码(码字)的海明距离的最小值称为该编码集的海明距离(码距)。
说白了就是两个编码之间的不同位有几个就是他们之间的海明距离。
下面不需要自己推导：
- 如果想通过海明码去检验d位错的话，那么需要的码距是d+1位
- 如果想通过海明码去纠正d位错的话，那么需要的码距是2d+1位
1、确定校验码位数r
数据/信息有m位，冗余码/校验码有r位
校验码一共有2^r种取值
海明不等式：2^r >=m+r+1
例题1：
要发送的数据: D=1100，求出校验码位数
解答：
可以得出数据位数m=4，满足不等式的最小r为3，即2^3>=4+3+1
也就是D=1100的海明码应该有4+3=7位，其中原数据4位，校验码3位。
例题2：
要发送的数据: D=101101,求出校验码位数
解答：
数据的位数m=6，满足不等式的最小r为4，即2^4>=6+4+1
也就是D=101101的海明码应该有6+4=10位，其中原数据6位，校验码4位。
2、确定校验码和数据的位置
例题1：
假设D=1100，校验码3位
校验码放在序号为2^n的位置，数据按序填上
然后再将1100依次填入空白处
例题2：
假设D=101101，校验码4位
3、求出校验码的值
例题1：
假设D=1100
然后用通配符管制
4号校验码负责4，5，6，7的校验
2号校验码负责2，3，6，7的校验
1号校验码负责1，3，5，7的校验
然后采用偶校验(具体采用偶校验还是奇校验题目中会给你说明)得出结果：
偶校验讲解：
- 4号校验4567，其中567对应的值为011，进行偶校验时，必须有偶数个1，所以4为0。
- 2号校验2367，其中367对应的值为011，进行偶校验时，必须有偶数个1，所以2为0。
- 1号校验1357，其中357对应的值为001，进行偶校验时，必须有偶数个1，所以1为1。
故1100的海明码为：1000011
例题2：
假设D=101101
故101101的海明码为0010011101
4、检错并纠错
假设D=1100
若接收方收到的数据为1110001，（7到1位）检错类似奇偶校验
纠错的方法一：
1，3，5，7出错了，4，5，6，7出错了，得出5和7可能是错的，再由2，3，6，7是正确的排除7，所以错误的是5.
文字描述：找到不满足奇/偶校验的分组取交集，并与符合校验的分组取差集。
纠错方法二：
首先列出X1、X2、X4的校验结果，然后通过自身偶校验得出X1、X2、X4的结果为101，得出十进制是5，所以第五位错了。
总结
以上就是数据链路层之差错控制、奇偶校验码、CRC循环冗余码、海明码的相关知识点，希望对你有所帮助。