計算機循環(huán)冗余校驗算法分析

申豪東

摘 要 在計算機網(wǎng)絡通信中，為了將數(shù)據(jù)信息正確而迅速地在發(fā)送端及接收端間進行有效傳輸，必須采用差錯控制技術(shù)來保障數(shù)據(jù)傳輸?shù)恼_性與可靠性。循環(huán)冗余校驗碼（Cyclic redundancy check：CRC）因其檢驗速度快、檢錯率高且成本較低被廣泛應用于計算機網(wǎng)絡通信領域，提升了計算機信息傳輸?shù)馁|(zhì)量。文章對CRC的概念及工作原理進行了簡要分析，并結(jié)合CRC-8進行了算法設計與總結(jié)分析，并指出了CRC的優(yōu)勢所在。

關鍵詞 計算機網(wǎng)絡通信；循環(huán)冗余校驗碼（CRC）；算法；分析

中圖分類號 TP3 文獻標識碼 A 文章編號 1674-6708（2019）229-0131-02

計算機網(wǎng)絡通信是在公共的通信協(xié)議基礎之上實現(xiàn)數(shù)據(jù)的發(fā)送與接受，而計算機是利用數(shù)據(jù)鏈路將應用程序、數(shù)據(jù)傳輸包等資源進行系統(tǒng)連接，從而在不同系統(tǒng)內(nèi)進行信息的流通與共享。計算機網(wǎng)絡通信數(shù)據(jù)信息在傳輸時并不一定不出出現(xiàn)錯誤代碼，其傳輸?shù)恼_率往往受到外界條件的干擾，導致錯誤代碼的產(chǎn)生[ 1 ]，而數(shù)據(jù)通信系統(tǒng)傳輸?shù)恼_率與傳輸速度也存在一定的內(nèi)在？關系。

隨著網(wǎng)絡通信數(shù)據(jù)傳輸速度的提升，傳輸過程中錯誤碼的比例也隨之提高。因此，？通過合理的方法解決數(shù)據(jù)傳輸正確率與傳輸速度的矛盾關系是檢驗一個計算機通信系統(tǒng)是否有效的？關鍵。

CRC算法就是對傳輸數(shù)據(jù)進行高效校驗且誤判率很低的控制方法。本文針對當前網(wǎng)絡數(shù)據(jù)在傳輸過程中的一些校驗算法，結(jié)合對計算機數(shù)據(jù)傳輸?shù)睦斫猓治隽搜h(huán)冗余校驗算法，為進一步深入學習計算機相關專業(yè)奠定基礎。

1 循環(huán)冗余校驗算法原理

1.1 CRC算法介紹

CRC在計算機通信過程中能夠完成對信息字段的隨意選擇，并能完成對選擇信息字段的校驗，校驗后的信息字段通過多項式計算得到新的結(jié)果，將結(jié)果附在幀后，并在接受設備中進行同樣的信息字段選擇、校驗與計算的過程，從而在一定程度上保證了數(shù)據(jù)由發(fā)送端至接收端傳輸過程的正確性與完整性[2]。因此，在數(shù)據(jù)通信領域，CRC成為了較為常用的查錯校驗？方法。

CRC是在通信過程中常用的二元碼，而二元碼在信息傳遞過程中往往會發(fā)生0到1或從1到0的突變現(xiàn)象。在對CRC進行操作之前，應當測試位于存儲位置的存儲字節(jié)數(shù)，以保證存儲位置能夠具備存儲龐大參數(shù)表數(shù)據(jù)的空間。計算機網(wǎng)絡通信通過硬軟件兩部分實現(xiàn)算法，實現(xiàn)效果與數(shù)據(jù)傳輸?shù)乃俣瘸烧龋珻RC通過發(fā)送相應數(shù)據(jù)包的方式來使得通信數(shù)據(jù)傳輸?shù)墓δ艿玫剑靠刂啤?/p>

由于不同的數(shù)據(jù)包具有不同的字節(jié)長度，因此在數(shù)據(jù)傳輸過程中需要使用專門用于測量字節(jié)長度的工具來對不同的數(shù)據(jù)包的字節(jié)長度進行測量，以保證在信息傳遞過程中的正確性[3]。數(shù)據(jù)包字節(jié)的尾部包含了數(shù)據(jù)與序列校驗碼等信息，在數(shù)據(jù)傳輸過程中發(fā)揮著糾正錯誤數(shù)據(jù)編碼的？作用。

