CRC校驗原理及推導(dǎo)過程

　　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ù)比特序列當作一個信息多項式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)冗余校驗碼的檢錯能力有以下特點：

　?。?）可檢測出所有奇數(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碼校驗