循環(huán)冗余校驗碼（CRC），簡稱循環(huán)碼，是一種常用的、具有檢錯、糾錯能力的校驗碼，在早期的通信中運用廣泛。通過某種數(shù)學(xué)運算來建立數(shù)據(jù)位和校驗位的約定關(guān)系。這種數(shù)學(xué)運算就是“模2除法”。這種編碼基本思想是將要傳送的信息M(X)表示為一個多項式L，用L除以一個預(yù)先確定的多項式G(X)，得到的余式就是所需的循環(huán)冗余校驗碼，所以這種校驗又稱多項式校驗。理論上可以證明循環(huán)冗余校驗碼的檢錯能力有以下特點：①可檢測出所有奇數(shù)位錯；②可檢測出所有雙比特的錯；③可檢測出所有小于、等于校驗位長度的突發(fā)錯。

1.模2除法

先說下什么是“模2除法”，我們知道模2加減是不進位、不借位的加減法，比如1+1=0，1+0=1，101+011=110，等于每一位的異或運算，相同bit加減為0，不同bit加減則為1。模2除法同理，即當(dāng)部分余數(shù)首位是1時商取1，反之商取0。然后每一位的減法運算是按位減，不產(chǎn)生借位。余數(shù)的位數(shù)一定要是比除數(shù)位數(shù)只能少一位，哪怕前面位是0，甚至是全為0（附帶好整除時）也都不能省略。舉例如下圖所示：

2.校驗位的生成

循環(huán)冗余校驗碼由信息碼n位和校驗碼k位構(gòu)成。k位校驗位拼接在n位數(shù)據(jù)位后面，則n+k為CRC校驗碼的字長。n位信息位可以表示成為一個報文多項式M(x)，最高冪次是x^(n-1)。 約定的生成多項式G(x)是一個k+1位的二進制數(shù)，最高冪次是x^k。 將報文多項式M(x)乘以x^k，即其對應(yīng)的2進制序列左移k位后，模2除以G(x)，得到的k位余數(shù)就是校驗位。將這些校驗位加在被除數(shù)上，作為實際發(fā)送的數(shù)據(jù)，則傳輸過程中如果不出錯，收端收到的數(shù)據(jù)一定是可以整除校驗位的，因為導(dǎo)致不能整除的余數(shù)已經(jīng)在發(fā)送的時候被模2加在了被除數(shù)上。生成多項式必須是發(fā)送端和接收端都知道的信息，且最高位和最低位必須均為“1”。

3.計算舉例

下面通過一個例子來進一步解釋CRC的基本工作原理：
(1)假設(shè)約定的生成多項式為G(x)=x^4+x+1，則其二進制表示為10011，共5位，其中k=4。
(2)假設(shè)要發(fā)送數(shù)據(jù)序列的二進制為101011，共6位，則報文多項式為M(x)=x^5
+x^3+x+1。
(3)將報文多項式乘以x^k, 即乘以x^4， 生成M(x)*x^k = x^9 + x^7 +x^5 + x^4，表示為二進制則為1010110000，即等于在要發(fā)送的二進制數(shù)據(jù)后面加4個0，共10位。
(4)用生成多項式的二進制表示10011去除1010110000，按模2算法求得余數(shù)比特序列為0100（注意余數(shù)一定是k位的）。

(5)將余數(shù)添加到要發(fā)送的數(shù)據(jù)后面，得到真正要發(fā)送的數(shù)據(jù)的比特流：1010110100，其中前6位為原始數(shù)據(jù)，后4位為CRC校驗碼。
(6)接收端在接收到帶CRC校驗碼的數(shù)據(jù)后，如果數(shù)據(jù)在傳輸過程中沒有出錯，將一定能夠被相同的生成多項式G(x)除盡，如果數(shù)據(jù)在傳輸中出現(xiàn)錯誤，生成多項式G(x)去除后得到的結(jié)果肯定不為0。

總結(jié)

以上是生活随笔為你收集整理的CRC循环校验码原理及计算举例的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。