循環(huán)冗余校驗(yàn)

目錄
·簡(jiǎn)介
·實(shí)現(xiàn)
·變體
·錯(cuò)誤檢測(cè)能力
·CRC 多項(xiàng)式規(guī)范
·CRC 與數(shù)據(jù)完整性
·參見(jiàn)




Cyclic Redundancy Check -- 循環(huán)冗余校驗(yàn)（法）


循環(huán)冗余校驗(yàn)（CRC）是一種根據(jù)網(wǎng)絡(luò)數(shù)據(jù)封包或電腦檔案等數(shù)據(jù)產(chǎn)生少數(shù)固定位數(shù)的一種散列函數(shù)。用來(lái)檢測(cè)或校驗(yàn)數(shù)據(jù)傳輸或者保存后可能出現(xiàn)的錯(cuò)誤。生成的數(shù)字在傳輸或者儲(chǔ)存之前計(jì)算出來(lái)并且附加到數(shù)據(jù)后面，然后接收方進(jìn)行檢驗(yàn)確定數(shù)據(jù)是否發(fā)生變化。由于本函數(shù)易于用二進(jìn)制的電腦硬件使用、容易進(jìn)行數(shù)學(xué)分析并且尤其善于檢測(cè)傳輸通道干擾引起的錯(cuò)誤，因此獲得廣泛應(yīng)用。





簡(jiǎn)介

CRC“校驗(yàn)和”是兩個(gè)位元數(shù)據(jù)流采用二進(jìn)制除法（沒(méi)有進(jìn)位，使用XOR異或來(lái)代替減法）相除所得到的余數(shù)。其中被除數(shù)是需要計(jì)算校驗(yàn)和的信息數(shù)據(jù)流的二進(jìn)制表示；除數(shù)是一個(gè)長(zhǎng)度為n + 1的預(yù)定義（短）的二進(jìn)制數(shù)，通常用多項(xiàng)式的系數(shù)來(lái)表示。在做除法之前，要在信息數(shù)據(jù)之后先加上n個(gè)0.
CRCa 是基于有限域GF(2)(關(guān)于2同余)的多項(xiàng)式環(huán)。簡(jiǎn)單的來(lái)說(shuō)，就是所有系數(shù)都為0或1（又叫做二進(jìn)制）的多項(xiàng)式系數(shù)的集合，并且集合對(duì)于所有的代數(shù)操作都是封閉的。例如：

2會(huì)變成0，因?yàn)閷?duì)系數(shù)的加法都會(huì)模2. 乘法也是類(lèi)似的：

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

也就是說(shuō)，

x3 + x2 + x) = (x2 + 1)(x + 1) ? 1

這里除法得到了商x2 + 1和余數(shù)-1，因?yàn)槭瞧鏀?shù)所以最后一位是1。
字符串中的每一位其實(shí)就對(duì)應(yīng)了這樣類(lèi)型的多項(xiàng)式的系數(shù)。為了得到CRC, 我們首先將其乘以xn，這里n是一個(gè)固定多項(xiàng)式的階數(shù), 然后再將其除以這個(gè)固定的多項(xiàng)式，余數(shù)的系數(shù)就是CRC。
在上面的等式中，x2 + x + 1表示了本來(lái)的信息位是<code>111</code>, x + 1是所謂的鑰匙, 而余數(shù)1（也就是x0）就是CRC. key的最高次為1, 所以我們將原來(lái)的信息乘上x(chóng)1來(lái)得到x3 + x2 + x，也可視為原來(lái)的信息位補(bǔ)1個(gè)零成為<code>1110</code>。
一般來(lái)說(shuō)，其形式為：

這里 M(x) 是原始的信息多項(xiàng)式。K(x)是n階的“鑰匙”多項(xiàng)式。表示了將原始信息后面加上n個(gè)0。R(x)是余數(shù)多項(xiàng)式，既是CRC“校驗(yàn)和”。在通訊中，發(fā)送者在原始的信息數(shù)據(jù)M后加上n位的R（替換本來(lái)附加的0）再發(fā)送。接收者收到M和R后，檢查是否能被K(x)整除。如果是，那么接收者認(rèn)為該信息是正確的。值得注意的是就是發(fā)送者所想要發(fā)送的數(shù)據(jù)。這個(gè)串又叫做codeword.
CRCs 經(jīng)常被叫做“校驗(yàn)和”, 但是這樣的說(shuō)法嚴(yán)格來(lái)說(shuō)并不是準(zhǔn)確的，因?yàn)榧夹g(shù)上來(lái)說(shuō)，校驗(yàn)“和”是通過(guò)加法來(lái)計(jì)算的，而不是CRC這里的除法。
“錯(cuò)誤糾正編碼”常常和CRCs緊密相關(guān)，其語(yǔ)序糾正在傳輸過(guò)程中所產(chǎn)生的錯(cuò)誤。這些編碼方式常常和數(shù)學(xué)原理緊密相關(guān)。



