2.6 数据校验码

本节是信息编码理论在计算机中的应用，核心在于理解如何通过增加冗余位来检测甚至纠正数据在存储或传输过程中可能出现的错误。汉明码是本节的难点和考点。

基础逻辑与核心概念

• 码距 (Hamming Distance)：两个码字之间对应位上数值不同的位数。例如，101 和 110 的码距是2。
• 检错与纠错能力：
  • 要检测 $d$ 位错误，码距至少为 $d+1$。
  • 要纠正 $d$ 位错误，码距至少为 $2d+1$。

1. 奇偶校验码 (Parity Check)

• 原理：在有效信息位后增加1位校验位，使得整个码字中1的个数为奇数（奇校验）或偶数（偶校验）。
• 能力：
  • 码距为2。
  • 能检测出奇数位的错误。
  • 不能检测出偶数位的错误。
  • 不能纠错，因为它无法定位错误发生在哪一位。
• 交叉奇偶校验：通过对数据块进行水平和垂直双向的奇偶校验，可以检测并纠正一位错误。

2. 汉明校验码 (Hamming Code) (难点与高频考点)

• 原理：一种多重奇偶校验，通过巧妙地设置多个校验位，并让它们对信息位进行分组校验，从而实现错误位的定位和纠正。

• 编码规则：

  1. 确定校验位数 k：设信息位有 $n$ 位，校验位有 $k$ 位，则必须满足： $2^k\ge n+k+1$ 这个公式确保了校验结果（指误字）的组合足够表示“无错”和“每一位出错”这 $n+k+1$ 种情况。
  2. 确定校验位位置：校验位 $P_i$ 放在海明码中第 $2^{i-1}$ 的位置上（$i=1,2,3,...$）。
  3. 确定校验关系：
     • 每一位信息位由多个校验位共同校验。
     • 校验位 $P_i$ 的值，由所有其位置序号的二进制表示中第 $i$ 位为1的数据位（包括其他校验位）进行异或运算得到（以偶校验为例）。
     • 分组技巧：海明码的第 $j$ 位由哪些校验位来校验，取决于 $j$ 的二进制表示。例如，第 $11({1011}_2)$ 位数据，由 $P_1,P_2,P_4$ 共同校验。
  4. 计算校验位的值 (以偶校验为例)： $P_i=D_{j1}\oplus D_{j2}\oplus ...$ 其中 $D_{jx}$ 是所有被 $P_i$ 校验的信息位。

• 检错与纠错：

  1. 接收端收到数据后，重新计算各校验位，得到新的校验结果 $S_i$。
  2. 将新的校验结果与收到的校验位进行异或，得到指误字 G (Syndrome)：$G_i=P_{i\mathrm{\_}new}\oplus P_{i\mathrm{\_}received}$。
  3. 判断：
     • 如果指误字 G 全为0，表示无错误。
     • 如果指误字 G 不全为0，其十进制值就指明了出错的位数。例如，G = 101 (二进制)，则说明是第5位出错了。
     • 将出错位取反即可完成纠错。

难点与考点：

• 汉明码的编码和解码过程是必考的计算题。
• 必须熟练掌握 $2^k\ge n+k+1$ 公式的应用，以确定所需的最少校验位数。
• 分组规则是核心，一定要理解每个校验位校验哪些信息位。

3. 循环冗余校验码 (CRC - Cyclic Redundancy Check)

• 原理：利用多项式除法（模2除法）来产生校验码。

• 编码过程：

  1. 选取一个生成多项式 G(x) (收发双方约定)。
  2. 将要发送的 $n$ 位信息码左移 $k$ 位（$k$ 是 G(x) 的最高次幂），相当于在信息码后面补 $k$ 个0。
  3. 用 G(x) 对应的二进制码去除左移后的信息码（模2除法，即异或运算）。
  4. 得到的 $k$ 位余数就是CRC校验码。
  5. 将此余数拼接到原始信息码的末尾发送出去。

• 检错过程：

  • 接收端用同样的 G(x) 去除收到的整个码字。
  • 如果余数为0，则认为数据无误。
  • 如果余数不为0，则表示数据出错。

• 特点：

  • 检错能力非常强，可以检测出几乎所有类型的常见错误。
  • 硬件实现简单（使用移位寄存器和异或门）。
  • 通常不用于自动纠错，而是要求重传。广泛应用于网络通信和磁盘存储。