循環冗餘檢查

**循環冗餘校驗**（英語：**Cyclic redundancy check**，通稱「**CRC**」）是一種根據網路數據封包或電腦檔案等數據產生簡短固定位數驗證碼的一種雜湊函式，主要用來檢測或校驗數據傳輸或者儲存後可能出現的錯誤。生成的數字在傳輸或者儲存之前計算出來並且附加到數據後面，然後接收方進行檢驗確定數據是否發生變化。由於本函式易於用二進制的電腦硬體使用、容易進行數學分析並且尤其善於檢測傳輸通道干擾引起的錯誤，因此獲得廣泛應用。此方法是由 W. Wesley Peterson 於 1961 年發表。

## 簡介

CRC 為校驗和的一種，是兩個位元組數據流採用二進制除法（沒有進位，使用 XOR 來代替減法）相除所得到的餘數。其中被除數是需要計算校驗和的資訊數據流的二進制表示；除數是一個長度為 $(n+1)$ 的預定義（短）的二進制數，通常用多項式的系數來表示。在做除法之前，要在資訊數據之後先加上 $n$ 個 0。

CRC 是基於有限域 **GF(2)**（即除以 2 的同餘）的多項式環。簡單的來說，就是所有系數都為 0 或 1（又叫做二進制）的多項式系數的集合，並且集合對於所有的代數操作都是封閉的。例如：

　
: $(x^{3}+x)+(x+1)=x^{3}+2x+1\equiv x^{3}+1$

2 會變成 0，因為對系數的加法運算都會再取 2 的模數。乘法也是類似的：

　
: $(x^{2}+x)(x+1)=x^{3}+2x^{2}+x\equiv x^{3}+x$

同樣可以對多項式作除法並且得到商和餘數。例如，如果用 _x_3 + _x_2 + _x_ 除以 _x_ + 1。會得到：

　
: ${\frac {(x^{3}+x^{2}+x)}{(x+1)}}=(x^{2}+1)-{\frac {1}{(x+1)}}$

也就是說，

　
: $(x^{3}+x^{2}+x)=(x^{2}+1)(x+1)-1$

等價於：

　
: $(x^{2}+x+1)x=(x^{2}+1)(x+1)-1$

這裡除法得到了商 _x_2 + 1 和餘數 - 1，因為是奇數所以最後一位是 1。

字串中的每一位其實就對應了這樣類型的多項式的系數。為了得到 CRC，首先將其乘以 $x^{n}$ ，這裡 $n$ 是一個固定多項式的**階數**，然後再將其除以這個固定的多項式，餘數的系數就是 CRC。

在上面的等式中， $x^{2}+x+1$ 表示了本來的資訊位是 `111`, $x+1$ 是所謂的**鑰匙**，而餘數 $1$ （也就是 $x^{0}$ ）就是 CRC. key 的最高次為 1, 所以將原來的資訊乘上 $x^{1}$ 來得到 $x^{3}+x^{2}+x$ ，也可視為原來的資訊位補 1 個零成為 `1110`。

一般來說，其形式為：

　
: $M(x)\cdot x^{n}=Q(x)\cdot K(x)-R(x)$

這裡 M (x) 是原始的資訊多項式。K (x) 是 $n$ 階的「鑰匙」多項式。 $M(x)\cdot x^{n}$ 表示了將原始資訊後面加上 $n$ 個 0。R (x) 是餘數多項式，即是 CRC「校驗和」。在通訊中，發送者在原始的資訊數據 M 後附加上 $n$ 位的 R（替換本來附加的 0）再發送。接收者收到 M 和 R 後，檢查 $M(x)\cdot x^{n}+R(x)$ 是否能被 $K(x)$ 整除。如果是，那麼接收者認為該資訊是正確的。值得注意的是 $M(x)\cdot x^{n}+R(x)$ 就是發送者所想要發送的數據。這個串又叫做 _codeword_.

CRCs 經常被叫做「校驗和」，但是這樣的說法嚴格來說並不是準確的，因為技術上來說，校驗「和」是通過加法來計算的，而不是 CRC 這裡的除法。

「糾錯碼」（Error–Correcting Codes，簡稱 ECC）常常和 CRCs 緊密相關，其語序糾正在傳輸過程中所產生的錯誤。這些編碼方式常常和數學原理緊密相關。例如常見於通訊或資訊傳遞上 BCH 碼、前向錯誤更正、錯誤檢測與糾正等。

## 實現

## 變體

CRC 有幾種不同的變體：