實(shí)現(xiàn)



變體

CRC 有幾種不同的變體

<code>shiftRegister</code> 可以逆向使用，這樣就需要檢測(cè)最低位的值，每次向右移動(dòng)一位。這就要求 <code>polynomial</code> 生成逆向的數(shù)據(jù)位結(jié)果。實(shí)際上這是最常用的一個(gè)變體。
可以先將數(shù)據(jù)最高位讀到移位寄存器，也可以先讀最低位。在通訊協(xié)議中，為了保留 CRC 的突發(fā)錯(cuò)誤檢測(cè)特性，通常按照物理層發(fā)送數(shù)據(jù)位的方式計(jì)算 CRC。
為了檢查 CRC，需要在全部的碼字上進(jìn)行 CRC 計(jì)算，而不是僅僅計(jì)算消息的 CRC 并把它與 CRC 比較。如果結(jié)果是 0，那么就通過(guò)這項(xiàng)檢查。這是因?yàn)榇a字 可以被 K(x) 整除。
移位寄存器可以初始化成 1 而不是 0。同樣，在用算法處理之前，消息的最初 n 個(gè)數(shù)據(jù)位要取反。這是因?yàn)槲唇?jīng)修改的 CRC 無(wú)法區(qū)分只有起始 0 的個(gè)數(shù)不同的兩條消息。而經(jīng)過(guò)這樣的取反過(guò)程，CRC 就可以正確地分辨這些消息了。
CRC 在附加到消息數(shù)據(jù)流的時(shí)候可以進(jìn)行取反。這樣，CRC 的檢查可以用直接的方法計(jì)算消息的 CRC、取反、然后與消息數(shù)據(jù)流中的 CRC 比較這個(gè)過(guò)程來(lái)完成，也可以通過(guò)計(jì)算全部的消息來(lái)完成。在后一種方法中，正確消息的結(jié)果不再是 0，而是 除以 K(x) 得到的結(jié)果。這個(gè)結(jié)果叫作核驗(yàn)多項(xiàng)式 C(x)，它的十六進(jìn)制表示也叫作幻數(shù)。

按照慣例，使用 CRC-32 多項(xiàng)式以及 CRC-16-CCITT 多項(xiàng)式時(shí)通常都要取反。CRC-32 的核驗(yàn)多項(xiàng)式是

C(x) = x31 + x30 + x26 + x25 + x24 + x18 + x15 + x14 + x12 + x11 + x10 + x8 + x6 + x5 + x4 + x3 + x + 1。



錯(cuò)誤檢測(cè)能力

CRC 的錯(cuò)誤檢測(cè)能力依賴于關(guān)鍵多項(xiàng)式的階次以及所使用的特定關(guān)鍵多項(xiàng)式。誤碼多項(xiàng)式 E(x) 是接收到的消息碼字與正確消息碼字的異或結(jié)果。當(dāng)且僅當(dāng)誤碼多項(xiàng)式能夠被 CRC 多項(xiàng)式整除的時(shí)候 CRC 算法無(wú)法檢查到錯(cuò)誤。

由于 CRC 的計(jì)算基于除法，任何多項(xiàng)式都無(wú)法檢測(cè)出一組全為零的數(shù)據(jù)出現(xiàn)的錯(cuò)誤或者前面丟失的零。但是，可以根據(jù) CRC 的變體來(lái)解決這個(gè)問(wèn)題。
所有只有一個(gè)數(shù)據(jù)位的錯(cuò)誤都可以被至少有兩個(gè)非零系數(shù)的任意多項(xiàng)式檢測(cè)到。誤碼多項(xiàng)式是 xk，并且 xk 只能被 的多項(xiàng)式 xi 整除。
CRC 可以檢測(cè)出所有間隔距離小于多項(xiàng)式階次的雙位錯(cuò)誤，在這種情況下的誤碼多項(xiàng)式是。

如上所述，xk 不能被 CRC 多項(xiàng)式整除，它得到一個(gè) xi ? k + 1 項(xiàng)。根據(jù)定義，滿足多項(xiàng)式整除 xi ? k + 1 的 i ? k 最小值就是多項(xiàng)是的階次。最高階次的多項(xiàng)式是本原多項(xiàng)式，帶有二進(jìn)制系數(shù)的 n 階多項(xiàng)式