雖然在數(shù)據(jù)傳輸過程中不可避免的出現(xiàn)差錯，但通過CRC可以在一定程度上降低差錯發(fā)生的概率。在實際應用的過程CRC值通常在發(fā)射端計算并發(fā)送，接收端會接收到涵蓋CRC值信息包。接收端將接收到的信息包進行解碼并計算出CRC值后與收到的CRC值進行比較以判斷接受的信息是否正確？無誤。

1.2 CRC算法步驟

循環(huán)冗余校驗算法的實現(xiàn)需要按照特定的步驟進行，其中有兩個步驟是關鍵。

一是預先隨機選擇確定一個最高位和最低位為1，且符合國際標準的二進制多項式（如X3+X2+1，可以表示為1101），該多項式在發(fā)送端和接收端都作為除數(shù)使用；二是通過模2除法運算的方式將原始幀與隨機選擇并計算出來的二進制多項式數(shù)值相除，計算出CRC。具體步驟可以如下？描述。

首先，選擇一個合適的數(shù)作為除數(shù)。

接著，通過計算的方式計算出這個合適除數(shù)的二進制位數(shù)，并以模2除法的方式將生成的數(shù)據(jù)幀除以選定的除數(shù)，CRC即為以該種方式相除得到的余數(shù)，CRC的位數(shù)因余數(shù)的位數(shù)比除數(shù)位數(shù)少一位，得到數(shù)值首位數(shù)字0需要保留在CRC中，不能？忽略。

最后，在原數(shù)據(jù)幀后加上計算出的首位為0的CRC，形成新的數(shù)據(jù)幀并發(fā)送至接收端，接收端獲取數(shù)據(jù)幀后以模2的方式除以的比除數(shù)位數(shù)少一位的余數(shù)，如果計算結(jié)果可以整除，則說明接收端接收到的數(shù)據(jù)幀沒有錯誤，即在傳輸過程中沒有出現(xiàn)差錯[4]。若計算的有誤，則需要重新檢驗，并通知重新發(fā)送數(shù)據(jù)幀。

2 循環(huán)冗余校驗算法設計

2.1 校驗算法設計背景

在通過計算機實現(xiàn)網(wǎng)絡實體通信時，首先要將要交換的信息分割成眾多的數(shù)據(jù)段，并分別在每個數(shù)據(jù)前后加入首部和校驗碼后形成完整的數(shù)據(jù)包。因為各個數(shù)據(jù)包中包含了各類有用的信息，且可在數(shù)據(jù)傳輸過程中進行人為控制，因此通過CRC校驗的方法提升數(shù)據(jù)通信過程中的準確率。

當將數(shù)據(jù)包末端加上CRC并經(jīng)計算機發(fā)送端發(fā)送時，計算機發(fā)送的數(shù)據(jù)就與CRC發(fā)生了聯(lián)系，并建立了編碼關系。隨后計算機接收端接收到來自發(fā)送端的數(shù)據(jù)包并進行譯碼獲得信息，再與經(jīng)發(fā)送端發(fā)送的信息進行比較分析，若兩種數(shù)據(jù)一致則說明數(shù)據(jù)包在傳輸過程中未受到其他干擾因素的影響，得到了正確的編碼信息[5]。

如果運算后得到的數(shù)據(jù)與發(fā)送端發(fā)送的數(shù)據(jù)不一致，則說明數(shù)據(jù)包在發(fā)送過程中出現(xiàn)了偏差，則需要以自動重發(fā)的方式將數(shù)據(jù)包重新發(fā)送，在通過同樣的過程將數(shù)據(jù)包進行譯碼再進行比對，直到接收端譯碼得到的數(shù)據(jù)與發(fā)送端傳輸?shù)臄?shù)據(jù)一致，通過此種方法確保計算機信息傳輸過程中信息的準確無誤，為計算機信息傳輸安全提供有力？保障。

2.2 基于CRC-8的算法設計

