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

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

2、文章編號 1674-6708（2019）229-0131-02計算機(jī)網(wǎng)絡(luò)通信是在公共的通信協(xié)議基礎(chǔ)之上實現(xiàn)數(shù)據(jù)的發(fā)送與接受，而計算機(jī)是利用數(shù)據(jù)鏈路將應(yīng)用程序、數(shù)據(jù)傳輸包等資源進(jìn)行系統(tǒng)連接，從而在不同系統(tǒng)內(nèi)進(jìn)行信息的流通與共享。計算機(jī)網(wǎng)絡(luò)通信數(shù)據(jù)信息在傳輸時并不一定不出出現(xiàn)錯誤代碼，其傳輸?shù)恼_率往往受到外界條件的干擾，導(dǎo)致錯誤代碼的產(chǎn)生 1 ，而數(shù)據(jù)通信系統(tǒng)傳輸?shù)恼_率與傳輸速度也存在一定的內(nèi)在？關(guān)系。隨著網(wǎng)絡(luò)通信數(shù)據(jù)傳輸速度的提升，傳輸過程中錯誤碼的比例也隨之提高。因此，？通過合理的方法解決數(shù)據(jù)傳輸正確率與傳輸速度的矛盾關(guān)系是檢驗一個計算機(jī)通信系統(tǒng)是否有效的？關(guān)鍵。crc算法就是對傳輸數(shù)據(jù)進(jìn)

3、行高效校驗且誤判率很低的控制方法。本文針對當(dāng)前網(wǎng)絡(luò)數(shù)據(jù)在傳輸過程中的一些校驗算法，結(jié)合對計算機(jī)數(shù)據(jù)傳輸?shù)睦斫?，分析了循環(huán)冗余校驗算法，為進(jìn)一步深入學(xué)習(xí)計算機(jī)相關(guān)專業(yè)奠定基礎(chǔ)。1 循環(huán)冗余校驗算法原理1.1 crc算法介紹crc在計算機(jī)通信過程中能夠完成對信息字段的隨意選擇，并能完成對選擇信息字段的校驗，校驗后的信息字段通過多項式計算得到新的結(jié)果，將結(jié)果附在幀后，并在接受設(shè)備中進(jìn)行同樣的信息字段選擇、校驗與計算的過程，從而在一定程度上保證了數(shù)據(jù)由發(fā)送端至接收端傳輸過程的正確性與完整性2。因此，在數(shù)據(jù)通信領(lǐng)域，crc成為了較為常用的查錯校驗？方法。crc是在通信過程中常用的二元碼，而二元碼在信息傳

4、遞過程中往往會發(fā)生0到1或從1到0的突變現(xiàn)象。在對crc進(jìn)行操作之前，應(yīng)當(dāng)測試位于存儲位置的存儲字節(jié)數(shù)，以保證存儲位置能夠具備存儲龐大參數(shù)表數(shù)據(jù)的空間。計算機(jī)網(wǎng)絡(luò)通信通過硬軟件兩部分實現(xiàn)算法，實現(xiàn)效果與數(shù)據(jù)傳輸?shù)乃俣瘸烧龋琧rc通過發(fā)送相應(yīng)數(shù)據(jù)包的方式來使得通信數(shù)據(jù)傳輸?shù)墓δ艿玫?？控制。由于不同的?shù)據(jù)包具有不同的字節(jié)長度，因此在數(shù)據(jù)傳輸過程中需要使用專門用于測量字節(jié)長度的工具來對不同的數(shù)據(jù)包的字節(jié)長度進(jìn)行測量，以保證在信息傳遞過程中的正確性3。數(shù)據(jù)包字節(jié)的尾部包含了數(shù)據(jù)與序列校驗碼等信息，在數(shù)據(jù)傳輸過程中發(fā)揮著糾正錯誤數(shù)據(jù)編碼的？作用。雖然在數(shù)據(jù)傳輸過程中不可避免的出現(xiàn)差錯，但通過crc可以

5、在一定程度上降低差錯發(fā)生的概率。在實際應(yīng)用的過程crc值通常在發(fā)射端計算并發(fā)送，接收端會接收到涵蓋crc值信息包。接收端將接收到的信息包進(jìn)行解碼并計算出crc值后與收到的crc值進(jìn)行比較以判斷接受的信息是否正確？無誤。1.2 crc算法步驟循環(huán)冗余校驗算法的實現(xiàn)需要按照特定的步驟進(jìn)行，其中有兩個步驟是關(guān)鍵。一是預(yù)先隨機(jī)選擇確定一個最高位和最低位為1，且符合國際標(biāo)準(zhǔn)的二進(jìn)制多項式（如x3+x2+1，可以表示為1101），該多項式在發(fā)送端和接收端都作為除數(shù)使用；二是通過模2除法運(yùn)算的方式將原始幀與隨機(jī)選擇并計算出來的二進(jìn)制多項式數(shù)值相除，計算出crc。具體步驟可以如下？描述。首先，選擇一個合適的數(shù)

6、作為除數(shù)。接著，通過計算的方式計算出這個合適除數(shù)的二進(jìn)制位數(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)冗余校驗算法設(shè)計2.1 校驗算法設(shè)計背景在通過計算機(jī)實現(xiàn)網(wǎng)絡(luò)實體通信時，首先

