目录

CRC码错误检测能力详解

一、CRC核心机制：多项式除法（模2运算）

二、CRC 检测能力深度剖析

1. 检测所有单位错 (Single-bit Errors)

2. 检测所有奇数位错 (Odd-number-of-bit Errors)

3. 检测所有两位错 (Double-bit Errors)

4. 检测所有突发长度 ≤ r 的突发错 (Burst Errors of Length ≤ r)

5. 检测突发长度 = r + 1 的突发错 (Burst Errors of Length = r + 1)

6. 检测突发长度 > r + 1 的突发错 (Burst Errors of Length > r + 1)

三、总结与关键点提炼

四、结论

---

CRC码错误检测能力详解

一、CRC核心机制：多项式除法（模2运算）

CRC的核心在于利用生成多项式（Generator Polynomial）进行多项式除法运算。整个过程基于模2运算（即异或运算）：

1. 数据表示： 任何长度为 k 位的待发送数据 D 都可以表示为一个 k-1 次二进制系数多项式 D(X)。例如，数据 1101 对应 D(X) = X³ + X² + 1。

2. 生成多项式： 使用一个双方预先约定的、次数为 r 的生成多项式 G(X)。其二进制表示有 r+1 位（最高位和最低位必须是1）。例如，G(X) = X³ + X + 1 对应二进制 1011（r=3）。

3. 校验位产生：

   • 在原始数据 D(X) 末尾添加 r 个 0，得到新的多项式 Xʳ * D(X)。这相当于将数据位左移 r 位。

   • 将 Xʳ * D(X) 除以 G(X)，使用模2除法。

   • 得到 余数多项式 R(X)（次数小于 r）。

   • 将 R(X) 的二进制系数作为 r 位的 CRC 校验码（冗余码）。

4. 发送帧构造： 将原始数据 D 与计算得到的 r 位校验码拼接起来，形成最终的发送码字 T(X) = Xʳ * D(X) + R(X)。这个 T(X) 有一个关键特性：它能被 G(X) 整除（模2）。因为：
   T(X) = Xʳ * D(X) + R(X)
   根据除法定义： Xʳ * D(X) = Q(X) * G(X) + R(X) （Q(X) 是商）
   所以： T(X) = Q(X) * G(X) + R(X) + R(X) = Q(X) * G(X) （模2运算下 R(X) + R(X) = 0）

5. 接收端校验：

   • 接收端收到码字 T'(X)（可能包含传输错误）。

   • 将 T'(X) 除以相同的 G(X)（模2除法）。

   • 如果余数为 0： 认为传输没有错误（或发生了无法检测的错误）。

   • 如果余数不为 0： 确认传输发生了错误。

核心检测原理： 传输错误会使接收到的多项式 T'(X) 不等于发送的 T(X)。如果 T'(X) - T(X)（即错误图样多项式 E(X)）不能被 G(X) 整除，那么 T'(X) 除以 G(X) 的余数就不为零，错误就能被检测出来。

二、CRC 检测能力深度剖析

1. 检测所有单位错 (Single-bit Errors)

• 错误图样： E(X) = Xⁱ (只有第 i 位出错，由 0 变 1 或 1 变 0)。

• 检测条件： G(X) 是否能整除 E(X) = Xⁱ？这要求 G(X) 是 Xⁱ 的因子。因为 Xⁱ 只有一个因子 X（在二进制域中），所以检测所有单位错的条件是 G(X) 包含 X⁰ 项（即常数项为 1）。

• 结论： 所有标准的 CRC 生成多项式 G(X) 的最低次项都是 X⁰（即二进制表示最低位是 1）。因此，CRC 码能 100% 检测所有单位错。

2. 检测所有奇数位错 (Odd-number-of-bit Errors)

• 错误图样： E(X) 有奇数个系数为 1 的项（即奇数个比特翻转）。

• 检测条件： 关键在于 G(X) 是否具有一个特殊的代数性质：它是一个 本原多项式 (Primitive Polynomial) 或者是包含 (X + 1) 因子的多项式。更直接的条件是：G(X) 必须包含 (X + 1) 作为因子。

