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

　　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ǔ)的四則運算，運算時不考慮位間進(jìn)位和借位。

　　模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位有效信息位表達(dá)為多項式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ù)表達(dá)式為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