循環冗餘校驗

维基百科,自由的百科全书
(重定向自循环冗余校验
跳转至: 导航搜索

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

簡介[编辑]

CRC為校驗和的一種,是兩個字節數據流採用二進制除法(沒有進位,使用XOR來代替減法)相除所得到的餘數。其中被除數是需要計算校驗和的信息數據流的二進制表示;除數是一個長度為(n+1)的預定義(短)的二進制數,通常用多項式的係數來表示。在做除法之前,要在信息數據之後先加上n個0.

CRCa 是基於有限域 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

我們同樣可以對多項式作除法並且得到商和餘數。例如, 如果我們用x3 + x2 + 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

這裡除法得到了商x2 + 1和餘數-1,因為是奇數所以最後一位是1。

字符串中的每一位其實就對應了這樣類型的多項式的係數。為了得到CRC, 我們首先將其乘以x^{n},這裡n是一個固定多項式的階數, 然後再將其除以這個固定的多項式,餘數的係數就是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.

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

錯誤糾正編碼Error–Correcting Codes,簡稱ECC)常常和CRCs緊密相關,其語序糾正在傳輸過程中所產生的錯誤。這些編碼方式常常和數學原理緊密相關。(例如常見于通訊或資訊傳遞上BCH码前向錯誤更正Error detection and correction英语Error detection and correction等)

實現[编辑]

變體[编辑]

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 \le 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) 0x7 or 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 or 0x8C
CRC-8 x^8 + x^7 + x^6 + x^4 + x^2 +1 0xD5(0x??)
CRC-10 x10 + x9 + x5 + x4 + x + 1 0x233 (0x????)
CRC-12 x^{12} + x^{11} + x^3 + x^2 + x + 1
(用途:通信系統)
0x80F or 0xF01 (0xE03)
CRC-16-Fletcher 參見 Fletcher's checksum 用於 Adler-32 A & B CRC
CRC-16-CCITT x16 + x12 + x5 + 1 (X25, V.41, Bluetooth, PPP, IrDA) 0x1021 or 0x8408 (0x0811)
CRC-16-IBM x16 +x15 + x2 + 1 0x8005 or 0xA001 (0x4003)
CRC-16-BBS x16 + x15 + x10 + x3 (用途:XMODEM 協議) 0x8408 (0x????)
CRC-32-Adler See Adler-32 參見 Adler-32
CRC-32-MPEG2 See 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 or 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 or 0x82F63B78 (0x05EC76F1)
CRC-64-ISO x^{64} + x^4 + x^3 + x + 1
(use: ISO 3309)
0x000000000000001B or 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
(as described in ECMA-182 p.63)
0x42F0E1EBA9EA3693 or 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中的證明。我們可以用 Message authentication code 驗證數據完整性。

CRC發生碰撞的情況[编辑]

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

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

參見[编辑]

總的分類

特殊技術參考

參考文獻[编辑]

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

外部鏈接[编辑]