循環(huán)冗余校驗碼

1、循環(huán)循環(huán)冗余檢查（冗余檢查（CRCCRC）是一種數(shù)據(jù)傳輸檢錯功能，）是一種數(shù)據(jù)傳輸檢錯功能，對數(shù)據(jù)進行對數(shù)據(jù)進行多項式多項式g g（X X）計算）計算，并將得到的結果，并將得到的結果附附在在要傳輸?shù)男畔⒁獋鬏數(shù)男畔⒌牡暮竺妫邮赵O備也執(zhí)行類似后面，接收設備也執(zhí)行類似的算法，以保證數(shù)據(jù)傳輸?shù)恼_性和完整性。若的算法，以保證數(shù)據(jù)傳輸?shù)恼_性和完整性。若CRCCRC校驗不通過，系統(tǒng)重復向硬盤復制數(shù)據(jù)，陷校驗不通過，系統(tǒng)重復向硬盤復制數(shù)據(jù)，陷入死循環(huán)，導致復制過程無法完成。出現(xiàn)循環(huán)冗入死循環(huán)，導致復制過程無法完成。出現(xiàn)循環(huán)冗余檢查錯誤的可能原因非常多，硬件軟件的故障余檢查錯誤的可能原因非常多，硬件軟件

2、的故障都有可能都有可能。接收方如何檢查收到的信息有無錯誤？接收方如何檢查收到的信息有無錯誤？ 首先接收方和發(fā)送方約定一個首先接收方和發(fā)送方約定一個“生成多項生成多項式式”g(xg(x）。相當于兩方傳遞信息需要對的口令。）。相當于兩方傳遞信息需要對的口令。CRC（Cyclic Redundancy Check）循環(huán)冗余校驗碼，是常用的校驗碼，在早期的通信中運用廣泛，因為早期的通信技術不夠可靠（不可靠性的來源是通信技術決定的，比如電磁波通信時受雷電等因素的影響），不可靠的通信就會帶來確認信息的困惑。對通信的可靠性檢查就需要校驗，校驗是從數(shù)據(jù)本身進行檢查，它依靠某種數(shù)學上約定的形式進行檢查，校驗的結

3、果是可靠或不可靠，如果可靠就對數(shù)據(jù)進行處理，如果不可靠，就丟棄重發(fā)或者進行修復。（倒推法）：（倒推法）：發(fā)送方發(fā)送的是T(x)，接收方接收到的是R(x)，若T(x)和R(X)相等，則傳輸?shù)倪^程中沒有出現(xiàn)錯誤。如何判斷T(x)和R(X)是否相等？若R(X)能夠被g(x)整除，則接收方認為T(x)和R(X)相等，即傳輸?shù)倪^程中沒有出現(xiàn)錯誤。發(fā)送方要傳輸?shù)男畔nfo包含在T(x)里，info是T(x)的一部分，但不能說info就是T(x)。實際應用中，g(x)的取值是有限制的，它受限于以下國際標準：CRC-CCITT=x16+x12+x5+1CRC-16=x16+x15+x2+1CRC-12=x1

4、2+x11+x3+x2+x+1關于g(x)的國際標準還有一些，這里不一一介紹。人工計算循環(huán)冗余校驗碼需要先弄清的知識：多項式除法、異或運算。CRC碼是由兩部分組成，前部分是信息碼，就是需要校驗的信息，后部分是校驗碼，如果CRC碼共長n個bit，信息碼長k個bit，就稱為（n,k）碼。它的編碼規(guī)則是：移位 將原信息碼（kbit）左移r位（k+r=n)，而后尾巴上添r個0。相除 運用一個生成多項式g(x)（必須轉換成二進制數(shù)）用模2除上面的式子，得到的余數(shù)就是校驗碼。 移位后的信息碼mod多項式g(x)=校驗碼非常簡單，要說明的：模2除就是在除的過程中用模2加，模2加實際上就是我們熟悉的異或運算，

