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

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

　　二進制信息位串沿一條信號線逐位在部件之間或計算機之間傳送稱為串行傳送。CRC(Cyclic Redundancy check)碼可以發(fā)現(xiàn)并糾正信息串行讀寫、存儲或傳送過程中出現(xiàn)的一位、多位錯誤，因此在磁介質(zhì)存儲器讀寫和計算機之間通信方面得到廣泛應(yīng)用。

　　CRC碼一般是指k位信息碼之后拼接r位校驗碼。應(yīng)用CRC碼的關(guān)鍵，是如何從k位信息位簡便地得到r位校驗位(編碼)的值，以及如何判斷k+r位的碼字是否正確。下面僅就CRC碼應(yīng)用中的問題做簡單介紹(有關(guān)的理論問題請參閱有關(guān)書籍)。

① CRC碼的編碼方法

　　先介紹CRC碼編碼用到的模2除運算。

　　模2運算是指以按位模2相加為基礎(chǔ)的四則運算，運算時不考慮位間進位和借位。

　　模2加減：即按位加,可用異或邏輯實現(xiàn)。模2加與模2減的結(jié)果相同,即
　　　　0±0=0 0±1=1 1±0=1 1±1=0。兩個相同的數(shù)據(jù)的模2和為0。

　　模2乘：按模2加求部分積之和。
　　例: 　　　1010
　　　　 　　　101
　　　　　
　　　　　　　1010
　　　　　　 0000
　　　　　　1010
　　　　　
　　　　 　 100010

　　模2除：按模2減（加）求部分余數(shù)。每求一位商應(yīng)使部分余數(shù)減少一位。
　　上商的原則是：當(dāng)部分余數(shù)的最高位為1時，該位商取1；為0時，該位商取0。當(dāng)部分的余數(shù)的位數(shù)小于除數(shù)的位數(shù)時，該余數(shù)即為最后余數(shù)。
　　例如，

　　下面介紹CRC碼的編碼方法。
　　首先,可將待編碼的k位有效信息位表達為多項式M(x)形式:
　　　　M(x)= C_k-1x^k-1 + C_k-2x ^k-2+…+C_ixⁱ+…+C₁x¹+C₀
　　式中C_i為0或1，x為偽變量，并用xⁱ指明各位間的排列位置。

　　若將信息位組左移r位,則可表示為多項式M(x) * x^r ,這樣就可以空出初值為０的r個校驗位，即
　　　　　　

　　CRC碼的碼字，是用k個數(shù)據(jù)位拼接上r個校驗位得到的。校驗位的值，就是通過對多項式M(x) * x^r除以生成多項式G(x)(特定的一個多項式)所得到的余式。為了得到r位余數(shù)(校驗位)，G(x)必須是r+1位的，即為r次的多項式。
設(shè)所得余數(shù)表達式為R(x),商為 Q(x)，就有：
　　　　　M(x).x^r / G(x) = Q(x) + R(x) / G(x)

　　將r次余式直接拼接在源數(shù)據(jù)多項式的右側(cè)，可寫成M(x).xr + R(x)，并可推導(dǎo)出：
　　　　　M(x).x^r + R(x) = [ Q(x)* G(x) + R(x) ] + R(x)
　　　　　　　　　　　　 = [ Q(x)* G(x) ] + [ R(x)+R(x) ]
　　　　　　　　　　　　 = Q(X)* G(x)

　　這證明所得到的CRC碼字是一個可被G(x)（多項式）數(shù)碼除盡的數(shù)碼（多項式）。
　　例：對四位源信息 1100，來求三個校驗位的值，可選擇生成多項式為 1011，則有：
　　　　 M(x) = x³ + x² = 1100 　　　(k = 4)
　　　　 M(x)*x³ = x⁶ + x⁵ = 1100000 (左移， r = 3位)
　　　　 G(x) = x³+ x + 1 =1011 　　 (r+1 = 4位)

　　

　　所得到的碼字（系統(tǒng)線性（7,4）分組碼）為：
　　　　 M(x).x³ + R(x) = 1100000 + 010 = 1100010