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

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

　　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