• 原理： 模2运算下，E(X) 能被 (X + 1) 整除的充要条件是 E(X) 有偶数个非零项（即偶数个比特翻转）。证明如下：

  • 计算 E(1)（将 X=1 代入 E(X)）：在模2下，1ⁱ 总是 1。

  • E(1) 等于 E(X) 中所有系数的模2和（因为 Xⁱ 项代入 X=1 后就是其系数）。

  • 系数为 1 的项有奇数个 => 系数模2和为 1 => E(1) = 1。

  • 系数为 1 的项有偶数个 => 系数模2和为 0 => E(1) = 0。

  • 根据多项式因式定理：(X + 1) 整除 E(X) 当且仅当 E(1) = 0。

  • 因此，(X + 1) 能整除 E(X) 当且仅当 E(X) 有偶数个 1（即偶数位错）。

• 结论： 如果 G(X) 包含 (X + 1) 因子，那么所有含有奇数个 1 的错误图样 E(X) 都不能被 (X + 1) 整除，自然也不能被整个 G(X) 整除（因为 G(X) 包含 (X + 1)）。因此，所有奇数位错都能被检测到。 绝大多数实用的 CRC 生成多项式都满足 G(1) = 0（即 G(X) 有偶数个非零系数），这表明 (X + 1) 是其因子。

3. 检测所有两位错 (Double-bit Errors)

• 错误图样： E(X) = Xⁱ + Xʲ (i > j，表示第 i 位和第 j 位同时出错)。

• 检测条件： CRC 无法检测两位错的条件是 G(X) 能整除 E(X) = Xʲ(Xⁱ⁻ʲ + 1)。这意味着 G(X) 必须是 (Xⁱ⁻ʲ + 1) 的一个因子。

• 关键点： (Xᵐ + 1) 可以被分解为一些次数小于等于 m 的不可约多项式的乘积。G(X) 要避免成为任何 (Xᵐ + 1) 的因子（对于 m 小于最大可能帧长）。

• 结论： 如果生成多项式 G(X) 选择的足够好（例如是一个 本原多项式 或具有高次数的不可约多项式），那么对于实际通信中可能出现的帧长度（k），G(X) 不会整除任何形如 (Xᵐ + 1) 的多项式（m 在 1 到 k-1 之间）。因此，精心选择的 CRC 生成多项式可以保证检测所有发生在帧长度范围内的两位错。 标准化的 CRC 多项式（如 CRC-16, CRC-32）都满足此条件。

4. 检测所有突发长度 ≤ r 的突发错 (Burst Errors of Length ≤ r)

• 突发错误定义： 一串连续的比特错误，其中第一个和最后一个比特是错误的，中间的比特可能错也可能不错。突发错误的长度定义为从第一个错误比特到最后一个错误比特之间的位数（包含首尾）。

• 错误图样： E(X) = Xʲ * B(X)。其中：

  • j 是突发错误在接收帧中的起始位置（低位）。

  • B(X) 是一个次数为 (l - 1) 的多项式（l 是突发长度），其最高次项系数和常数项系数都为 1（因为突发错误的首位和末位必须是 1）。B(X) 描述了突发错误的模式。

• 检测条件： CRC 无法检测该突发错误的条件是 G(X) 能整除 E(X) = Xʲ * B(X)。由于 G(X) 包含 X⁰ 项（常数项 1），它不能整除 Xʲ（除非 j=0，这不影响结论）。因此，G(X) 能整除 E(X) 的必要条件是 G(X) 能整除 B(X)。

• 关键点： B(X) 是一个次数为 (l - 1) 的多项式。G(X) 是一个次数为 r 的多项式。

• 结论：

  • 如果突发长度 l ≤ r，则 B(X) 的次数 (l - 1) < r。

  • G(X) 是一个 r 次多项式。一个 r 次多项式 G(X) 不可能 整除一个次数比它低的多项式 B(X)（(l - 1) < r），除非 B(X) 是零多项式（这对应于没有错误）。

  • 因此，任何长度 l ≤ r 的突发错误都必然导致 E(X) 不能被 G(X) 整除，从而能被 100% 检测出来。

5. 检测突发长度 = r + 1 的突发错 (Burst Errors of Length = r + 1)

