循環(huán)冗余校驗

循環(huán)冗余校驗

百科解釋

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

CRC“校驗和”是兩個位元數(shù)據(jù)流采用二進制除法（沒有進位，使用XOR異或來代替減法）相除所得到的余數(shù)。其中被除數(shù)是需要計算校驗和的信息數(shù)據(jù)流的二進制表示；除數(shù)是一個長度為n + 1的預定義（短）的二進制數(shù)，通常用多項式的系數(shù)來表示。在做除法之前，要在信息數(shù)據(jù)之后先加上n個0.
CRCa 是基于有限域GF(2)(關于2同余)的多項式環(huán)。簡單的來說，就是所有系數(shù)都為0或1（又叫做二進制）的多項式系數(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。
字符串中的每一位其實就對應了這樣類型的多項式的系數(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，也可視為原來的信息位補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)整除。如果是，那么接收者認為該信息是正確的。值得注意的是就是發(fā)送者所想要發(fā)送的數(shù)據(jù)。這個串又叫做codeword.
CRCs 經(jīng)常被叫做“校驗和”, 但是這樣的說法嚴格來說并不是準確的，因為技術上來說，校驗“和”是通過加法來計算的，而不是CRC這里的除法。
“錯誤糾正編碼”常常和CRCs緊密相關，其語序糾正在傳輸過程中所產(chǎn)生的錯誤。這些編碼方式常常和數(shù)學原理緊密相關。

CRC 有幾種不同的變體

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

CRC 多項式規(guī)范

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

對于一些復雜的校驗和來說這些十六進制數(shù)值是很重要的，如 CRC-32 以及 CRC-64。通常小于 CRC-16 的 CRC 不需要使用這些值。
通�？梢酝ㄟ^改變這些值來得到各自不同的校驗和，但是校驗和算法機制并沒有變化。

CRC 標準化問題

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

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

盡管在錯誤檢測中非常有用，CRC 并不能可靠地驗證數(shù)據(jù)完整性（即數(shù)據(jù)沒有發(fā)生任何變化），這是因為 CRC 多項式是線性結構，可以非常容易地故意改變數(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ù)的 CRC 可能會與使用較多數(shù)據(jù)位但是設計很差的 CRC 的效率相媲美。在這種情況下 CRC-32 幾乎同 CRC-40 一樣優(yōu)秀。

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

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

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

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

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

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

總的分類

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

特殊技術參考

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

通信詞典解釋