差错控制

本节内容比较复杂，尤其是涉及到 CRC 和海明码的具体细节，掌握检错和纠错的大致流程即可，可能在选择题中考察。

分类

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

奇偶校验码

奇偶校验码（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 除法。如果计算结果的余数为零，则说明数据在传输过程中未发生错误；否则表示数据已损坏。

Data
Divisor
000....0
CRC
Sender
Data
CRC
Data
CRC
Divisor
Remainder
Receiver
n bits
n-1 bits
zero accept
non-zero reject

发送方

假设原始数据为：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$ 来满足以下条件：

$2^r \ge k + r + 1$

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

注意

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

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

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

$2^r \ge k + r + 1$

  • 步骤 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$
位置7654321
海明码$d_4$$d_3$$d_2$$p_3$$d_1$$p_2$$p_1$
数据110-1--
注意

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

  • 步骤 3：计算校验位

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

位置7654321
二进制111110101100011010001
  • $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：生成海明码
位置7654321
海明码$d_4$$d_3$$d_2$$p_3$$d_1$$p_2$$p_1$
数据1100110

所以， $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$，无错误

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

$$(p_1’ \oplus p_1, p_2’ \oplus p_2, p_3’ \oplus p_3) = (0 \oplus 0, 1 \oplus 0, 0 \oplus 0) = (0, 1, 0)$$

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

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

位置7654321
海明码$d_4$$d_3$$d_2$$p_3$$d_1$$p_2$$p_1$
修改前1100100
修改后1100110

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

海明距离

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

1
0
0
1
0
1
1
0
1
1
0
1
1
0
1
0
A
B
0
1
0
0
1
1
0
0
XOR Bit Operations

编码集

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

编码集的关键属性之一是其最小海明距离（记作 $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 位错误，伴随式可能不唯一，可检测但不可纠正，因为错误位置无法唯一确定。