差错控制

💡 低优先级

说实话本节细节极多但是考查频率很低，考的话一般是在选择题考一题，这一节的几个知识点说实话只能硬背了，大家可以根据自身精力决定要不要搏一搏这可能出现的两分。

分类

• 检错编码 ：奇偶校验码、循环冗余码
• 纠错编码 ：海明码

奇偶校验码

奇偶校验码（Parity Check Code）是一种 简单高效 的错误检测机制，广泛应用于数据传输和存储系统中，用于发现 单比特错误 。其核心思想是通过添加一个 校验比特 （parity bit），确保数据中“1”的总数符合特定的奇偶规则。

奇偶校验码有两种常见的类型：奇校验 和 偶校验 。

1. 奇校验 （Odd Parity）：

• 校验比特的值使数据（包括校验比特）中“1”的总数为 奇数 。
• 例如，若原始数据“1”的个数为 偶数 ，校验比特设为 1 ；若为 奇数 ，设为 0 。
• 若接收端检测到“1”的总数为 偶数 ，则说明传输中存在错误。

2. 偶校验 （Even Parity）：

• 校验比特确保数据中“1”的总数为 偶数 。
• 例如，若原始数据“1”的个数为 奇数 ，校验比特设为 1 ；若为 偶数 ，设为 0 。
• 若接收端检测到“1”的总数为 奇数 ，则表明数据出错。

奇偶校验码的 工作原理 如下：

• 发送端 ：根据奇校验或偶校验规则，计算原始数据中 “1” 的个数，设置校验比特，并将数据连同校验比特一起发送。
• 接收端 ：检查接收到的数据（包括校验比特）中 “1” 的总数是否符合预设的奇偶规则。若不符合，说明传输过程中可能发生了单比特错误。

奇偶校验的工作原理是发送端计算数据中所有比特的总数，并根据所选的奇偶性规则设置校验比特的值。接收端在接收数据后再次计算所有比特的总数，包括校验比特，然后检查总数是否满足所选的奇偶性规则。如果总数不符合规则，接收端将检测到错误。

循环冗余码

循环冗余校验 （CRC, Cyclic Redundancy Check）是一种常用的数据完整性校验方法，广泛应用于数据传输和存储系统中，用于检测数据在传输过程中是否发生了错误。其核心思想是将数据视为一个二进制多项式，并使用特定的 生成多项式 对其进行 模 2 除法 ，最终所得的余数即为 CRC 校验值。

校验流程

CRC 的基本校验过程包括以下几个步骤：

• 生成多项式
  CRC 的关键是一个预先定义好的 生成多项式 ，通常用二进制数表示。该多项式必须在发送端和接收端之间事先达成一致。

• 计算校验码（发送端）
  发送端将待发送的数据帧看作一个二进制多项式，然后在数据末尾附加 k-1 个 0（其中 k 是生成多项式的位数），得到 扩展数据 。将这组数据用 模 2 除法 除以生成多项式，得到的余数即为 CRC 校验码 。

• 附加并发送
  将上述余数作为 CRC 校验码，附加在原始数据帧之后，组成完整的传输数据帧并发送。

• 校验（接收端）
  接收端收到数据后，以相同方式使用 生成多项式 进行 模 2 除法 。如果计算结果的余数为 零 ，则说明数据在传输过程中未发生错误；否则表示数据已损坏。

发送方

假设原始数据为：1010001101，选用的生成多项式为：110101，则对应多项式形式为：\(x^5 + x^4 + x^2 + 1\)。

发送方计算 CRC 校验码的操作流程如下：

1. 扩展数据 ：生成多项式是 6 位，因此我们在数据尾部补上 6-1 = 5 个零，得到扩展数据：101000110100000
2. 模 2 除法计算 CRC（使用异或操作） ：

​
110101011 —————— 110101 | 101000110100000 110101 —— 111011 110101 —— 111010 110101 —— 111110 110101 —— 101100 110101 —— 110010 110101 —— 01110

