數學的優雅：剖開CRC的多項式除法核心
看似復雜的CRC校驗，其核心建立在優雅的數學基礎之上。本文將為您揭開CRC算法的數學面紗，讓您真正理解多項式除法的精妙之處。
模2運算：CRC世界的特殊算術
CRC計算建立在一種特殊的代數系統上—— 模2運算 （Modulo-2 Arithmetic）。這與我們熟悉的十進制算術有很大不同。
模2加法和減法
在模2世界中，加法和減法有一個驚人的特性： 它們其實就是異或（XOR）操作 ！
| 輸入 A | 輸入 B | 結果 (A + B mod 2) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
重要特性 ：
- 1 + 1 = 0（而不是2）
- 沒有進位概念
- 加法和減法結果相同：A - B = A + B
這種特性非常適合數字電路實現，因為異或門既簡單又高效。
模2乘法和除法
模2乘法和除法與我們熟悉的二進制乘除類似，但使用模2加法（即異或）進行計算：
乘法示例 ：
1101 (被乘數)
× 101 (乘數)
--------11010000
1101
--------
111001 (結果)
關鍵點 ：乘法通過移位和模2加法完成，沒有傳統算術中的進位加法。
多項式表示：二進制數據的另一種視角
CRC算法的精妙之處在于它將二進制數據視為多項式。
如何將二進制轉換為多項式？
每一位二進制數代表多項式的一項系數（0或1），而位的位置代表x的指數。
示例 ：
- 二進制數
1101轉換為多項式：1·x3 + 1·x2 + 0·x1 + 1·x? = x3 + x2 + 1 - 二進制數
1011轉換為多項式：x3 + x + 1
生成多項式：CRC的核心
每個CRC變體都有一個特定的 生成多項式 （Generator Polynomial），它決定了CRC的檢錯能力和計算方式。
常見CRC標準的生成多項式：
- CRC-8: x? + x2 + x + 1 (對應二進制:
100000111) - CRC-16: x1? + x1? + x2 + 1 (對應二進制:
11000000000000101) - CRC-32: x32 + x2? + x23 + x22 + x1? + x12 + x11 + x1? + x? + x? + x? + x? + x2 + x + 1 (對應二進制:
1 00000100 11000001 00011101 10110111)
CRC計算過程：一步步分解
現在讓我們將模2運算和多項式表示結合起來，看看完整的CRC計算過程。
步驟1：原始數據補零
假設我們要計算數據 1101 的CRC，使用生成多項式 1011（即x3 + x + 1）：
- 在原始數據末尾添加 n個零 ，其中n是生成多項式的次數（位數-1）
- 生成多項式
1011是3次多項式（最高次項是x3），所以添加3個零 - 原始數據
1101變為1101000
步驟2：執行模2除法
現在用生成多項式 1011 除補零后的數據 1101000：
1110 ← 商（通常丟棄不用）--------
1011 ) 1101000 ← 被除數（補零后的數據）1011 ← 對齊最高位，執行模2減（異或）-----1100 ← 中間結果1011 ← 生成多項式對齊新最高位-----1110 ← 中間結果1011 ← 生成多項式對齊新最高位-----1010 ← 中間結果1011 ← 生成多項式對齊新最高位-----001 ← 余數（這就是CRC值！）
步驟3：得到CRC校驗值
除法得到的余數 001 就是我們要求的CRC校驗值。由于余數位數應比生成多項式次數少1，這里我們得到3位余數中的最后2位是有效位，但通常我們會保留所有位作為CRC值。
完整CRC碼
將原始數據與CRC值組合：1101 + 001 = 1101001
接收方可以使用同樣的生成多項式驗證這個數據的完整性。
為什么多項式除法能檢測錯誤？
現在我們來解答這個關鍵問題：為什么這種方法能有效檢測錯誤？
數學原理
- 發送方 ：計算數據D(x)除以G(x)的余數R(x)，發送[D(x) + R(x)]
- 接收方 ：用G(x)除接收到的數據[D(x) + R(x)]
如果傳輸沒有錯誤：
- [D(x) + R(x)] / G(x) = D(x)/G(x) + R(x)/G(x)
- 由于R(x)是D(x)/G(x)的余數，所以D(x) = Q(x)·G(x) + R(x)
- 因此[D(x) + R(x)] = Q(x)·G(x) + R(x) + R(x) = Q(x)·G(x) + 0
- 因為R(x) + R(x) = 0（模2加法）
- 所以接收方除法余數為0，表明數據正確
如果傳輸有錯誤：
- 接收到的數據變為[D(x) + R(x) + E(x)]，其中E(x)是錯誤多項式
- 除以G(x)得到的余數不為0（除非E(x)恰好能被G(x)整除，這種情況概率很低）
檢錯能力分析
CRC能夠檢測：
- 所有單比特錯誤 ：E(x) = x?，不能被G(x)整除（因為G(x)至少有2項）
- 所有雙比特錯誤 ：E(x) = x? + x? = x?(x??? + 1)，只要G(x)選擇適當
- 任何奇數個錯誤 ：如果G(x)包含因子(x+1)
- 大多數突發錯誤 ：特別是長度小于等于生成多項式次數的突發錯誤
實際示例：手動計算CRC-4
讓我們用一個更完整的例子鞏固理解：
輸入數據 ：11010111 (8 bits)
生成多項式 ：10011 (x? + x + 1, CRC-4)
- 補零 ：生成多項式次數為4，補4個零 →
110101110000 - 模2除法 ：
逐位計算過程：110101110000 ÷ 10011第一步： 11010 ⊕ 10011 = 10011
第二步： 10011 ⊕ 10011 = 00000
第三步： 00001 ⊕ 00000 = 00001
第四步： 00001 ⊕ 00000 = 00001
第五步： 00001 ⊕ 00000 = 00001
第六步： 00001 ⊕ 00000 = 00001
第七步： 00000 ⊕ 00000 = 00000
第八步： 00000 ⊕ 00000 = 00000余數：0001 → CRC值 = `0001`
- 完整傳輸數據 ：
110101110001
接收方用同樣的生成多項式除接收到的數據，余數為0則表明數據正確。
總結與展望
通過本文，我們深入探討了CRC算法的數學基礎：
- ? 模2運算是CRC計算的數學基礎，特別是異或操作
- ? 多項式表示將二進制數據抽象為代數形式
- ? 模2除法是CRC計算的核心操作
- ? 數學原理保證了CRC的強大檢錯能力
