循環冗餘碼檢視原始碼討論檢視歷史

循環冗餘碼原圖鏈接圖片來源優酷網

循環校驗碼（CRC碼），是數據通信領域中最常用的一種差錯校驗碼，其特徵是信息字段和校驗字段的長度可以任意選定。

中文名:循環冗餘碼

外文名:CRC碼

領 域:數據通信領域

性 質:差錯校驗碼

1. 含義

循環冗餘碼，又稱為多項式碼。CRC的工作方法是在發送端產生一個冗餘碼，附加在信息位後面一起發送到接收端，接收端收到的信息按發送端形成循冗餘碼同樣的算法進行校驗，如果發現錯誤，則通知發送端重發。

在數據存儲和數據通訊領域，為了保證數據的正確，就不得不採用檢錯的手段。在諸多檢錯手段中，CRC是最著名的一種，其特點是:檢錯能力極強，開銷小，易於用編碼器及檢測電路實現。從其檢錯能力來看，它所不能發現的錯誤的幾率僅為0.0047%以下。從性能上和開銷上考慮，均遠遠優於奇偶校驗及算術和校驗等方式。因而，在數據存儲和數據通訊領域，CRC無處不在：著名的通訊協議X.25的FCS(幀檢錯序列)採用的是CRC-CCITT，WinRAR、NERO、ARJ、LHA等壓縮工具軟件採用的是CRC32，磁盤驅動器 的讀寫採用了CRC16，通用的圖像存儲格式GIF、TIFF等也都用CRC作為檢錯手段。

CRC的本質是模-2除法的餘數，採用的除數不同，CRC的類型也就不一樣。通常，CRC的除數用生成多項式來表示。

根據應用環境與習慣的不同，CRC又可分為以下幾種標準：

1）CRC-12碼；

2）CRC-16碼；

3）CRC-CCITT碼；

4）CRC-32碼。

CRC-12碼通常用來傳送6-bit字符串。

CRC-16及CRC-CCITT碼則是用來傳送8-bit字符串，其中CRC-16為美國採用，而CRC-CCITT為歐洲國家所採用。CRC-32碼大都被採用在一種稱為Point-to- Point的同步傳輸中。

2. 生成CRC碼的基本原理

任意一個由二進制位串組成的代碼都可以和一個係數僅為『0』和『1』取值的多項式一一對應。例如：代碼1010111對應的多項式為x6+x4+x2+x+1，而多項式為x5+x3+x2+x+1對應的代碼101111。

常用的CRC循環冗餘校驗標準多項式如下：

CRC(12位) =X^12+X^11+X^3+X^2+X+1

CRC(16位) = X^16+X^15+X^2+1

CRC(CCITT) = X^16+X^12 +X^5+1

CRC(32位) = 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

以CRC(16位)多項式為例，其對應校驗二進制位列為1 1000 0000 00000101。

各多項式的係數均為二進制數，所涉及的四則運算仍遵循對二取模的運算規則。

(註：對二取模的四則運算指參與運算的兩個二進制數各位之間凡涉及加減運算時均進行XOR異或運算，即：1 XOR 1=0，0 XOR 0=0，1 XOR 0=1，0 XOR 1=1，即相同為0，不同為1)

3. CRC碼集選擇的原則

若設碼字長度為N，信息字段為K位，校驗字段為R位(N=K+R)，則對於CRC碼任一碼字，存在且僅存在一個R次多項式g(x)，使得

V(x)=A(x)g(x)=xRm(x)+r(x);其中:m(x)為K次信息多項式，r(x)為R-1次校驗多項式，g(x)稱為生成多項式：g(x)=g0+g1x+g2x2+...+g(R-1)x(R-1)+gRxR發送方通過指定的g(x)產生CRC碼字，接收方則通過該g(x)來驗證收到的CRC碼字。

4. CRC校驗碼軟件生成方法

藉助於多項式除法，其餘數為校驗字段。例如：信息字段代碼為:1011001；對應m(x)=x6+x4+x3+1假設生成多項式為：g(x)=x4+x3+1；則對應g(x)的代碼為:11001x4m(x)=x10+x8+x7+x4對應的代碼記為：10110010000；採用多項式除法:得餘數為:1010(即校驗字段為：1010）發送方：發出的傳輸字段為:10110011010信息字段校驗字段接收方：使用相同的生成碼進行校驗:接收到的字段/生成碼（二進制除法）如果能夠除盡，則正確，給出餘數（1010）的計算步驟：除法沒有數學上的含義，而是採用計算機的模二除法，即，除數和被除數做異或運算10110010000/11001=111101111011100=1010

5. 特點

如果生成多項式選擇得當，CRC是一種很有效的差錯校驗方法。理論上可以證明循環冗餘校驗碼的檢錯能力有以下特點：

1）可檢測出所有奇數個錯誤；

2）可檢測出所有雙比特的錯誤；

3）可檢測出所有小於等於校驗位長度的連續錯誤；

4）以相當大的概率檢測出大於校驗位長度的連續錯誤。