循環(huán)冗余校驗CRC（Cyclic Redundancy Check）是數(shù)據(jù)通信領域常用的一種數(shù)據(jù)傳輸檢錯技術。通過在發(fā)送端對數(shù)據(jù)按照某種算法計算出校驗碼，并將得到的校驗碼附在數(shù)據(jù)幀的后面，一起發(fā)送到接收端。接收端對收到的數(shù)據(jù)和校驗碼按照相同算法進行驗證，以此判斷接收到的數(shù)據(jù)是否正確、完整。

CRC簡介

我們知道，數(shù)據(jù)在傳輸過程中可能會因為傳輸介質(zhì)故障或外界的干擾而產(chǎn)生比特差錯（使原來的0變?yōu)?，原來的1變?yōu)?），從而導致接收方接收到錯誤的數(shù)據(jù)。為盡量提高接收方收到數(shù)據(jù)的正確率，在接收數(shù)據(jù)之前需要對數(shù)據(jù)進行差錯檢測，僅當檢測的結果為正確時才接收數(shù)據(jù)。

差錯檢測的方式有多種，常見的有奇偶校驗、求和校驗、CRC校驗等。他們的工作原理都是發(fā)送端對數(shù)據(jù)按照某種算法計算出來校驗碼，將校驗碼和數(shù)據(jù)一起發(fā)送到接收端，然后接收端進行檢驗確定數(shù)據(jù)是否發(fā)生變化。

CRC是由W. Wesley Peterson在1961年發(fā)表的論文中提出，由于CRC校驗在速度、成本、正確率等方面比其他校驗方式更具有優(yōu)勢，因此，CRC成為計算機信息、通信領域最為普遍的校驗方式。例如在標準的以太幀格式中，最后有4個字節(jié)長度的冗余位，用于存儲CRC校驗的值，這個冗余位又常稱為幀檢驗序列FCS（Frame Check Sequence）。

以太幀結構

CRC是如何計算的？

CRC的思想就是先在要發(fā)送的K比特長度的數(shù)據(jù)后面附加一個R比特長度的校驗碼，然后生成一個新幀發(fā)送給接收端。接收端接收到新幀后，根據(jù)收到的數(shù)據(jù)和校驗碼來驗證接收到的數(shù)據(jù)是否正確。

數(shù)據(jù)+校驗碼示例

數(shù)據(jù)+校驗碼示例?

當然，這個附加的校驗碼不是隨意添加的，要使所生成的新幀能與發(fā)送端和接收端共同選定的某個特定數(shù)整除（“模2除法”）。接收端把接收到的新幀除以這個選定的除數(shù)。因為在發(fā)送數(shù)據(jù)幀之前就已通過附加一個數(shù)，做了“去余”處理（也就已經(jīng)能整除了），所以結果應該是沒有余數(shù)。如果有余數(shù)，則表明該幀在傳輸過程中出現(xiàn)了差錯。

在K比特數(shù)據(jù)后面再拼接R比特的校驗碼，整個編碼長度為N比特，這種編碼也叫(N,K)碼。對于一個給定的(N,K)碼，可以證明存在一個最高次冪為N-K=R的多項式g(x)，根據(jù)g(x)可以生成R比特的校驗碼。其算法是以GF(2)多項式算術為數(shù)學基礎的，原理如下圖所示。

CRC計算公式?

g(x)叫做這個校驗碼的生成多項式。不同的CRC生成多項式，其檢錯能力是不同的。要使用R位校驗碼，生成多項式的次冪應為R。以下為常見的一些標準多項式。

常見生成多項式

這些多項式的值便是模2除法的除數(shù)。而根據(jù)這個除數(shù)獲得校驗碼并進行校驗的原理可以分為以下幾個步驟：

發(fā)送端、接收端在通信前，約定好除數(shù)P，也就是前面說的多項式的值。P應該是R+1位長度；
發(fā)送端首先在原來的K位數(shù)據(jù)后面加R個0，相當于原來的數(shù)據(jù)左移了R位；
然后進行模2除法運算（其實就是異或XOR運算），將加0之后的K+R位的數(shù)除以P，循環(huán)計算，直到余數(shù)的階數(shù)小于R，這個余數(shù)就是附加的校驗碼，如果長度不足R位需要在前面加0補齊；
發(fā)送端將R位校驗碼附加在原數(shù)據(jù)后面發(fā)送給接收方；
接收方接收到數(shù)據(jù)后，將數(shù)據(jù)以模2除法方式除以除數(shù)P。如果沒有余數(shù)，說明在傳輸過程中沒有出現(xiàn)錯誤，否則說明有錯誤。

下面以一個簡單示例來展示CRC的計算過程：

以g(x)為CRC-4=X4+X+1為例，此時除數(shù)P=10011。假設源數(shù)據(jù)M為10110011。

在發(fā)送端將M左移4位，然后除以P。

發(fā)送端CRC計算示例?

計算得到的余數(shù)就是0100，也就是CRC校驗碼。將0100附加到原始數(shù)據(jù)幀10110011后，組成新幀101100110100發(fā)送給接收端。接收端接收到該幀后，會用該幀去除以上面選定的除數(shù)P，驗證余數(shù)是否為0，如果為0，則表示數(shù)據(jù)在傳輸過程中沒有出現(xiàn)差錯。