冗余碼

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




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


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





簡介

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

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

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

也就是說，

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

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

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



實現(xiàn)



變體

CRC 有幾種不同的變體

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

按照慣例，使用 CRC-32 多項式以及 CRC-16-CCITT 多項式時通常都要取反。CRC-32 的核驗多項式是

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



錯誤檢測能力

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

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

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


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)在不同時期定義了不同的校驗和。



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

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

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

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


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

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

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

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

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

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



參見

總的分類

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

特殊技術(shù)參考

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

• 通信詞典解釋