7、要將要交換的信息分割成眾多的數(shù)據(jù)段，并分別在每個數(shù)據(jù)前后加入首部和校驗碼后形成完整的數(shù)據(jù)包。因為各個數(shù)據(jù)包中包含了各類有用的信息，且可在數(shù)據(jù)傳輸過程中進(jìn)行人為控制，因此通過crc校驗的方法提升數(shù)據(jù)通信過程中的準(zhǔn)確率。當(dāng)將數(shù)據(jù)包末端加上crc并經(jīng)計算機(jī)發(fā)送端發(fā)送時，計算機(jī)發(fā)送的數(shù)據(jù)就與crc發(fā)生了聯(lián)系，并建立了編碼關(guān)系。隨后計算機(jī)接收端接收到來自發(fā)送端的數(shù)據(jù)包并進(jìn)行譯碼獲得信息，再與經(jīng)發(fā)送端發(fā)送的信息進(jìn)行比較分析，若兩種數(shù)據(jù)一致則說明數(shù)據(jù)包在傳輸過程中未受到其他干擾因素的影響，得到了正確的編碼信息5。如果運(yùn)算后得到的數(shù)據(jù)與發(fā)送端發(fā)送的數(shù)據(jù)不一致，則說明數(shù)據(jù)包在發(fā)送過程中出現(xiàn)了偏差，則需要以自動重

8、發(fā)的方式將數(shù)據(jù)包重新發(fā)送，在通過同樣的過程將數(shù)據(jù)包進(jìn)行譯碼再進(jìn)行比對，直到接收端譯碼得到的數(shù)據(jù)與發(fā)送端傳輸?shù)臄?shù)據(jù)一致，通過此種方法確保計算機(jī)信息傳輸過程中信息的準(zhǔn)確無誤，為計算機(jī)信息傳輸安全提供有力？保障。2.2 基于crc-8的算法設(shè)計首先按照要求選擇特定的二進(jìn)制除數(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ù)時，往往存在高位先傳和低位先傳兩種不同的方式

9、。通常數(shù)據(jù)從高位先傳的方式即循環(huán)異或從數(shù)據(jù)的高位開始稱為順序異或，對于數(shù)據(jù)從低位先傳的方式即循環(huán)異或從數(shù)據(jù)的低位開始，成為反序異或。兩種不同的異或方式，即使對應(yīng)相同的多項式，計算出來的結(jié)果也是不一樣的，因此設(shè)計時要首先確定好實際異或順序。在實際通信過程中，往往使用按字節(jié)查表的方式來獲得crc-8。這種算法以計算本字節(jié)之后的crc為基礎(chǔ)，把與跟上一字節(jié)的校驗碼相減差8位的位置處的數(shù)值向左移動8位得到數(shù)字，再加上上一字節(jié)校驗碼向右移8位后得到的數(shù)字，新的校驗碼即為這兩個數(shù)字之和的組成。將256個8位二進(jìn)制序列數(shù)的crc全部以表格的形式進(jìn)行數(shù)據(jù)統(tǒng)計，編碼時對應(yīng)表格中相應(yīng)的數(shù)值查閱即可，進(jìn)而提高了工作

10、效率6。2.3 crc算法校驗的優(yōu)勢分析在計算機(jī)網(wǎng)絡(luò)通信中運(yùn)用crc校驗時相對于其他校驗方法就有一定的優(yōu)勢。crc可以高比例的糾正信息傳輸過程中的錯誤，可以在極短的時間內(nèi)完成數(shù)據(jù)校驗碼的計算，并迅速完成糾錯過程，通過數(shù)據(jù)包自動重發(fā)的方式使得計算機(jī)的通信速度大幅提高，對通信效率和安全提供了？保障7。另外，由于crc算法檢驗的檢錯能力極強(qiáng)，且檢測成本較低，因此在對于編碼器和電路的檢測中使用較為廣泛。從檢錯的正確率與速度、成本等方面，都比奇偶校驗等校驗方式具有優(yōu)勢。因而，crc成為計算機(jī)信息通信領(lǐng)域最為普遍的校驗？方式。3 結(jié)論綜上所述，crc算法作為一種糾錯效率高、成本低廉的算法在計算機(jī)網(wǎng)絡(luò)通信糾

11、錯算法中廣泛應(yīng)用，極大的提升了在在數(shù)據(jù)傳輸?shù)倪^程中信息的可靠性和正確率。因此需要在計算的過程中，重點關(guān)注有關(guān)多項式和算法編譯碼的問題，并結(jié)合其他算法的綜合運(yùn)用，保障在信息傳輸過程中因各種原因?qū)е碌男畔㈠e誤被及時的發(fā)現(xiàn)與糾正，以提高計算機(jī)網(wǎng)絡(luò)整體通信效率與通信質(zhì)量。參考文獻(xiàn)1李長青.論crc算法在計算機(jī)網(wǎng)絡(luò)通信中的應(yīng)用j.數(shù)字技術(shù)與應(yīng)用，2017（12）：141-142.2高岳，馬帥.crc算法在計算機(jī)網(wǎng)絡(luò)通信中的應(yīng)用研究j.信息記錄材料，2017，18（10）：8-10.3李欣.crc算法在計算機(jī)網(wǎng)絡(luò)通信中的應(yīng)用分析j.物流工程與管理，2017，39（4）：166-167.4趙玉紅.循環(huán)冗余校驗的實現(xiàn)方法j.雷達(dá)與對抗，2006（4）：25-27.5杜杏菁，劉