• 错误图样： E(X) = Xʲ * B(X)。其中 B(X) 是一个次数为 r 的多项式（因为 l = r + 1, (l - 1) = r），其最高次项系数和常数项系数必须为 1。

• 检测条件： CRC 无法检测该突发错误的条件是 G(X) 能整除 E(X) = Xʲ * B(X)。如前所述，这等价于 G(X) 能整除 B(X)。

• 关键点： B(X) 和 G(X) 都是 r 次多项式。G(X) 能整除 B(X) 意味着 B(X) 必须是 G(X) 的一个倍式。由于两者次数相同，唯一的可能是 B(X) 正好等于 G(X) 本身（或 c * G(X), c 是常数，但在模2下 c=1），即 B(X) = G(X)。

• 分析：

  • 突发错误长度 l = r + 1。

  • 突发错误图样 B(X) 是一个 r 次多项式，其首项系数（对应突发错误的第一位）和常数项系数（对应突发错误的最后一位）固定为 1。

  • 要使 B(X) = G(X)，意味着突发错误图样 B(X) 的二进制序列必须精确匹配生成多项式 G(X) 的二进制序列（r+1 位）。

  • 在 B(X) 的 r+1 位中，最高位（Xʳ 系数）和最低位（X⁰ 系数）是固定的 1。中间的 (r - 1) 位可以是 0 或 1，共有 2ʳ⁻¹ 种可能的不同突发错误图样 B(X)。

  • 其中只有一种特定的图样 B(X) 满足 B(X) = G(X)，会导致 G(X) 整除 E(X)，从而使 CRC 校验通过（漏检）。

• 概率计算：

  • 总的可能突发长度 r+1 的错误图样 B(X) 数量：2ʳ⁻¹ (中间 r-1 位自由变化)。

  • 导致漏检的图样数量：1 (只有 B(X) = G(X) 这一种)。

  • 因此，漏检概率 P(miss) = 漏检图样数 / 总图样数 = 1 / 2ʳ⁻¹。

  • 检测概率 P(detect) = 1 - P(miss) = 1 - 1/2ʳ⁻¹。

• 结论： 对于一个 r 次生成多项式产生的 CRC 码，它能检测 1 - 1/2ʳ⁻¹ 的突发长度为 r + 1 的错误。例如：

  • r = 3：检测概率 = 1 - 1/2² = 1 - 1/4 = 75%

  • r = 16 (如 CRC-16)：检测概率 = 1 - 1/2¹⁵ = 1 - 1/32768 ≈ 99.997%

  • r = 32 (如 CRC-32)：检测概率 = 1 - 1/2³¹ = 1 - 1/2147483648 ≈ 99.99999995%

6. 检测突发长度 > r + 1 的突发错 (Burst Errors of Length > r + 1)

• 错误图样： E(X) = Xʲ * B(X)。其中 B(X) 是一个次数大于 r 的多项式（l > r + 1 => (l - 1) > r），其最高次项系数和常数项系数为 1。

• 检测条件： 无法检测的条件仍是 G(X) 能整除 E(X)，等价于 G(X) 能整除 B(X)。

• 分析： B(X) 的次数 (l - 1) > r。G(X) 能整除 B(X) 意味着 B(X) 必须是 G(X) 的一个倍式，即 B(X) = Q(X) * G(X)。其中 Q(X) 是一个次数为 (l - 1 - r) > 0 的多项式。

• 概率计算：

  • 总的可能突发长度 l > r + 1 的错误图样 B(X) 数量：首位和末位固定为 1，中间 (l - 2) 位自由变化，共有 2ˡ⁻² 种。

  • B(X) 是 G(X) 的倍式 (B(X) = Q(X) * G(X))。Q(X) 是一个次数为 (l - 1 - r) 的多项式，其系数自由变化（但 B(X) 的首位 1 限制了 Q(X) 的首位）。

  • 满足 B(X) = Q(X) * G(X) 且 B(X) 首尾为 1 的 Q(X) 的数量：Q(X) 需要 (l - r - 1) 个系数（除了最高位可能受约束）。最宽松的估计，漏检图样数量最多为 2ˡ⁻ʳ⁻¹ (考虑 Q(X) 的自由度)。

  • 漏检概率 P(miss) ≤ 漏检图样数 / 总图样数 ≤ 2ˡ⁻ʳ⁻¹ / 2ˡ⁻² = 1 / 2ʳ⁻¹。

