差错控制

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

分类

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

奇偶校验码

奇偶校验码（Parity Check Code）是一种错误检测机制，通常用于数据传输中，以检测传输过程中的单比特错误。奇偶校验码通过在数据中添加一个额外的比特（校验比特）来实现。这个校验比特的值被设置为确保数据中的所有比特（包括校验比特）的总数是奇数或偶数，具体取决于所选择的奇偶性规则。

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

  1. 奇校验（Odd Parity）：在奇校验中，校验比特被设置为确保数据中的所有比特的总数（包括校验比特）为奇数。如果在传输过程中某个比特发生了错误，导致总比特数变为偶数，接收端将检测到错误。
  2. 偶校验（Even Parity）：在偶校验中，校验比特被设置为确保数据中的所有比特的总数（包括校验比特）为偶数。如果在传输过程中某个比特发生了错误，导致总比特数变为奇数，接收端将检测到错误。

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

循环冗余码

循环冗余校验（CRC）是一种常用的数据完整性校验方法，主要用于数据传输的错误检测。CRC 的核心思想是将数据看作多项式的系数，并用特定的生成多项式进行除法操作，得到的余数即为 CRC 值。

CRC 校验大致流程：

  • 生成多项式：CRC 的核心是一个生成多项式，通常用二进制表示。这个多项式是事先定义好的，并且在发送端和接收端都必须知道。
  • 帧校验码计算：为了计算 CRC 校验码，发送端将数据帧和生成多项式进行除法运算，得到余数，然后将余数附加到数据帧的末尾。如果生成多项式是 n 位长，那么 CRC 校验码将是 n-1 位长。
  • 传输：将 CRC 校验码附加到数据帧的尾部，发送至接收端。
  • 接收端校验：接收端接收到数据帧后，也执行相同的 CRC 校验操作。它将接收到的数据帧与生成多项式进行除法运算，得到一个余数。如果余数为零，表示数据帧没有错误。如果余数不为零，表示数据帧存在错误。
Data
Divisor
000....0
CRC
Sender
Data
CRC
Data
CRC
Divisor
Remainder
Receiver
n bits
n-1 bits
zero accept
non-zero reject

以一个实际例子说明 CRC 校验过程：

假设我们要发送的数据是：1010001101

我们选择的生成多项式是：110101，对应的是 $x^5 + x^4 + x^2 + 1$

发送方操作：

  1. 为了进行校验码计算，首先在原始数据的尾部添加 k−1 个零（其中 k 是生成多项式的位数，这里是 4），所以数据变成了：1010001101 00000
  2. 使用生成多项式除以这个新的数据。实际上，我们使用二进制的异或操作来进行模 2 除法。
  3. 计算得到的余数就是 CRC。
              110101011
       ------------------
110101 | 101000110100000
         110101
         ------
          111011
          110101
          ------
            111010
            110101
            ------
              111110
              110101
              ------
                101100
                110101
                ------
                 110010
                 110101
                 ------
                   01110

将计算得到 CRC 01110 添加到数据后面一起发送，接收方接收到的数据为 101000110101110

接收方接收到数据后进行校验，计算过程如下：

              110101011
       --------------------------------------
110101 | 101000110101110
         110101
         ------
          111011
          110101
          ------
            111010
            110101
            ------
              111110
              110101
              ------
                101111
                110101
                ------
                 110101
                 110101
                 ------
                      0

计算得到余数为零，表示数据帧没有错误。

海明码

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

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

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

步骤 1：确定校验位数量

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

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

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

步骤 2：放置数据位

首先放置数据位 $d$ ：

  • 第 $3$ 位（$2^0+2^1$）: 数据位 $d_1$
  • 第 $5$ 位（$2^0+2^2$）: 数据位 $d_2$
  • 第 $6$ 位（$2^1+2^2$）: 数据位 $d_3$
  • 第 $7$ 位（$2^0+2^1+2^2$）: 数据位 $d_4$

将校验位（ $p$ ）插入到数据位中的适当位置。校验位位置通常是 $2$ 的幂（ $1, 2, 4, 8, …$ ）。

位置1234567
海明码$p_1$$p_2$$d_1$$p_3$$d_2$$d_3$$d_4$
数据--$1$-$0$$1$$1$

步骤 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：生成海明码

位置1234567
海明码$p_1$$p_2$$d_1$$p_3$$d_2$$d_3$$d_4$
数据$0$$1$$1$$0$$0$$1$$1$

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

步骤 5：检测和纠正错误

假设在传输过程中第二位出现了错误，接收的码变为 $0010011$ 。接收者现在要检查每个校验位：

  • $p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0$ (没有变化)
  • $p_2 = d_1 \oplus d_3 \oplus d_4 = 1 \oplus 1 \oplus 1 = 1$ (错误)
  • $p_3 = d_2 \oplus d_3 \oplus d_4 = 0 \oplus 1 \oplus 1 = 0$ (没有变化)

校验位 $p$ _ $2$ 错误，这告诉我们位模式 $ 2, 3, 6, 7 $ 中的某个位出错。因为只有 $p_2$ 指示出错误，我们可以断定是第 $2$ 位出错了。

要纠正这个错误，只需要改变第二位：

从：0 1 1 0 0 1 1
到：0 0 1 0 0 1 1

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