* `shiftRegister` 可以逆向使用，這樣就需要檢測最低位的值，每次向右移動一位。這就要求 `polynomial` 生成逆向的數據位結果。_實際上這是最常用的一個變體。_
* 可以先將數據最高位讀到移位暫存器，也可以先讀最低位。在通訊協定中，為了保留 CRC 的突發錯誤檢測特性，通常按照物理層發送數據位的方式計算 CRC。
* 為了檢查 CRC，需要在全部的碼字上進行 CRC 計算，而不是僅僅計算訊息（Message）的 CRC 並把它與 CRC 比較。如果結果是 0，那麼就通過這項檢查。這是因為碼字 $M(x)\cdot x^{n}+R(x)=Q(x)\cdot K(x)$ 可以被 $K(x)$ 整除。
* 移位暫存器可以初始化成 1 而不是 0。同樣，在用演算法處理之前，訊息的最初 $n$ 個數據位要反相。這是因為未經修改的 CRC 無法區分只有起始 0 的個數不同的兩條訊息。而經過這樣的反相過程，CRC 就可以正確地分辨這些訊息了。
* CRC 在附加到訊息數據流（Message stream）的時候可以進行位元組反相。這樣，CRC 的檢查可以用直接的方法計算訊息的 CRC、反相、然後與訊息數據流中的 CRC 比較這個過程來完成，也可以通過計算全部的訊息來完成。在後一種方法中，正確訊息的結果不再是 0，而是 $\sum _{i=n}^{2n-1}x^{i}$ 除以 $K(x)$ 得到的結果。這個結果叫作核驗多項式 $C(x)$ ，它的十六進製表示也叫作幻數。

按照慣例，使用 CRC-32 多項式以及 CRC-16-CCITT 多項式時通常都要反相。CRC-32 的核驗多項式是 
 $C(x)=x^{31}+x^{30}+x^{26}+x^{25}+x^{24}+x^{18}+x^{15}+x^{14}+x^{12}+x^{11}+x^{10}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x+1$ 。

* 對於要處理的資料 M (x) 有前置 0 時，用 $x^{m}L(x)$ 與 $M(x).x^{n}$ 兩式相加作反相運算，使得前置的 0 變成 1 後，再作 mod 2 運算得到 CRC。公式：

 $M(x)\cdot x^{n}+x^{m}L(x)=Q(x)\cdot K(x)+R(x)$ 
 $L(x)\,\!$ $=\sum _{i=0}^{n-1}x^{i}$ 
 $T(x)=M(x)\cdot x^{n}+L(x)+R(x)$ 
例： $M(x)=01111$ 
 $K(x)=x^{3}+x^{2}+1=1101$ ，這裡可知 $n=3$ 
 $M(x).x^{3}=01111000$ 
因 $\sum _{i=0}^{n-1}x^{i}$ ， $n=3$ 故 L (x) 階數從 2 開始 
 $L(x)=x^{2}+x^{1}+x^{0}=111$ 
用 $x^{m}L(x)$ 求得一組 n 個 1 及 m 個 0 以便與 $M(x).x^{n}$ 相加 
令 m = 5， $X^{m}L(x)=X^{5}L(x)=11100000$ （bitwise shift） 
 $M(x).x^{n}+x^{m}L(x)=01111000+11100000=10011000$ （使 M 前置的 0 變成 1） 
用 $10011000$ mod2 $K(x)$ 求得餘 R (x)= 011 
 $T(x)=M(x).x^{n}+L(x)+R(x)=01111000+111+011=01111100$ 送出 
接收端 L (x) = 111 且開頭不為 1 => m = 5 
可反推 $M(x).x^{n}+x^{m}L(x)+R(x)=01111000+11100000+011=10011011$ 
用 10011011 mod2 1101 可驗證能被 K (x) 整除。

## 錯誤檢測能力

CRC 的錯誤檢測能力依賴於關鍵多項式的階次以及所使用的特定關鍵多項式。_誤碼多項式_ $E(x)$ 是接收到的訊息碼字與正確訊息碼字的_互斥或_結果。當且僅當誤碼多項式能夠被 CRC 多項式整除的時候 CRC 演算法無法檢查到錯誤。

* 由於 CRC 的計算基於除法，任何多項式都無法檢測出一組全為零的數據出現的錯誤或者前面丟失的零。但是，可以根據 CRC 的變體來解決這個問題。
* 所有只有一個數據位的錯誤都可以被至少有兩個非零系數的任意多項式檢測到。誤碼多項式是 $x^{k}$ ，並且 $x^{k}$ 只能被 $i\leq k$ 的多項式 $x^{i}$ 整除。
* CRC 可以檢測出所有間隔距離小於多項式階次的雙位錯誤，在這種情況下的誤碼多項式是

```
$E(x)=x^{i}+x^{k}=x^{k}\cdot (x^{i-k}+1),\;i>k$。
```

如上所述， $x^{k}$ 不能被 CRC 多項式整除，它得到一個 $x^{i-k}+1$ 項。根據定義，滿足多項式整除 $x^{i-k}+1$ 的 ${i-k}$ 最小值就是多項式的階次。最高階次的多項式是本原多項式，帶有二進制系數的 $n$ 階多項式

## CRC 多項式規範

下面的表格略去了「初始值」、「反射值」以及「最終互斥或值」。