• 结论： 对于一个 r 次生成多项式产生的 CRC 码，它能检测 至少 1 - 1/2ʳ⁻¹ 的突发长度大于 r + 1 的错误。这是一个非常强的保证，表明随着 r 的增加，漏检概率呈指数级下降。即使对于很长的突发错误，CRC 的检测能力也非常高。

三、总结与关键点提炼

1. 核心机制： CRC 通过模2多项式除法产生校验码，发送码字 T(X) 能被生成多项式 G(X) 整除。接收端通过校验余数是否为0检测错误。

2. 100% 检测能力：

   • 所有单位错： 要求 G(X) 常数项为 1 (所有标准 CRC 满足)。

   • 所有奇数位错： 要求 G(X) 包含 (X + 1) 因子 (绝大多数标准 CRC 满足)。

   • 所有两位错： 要求 G(X) 选择得当（如本原多项式或高次不可约多项式），标准 CRC 满足。

   • 所有突发长度 l ≤ r 的错误： 这是由 G(X) 的阶数 r 直接保证的数学性质。

3. 高概率检测能力：

   • 突发长度 l = r + 1 的错误： 检测概率为 1 - 1/2ʳ⁻¹。随着 r 增加，概率迅速趋近于 100%。

   • 突发长度 l > r + 1 的错误： 检测概率至少为 1 - 1/2ʳ⁻¹。同样，随着 r 增加，漏检概率极小。

4. r 的意义：

   • r 是 生成多项式 G(X) 的次数，也是 CRC 校验码的位数。

   • 它直接决定了 可保证检测的突发错误最大长度 (r)。

   • 它决定了 检测长度 ≥ r+1 的突发错误的能力 (1 - 1/2ʳ⁻¹)，r 越大，此概率越接近 100%。

   • 它影响了 检测其他类型错误（如两位错）的可靠性（r 越大，生成多项式可选择范围越大，避免整除 Xᵐ + 1 更容易）。

5. 实际应用：

   • r 的选择： 根据信道错误特性和对可靠性的要求选择。常见的有：

     • r = 8 (CRC-8)：用于短帧、低要求场景。

     • r = 16 (CRC-16-CCITT, CRC-16-IBM)：广泛用于链路层（如PPP, HDLC）、Modbus、USB等，提供强健的检测能力。

     • r = 32 (CRC-32)：用于要求极高的场景，如以太网（IEEE 802.3）、SATA、PNG图像、ZIP/GZIP压缩文件等。其检测能力 (1 - 1/2³¹) 在大多数实际应用中可视为万无一失。

   • 生成多项式选择： 标准化多项式（如CRC-16-CCITT 0x1021, CRC-32 0x04C11DB7）经过精心设计，不仅满足上述数学要求，还具有最优的汉明距离等特性，以最大化检测各种错误模式的能力。

   • 效率： CRC 计算通过移位寄存器和异或门高效实现，硬件和软件实现都非常快速，开销小。

四、结论

CRC 码是一种高效且强大的错误检测码。由 r 位生成多项式产生的 CRC 码，其检测能力可总结如下：

• 100% 检测： 所有单位错、所有奇数位错、所有两位错（在合理帧长内）、所有突发长度 ≤ r 的突发错。

• 高概率检测 (1 - 1/2ʳ⁻¹)： 突发长度 = r + 1 的突发错。

• 至少高概率检测 (≥ 1 - 1/2ʳ⁻¹)： 突发长度 > r + 1 的突发错。

r 是决定 CRC 检测能力的核心参数。更大的 r 提供更强的保证检测能力和更高的长突发错误检测概率，代价是增加了额外的校验位开销。由于其优异的检测性能、计算效率和实现的简便性，CRC 码成为计算机网络、数据存储、通信系统等众多领域中应用最广泛的错误检测技术之一。理解其背后的多项式理论（模2运算、整除性）是掌握其强大检测能力本质的关键。