首先按照要求選擇特定的二進制除數(shù)，如有：x8+x5+x4+1-0x31（0x131）；x8+x2+x1+1-？0x07（0x107）；？ x8+x6+x4+x3+x2+x1-0x5E（0x15E）。在通過循環(huán)冗余校驗碼（CRC）-8校驗算法把校驗的數(shù)據(jù)通過循環(huán)異或與多項式比對時，由于通過循環(huán)異或的方式在實際中傳輸數(shù)據(jù)時，往往存在高位先傳和低位先傳兩種不同的方式。

通常數(shù)據(jù)從高位先傳的方式即循環(huán)異或從數(shù)據(jù)的高位開始稱為順序異或，對于數(shù)據(jù)從低位先傳的方式即循環(huán)異或從數(shù)據(jù)的低位開始，成為反序異或。兩種不同的異或方式，即使對應相同的多項式，計算出來的結(jié)果也是不一樣的，因此設計時要首先確定好實際異或順序。

在實際通信過程中，往往使用按字節(jié)查表的方式來獲得CRC-8。這種算法以計算本字節(jié)之后的CRC為基礎，把與跟上一字節(jié)的校驗碼相減差8位的位置處的數(shù)值向左移動8位得到數(shù)字，再加上上一字節(jié)校驗碼向右移8位后得到的數(shù)字，新的校驗碼即為這兩個數(shù)字之和的組成。將256個8位二進制序列數(shù)的CRC全部以表格的形式進行數(shù)據(jù)統(tǒng)計，編碼時對應表格中相應的數(shù)值查閱即可，進而提高了工作效率[6]。

2.3 CRC算法校驗的優(yōu)勢分析

在計算機網(wǎng)絡通信中運用CRC校驗時相對于其他校驗方法就有一定的優(yōu)勢。CRC可以高比例的糾正信息傳輸過程中的錯誤，可以在極短的時間內(nèi)完成數(shù)據(jù)校驗碼的計算，并迅速完成糾錯過程，通過數(shù)據(jù)包自動重發(fā)的方式使得計算機的通信速度大幅提高，對通信效率和安全提供了？保障[7]。

另外，由于CRC算法檢驗的檢錯能力極強，且檢測成本較低，因此在對于編碼器和電路的檢測中使用較為廣泛。從檢錯的正確率與速度、成本等方面，都比奇偶校驗等校驗方式具有優(yōu)勢。因而，CRC成為計算機信息通信領域最為普遍的校驗？方式。

3 結(jié)論

綜上所述，CRC算法作為一種糾錯效率高、成本低廉的算法在計算機網(wǎng)絡通信糾錯算法中廣泛應用，極大的提升了在在數(shù)據(jù)傳輸?shù)倪^程中信息的可靠性和正確率。因此需要在計算的過程中，重點關注有關多項式和算法編譯碼的問題，并結(jié)合其他算法的綜合運用，保障在信息傳輸過程中因各種原因?qū)е碌男畔㈠e誤被及時的發(fā)現(xiàn)與糾正，以提高計算機網(wǎng)絡整體通信效率與通信質(zhì)量。

參考文獻

[1]李長青.論CRC算法在計算機網(wǎng)絡通信中的應用[J].數(shù)字技術(shù)與應用，2017（12）：141-142.

[2]高岳，馬帥.CRC算法在計算機網(wǎng)絡通信中的應用研究[J].信息記錄材料，2017，18（10）：8-10.

[3]李欣.CRC算法在計算機網(wǎng)絡通信中的應用分析[J].物流工程與管理，2017，39（4）：166-167.

[4]趙玉紅.循環(huán)冗余校驗的實現(xiàn)方法[J].雷達與對抗，2006（4）：25-27.

[5]杜杏菁，劉春梅.循環(huán)冗余校驗算法分析和實現(xiàn)[J].華北科技學院學報，2005（3）：105-107.

[6]原明亭，蔣偉.基于字節(jié)查表的循環(huán)冗余校驗碼的軟件生成算法[J].山東礦業(yè)學院學報（自然科學版），2009（2）：73-75，78.

[7]顧文達，孫亞民，楊建榮.快速循環(huán)冗余校驗算法及其程序?qū)崿F(xiàn)[J].南京理工大學學報，2015（2）：113-116.