# 3.3 差错控制

## 3.3.1 差错的差生

差错基本上都是由于噪声引起的。

### 1、噪声的种类

* 全局性
  * 由于线路本身电气特性所产生的**随机噪声**（热噪声），是信道固有的，随机存在的
  * 解决方法：提高信噪比
* 局部性
  * 外界特定的短暂原因所造成的**冲击噪声**，是产生差错的**主要原因**
  * 解决办法：通常利用编码技术来解决

### 2、差错的种类

* **位错**：0变1、1变0
* **帧错**
  * 丢失：【1】【3】
  * 重复：【1】【2】【2】【3】
  * 失序：【1】【3】【2】

### 3、链路层提供的服务种类

对于通信质量好的网络，采用<mark style="color:purple;">**无确认无连接服务**</mark>

对于通信质量差的网络，采用<mark style="color:purple;">**有确认无连接服务**</mark>

对于无线传输链路，采用<mark style="color:purple;">**有确认有连接服务**</mark>

## 3.3.2 检错编码

### 1、奇偶校验码

有n-1位数据位和1位校验位，使1的个数分别为奇数或者偶数，则称为采用了奇校验（偶校验）。

**缺点**：只能检查出奇数个的错误，检错能力为50%

### 2、循环冗余编码（CRC）

将数据拆分为相等大小的组，每一组加上冗余码（FCS）构成帧再发送。

冗余码采用生成多项式与数据相除得到，具体流程如下所示

{% hint style="info" %}
例：要发送的数据是1101011011，采用CRC校验，生成多项式是10011，那么最终发送的数据应该是？

10011对应的多项式为：$$x^4+0x^3+0x^2+x+x^0$$，阶为4

将数据加上4位0，得到被除数：1101011011<mark style="color:red;">0000</mark>

将被除数与生成多项式模二相除（异或，同0异1）

<img src="https://1628974532-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FKXaHhVFQadnoaaLPklBX%2Fuploads%2Fgit-blob-4f0f80bffcb23c13f8d3291835c5d94f4b3bdd33%2FCRC.png?alt=media" alt="" data-size="original">

* 异或运算所得结果前面0省略，补足5位
* 最后的余数即为FCS

因此输出结果为1101011011<mark style="color:red;">1110</mark>
{% endhint %}

接收方在校验时，使用同样的生成多项式与数据相除，若余数为0，则表明数据无误，接收方接收信息。

否则，接收方会将这一帧**丢弃**。

{% hint style="warning" %}
CRC能够实现无比特差错的传输，但不是**可靠传输**。

可靠传输：发送方发送什么，接收方就接收什么。
{% endhint %}

## 3.3.3 纠错编码

### 1、海明码

#### （1）海明距离

两个合法编码（码字）的对应<mark style="color:orange;">**比特取值不同**</mark>的比特数称为这两个码字的<mark style="color:purple;">**海明距离**</mark>（码距）

一个有效编码集中，任意两个合法编码（码字）的海明距离的<mark style="color:orange;">**最小值**</mark>称为该编码集的<mark style="color:purple;">**海明距离**</mark>（码距）

对于一个n位的数据

* 使用海明码进行<mark style="color:orange;">**检错**</mark>，码距应为n+1
* 使用海明码进行<mark style="color:orange;">**纠错**</mark>，码距应为2n+1

{% hint style="warning" %}
计算机网络考察中，海明码

* <mark style="color:orange;">**检错**</mark>：双比特
* <mark style="color:orange;">**纠错**</mark>：单比特
  {% endhint %}

海明码的使用分为四步：

1. 确定校验码的位数
2. 确定校验码的位置
3. 求出校验码的值
4. 检错、纠错

#### （2）确定校验码的位数

若数据有m位，校验码有r位，则校验码的位数应满足：

$$
2^{r}\geq m+r+1
$$

#### （3）确定校验码和数据的位置

将校验码依次放在$$2^{r}$$位上，剩下的数据依次填入

#### （4）求出校验码的值

每位校验位依照自身序号中为1的位置确定所要检验的数据位

依据各校验码所对应的校验数据位，分别做偶校验，得到校验位的值

{% hint style="info" %}
例：要发送的数据为1100

m=4，满足条件的最小r=3，校验码有3位

确定校验码的位置：

<img src="https://1628974532-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FKXaHhVFQadnoaaLPklBX%2Fuploads%2Fgit-blob-d278ad470e43955439aafc8d088816877352e3fb%2F%E6%B5%B7%E6%98%8E%E7%A0%811.png?alt=media" alt="image-20211024100003204" data-size="original">

确定各校验码的值：

<img src="https://1628974532-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FKXaHhVFQadnoaaLPklBX%2Fuploads%2Fgit-blob-2c50dd9225b60c6ffcf88c17fe2f263cc867ea35%2F%E6%B5%B7%E6%98%8E%E7%A0%812.png?alt=media" alt="海明码2" data-size="original">

* $$x\_{1}$$负责1、3、5、7位的校验，偶校验结果为1；
* $$x\_{2}$$负责2、3、6、7位的校验，偶校验结果为0；
* $$x\_{4}$$负责4、5、6、7位的校验，偶校验结果为0

综上，海明码结果为110<mark style="color:red;">0</mark>0<mark style="color:red;">01</mark>
{% endhint %}

#### （5）检错和纠错

对各校验位进行奇偶校验，若为奇数，则证明数据出错。

将每位校验码所校验的位数再次求奇偶校验，得到新的结果转置所得的二进制值即为出错位数

{% hint style="info" %}
例：上例中接收方收到1110001，进行检错纠错

首先分别求1的奇偶：

* $$x\_{1}$$：1、3、5、7位，奇数
* $$x\_{2}$$：2、3、6、7位，偶数
* $$x\_{4}$$：4、5、6、7位，奇数

数据有错，求错误位：

* $$x\_{1}$$：1、3、5、7位，1011，结果为1
* $$x\_{2}$$：2、3、6、7位，0011，结果为0
* $$x\_{4}$$：4、5、6、7位，0111，结果为1

转置，得101，十进制为5，即第五位出错。
{% endhint %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aye10032.gitbook.io/computernetwork/di-san-zhang-shu-ju-lian-lu-ceng/3.3-cha-cuo-kong-zhi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.