[科普中國]-循環(huán)冗余檢查

循環(huán)冗余校驗（英語：Cyclic redundancy check，通稱“CRC”）是一種根據(jù)網(wǎng)上數(shù)據(jù)包或計算機(jī)文件等數(shù)據(jù)產(chǎn)生簡短固定位數(shù)校驗碼的一種散列函數(shù)，主要用來檢測或校驗數(shù)據(jù)傳輸或者保存后可能出現(xiàn)的錯誤。生成的數(shù)字在傳輸或者存儲之前計算出來并且附加到數(shù)據(jù)后面，然后接收方進(jìn)行檢驗確定數(shù)據(jù)是否發(fā)生變化。一般來說，循環(huán)冗余校驗的值都是32位的整數(shù)。由于本函數(shù)易于用二進(jìn)制的計算機(jī)硬件使用、容易進(jìn)行數(shù)學(xué)分析并且尤其善于檢測傳輸通道干擾引起的錯誤，因此獲得廣泛應(yīng)用。此方法是由W. Wesley Peterson于1961年發(fā)表。

簡介循環(huán)冗余校驗（英語：Cyclic redundancy check，通稱“CRC”）是一種根據(jù)網(wǎng)上數(shù)據(jù)包或計算機(jī)文件等數(shù)據(jù)產(chǎn)生簡短固定位數(shù)校驗碼的一種散列函數(shù)，主要用來檢測或校驗數(shù)據(jù)傳輸或者保存后可能出現(xiàn)的錯誤。生成的數(shù)字在傳輸或者存儲之前計算出來并且附加到數(shù)據(jù)后面，然后接收方進(jìn)行檢驗確定數(shù)據(jù)是否發(fā)生變化。一般來說，循環(huán)冗余校驗的值都是32位的整數(shù)。由于本函數(shù)易于用二進(jìn)制的計算機(jī)硬件使用、容易進(jìn)行數(shù)學(xué)分析并且尤其善于檢測傳輸通道干擾引起的錯誤，因此獲得廣泛應(yīng)用。此方法是由W. Wesley Peterson于1961年發(fā)表。

CRC為校驗和的一種，是兩個字節(jié)數(shù)據(jù)流采用二進(jìn)制除法（沒有進(jìn)位，使用XOR來代替減法）相除所得到的余數(shù)。其中被除數(shù)是需要計算校驗和的信息數(shù)據(jù)流的二進(jìn)制表示；除數(shù)是一個長度為的預(yù)定義（短）的二進(jìn)制數(shù)，通常用多項式的系數(shù)來表示。在做除法之前，要在信息數(shù)據(jù)之后先加上個0.

CRC是基于有限域GF(2)（即除以2的同余）的多項式環(huán)。簡單的來說，就是所有系數(shù)都為0或1（又叫做二進(jìn)制）的多項式系數(shù)的集合，并且集合對于所有的代數(shù)操作都是封閉的。例如：

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

我們同樣可以對多項式作除法并且得到商和余數(shù)。例如，如果我們用x+x+x除以x+ 1。我們會得到：

也就是說：

等價于：

這里除法得到了商x+ 1和余數(shù)-1，因為是奇數(shù)所以最后一位是1。

字符串中的每一位其實就對應(yīng)了這樣類型的多項式的系數(shù)。為了得到CRC，我們首先將其乘以，這里n是一個固定多項式的階數(shù)，然后再將其除以這個固定的多項式，余數(shù)的系數(shù)就是CRC。

在上面的等式中，表示了本來的信息位是111, 是所謂的鑰匙，而余數(shù)1（也就是）就是CRC. key的最高次為1,所以我們將原來的信息乘上來得到，也可視為原來的信息位補(bǔ)1個零成為1110。

一般來說，其形式為：

這里M(x)是原始的信息多項式。K(x)是階的“鑰匙”多項式。表示了將原始信息后面加上個0。R(x)是余數(shù)多項式，即是CRC“校驗和”。在通信中，發(fā)送者在原始的信息數(shù)據(jù)M后附加上n位的R（替換本來附加的0）再發(fā)送。接收者收到M和R后，檢查是否能被整除。如果是，那么接收者認(rèn)為該信息是正確的。值得注意的是就是發(fā)送者所想要發(fā)送的數(shù)據(jù)。這個串又叫做codeword.

CRCs經(jīng)常被叫做“校驗和”，但是這樣的說法嚴(yán)格來說并不是準(zhǔn)確的，因為技術(shù)上來說，校驗“和”是通過加法來計算的，而不是CRC這里的除法。

“錯誤糾正編碼”（Error–Correcting Codes，簡稱ECC）常常和CRCs緊密相關(guān)，其語序糾正在傳輸過程中所產(chǎn)生的錯誤。這些編碼方式常常和數(shù)學(xué)原理緊密相關(guān)。例如常見于通信或信息傳遞上BCH碼、前向錯誤更正、Error detection and correction等。

CRC多項式規(guī)范下面的表格略去了“初始值”、“反射值”以及“最終異或值”。

對于一些復(fù)雜的校驗和來說這些十六進(jìn)制數(shù)值是很重要的，如CRC-32以及CRC-64。通常小于CRC-16的CRC不需要使用這些值。

通常可以通過改變這些值來得到各自不同的校驗和，但是校驗和算法機(jī)制并沒有變化。

CRC標(biāo)準(zhǔn)化問題

由于CRC-12有三種常用的形式，所以CRC-12的定義會有歧義

在應(yīng)用的CRC-8的兩種形式都有數(shù)學(xué)上的缺陷。

據(jù)稱CRC-16與CRC-32至少有10種形式，但沒有一種在數(shù)學(xué)上是最優(yōu)的。

同樣大小的CCITT CRC與ITU CRC不同，這個機(jī)構(gòu)在不同時期定義了不同的校驗和。1

CRC與數(shù)據(jù)完整性盡管在錯誤檢測中非常有用，CRC并不能可靠地校驗數(shù)據(jù)完整性（即數(shù)據(jù)沒有發(fā)生任何變化），這是因為CRC多項式是線性結(jié)構(gòu)，可以非常容易地故意改變量據(jù)而維持CRC不變，參見CRC and how to Reverse it中的證明。我們可以用Message authentication code校驗數(shù)據(jù)完整性。1

參見總的分類

糾錯碼

校驗和算法列表

奇偶校驗位

特殊技術(shù)參考

Adler-32

Fletcher's checksum

本詞條內(nèi)容貢獻(xiàn)者為:

張靜 - 副教授 - 西南大學(xué)