5、就是加法不考慮進位，公式是：0+0=1+1=0,1+0=0+1=1即異則真，非異則假。由此得到定理：a+b+b=a 也就是模2減和模2加直值表完全相同。有了加減法就可以用來定義模2除法，于是就可以用生成多項式g(x）生成CRC校驗碼。CRC碼生成和校驗基本分為三步：第一步：在數(shù)據(jù)單元(k位）的末尾加上r個0。r是一個比預定除數(shù)g(x)的比特位數(shù)(r+1)少1的數(shù)。第二步：采用二進制除法將新的加長的數(shù)據(jù)單元（k+r位)除以除數(shù)g(x) 。由此除法產生的余數(shù)就是循環(huán)冗余碼校驗碼。第三步：求CRC循環(huán)冗余校驗碼(K+r)被除數(shù)+r(余數(shù))如果余數(shù)位數(shù)小于r，最左的缺省位數(shù)為0。如果余數(shù)為0,則r=0

6、。生成多項式應滿足以下原則a、生成多項式的最高位和最低位必須為1。b、當被傳送信息（CRC碼）任何一位發(fā)生錯誤時，被生成多項式做模2除后應該使余數(shù)不為0。c、不同位發(fā)生錯誤時，應該使余數(shù)不同。d、對余數(shù)繼續(xù)做模2除，應使余數(shù)循環(huán)。 任何一個二進制數(shù)序列可以和一個只含有0和1兩個系數(shù)的代數(shù)多項式建立起一一對應的關系。因此，用來求CRC碼的那個除數(shù)通常用多項式來表示。原因如下：代數(shù)多項式很短可以通過多項式來進行概念的數(shù)學證明。 任何一個n位的二進制數(shù)都可以用一個n-1 次的多項式來表示,這種多項式叫碼多項式（又叫信息多項式） 。碼多項式與二進制序列之間的一一對應關系：（an-1 an-2a1a0）

7、N A (x)= an-1Xn-1+an-2Xn-2 +a1X+a0X0碼多項式以n=3位二進制數(shù)為例 二進制數(shù) 對應多項式 000 001 010 011 100 101 111 01xx+1x2x2+1x2+ x+1n1011011 x6+x4+x3+x+1nx5+x4+x2+x 110110碼多項式運算法則:二進制碼多項式的加減運算為模2加運算，即兩個碼多項式相加時，對應項系數(shù)進行模2加減。乘除運算與普通多項式類似；模2加減：即各位做不帶進位、借位的按位加減。這種加減運算實際上就是邏輯上的異或運算。即加法和減法等價。碼多項式碼多項式生成多項式G(x):求CRC碼時所用的“除數(shù)”所對應的多

8、項式叫生成多項式。在串行通信中通常使用下列三種生成多項式G（X）來產生CRC碼。CRC-16：G(x)=X16+X15+X2+1，美國二進制同步系統(tǒng)中采用。CRC-CCITT：G(x)=X16+X12+X5+1，CCITT推薦。CRC-32：G(x)=X32+X26+X23+X22+ X16+X12+ X11+X10+X8+1X7+ X5+X4+X2+X+ 1碼多項式碼多項式循環(huán)冗余碼生成器采用模2除法。下圖顯示了這一過程。CRC校驗器的功能完全像發(fā)生器一樣，當收到附加了CRC碼的數(shù)據(jù)后，做同樣的模2 除法。如果余數(shù)是全0，則將CRC碼丟棄，接受數(shù)據(jù)。否則，丟棄收到的數(shù)據(jù)。r個比特0數(shù)據(jù)g(x

9、)CRC校驗碼r+1r余數(shù)先發(fā)數(shù)據(jù)位先發(fā)數(shù)據(jù)位后發(fā)校驗位后發(fā)校驗位g(x)余數(shù)r+1r數(shù)據(jù)0接收，非接收，非0拒絕拒絕數(shù)據(jù)發(fā)送方發(fā)送方接收方接收方 0G(X) 111010100011010 CRC校驗碼 信息碼 CRC冗余校驗碼CRC碼是很有效的差錯校驗方法。除了正好數(shù)據(jù)塊的比特值是按除數(shù)值變化的錯誤外，循環(huán)冗余校驗(CRC)將檢測出其他所有錯誤。而且，常用的CRC除數(shù)通常有17，或是33個比特，使得不可檢測的錯誤可能降低到幾乎近于零。CRC接收電路再配上適當?shù)挠布娐凡粌H可以檢錯，而且可以糾錯，糾錯能力很強特別適合檢測突發(fā)性錯誤，在數(shù)據(jù)通信中得到較廣泛的應用。能檢測出全部單個錯誤能檢測出全

10、部隨機二位錯誤能檢測出全部奇數(shù)個錯誤能檢測出全部長度小于k位的突發(fā)錯誤能以1-（1/2）k-1概率檢測出長度為（k+1）位的突發(fā)性錯誤例如：g(x)=x4+x3+x2+1，（7,3）碼，信息碼110產生的CRC碼就是：對于g(x)=x4+x3+x2+1的解釋：（都是從右往左數(shù)）x4就是第五位是1，因為沒有x1所以第2位就是0。11101 | 110,0000（設a=11101 ，b=1100000）用b除以a做模2運算得到余數(shù)：1001余數(shù)是1001，所以CRC碼是1001，傳輸碼為：110,1001若信息碼字為11100011，生成多項式 G（X）=X5+X4+X+1，則計算出的 CRC 校驗碼為？1110001100000/110011=10110110*1100