最终余数为：01110，所以完整的数据帧为：1010001101 01110。

接收方

继续以上述例子进行说明，接收方收到的数据为：101000110101110

同样使用生成多项式 110101 进行 模 2 除法 ： 110101011 ————————————– 110101 | 101000110101110 110101 —— 111011 110101 —— 111010 110101 —— 111110 110101 —— 101111 110101 —— 110101 110101 —— 0

余数为 0，表示数据帧未被破坏，校验通过 。

注意

使用异或进行 CRC 计算

在 CRC 运算中，模 2 除法的“减法”实际上就是按位 异或 操作（XOR）。这是因为在二进制中，加法和减法在无进位的情况下是等价的。比如：

• 1 ⊕ 1 = 0（相当于 1 - 1 或 1 + 1（不进位））
• 0 ⊕ 0 = 0
• 1 ⊕ 0 = 1
• 0 ⊕ 1 = 1

因此，CRC 的除法过程实际上是不断地将当前被除数高位与 生成多项式 对齐后进行 异或 操作，然后向右滑动继续处理，直到处理完所有位。

海明码

海明码（Hamming Code）是一种用于 错误检测 和 纠正 的编码方案，通常用于数据传输和存储系统中。它的主要目标是检测和纠正数据中的 单比特错误 。

海明码的核心思想是在 数据位 之间插入一定数量的 校验位 （也称为奇偶校验位），使得每个校验位都负责检查一组特定的位。校验位的数量取决于数据位的数量，并且它们的位置通常是 2 的幂次（即第 1 位、第 2 位、第 4 位……）。

生成过程

以一个 实例 说明海明码的 生成和纠正 过程：

• 步骤 1：确定校验位数量

假如我们的数据是 1011 ，也就是 4 位。根据海明码的原则，我们需要确定足够的校验位 r 来满足以下条件：

2r≥k+r+1

对于 k=4 （数据位），我们找到最小的 r 为 3 。

注意

对于 k 位数据，应该有多少位校验位

假设我们有 k 位数据，我们需要添加 r 位校验位，那么校验位的总数必须满足以下条件：

所有数据位和校验位的总数加起来可以由校验位来表示。也就是说，每一位数据位和校验位在位模式中都有一个唯一的表示。这意味着 2r 必须至少等于 k+r+1 ，其中加 1 是因为校验位模式全为零（即没有错误）的情况也必须被考虑在内，即

2r≥k+r+1

• 步骤 2：放置校验位和数据位

首先将校验位（ p ）插入到数据位中的适当位置。校验位下标是 2 的幂（ 1,2,4,8,… ）。

• 第 1(20) 位：校验位 p1​
• 第 2(21) 位：校验位 p2​
• 第 4(22) 位：校验位 p3​

然后再放置剩余的 数据位 d ：

• 第 3 位：数据位 d1​
• 第 5 位：数据位 d2​
• 第 6 位：数据位 d3​
• 第 7 位：数据位 d4​

注意

注意到上述我们提到的关于校验位和数据位的第 n 位，下标是从 1 开始 而不是 0 开始的。

• 步骤 3：计算校验位

首先给出位置下标的二进制表示：

• p1​ 检查位置 1 、 3 、 5 、 7 的位（最低位为 1） 。所以 p1​=d1​⊕d2​⊕d4​=1⊕0⊕1=0 ，所以 p1​=0 。
• p2​ 检查位置 2 、 3 、 6 、 7 的位（次低位为 1）。这些位的异或值为 p2​=d1​⊕d3​⊕d4​=1⊕1⊕1=1 ，所以 p2​=1 。
• p3​ 检查位置 4 、 5 、 6 、 7 的位（最高位为 1） 。这些位的异或值为 p3​=d2​⊕d3​⊕d4​=0⊕1⊕1=0 ，所以 p3​=0 。

• 步骤 4：生成海明码

所以， 1011 的 (7,4) 海明码是 0110011 。任何一位的单一错误都可以通过分析 校验位 来检测并纠正。

