基本介紹
1. 含義,2. 生成CRC碼的基本原理,3. CRC碼集選擇的原則,4. CRC校驗碼軟體生成方法,5. 特點,
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）以相當大的機率檢測出大於校驗位長度的連續錯誤。
