循環冗餘校驗

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

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

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

簡介

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³ + x² + 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² + 1和餘數-1，因為是奇數所以最後一位是1。

字串中的每一位其實就對應了這樣類型的多項式的系數。為了得到CRC，首先將其乘以 $x^{n}$ ，這裏 $n$ 是一個固定多項式的階數（英語：Degree of a polynomial），然後再將其除以這個固定的多項式，餘數的系數就是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.

實現

變體

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-1	$x+1$ （用途：硬件，也稱為奇偶校驗位）	0x1 or 0x1 (0x1)
CRC-5-CCITT	$x^{5}+x^{3}+x+1$ （ITU G.704標準）	0xB（0x??）
CRC-5-USB	$x^{5}+x^{2}+1$ （用途：USB信令包）	0x5 or 0x14 (0x9)
CRC-7	$x^{7}+x^{3}+1$ （用途：通訊系統）	0x9 or 0x48 (0x11)
CRC-8-ATM	$x^{8}+x^{2}+x+1$ （用途：ATM HEC, PMBUS （參見SMBUS org[1] （頁面存檔備份，存於互聯網檔案館）））	0x7或0xE0 (0xC1)
CRC-8-CCITT	$x^{8}+x^{7}+x^{3}+x^{2}+1$ （用途：1-Wire 總線）	0x8D
CRC-8-Dallas/Maxim	$x^{8}+x^{5}+x^{4}+1$ （用途：1-Wire bus）	0x31或0x8C
CRC-8	$x^{8}+x^{7}+x^{6}+x^{4}+x^{2}+1$	0xD5（0x??）
CRC-10	$x^{10}+x^{9}+x^{5}+x^{4}+x+1$	0x233（0x????）
CRC-12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1$ （用途：通訊系統）	0x80F或0xF01 (0xE03)
CRC-16-Fletcher	參見Fletcher's checksum	用於Adler-32 A & B CRC
CRC-16-CCITT	$x^{16}+x^{12}+x^{5}+1$ （X25, V.41, Bluetooth, PPP, IrDA）	0x1021或0x8408 (0x0811)
CRC-16-IBM	$x^{16}+x^{15}+x^{2}+1$ （用途：Modbus）	0x8005或0xA001 (0x4003)
CRC-16-BBS	$x^{16}+x^{15}+x^{10}+x^{3}$ （用途：XMODEM協定）	0x8408（0x????）
CRC-32-Adler	參見Adler-32	參見Adler-32
CRC-32-MPEG2	參見IEEE 802.3	參見IEEE 802.3
CRC-32-IEEE 802.3	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$	0x04C11DB7或0xEDB88320 (0xDB710641)
CRC-32C(Castagnoli)	$x^{32}+x^{28}+x^{27}+x^{26}+x^{25}+x^{23}+x^{22}+x^{20}+x^{19}+x^{18}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+1$	0x1EDC6F41或0x82F63B78 (0x05EC76F1)
CRC-64-ISO	$x^{64}+x^{4}+x^{3}+x+1$ （用途: ISO 3309）	0x000000000000001B或0xD800000000000000 (0xB000000000000001)
CRC-64-ECMA-182	$x^{64}+x^{62}+x^{57}+x^{55}+x^{54}+x^{53}+x^{52}+x^{47}+x^{46}+x^{45}+x^{40}+x^{39}+x^{38}+x^{37}+x^{35}+x^{33}+x^{32}$ $+x^{31}+x^{29}+x^{27}+x^{24}+x^{23}+x^{22}+x^{21}+x^{19}+x^{17}+x^{13}+x^{12}+x^{10}+x^{9}+x^{7}+x^{4}+x+1$ （參見ECMA-182 （頁面存檔備份，存於互聯網檔案館） p.63）	0x42F0E1EBA9EA3693或0xC96C5795D7870F42 (0x92D8AF2BAF0E1E85)
CRC-128	IEEE-ITU標準。被MD5 & SHA-1取代
CRC-160	IEEE-ITU標準。被MD5 & SHA-1取代

CRC與數據完整性

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

CRC發生碰撞的情況

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

理論上來講，CRC64的碰撞概率大約是每18×10¹⁸個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整除，那麼不存在可以被它整除的有奇數個非零系數的多項式。因此，它可以用來檢測輸入訊息中的奇數個錯誤，就像奇偶校驗函數那樣。

參見

總的分類

特殊技術參考

參考文獻

^ Peterson, W. W. and Brown, D. T. Cyclic Codes for Error Detection. Proceedings of the IRE. January 1961, 49: 228. ISSN 0096-8390. doi:10.1109/JRPROC.1961.287814.

外部連結

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. （頁面存檔備份，存於互聯網檔案館）

[PetersonBrown1961-1] Peterson, W. W. and Brown, D. T. Cyclic Codes for Error Detection. Proceedings of the IRE. January 1961, 49: 228. ISSN 0096-8390. doi:10.1109/JRPROC.1961.287814.

[1]