CRC校驗基本原理

　　CRC檢驗原理實際上就是在一個p位二進制數(shù)據(jù)序列之后附加一個r位二進制檢驗碼（序列），從而構(gòu)成一個總長為n＝p＋r位的二進制序列；附加在數(shù)據(jù)序列之后的這個檢驗碼與數(shù)據(jù)序列的內(nèi)容之間存在著某種特定的關(guān)系。如果因干擾等原因使數(shù)據(jù)序列中的某一位或某些位發(fā)生錯誤，這種特定關(guān)系就會被破壞。因此，通過檢查這一關(guān)系，就可以實現(xiàn)對數(shù)據(jù)正確性的檢驗。

　　CRC檢驗碼的計算

　　設(shè)信息字段為K位，校驗字段為R位，則碼字長度為N（N=K+R）。設(shè)雙方事先約定了一個R次多項式g（x），則CRC碼：

　　V（x）=A（x）g（x）=xRm（x）+r（x）

　　其中： m（x）為K次信息多項式， r（x）為R-1次校驗多項式。

　　這里r（x）對應(yīng)的代碼即為冗余碼，加在原信息字段后即形成CRC碼。

　　r（x）的計算方法為：在K位信息字段的后面添加R個0，再除以g（x）對應(yīng)的代碼序列，得到的余數(shù)即為r（x）對應(yīng)的代碼（應(yīng)為R－1位；若不足，而在高位補0）。

　　循環(huán)冗余檢驗

　　循環(huán)冗余檢驗英文名稱為Cyclical Redundancy Check，簡稱CRC。它是利用多項式除法及余數(shù)的原理來做錯誤檢測的。它將要發(fā)送的數(shù)據(jù)比特序列當(dāng)作一個信息多項式u（x）的系數(shù)，發(fā)送時去除以約定的生成多項式g（x），得到一個余數(shù)多項式v（x），將余數(shù)多項式加到信息多項式之后發(fā)送到接收端，接收端同樣用g（x）去除接收到的接收多項式r（x），進行計算，然后把計算結(jié)果與由生成多項式g（x）決定的固定序列比較，來檢測傳輸錯誤。由此可以看出其同時具有循環(huán)碼和冗余碼的特征，所以這種錯誤檢測方法叫循環(huán)冗余校驗，編碼叫循環(huán)冗余校驗碼。

　　理論上可以證明循環(huán)冗余校驗碼的檢錯能力有以下特點：

　　（1）可檢測出所有奇數(shù)位錯。

　　（2）可檢測出所有雙比特的錯。

　　（3）可檢測出所有小于、等于校驗位長度的突發(fā)錯。

　　CRC碼編碼

　　歸納起來有以下三步驟：

　　編碼電路有兩種方式：

　　1，信息位由高位到低位的順序從循環(huán)移位寄存器體左側(cè)依次輸入，信息位完全進入循環(huán)體后繼續(xù)輸入n?k?1個0，最后循環(huán)體中寄存器的值就是余式碼字；

　　圖1 左側(cè)串行輸入循環(huán)移位寄存器體

　　2，信息位由高位到低位的順序從循環(huán)移位寄存器體右側(cè)依次輸入，信息位完全進入循環(huán)體后寄存器的值就是余式碼字。

　　圖2 右側(cè)串行輸入循環(huán)移位寄存器體

　　注：1，移位寄存器循環(huán)體中余式碼字低位在左側(cè)，高位在右側(cè)。

　　CRC碼校驗

　　CRC碼校驗的基本原理

　　所有的CRC校驗都是基于以下這個等式：

　　發(fā)送端M和G（對某一種確定的CRC校驗，其G是固定的）是已知的，CRC計算就是 為了求出校驗字段R；接收端M，R，G都是已知的，主要的操作都是為了驗證等式是否成立，方法有很多種。

　　下表展示了用于被用于一些常用的CRC標(biāo)準(zhǔn)的生成多項式，Hex列表示生成多項式對應(yīng)的十六進制，MSB（most significant bit，可以理解為最左邊的一位）省略，因為該位總是為1：

　　發(fā)送端和接收端的具體處理方法

　　CRC校驗碼在工程應(yīng)用過程中相比數(shù)學(xué)計算稍微有些變化：

　　1，在發(fā)送端對全0數(shù)據(jù)包的編碼處理。

　　數(shù)學(xué)計算中，當(dāng)信息字段全部為0時的得到的余式碼字也是全零的，但是在工程應(yīng)用中，當(dāng)非0信息字段在編碼后發(fā)送給接收端，在線路傳輸中出現(xiàn)干擾或者是其他情況的錯誤，導(dǎo)致接收端收到的全零數(shù)據(jù)，即信息字段和余式字段都為0。如果在發(fā)送端不做特殊處理，在接收端就檢驗不出來這樣的錯誤數(shù)據(jù)包。于是，在通信傳輸時，很多協(xié)議規(guī)定在發(fā)送端對CRC編碼時定義一個Key寄存器，對CRC編碼進行初始化，定義一個不為0的初值，Key寄存器通常被設(shè)置為全1。結(jié)合圖1、圖2來說，就是在信息輸入給循環(huán)體之前，其D觸發(fā)器的值為1。

　　2，對接收端收到的數(shù)據(jù)包中拖尾0數(shù)據(jù)的處理。

　　接收端接收到信息字段和余式字段，計算出數(shù)據(jù)包的余式碼字，并與余式字段做比較，就能檢測出錯誤。更簡單的做法是，接收端對接收 到的所有數(shù)據(jù)求余式（包括信息字段和余式字段），如果沒有傳輸錯誤所得的余式一定為0。但是，余式為0并不一定能夠說明數(shù)據(jù)包沒有改變，如果數(shù)據(jù)包在余式字段后有0增加或者刪除的情況出現(xiàn)，就無法被檢測出來。

　　為了更好的理解公式的推導(dǎo)過程，需要用到1.2節(jié)中的幾個關(guān)于取模運算法則。接收端如何才能識別無差錯的傳輸呢？我們知道在發(fā)送側(cè)滿足：

　　余式值用十六進制表示：C704DD7B。

　　到此，關(guān)于通信用的CRC校驗實現(xiàn)原理除了通信過程中比特流順序之外，基本上是理順，使得知其然也知其所以然。