差错控制¶

数据链路层在传输过程中可能因噪声导致位错（帧内某些比特翻转）。差错控制的任务是发现这些错误，必要时纠正或触发重传。

按处理方式，差错控制分为两类：

检错编码¶

检错编码只需让接收方判断有无错误，出错后通常丢弃并重传，不需要定位错在哪一位。

奇偶校验码¶

Example

奇偶校验利用异或运算（模 2 加，记作 \(\oplus\)）生成/检验校验位：

• \(0 \oplus 0 = 0\)，\(0 \oplus 1 = 1\)，\(1 \oplus 0 = 1\)，\(1 \oplus 1 = 0\)

校验位规则（设最高位为校验位）：

类型	规则	例：信息位 1001101（4 个 1）
奇校验	全体比特中 1 的个数为奇数	校验位 = 1 → 1 1001101
偶校验	全体比特中 1 的个数为偶数	校验位 = 0 → 0 1001101

偶校验位的生成：对所有信息位做异或，结果即为偶校验位。例：\(1 \oplus 0 \oplus 0 \oplus 1 \oplus 1 \oplus 0 \oplus 1 = 0\)。

接收方检验：对收到的全部比特（含校验位）做异或。结果为 1 → 检测到错误；结果为 0 → 未检测到错误。

在实际场景中，偶校验的运用比奇校验更加广泛。

CRC 循环冗余校验码¶

CRC（Cyclic Redundancy Check）是数据链路层最常用的检错方法，以太网帧尾 FCS 字段即采用 CRC-32。

基本思想¶

把比特串看作多项式系数（高位对应高次项），用生成多项式 \(G(x)\) 做模 2 除法，余数作为冗余码（FCS）附加在数据后面。接收方用同样的 \(G(x)\) 去除，余数为 0 则认为无错。

CRC 码的构造¶

设 \(G(x)\) 的阶数为 \(r\)（即冗余码位数为 \(r\)），信息位对应多项式为 \(M(x)\)：

1. 在 \(M(x)\) 末尾附加 \(r\) 个 0（相当于乘以 \(x^r\)），得到 \(M(x) \cdot x^r\)

2. 用 \(G(x)\) 对 \(M(x) \cdot x^r\) 做模 2 除法，得到余数 \(R(x)\)

3. 发送的帧 = 原信息位 + \(R(x)\)（共 \(r\) 位冗余码）

CRC 码的校验¶

接收方收到帧后，用同样的生成多项式 \(G(x)\) 对整个帧（信息位 + FCS）做模 2 除法：

• 余数为 0 → 认为无差错

• 余数非 0 → 认为有差错，丢弃该帧

CRC 码的检错与纠错能力¶

设 \(G(x)\) 的阶数为 \(r\)，则：

纠错编码¶

纠错编码不仅能让接收方发现错误，还能定位并纠正错误位，无需重传。408 重点掌握海明码的基本原理。

海明码¶

海明码（Hamming Code）是一种典型的线性分组纠错码，通过增加冗余校验位，使接收方能纠正有限个比特错误。

码距¶

码距（Hamming Distance，也称最小汉明距离 \(d_{\min}\)）指任意两个合法码字之间，对应位不同的比特数的最小值。

码距决定纠错/检错能力：

海明码的编码过程¶

以 (7, 4) 海明码 为例：7 位码字中，4 位为信息位，3 位为校验位。

校验位位置：放在编号为 \(2^i\) 的位置（即第 1、2、4 位），其余位置放信息位。

位编号：  1   2   3   4   5   6   7
        P1  P2  D1  P4  D2  D3  D4
        ↑   ↑       ↑
      2^0 2^1     2^2

各校验位的覆盖范围：\(P_i\) 负责检查所有编号二进制表示中第 \(i\) 位为 1 的位置。

编码步骤（设 4 位信息为 \(D_1 D_2 D_3 D_4\)）：

1. 按上表填入信息位

2. 每个校验位 = 其覆盖范围内所有位的偶校验（异或结果为 0）

位编号：  1   2   3   4   5   6   7
        P1  P2  1   P4  0   1   1

接收方纠错：对 \(P_1, P_2, P_4\) 分别做偶校验，得到纠错码 \(S_1 S_2 S_4\)：

• \(S_1 S_2 S_4 = 000\) → 无错

• \(S_1 S_2 S_4 \neq 000\) → 将 \(S_1 S_2 S_4\) 看作二进制数，其值即为出错位的编号，翻转该位即可纠正