循環冗餘校驗

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

簡介

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

CRC是基於有限域GF(2)(即除以2同余)的多項式環。簡單的來說,就是所有係數都為0或1(又叫做二進制)的多項式係數的集合,並且集合對於所有的代數操作都是封閉的。例如:

2會變成0,因為對係數的加法運算都會再取2的模數。乘法也是類似的:

同樣可以對多項式作除法並且得到商和餘數。例如,如果用x3 + x2 + x除以x + 1。會得到:

也就是說,

等價於:

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

字符串中的每一位其實就對應了這樣類型的多項式的係數。為了得到CRC,首先將其乘以,這裡是一個固定多項式的階數,然後再將其除以這個固定的多項式,餘數的係數就是CRC。

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

一般來說,其形式為:

這裡M(x)是原始的信息多項式。K(x)是階的「鑰匙」多項式。表示了將原始信息後面加上個0。R(x)是餘數多項式,即是CRC「校驗和」。在通訊中,發送者在原始的信息數據M後附加上位的R(替換本來附加的0)再發送。接收者收到M和R後,檢查是否能被整除。如果是,那麼接收者認為該信息是正確的。值得注意的是就是發送者所想要發送的數據。這個串又叫做codeword.

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

纠错码(,簡稱ECC)常常和CRCs緊密相關,其語序糾正在傳輸過程中所產生的錯誤。這些編碼方式常常和數學原理緊密相關。例如常見于通訊或資訊傳遞上BCH码前向錯誤更正错误检测与纠正等。

變體

CRC有幾種不同的變體

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

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

  • 對於要處理的資料M(x)有前置0時,用兩式相加作反相運算,使得前置的0變成1後,再作mod 2運算得到CRC。公式:




例:
,這裡可知

故L(x)階數從2開始

求得一組n個1及m個0以便與相加
令m = 5,(bitwise shift)
(使M前置的0變成1)
mod2 求得餘R(x)= 011
送出
接收端L(x) = 111且開頭不為1 => m = 5
可反推
用10011011 mod2 1101可驗證能被K(x)整除。

錯誤檢測能力

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

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

如上所述,不能被CRC多項式整除,它得到一個項。根據定義,滿足多項式整除最小值就是多項式的階次。最高階次的多項式是本原多項式,帶有二進制係數的階多項式

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
(用途:硬件,也稱為奇偶校驗位
0x1 or 0x1 (0x1)
CRC-5-CCITTITU G.704標準)0xB(0x??)
CRC-5-USB(用途:USB信令包)0x5 or 0x14 (0x9)
CRC-7(用途:通信系統)0x9 or 0x48 (0x11)
CRC-8-ATM(用途:ATM HEC, PMBUS (參見SMBUS org))0x7或0xE0 (0xC1)
CRC-8-CCITT(用途:1-Wire 總線0x8D
CRC-8-Dallas/Maxim(用途:1-Wire bus0x31或0x8C
CRC-80xD5(0x??)
CRC-100x233(0x????)
CRC-12(用途:通信系統)0x80F或0xF01 (0xE03)
CRC-16-Fletcher參見Fletcher's checksum用於Adler-32 A & B CRC
CRC-16-CCITTX25, V.41, Bluetooth, PPP, IrDA0x1021或0x8408 (0x0811)
CRC-16-IBM(用途:Modbus)0x8005或0xA001 (0x4003)
CRC-16-BBS(用途:XMODEM協議)0x8408(0x????)
CRC-32-Adler參見Adler-32參見Adler-32
CRC-32-MPEG2參見IEEE 802.3參見IEEE 802.3
CRC-32-IEEE 802.30x04C11DB7或0xEDB88320 (0xDB710641)
CRC-32C(Castagnoli)0x1EDC6F41或0x82F63B78 (0x05EC76F1)
CRC-64-ISO
(用途: ISO 3309)
0x000000000000001B或0xD800000000000000 (0xB000000000000001)
CRC-64-ECMA-182

(參見ECMA-182 p.63)
0x42F0E1EBA9EA3693或0xC96C5795D7870F42 (0x92D8AF2BAF0E1E85)
CRC-128IEEE-ITU標準。被MD5 & SHA-1取代
CRC-160IEEE-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. . Proceedings of the IRE. January 1961, 49: 228. ISSN 0096-8390. doi:10.1109/JRPROC.1961.287814.

外部連結

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.