From Wiki-Cyclic redundancy check
A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data. Blocks of data entering these systems get a short check value attached, based on the remainder of a polynomial division of their contents. On retrieval, the calculation is repeated and, in the event the check values do not match, corrective action can be taken against data corruption.
From 循環(huán)冗余校驗CRC簡介
- CRC為校驗和的一種，是兩個字節(jié)數(shù)據(jù)流采用二進制除法（沒有借位和進位，使用異或來代替減法）相除所得到的余數(shù)。
- 其中被除數(shù)是需要計算校驗和的信息數(shù)據(jù)流的二進制表示；除數(shù)是一個長度為(n+1)的預(yù)定義二進制數(shù)，通常用多項式的系數(shù)來表示。
- 在做除法之前，要在信息數(shù)據(jù)之后先加上n個0。冗余碼的位數(shù)是n位。冗余碼的計算方法是，先將信息碼后面補0，補0的個數(shù)是生成多項式最高次冪；將補零之后的信息碼用模二除法（非二進制除法）除以G(X)對應(yīng)的2進制碼，注意除法過程中所用的減法是模2減法（注意是高位對齊），即沒有借位的減法，也就是異或運算。
- 當被除數(shù)逐位除完時，得到比除數(shù)少一位的余數(shù)。此余數(shù)即為冗余位,將其添加在信息位后便構(gòu)成CRC碼字。
例如，假設(shè)信息碼字為11100011，生成多項式G(X)=X5+X4+X+1，計算CRC碼字。G(X) = X5+X4+X+1,也就是110011，因為最高次是5，所以，在信息碼字后補5個0，變?yōu)?110001100000。
用1110001100000模二除法除以110011，余數(shù)為11010，即為所求的冗余位。因此發(fā)送出去的CRC碼字為原始碼字11100011末尾加上冗余位11010，即 1110001111010。
接收端收到碼字后，采用同樣的方法驗證，即將收到的碼字用模二除法除以110011（是G(X)對應(yīng)的二進制生成碼），發(fā)現(xiàn)余數(shù)是0，則認為碼字在傳輸過程中沒有出錯。
盡管在錯誤檢測中非常有用，CRC并不能可靠地校驗數(shù)據(jù)完整性（即數(shù)據(jù)沒有發(fā)生任何變化），這是因為CRC多項式是線性結(jié)構(gòu)，可以非常容易地故意改變量據(jù)而維持CRC不變。
