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

申豪東

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

關(guān)鍵詞 計(jì)算機(jī)網(wǎng)絡(luò)通信；循環(huán)冗余校驗(yàn)碼（CRC）；算法；分析

中圖分類號(hào) TP3 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào) 1674-6708（2019）229-0131-02

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

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

CRC算法就是對(duì)傳輸數(shù)據(jù)進(jìn)行高效校驗(yàn)且誤判率很低的控制方法。本文針對(duì)當(dāng)前網(wǎng)絡(luò)數(shù)據(jù)在傳輸過(guò)程中的一些校驗(yàn)算法，結(jié)合對(duì)計(jì)算機(jī)數(shù)據(jù)傳輸?shù)睦斫?，分析了循環(huán)冗余校驗(yàn)算法，為進(jìn)一步深入學(xué)習(xí)計(jì)算機(jī)相關(guān)專業(yè)奠定基礎(chǔ)。

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

1.1 CRC算法介紹

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

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

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

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

1.2 CRC算法步驟

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

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

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

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

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

2 循環(huán)冗余校驗(yàn)算法設(shè)計(jì)

2.1 校驗(yàn)算法設(shè)計(jì)背景

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

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

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

2.2 基于CRC-8的算法設(shè)計(jì)

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

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

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

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

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

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

3 結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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

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