CRC 多項(xiàng)式規(guī)范

下面的表格略去了“初始值”、“反射值”以及“最終異或值”。

對(duì)于一些復(fù)雜的校驗(yàn)和來(lái)說(shuō)這些十六進(jìn)制數(shù)值是很重要的，如 CRC-32 以及 CRC-64。通常小于 CRC-16 的 CRC 不需要使用這些值。
通�？梢酝ㄟ^(guò)改變這些值來(lái)得到各自不同的校驗(yàn)和，但是校驗(yàn)和算法機(jī)制并沒(méi)有變化。

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

由于 CRC-12 有三種常用的形式，所以 CRC-12 的定義會(huì)有歧義
在應(yīng)用的 CRC-8 的兩種形式都有數(shù)學(xué)上的缺陷。
據(jù)稱 CRC-16 與 CRC-32 至少有 10 種形式，但沒(méi)有一種在數(shù)學(xué)上是最優(yōu)的。
同樣大小的 CCITT CRC 與 ITU CRC 不同，這個(gè)機(jī)構(gòu)在不同時(shí)期定義了不同的校驗(yàn)和。



CRC 與數(shù)據(jù)完整性

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

CRC發(fā)生碰撞的情況
與所有其它的散列函數(shù)一樣，在一定次數(shù)的碰撞測(cè)試之后 CRC 也會(huì)接近 100% 出現(xiàn)碰撞。CRC 中每增加一個(gè)數(shù)據(jù)位，就會(huì)將碰撞數(shù)目減少接近 50%，如 CRC-20 與 CRC-21 相比。

理論上來(lái)講，CRC64 的碰撞概率大約是每 18×1018 個(gè) CRC 碼出現(xiàn)一次。
由于 CRC 的不分解多項(xiàng)式特性，所以經(jīng)過(guò)合理設(shè)計(jì)的較少位數(shù)的 CRC 可能會(huì)與使用較多數(shù)據(jù)位但是設(shè)計(jì)很差的 CRC 的效率相媲美。在這種情況下 CRC-32 幾乎同 CRC-40 一樣優(yōu)秀。


設(shè)計(jì) CRC 多項(xiàng)式
生成多項(xiàng)式的選擇是 CRC 算法實(shí)現(xiàn)中最重要的部分，所選擇的多項(xiàng)式必須有最大的錯(cuò)誤檢測(cè)能力，同時(shí)保證總體的碰撞概率最小。多項(xiàng)式最重要的屬性是它的長(zhǎng)度，也就是最高非零系數(shù)的數(shù)值，因?yàn)樗�直接影響著�?jì)算的校驗(yàn)和的長(zhǎng)度。
最常用的多項(xiàng)式長(zhǎng)度有

9 位 (CRC-8)
17 位 (CRC-16)
33 位 (CRC-32)
65 位 (CRC-64)

在構(gòu)建一個(gè)新的 CRC 多項(xiàng)式或者改進(jìn)現(xiàn)有的 CRC 時(shí)，一個(gè)通用的數(shù)學(xué)原則是使用滿足所有模運(yùn)算不可分解多項(xiàng)式約束條件的多項(xiàng)式。

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

生成多項(xiàng)式的特性可以從算法的定義中推導(dǎo)出來(lái)：

如果 CRC 有多于一個(gè)的非零系數(shù)，那么 CRC 能夠檢查出輸入消息中的所有單數(shù)據(jù)位錯(cuò)誤。
CRC 可以用于檢測(cè)短于 2k 的輸入消息中的所有雙位錯(cuò)誤，其中 k 是多項(xiàng)式的最長(zhǎng)的不可分解部分的長(zhǎng)度。
如果多項(xiàng)式可以被 x+1 整除，那么不存在可以被它整除的有奇數(shù)個(gè)非零系數(shù)的多項(xiàng)式。因此，它可以用來(lái)檢測(cè)輸入消息中的奇數(shù)個(gè)錯(cuò)誤，就象奇偶校驗(yàn)函數(shù)那樣。



參見(jiàn)

總的分類(lèi)

糾錯(cuò)碼
校驗(yàn)和算法列表
奇偶校驗(yàn)位

特殊技術(shù)參考

Adler-32
Fletcher&＃39;&＃39;&＃39;&＃39;&＃39;&＃39;&＃39;&＃39;s checksum

• 通信詞典解釋