# 3.3 差错控制

## 一、差错控制概述

### 1.1 什么是差错

**差错**：数据在传输过程中发生的错误。

**差错类型**：
- **比特差错**：0变成1，或1变成0
- **帧差错**：帧丢失、帧重复、帧失序

### 1.2 差错产生的原因

- **噪声**：热噪声、冲击噪声
- **信号衰减**
- **干扰**：电磁干扰
- **信道特性**：带宽受限、多径效应

### 1.3 差错控制的方法

**检错编码**：
- 只能检测差错，不能纠正
- 发现差错后要求重传
- 如：奇偶校验、CRC

**纠错编码**：
- 能够检测并纠正差错
- 开销大
- 如：海明码

---

## 二、检错编码

### 2.1 奇偶校验码

#### 奇校验

**规则**：
- 数据位 + 1位校验位
- 数据中1的个数 + 校验位 = 奇数

**例子**：
```
数据：1011010（有4个1，偶数）
校验位：1
传输：10110101（5个1，奇数）
```

#### 偶校验

**规则**：
- 数据位 + 1位校验位
- 数据中1的个数 + 校验位 = 偶数

**例子**：
```
数据：1011010（有4个1，偶数）
校验位：0
传输：10110100（4个1，偶数）
```

**特点**：
- 简单，开销小
- 只能检测奇数个比特错误
- 不能检测偶数个比特错误
- 不能纠错

### 2.2 CRC循环冗余检验

#### 基本概念

**CRC（Cyclic Redundancy Check）**：
- 基于模2运算的检错编码
- 检错能力强
- 广泛应用于数据链路层

#### 模2运算

**模2加/减（异或运算）**：
```
0 ± 0 = 0
0 ± 1 = 1
1 ± 0 = 1
1 ± 1 = 0
```

**特点**：
- 加法 = 减法 = 异或
- 不产生进位和借位

#### CRC编码过程

**步骤**：
1. **确定生成多项式G(x)**：
   - k+1位（k阶多项式）
   - 最高位和最低位为1

2. **数据后补k个0**：
   - 原数据M位
   - 补0后M+k位

3. **模2除法**：
   - 用补0后的数据除以生成多项式
   - 得到余数R（k位）

4. **得到CRC码**：
   - 原数据 + 余数
   - 共M+k位

**例子**：
```
数据：101001（M=6位）
生成多项式：G(x) = x³ + x² + 1（1101，k=3）

1. 数据后补3个0：101001000
2. 模2除以1101：
   101001000 ÷ 1101 = 110101 余 001
3. CRC码：101001001
```

#### CRC检错过程

**步骤**：
1. 接收方用收到的数据除以生成多项式
2. 如果余数为0，无差错
3. 如果余数不为0，有差错

#### 常见生成多项式

| 名称 | 生成多项式 | 检错能力 |
|-----|-----------|---------|
| CRC-8 | x⁸ + x² + x + 1 | 8位 |
| CRC-16 | x¹⁶ + x¹⁵ + x² + 1 | 16位 |
| CRC-32 | x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1 | 32位 |

#### CRC的特点

**优点**：
- 检错能力强
- 能检测突发错误
- 实现简单（硬件）

**缺点**：
- 不能纠错
- 有漏检概率（很小）

---

## 三、纠错编码

### 3.1 海明码

#### 基本概念

**海明码（Hamming Code）**：
- 能够检测并纠正单比特错误的编码
- 由Richard Hamming于1950年提出

#### 海明距离

**海明距离**：两个码字对应位不同的位数。

**性质**：
- 要检测d位错，海明距离 ≥ d+1
- 要纠正d位错，海明距离 ≥ 2d+1

#### 海明码的构造

**确定校验位数量**：
- 数据位：m位
- 校验位：k位
- 满足：2ᵏ ≥ m + k + 1

**校验位的位置**：
- 位于2ⁱ的位置（1, 2, 4, 8, ...）

**校验位的计算**：
- 每个校验位负责校验特定位置的数据位
- 位置的二进制表示中有某一位为1的，由该位校验

**例子（4位数据，3位校验）**：
```
位置：  7   6   5   4   3   2   1
        D4  D3  D2  P3  D1  P2  P1

P1（位置1）：校验位置1,3,5,7（二进制第1位为1）
P2（位置2）：校验位置2,3,6,7（二进制第2位为1）
P3（位置4）：校验位置4,5,6,7（二进制第3位为1）

计算（偶校验）：
P1 = D1 ⊕ D2 ⊕ D4
P2 = D1 ⊕ D3 ⊕ D4
P3 = D2 ⊕ D3 ⊕ D4
```

#### 海明码的纠错

**步骤**：
1. 计算各校验位的校验值
2. 组成二进制数，指出错误位置
3. 翻转该位置的比特

**例子**：
```
接收：  7   6   5   4   3   2   1
        1   0   1   1   1   0   1

S1 = P1 ⊕ D1 ⊕ D2 ⊕ D4 = 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0
S2 = P2 ⊕ D1 ⊕ D3 ⊕ D4 = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0
S3 = P3 ⊕ D2 ⊕ D3 ⊕ D4 = 1 ⊕ 1 ⊕ 0 ⊕ 1 = 1

S3S2S1 = 100（二进制）= 4（十进制）
位置4出错，即P3出错
```

#### 海明码的特点

**优点**：
- 能纠正单比特错误
- 能检测双比特错误

**缺点**：
- 开销大
- 不能纠正多比特错误

---

## 四、考研重点

1. **差错控制概述**：
   - 差错的类型和原因
   - 检错编码和纠错编码的区别

2. **检错编码**：
   - 奇偶校验：奇校验、偶校验、特点
   - CRC：模2运算、编码过程、检错过程、常见生成多项式

3. **纠错编码**：
   - 海明码：构造方法、校验位计算、纠错过程

4. **各种编码的比较**：
   - 检错能力
   - 纠错能力
   - 开销

---

*下一节：3.4 流量控制与可靠传输机制*