循環冗余校驗碼---CRC碼

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

① CRC碼的編碼方法

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

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

　　模2加減：即按位加,可用異或邏輯實現。模2加與模2減的結果相同,即
　　　　0±0=0 0±1=1 1±0=1 1±1=0。兩個相同的數據的模2和為0。

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

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

　　下面介紹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個數據位拼接上r個校驗位得到的。校驗位的值，就是通過對多項式M(x) * x^r除以生成多項式G(x)(特定的一個多項式)所得到的余式。為了得到r位余數(校驗位)，G(x)必須是r+1位的，即為r次的多項式。
設所得余數表達式為R(x),商為 Q(x)，就有：
　　　　　M(x).x^r / G(x) = Q(x) + R(x) / G(x)

　　將r次余式直接拼接在源數據多項式的右側，可寫成M(x).xr + R(x)，并可推導出：
　　　　　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)（多項式）數碼除盡的數碼（多項式）。
　　例：對四位源信息 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位)

　　

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