检测和纠错

还是以 上文的例子 来说明海明码检测和纠错的过程。

假设在传输过程中第二位出现了错误，接收的码变为 0010011 。

首先，接收者现在要 重新计算校验位 ：

• p1​ （位置 1）：检查二进制最低位为 1 的位置（1, 3, 5, 7），即 p1​,d1​,d2​,d4​

• p1′​=0⊕1⊕0⊕1=0

• 接收到的 p1​=0 ，所以 p1′​=p1​ ，无错误

  • p2​ （位置 2）：检查二进制第二位为 1 的位置（2, 3, 6, 7），即 p2​,d1​,d3​,d4​

• p2′​=0⊕1⊕1⊕1=1

• 接收到的 p2​=0 ，所以 p2′​=p2​ ，有错误

  • p3​ （位置 4）：检查二进制第三位为 1 的位置（4, 5, 6, 7），即 p3​,d2​,d3​,d4​

• p3′​=0⊕0⊕1⊕1=0

• 接收到的 p3​=0 ，所以 p3′​=p3​ ，无错误

可以看到有错误发生，接下来需要 生成错误模式 ：

(p1′​⊕p1​,p2′​⊕p2​,p3′​⊕p3​)=(0⊕0,1⊕0,0⊕0)=(0,1,0)

错误模式为二进制 010 ，十进制值为 2 ，表示错误在位置 2 （即 p2​ ）。

最后一步是 纠正错误 ：位置 2 的值 p2​ 从 0 翻转为 1，得到纠正后的码字：

现在，海明码回到了正确的 0110011 状态。

海明距离

海明距离是指两个等长的比特序列（也称为码字）在对应位置上不相同的比特个数。它是衡量两个码字之间差异程度的重要指标，广泛应用于 编码理论 中，用于分析 错误检测 和 错误纠正 能力。

编码集

在通信或存储系统中，编码集 是指用于表示信息的一组码字。每个码字通常是一个固定长度的比特串，通过引入冗余位 ，编码集可以在传输过程中检测或纠正一定数量的错误。

编码集的关键属性之一是其最小海明距离 （记作 \(d\)）——即任意两个不同码字之间海明距离的最小值。它直接决定了该编码集的 容错能力 ：

• 检错能力 ：最多可以检测 **d −1 **位错误。
• 纠错能力 ：最多可以纠正 **⌊ 2d−1​⌋ **位错误。

最小海明距离越大，意味着码字之间越“分散”，在信道中被干扰后仍然能区分开来，因此检测和纠错能力更强。

举个实际例子，设有一个编码集，其中包含以下三个 4 位码字：

我们计算这三组码字之间的海明距离：

• 0000 与 0110 的海明距离为 2 （第2、3位不同）；
• 0000 与 1011 的海明距离为 3 ；
• 0110 与 1011 的海明距离为 3 。

因此，该编码集的最小海明距离 为 **d =2 **。

根据公式，该编码集最多可以：

• 检测 1 位错误 （ d−1=1 ）；
• 不能纠错 （ ⌊2d−1​⌋=0 ）。

如果我们想要具备1 位纠错能力 ，最小海明距离至少要达到 3 。

海明码示例

海明码（Hamming Code） 是一种经典的线性分组码，其最小海明距离为 **d =3 **。这意味着：

• 可以 检测最多 2 位错误 。
• 可以 纠正 1 位错误 。

接收端在解码过程中，会计算出一个称为 伴随式（syndrome） 的比特序列，用于判断是否发生了错误，以及错误的位置：

• 若伴随式为全零，说明数据未被破坏；
• 若伴随式为非零，且对应某个位的错误模式，则可准确定位并纠正该位；
• 若发生 2 位错误 ，伴随式可能不唯一，可检测但不可纠正 ，因为错误位置无法唯一确定。

相关笔记

• 通信概念
• 物理层设备
• 编码与调制
• 物理层
• 交换方式