差错控制

本节内容比较复杂，尤其是涉及到 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）是一种常用的数据完整性校验方法，主要用于数据传输的错误检测。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

实例

假设我们要发送的数据是：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

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

注意

用异或进行 CRC 计算

当我们在 CRC 计算中“减去”一个多项式，我们实际上是使用异或操作来模拟这个减法。因为在二进制中，减法和加法都可以使用异或操作来完成（只要没有进位）。具体来说，对于无进位的情况，1-1 = 0、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$ 状态。

海明距离

海明距离（Hamming Distance，也译作汉明距离）是指两个等长编码（码字）之间对应位置上不同比特的个数。它是衡量编码差异的指标，用于分析编码集的错误检测和纠正能力。

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

编码集

编码集 是指在数据通信或存储系统中用于表示信息的一组码字（codewords）。每个码字是一个固定长度的比特序列，设计目的是通过添加冗余比特来检测或纠正传输过程中的错误。编码集的检测和纠错能力主要由其 最小海明距离 决定：

最小海明距离是编码集中任意两个不同码字之间海明距离的最小值，记为 $d$。它反映了编码集的“分散性”：$d$ 越大，码字之间的差异越大，编码集的错误检测和纠正能力越强。

最小海明距离为 $d$ 的编码集具备如下能力：

  • 检错能力：最多可以检测 $d-1$ 位错误。
  • 纠错能力：最多可以纠错 $\lfloor (d - 1) / 2 \rfloor$。
注意

海明码的最小汉明距离是 3。

海明码可以纠正 1 位错误。通过计算伴随式（syndrome），接收端能够准确识别并纠正数据中单个比特的错误。

海明码可以检测最多 2 位错误。当发生 2 位错误时，伴随式会指示错误的存在，但无法准确纠正（因为可能与纠正 1 位错误的模式混淆）。