CRC 錯誤偵測技術



即是所謂的循環冗餘檢查碼 (Cyclic Redundancy Check Code) ,簡稱

CRC 碼,它是由待傳輸的資料區塊計算出的,CRC 的計算方式是將待傳

輸的區塊視為一堆連續位元所構成的一整個數值,並將此數值除以一特

定的除數,通常以二進位表示,此除數又稱為衍生多項式 (Generation

Polynomial),該除數一般皆由設計硬體或軟體的廠商所提供,而除數

值位元數目則視欲得到的 CRC 位元數目而定,目前較常使用的 CRC 位

元數目有 8、16 或 32,一般縮寫為 CRC-8、CRC-16、CRC-32,通常,

CRC 碼越長,則數據發生干擾卻不反應在 CRC 值的機率也就越低,不

過得多花些時間傳送較長的 CRC 碼。根據理論統計,CRC-16 可完全偵

測資料區塊內單一或兩個位元的錯誤、奇數個位元的錯誤、連續 16 個

位元或少於此數的錯誤,超過 17 個連續位元的錯誤偵測率則有

99.9969% ,其它位元長度的錯誤偵測率則可達 99.9984% 。

底下是一些數學符號所表示的 CRC 碼運算過程。吾人可將待傳送的區

塊資料位元串表示成一個很大的二進位數字,並令此數字等於 F,例如

,底下是某個區塊的位元串所連成的二進位數字:



F = 1011010111110111101110100100101110101... (區塊資料)



假設目前欲求 F 的 16 位元 CRC 值,並且,廠商所提供的衍生多項式

是:



16 12 5

G(x) = x + x + x + 1 (衍生多項式)



其中,x 是所採的進制,在二進位系統,x = 2,則 G 的值為:



G = 1,0001,0000,0010,0001 (二進位數字)



底下的式子中的餘數 C 即是 F 的 16 位元 CRC 值:



16

F ‧ 2 = A ‧ G + C



由於 C 是此式中的餘式,故稱此值為 Redundancy。

例如,底下即是透過上述的 G(x) 求得 11010101 (D5H) 的 CRC 值:

A

┌─────────────────

1,0001,0000,0010,0001│1101,0101 ‧ 1,0000,0000,0000,0000

╯......

──────────────────

(二進位長除法) 16 位元 CRC 值 → 1001,1011,1101,1000



衍生多項式的數值將影響到所產生的 CRC 值,根據理論計算,當衍生

多項式的數值恰為某些特定值時,所產生的 CRC 值最 "亂" ,換句話

說,它偵測資料受雜訊干擾的能力越高,在上個範例中所採用的多項

式也是 PC/XT 控制卡上μPD765A 所採用,該多項式也是 CRC-CCITT

v.41 所制定的標準,而目前在許多通訊上的應用亦採用此值。

理論上,在計算 CRC 時非常簡單,只要一個除法運算即可,運算之後

的餘數即是 CRC 值,但實際上所被除數 F 的位元數目可能以萬為單

位,如何利用程式以最簡易、最快的方式求得該餘數也是技術關鍵所

在。事實上,各式的檢查碼也不僅應用在網路通訊上,和數據的存取

、儲存、傳輸等類似的範疇也會用到,例如磁碟片或磁帶機上資料的

儲存即是,在 Apple 個人電腦的磁碟機即是利用 checksum 驗證所存

取資料的正確性,而 PC 的磁碟機則使用 CRC。

arrow
arrow
    全站熱搜

    狼翔月影 發表在 痞客邦 留言(1) 人氣()