差错检测和纠正——链路层

秒速五厘米 2023-05-30 12:00 8阅读 0赞

## 一、常见术语 ##

**1、比特级差错检测和纠正（bit-level reeor detection and correetoin）**  
对一个节点发送到另一个物理上连接的临近节点的链路层帧中的比特损伤进行检测和纠正，他们是链路层提供的两种服务。

**2、数据（D）**

**3、差错检测和纠正比特（Error-Detection and-Correction，EDC）**

**4、未检出比特差错（undetected bit error）**

## 二、差错检测 ##

**1、基本原理**  
发送方：信息数据+冗余数据  
接收方：检查信息数据和冗余数据的关系，发现差错  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]  
**2、差错检测分类**

*  奇偶校验：用来描述差错检测和纠正背后隐含的基本思想
 *  检验和方法：通常用于运输层
 *  **循环冗余检测**：通常应用于适配器中的链路层

## 三、奇偶校验（parity bit） ##

**奇偶校验其实是两个校验：奇校验和偶校验**  
发送信息 D 有 d 比特

**1、奇校验**  
发送方只需包含一个附加的比特，选择它的值，使得这 d+1 比特（初始信息加上一个校验比特）中的 1 的总数是奇数。

**2、偶校验（一般使用）**  
发送方只需包含一个附加的比特，选择它的值，使得这 d+1 比特（初始信息加上一个校验比特）中的 1 的总数是偶数。

如果采用偶校验方案中发现了奇数个值为 1 的比特，接收方知道至少出现了一个比特差错。（更精确的说法是：出现了奇数个比特差错）  
![在这里插入图片描述][20191110165017998.png]

一维奇偶校验只能查看是否出现错误，不知道哪里错了，也不能改正。

**3、二维奇偶校验（two-dimensional parity）**  
对每行和每列都添加一个奇偶校验位  
原来 i 行 j 列，现在 i+1 行 j+1列  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

因此接收方不仅**可以检查出现的单个比特差错，还能够识别并纠正**。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]

## 四、检验和方法 ##

**1、发送方**  
将段内容作为16比特整数序列来处理  
检查和: 段内容相加(补码和)  
发送方将检查和的值放入 UDP 检查和字段

**2、接收方**  
计算接收到段的检查和  
检查是否计算的检查和等于 检查和字段的值:  
NO – 检测到差错  
YES – 没有检测到差错. 尽管如此，还可能有错。

**3、计算**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 3]  
求和，回卷，求反后的结果就是检验和。  
**接收方：传送后，把全部的3个16bit（原始两个16bit、检验和）加在一起。如果该分组中没有出现错误，和的结果应该是 1111111111111111 。如果有 0，说明分组传送出现了错误。**

## 五、循环冗余检测 ##

**1、循环冗余检测（Cyclic Redundancy Check，CRC）**  
（1）**CRC编码也被称为多项式编码（polynomial code）**，因为该编码能够将要发送的比特串看作是系数为 0 和 1 的一个多项式。对比特串操作被解释为多项式算术。

（2）循环冗余校验码CRC是计算机网络和数据通信中使用最为广泛的检错码之一。

*  检错能力强
 *  （硬件）实现简单
 *  广泛用于实践中 (ATM, HDLC)

**2、CRC算法**  
D：D数据拥有 d 比特  
G：发送方和接收方需要协商一个 r+1 比特模式，称为生成多项式（G），G的最高有效位的比特（最高位）是 1  
R：发送方选择 r 个附加比特，称为R

R 附加到 D 上，一共有 d+r 个比特（二进制），用模 2 算术恰好能够被 G 整除（没有余数），即 **（D+R）/G，如果余数为非 0，接收方知道出现了差错，否则认为数据正确而被接收。**  
![在这里插入图片描述][20191110172047444.png]

**所有 CRC 计算采用模 2 算术，即在加法中不进位，在减法中不借位，意味加法和减法是相同的，等价于操作数的按位异或（XOR）运算。**  
例如：

1011 - 0101 = 1110
    1011 XOR 0101 = 1110

![在这里插入图片描述][20191110175030498.png]![在这里插入图片描述][20191110175831949.png]

CRC标准有8、12、16、32比特生成多项式G，一般采用32比特。

**3、例子**  
D = 101110，d = 6，G = 1001，r = 3  
在这种情况下传输 9 个比特是 101110011，即 R = 01。  
把 D+R 拼到一起传送，接收方接收到信息，让（D+R）/G 即可，余数为0表示无差错。  
![在这里插入图片描述][20191110175712918.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191110143956775.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[20191110165017998.png]: https://img-blog.csdnimg.cn/20191110165017998.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191110165900525.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191110170238311.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191110170607865.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[20191110172047444.png]: https://img-blog.csdnimg.cn/20191110172047444.png
[20191110175030498.png]: https://img-blog.csdnimg.cn/20191110175030498.png
[20191110175831949.png]: https://img-blog.csdnimg.cn/20191110175831949.png
[20191110175712918.png]: https://img-blog.csdnimg.cn/20191110175712918.png