* 對於一些複雜的校驗和來說這些十六進制數值是很重要的，如 CRC-32 以及 CRC-64。通常小於 CRC-16 的 CRC 不需要使用這些值。
* 通常可以通過改變這些值來得到各自不同的校驗和，但是校驗和演算法機制並沒有變化。

CRC 標準化問題

* 由於 CRC-12 有三種常用的形式，所以 CRC-12 的定義會有歧義
* 在應用的 CRC-8 的兩種形式都有數學上的缺陷。
* 據稱 CRC-16 與 CRC-32 至少有 10 種形式，但沒有一種在數學上是最優的。
* 同樣大小的 CCITT CRC 與 ITU CRC 不同，這個機構在不同時期定義了不同的校驗和。

## 常用 CRC（按照 ITU-IEEE 規範）

## CRC 與數據完整性

儘管在錯誤檢測中非常有用，CRC 並不能可靠地驗證數據完整性（即數據沒有發生任何變化），這是因為 CRC 多項式是線性結構，可以非常容易地_故意_改變數據而維持 CRC 不變，參見 CRC and how to Reverse it （頁面存檔備份，存於網際網路檔案館）中的證明。可以用 Message authentication code 驗證數據完整性。

### CRC 發生碰撞的情況

與所有其它的雜湊函式一樣，在一定次數的碰撞測試之後 CRC 也會接近 100% 出現碰撞。CRC 中每增加一個數據位，碰撞機率就會減少接近 50%，如 CRC-20 與 CRC-21 相比。

* 理論上來講，CRC64 的碰撞概率大約是每 18×1018 個 CRC 碼出現一次。
* 由於 CRC 的不分解多項式特性，所以經過合理設計的較少位數的 CRC 可能會與使用較多數據位但是設計很差的 CRC 的效率相媲美。在這種情況下 CRC-32 幾乎同 CRC-40 一樣優秀。

### 設計 CRC 多項式

生成多項式的選擇是 CRC 演算法實現中最重要的部分，所選擇的多項式必須有最大的錯誤檢測能力，同時保證總體的碰撞概率最小。多項式最重要的屬性是它的長度，也就是最高非零系數的數值，因為它直接影響著計算的校驗和的長度。

最常用的多項式長度有

* 9 位（CRC-8）
* 17 位（CRC-16）
* 33 位（CRC-32）
* 65 位（CRC-64）

在構建一個新的 CRC 多項式或者改進現有的 CRC 時，一個通用的數學原則是使用滿足所有模運算不可分解多項式約束條件的多項式。

* 這種情況下的不可分解是指多項式除了 1 與它自身之外不能被任何其它的多項式整除。

生成多項式的特性可以從演算法的定義中推導出來：

* 如果 CRC 有多於一個的非零系數，那麼 CRC 能夠檢查出輸入訊息中的所有單數據位錯誤。
* CRC 可以用於檢測短於 2k 的輸入訊息中的所有雙位錯誤，其中 k 是多項式的最長的不可分解部分的長度。
* 如果多項式可以被 x+1 整除，那麼不存在可以被它整除的有奇數個非零系數的多項式。因此，它可以用來檢測輸入訊息中的奇數個錯誤，就像奇偶校驗函式那樣。

## 參見

總的分類

* 糾錯碼
* 校驗和演算法列表
* 奇偶校驗位

特殊技術參考

* Adler-32
* Fletcher's checksum

## 參考文獻

## 外部連結

* Tutorial and C++ implementation of CRC (所參照網址代碼執行存在問題)
* Cyclic redundancy check - a simple guide to what it means for your data, CD and DVD discs. http://www.softwarepatch.com/tips/cyclic-redundancy.html （頁面存檔備份，存於網際網路檔案館）
* _The CRC Pitstop_
* Williams, R.（1993-09）_A Painless Guide to CRC Error Detection Algorithms_
* _Understanding Cyclic Redundancy Check_
* Black, R.（1994-02）_Fast CRC32 in Software_—Algorithm 4 is used in Linux and info-zip's zip and unzip.
* Barr, M.（_1999-11_, _1999-12_, _2000-01_）checksums, CRCs, and their source code. Embedded Systems Programming
* CRC32: Generating a checksum for a file, C++ implementation by Brian Friesen
* Online Tool to compute common CRCs（8/16/32/64）from strings
* Online CRC calculator （頁面存檔備份，存於網際網路檔案館）
* Online CRC Tool: Generator of synthesizable CRC functions （頁面存檔備份，存於網際網路檔案館）
* Online Char(ASCII), HEX, Binary, Base64, etc... Encoder/Decoder with MD2, MD4, MD5, SHA1+2, CRC, etc. hashing algorithms
* CRC16 to CRC64 collision research （頁面存檔備份，存於網際網路檔案館）
* Reversing CRC – Theory and Practice. （頁面存檔備份，存於網際網路檔案館）