校验码

校验码详解

校验码是计算机系统中用于检测和纠正数据传输或存储过程中出现错误的编码方式，其核心原理是通过增加冗余信息（校验位）来提高数据的可靠性。下面将从核心概念到具体校验码类型进行详细说明。

校验码的核心概念

码距

• 定义：在一组编码（如二进制编码）中，任意两个不同码字之间对应位不同的数量称为 “距离”，其中最小的那个距离即为该编码的码距。
• 示例：
  若编码为00和01，两码字只有 1 位不同，码距为 1；
  若编码为000和111，3 位均不同，码距为 3。
• 意义：码距越大，检错和纠错能力越强：
  • 码距 = 1：无检错能力（无法区分合法编码与错误编码）。
  • 码距≥2：可检测 1 位错误。
  • 码距≥3：可检测 2 位错误，或纠正 1 位错误。

检错与纠错

• 检错：通过校验码判断数据是否存在错误（如传输中某一位被翻转），但不明确错误位置，也无法修正。
• 纠错：不仅能检测错误，还能确定错误位置并自动修正，需要更强的冗余信息支持。

常用校验码类型

奇偶校验码

• 编码规则：
  在有效信息位后添加 1 位校验位，使整个校验码中 “1” 的总数满足：
  • 奇校验：1 的总数为奇数（如信息位1010，校验位为0，结果10100含 2 个 1，需补 1 使总数为 3，即10101）。
  • 偶校验：1 的总数为偶数（如信息位1010，校验位为1，结果10101含 3 个 1，需补 1 使总数为 4，即10101→修正为10100）。
• 优缺点：
  • 优点：实现简单，仅需 1 位冗余位，适用于低速传输场景（如 ASCII 码传输）。
  • 缺点：只能检测奇数个错误（如 1 位、3 位错误），无法检测偶数个错误，且完全不能纠错。

CRC 循环冗余校验码

• 编码规则：
  1. 将 k 位有效信息表示为多项式M(x)，选择一个 r+1 位的生成多项式G(x)（预先约定）。
  2. 计算M(x) * x^r（即信息位后补 r 个 0），再通过模二除法（不进位加法、不借位减法，等价于异或运算）除以G(x)，得到余数R(x)（r 位）。
  3. 最终校验码为M(x) * x^r + R(x)（信息位 + 余数）。
• 检错原理：
  接收方用同样的G(x)对收到的校验码做模二除法，若余数为 0，则数据大概率正确；若余数非 0，则存在错误（不同错误对应唯一余数，可查表定位错误位，但通常仅用于检错）。
• 优缺点：
  • 优点：检错能力强，可检测出单比特错误、多比特错误、突发错误（长度≤r 的连续错误）。
  • 缺点：需要预先约定生成多项式（如以太网常用G(x)=x^32+x^26+x^23+...+1），且不能纠错。

海明校验码

• 编码规则：
  1. 在有效信息位中插入 k 位校验位，使校验位与信息位形成多个奇偶校验组（每个校验位负责检测特定位置的位）。
  2. 校验位数量 k 与信息位数量 n 需满足公式：2^k ≥ n + k + 1（确保能区分所有可能的错误位置，包括无错情况）。
     例如：n=4（信息位 4 位），需 k=3（2^3=8 ≥ 4+3+1=8）。
• 纠错原理：
  接收方通过各校验组的奇偶性计算 “错误位置码”：
  • 若位置码为 0，无错误；
  • 若位置码为非 0 值，则对应位置的位出错，翻转该位即可纠错。
• 优缺点：
  • 优点：能检测 2 位错误，纠正 1 位错误，冗余位较少（相比 CRC 更高效）。
  • 缺点：实现较复杂，适用于对可靠性要求高的场景（如内存数据校验）。

校验码对比总结

校验码类型	冗余位数量	检错能力	纠错能力	典型应用场景
奇偶校验	1 位	仅检测奇数个错误	无	低速串行通信
CRC 校验	r 位（通常 8-32 位）	单比特、多比特、突发错误	无	以太网、硬盘存储
海明校验	k 位（满足2^k ≥ n+k+1）	检测 2 位错误	纠正 1 位错误	内存、航天器数据传输