差错控制

分类

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

奇偶校验码

奇偶校验码（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，表示数据帧未被破坏，校验通过。

海明码

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

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

生成过程

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

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

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

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

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

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

• 第 $1 (2^0)$ 位：校验位 $p_1$
• 第 $2 (2^1)$ 位：校验位 $p_2$
• 第 $4 (2^2)$ 位：校验位 $p_3$

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

• 第 $3$ 位：数据位 $d_1$
• 第 $5$ 位：数据位 $d_2$
• 第 $6$ 位：数据位 $d_3$
• 第 $7$ 位：数据位 $d_4$

• 步骤 3：计算校验位

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

• $p_1$ 检查位置 $1$ 、 $3$ 、 $5$ 、 $7$ 的位（最低位为 1） 。所以 $p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0$ ，所以 $p_1 = 0$ 。
• $p_2$ 检查位置 $2$ 、 $3$ 、 $6$ 、 $7$ 的位（次低位为 1）。这些位的异或值为 $p_2 = d_1 \oplus d_3 \oplus d_4 = 1 \oplus 1 \oplus 1 = 1$ ，所以 $p_2 = 1$ 。
• $p_3$ 检查位置 $4$ 、 $5$ 、 $6$ 、 $7$ 的位（最高位为 1） 。这些位的异或值为 $p_3 = d_2 \oplus d_3 \oplus d_4 = 0 \oplus 1 \oplus 1 = 0$ ，所以 $p_3 = 0$ 。

• 步骤 4：生成海明码

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

检测和纠错

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

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

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

• $p_1$ （位置 1）：检查二进制最低位为 1 的位置（1, 3, 5, 7），即 $p_1, d_1, d_2, d_4$
  • $p_1' = 0 \oplus 1 \oplus 0 \oplus 1 = 0$
  • 接收到的 $p_1 = 0$ ，所以 $p_1' = p_1$ ，无错误
• $p_2$ （位置 2）：检查二进制第二位为 1 的位置（2, 3, 6, 7），即 $p_2, d_1, d_3, d_4$
  • $p_2' = 0 \oplus 1 \oplus 1 \oplus 1 = 1$
  • 接收到的 $p_2 = 0$ ，所以 $p_2' \ne p_2$ ，有错误
• $p_3$ （位置 4）：检查二进制第三位为 1 的位置（4, 5, 6, 7），即 $p_3, d_2, d_3, d_4$
  • $p_3' = 0 \oplus 0 \oplus 1 \oplus 1 = 0$
  • 接收到的 $p_3 = 0$ ，所以 $p_3' = p_3$ ，无错误

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

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

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

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

海明距离

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

编码集

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

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

• 检错能力：最多可以检测 $d - 1$ 位错误。
• 纠错能力：最多可以纠正 $\left\lfloor \frac{d - 1}{2} \right\rfloor$ 位错误。

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

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

0000, 0110, 1011

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

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

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

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

• 检测 1 位错误（ $d - 1 = 1$ ）；
• 不能纠错（ $\left\lfloor \frac{d - 1}{2} \right\rfloor = 0$ ）。

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

海明码示例

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

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

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

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