計(jì)算機(jī)網(wǎng)絡(luò)通信中CRC算法的應(yīng)用研究

岳立文

（白銀礦冶職業(yè)技術(shù)學(xué)院，甘肅 白銀 730900）

計(jì)算機(jī)網(wǎng)絡(luò)通信是通過(guò)多種算法處理而實(shí)現(xiàn)的。用數(shù)據(jù)線路將不同位置的服務(wù)器終端進(jìn)行連接，實(shí)現(xiàn)數(shù)據(jù)資源共享，構(gòu)建信息資源豐富的網(wǎng)絡(luò)社會(huì)。但隨著計(jì)算機(jī)網(wǎng)絡(luò)通信頻率的加快，數(shù)據(jù)信息會(huì)受磁場(chǎng)等外在因素的干擾，從而影響信息傳輸質(zhì)量，并造成信息失真、誤碼率高等問(wèn)題［1］。采用CRC算法，其差錯(cuò)糾正控制可有效解決信息誤差，降低誤碼率，提升計(jì)算機(jī)網(wǎng)絡(luò)通信質(zhì)量和通信水平。

1 CRC算法概述

1.1 CRC算法涵義及算法原理

CRC即循環(huán)冗余校驗(yàn)碼（Cyclic Redundancy Check），是數(shù)通領(lǐng)域較為常用的具有糾錯(cuò)、檢錯(cuò)能力的一種差錯(cuò)檢驗(yàn)碼，其特征是信息字段和校驗(yàn)字段的長(zhǎng)度可以任意選定。循環(huán)冗余檢驗(yàn)是一種數(shù)據(jù)傳統(tǒng)檢錯(cuò)功能，對(duì)數(shù)據(jù)進(jìn)行多項(xiàng)式計(jì)算，并將得到的結(jié)果附在幀的后面，接收設(shè)備也運(yùn)行類似的算法，以保證數(shù)據(jù)傳輸?shù)恼_性和完整性。其在通信過(guò)程中，時(shí)長(zhǎng)會(huì)產(chǎn)生變化，可以由0變?yōu)?，也可以由1變?yōu)?，將待發(fā)送的位串看成系數(shù)為0或1的多項(xiàng)式。收發(fā)雙方約定一個(gè)生成多項(xiàng)式G（x）（其最高階和最低階系數(shù)必須為1），發(fā)送方用位串及G（x）進(jìn)行某種運(yùn)算得到校驗(yàn)和，并在幀的末尾加上校驗(yàn)和，使帶校驗(yàn)和的幀的多項(xiàng)式能被G（x）整除。接收方收到后，用 G（x）除多項(xiàng)式，如果有余數(shù)，則傳輸有錯(cuò)［2］。

1.2 CRC 算法分析

CRC循環(huán)冗余校驗(yàn)碼的編碼方式是用生成多項(xiàng)式G（x）去除待發(fā)送的數(shù)據(jù)串，最終得到的余數(shù)就是CRC校驗(yàn)碼，其實(shí)現(xiàn)過(guò)程如下：

（1）首先給定一個(gè)生成多項(xiàng)式G（x），它的階數(shù)是r階，再給定數(shù)據(jù)串幀數(shù)是k位的多項(xiàng)式，設(shè)為M（x），那么就需要將原幀 M（x）左移 r位，也就是在M（x）的后面加上r個(gè)0，生成的新數(shù)據(jù)串變成了 k＋r位，多項(xiàng)式也變成了 XM（x）。

（2）用新數(shù)據(jù)串XrM（x）去除以生成多項(xiàng)式G（x）對(duì)應(yīng)的數(shù)據(jù)串，運(yùn)用模二運(yùn)算，得到余數(shù)為 R（x）。

（3）將得到的余數(shù) R（x）加到數(shù)據(jù)串 M（x）的后面，生成新的數(shù)據(jù)串 T（x），新數(shù)據(jù)串 T（x）就是待發(fā)送的帶有校驗(yàn)和的幀多項(xiàng)式，即：

CRC的本質(zhì)就是將待發(fā)送的k位多項(xiàng)式轉(zhuǎn)換成了可以被生成多項(xiàng)式G（x）除盡的k＋r位多項(xiàng)式，解碼時(shí)可以用接收到的數(shù)據(jù)去除以生成多項(xiàng)式G（x），如果得到的余數(shù)為0，那么則表示傳輸過(guò)程正確，如果得到的余數(shù)不為0，那么表示傳輸1過(guò)程出現(xiàn)錯(cuò)誤。

1.3 CRC 算法的實(shí)現(xiàn)

在計(jì)算機(jī)網(wǎng)絡(luò)通信中算法中，主要包括硬件和軟件兩種實(shí)現(xiàn)形式，都是通過(guò)發(fā)送數(shù)據(jù)包的方式實(shí)現(xiàn)數(shù)據(jù)共享和數(shù)據(jù)傳輸，通過(guò)兩者比較，軟件實(shí)現(xiàn)形式更具優(yōu)勢(shì)，信息傳播速度更快、誤碼率較低，因此，目前在計(jì)算機(jī)網(wǎng)絡(luò)通信過(guò)程中，多以軟件形式呈現(xiàn)，其中，以太網(wǎng)是軟件形式的代表。在計(jì)算機(jī)網(wǎng)絡(luò)實(shí)體之間實(shí)現(xiàn)數(shù)據(jù)傳輸和數(shù)據(jù)共享時(shí)，為保證通信功能的有效實(shí)現(xiàn)，需通過(guò)發(fā)送數(shù)據(jù)包的方式進(jìn)行數(shù)據(jù)傳輸控制，保證數(shù)據(jù)信息的功能價(jià)值。數(shù)據(jù)包由段開(kāi)銷、數(shù)據(jù)序號(hào)、序列的校驗(yàn)碼等組成，其中，段開(kāi)銷作為數(shù)據(jù)傳輸?shù)某跏紨?shù)據(jù)，承載著數(shù)據(jù)開(kāi)始出傳輸?shù)絺鬏斀Y(jié)束的全過(guò)程，這一過(guò)程的數(shù)據(jù)安全是整個(gè)算法的保護(hù)重點(diǎn)，段開(kāi)銷安全性保護(hù)到位就不容易初夏誤碼問(wèn)題，若保護(hù)不到位，極易導(dǎo)致誤碼產(chǎn)生。數(shù)據(jù)序號(hào)作為數(shù)據(jù)的“名字”，主要承擔(dān)編組數(shù)據(jù)任務(wù)，如將5個(gè)數(shù)據(jù)編到1組，那么25個(gè)數(shù)據(jù)應(yīng)該編為5組，序號(hào)應(yīng)編至25。在計(jì)算機(jī)網(wǎng)絡(luò)通信數(shù)據(jù)共享與傳輸過(guò)程中，不同數(shù)據(jù)包都有不同的編碼，也有不同的字節(jié)長(zhǎng)度，數(shù)據(jù)編碼位于整個(gè)數(shù)據(jù)包的尾部，承擔(dān)數(shù)據(jù)糾錯(cuò)功能，通過(guò)對(duì)字節(jié)長(zhǎng)度的測(cè)算，檢驗(yàn)計(jì)算機(jī)網(wǎng)絡(luò)通信數(shù)據(jù)的安全性和準(zhǔn)確性。但在實(shí)際的數(shù)據(jù)傳輸過(guò)程中，數(shù)據(jù)錯(cuò)誤在所難免，如何將錯(cuò)誤率講到最低是當(dāng)前相關(guān)研究人員重點(diǎn)研究的關(guān)鍵。隨著科學(xué)技術(shù)水平的提高，我國(guó)計(jì)算機(jī)網(wǎng)絡(luò)通信誤碼率已經(jīng)達(dá)到了較高水平，已經(jīng)最大限度的控制了誤碼率的發(fā)生，PC表示誤碼率，計(jì)算公式為：PC＝所接收的錯(cuò)誤碼／所接收的總碼數(shù)［3］，技術(shù)人員可以通過(guò)上述公式計(jì)算誤碼率，并結(jié)合實(shí)際情況不斷完善計(jì)算機(jī)網(wǎng)絡(luò)通信傳輸技術(shù)，全面降低網(wǎng)絡(luò)通信過(guò)程中出現(xiàn)差錯(cuò)的幾率。

2 CRC算法的校驗(yàn)規(guī)則

能否除盡作為CRC算法中數(shù)據(jù)信息的校驗(yàn)規(guī)則，對(duì)于可以被多項(xiàng)式除盡的數(shù)據(jù)，說(shuō)明出錯(cuò)錯(cuò)誤的概率就較低，對(duì)于無(wú)法被多項(xiàng)式除盡的數(shù)據(jù)，則應(yīng)返回?cái)?shù)據(jù)校驗(yàn)中，檢查數(shù)據(jù)的的出錯(cuò)點(diǎn)，將多余的余數(shù)減去，再運(yùn)用多項(xiàng)式進(jìn)行除法運(yùn)算，若可以被除盡說(shuō)明誤碼問(wèn)題已解決。但在減去余數(shù)的這一過(guò)程涉及新的算法，涵蓋更為復(fù)雜的數(shù)學(xué)運(yùn)算，無(wú)法采用拼接的方式將數(shù)據(jù)進(jìn)行編碼。因此，對(duì)于這一現(xiàn)象，可采用前文CRC算法分析中提及的模2運(yùn)算方式，通過(guò)模2加、模2減、模2乘、模2除四種方式，計(jì)算最終結(jié)果。

在CRC算法錯(cuò)誤檢測(cè)機(jī)制中，采用奇偶校驗(yàn)法，通過(guò)奇數(shù)與偶數(shù)的不同，分別檢測(cè)奇數(shù)和偶數(shù)中的錯(cuò)誤數(shù)據(jù)。隨著技術(shù)進(jìn)步，當(dāng)前所能檢測(cè)的校驗(yàn)錯(cuò)誤最大數(shù)值可達(dá)到16位，且檢測(cè)效果較強(qiáng)。信息通訊過(guò)程中，信息接收部分接收到相關(guān)信息時(shí)，收到循環(huán)校驗(yàn)碼指令后，用多項(xiàng)式數(shù)字代碼做除法運(yùn)算，如果可以除盡，說(shuō)明數(shù)據(jù)傳輸中無(wú)誤碼現(xiàn)象，但如果有余數(shù)，說(shuō)明存在誤碼現(xiàn)象，可啟動(dòng)模2運(yùn)算程序，減去多余的余數(shù)，使得出的結(jié)果為整數(shù)，且余數(shù)為0。

3 計(jì)算機(jī)網(wǎng)絡(luò)通信中CRC算法的應(yīng)用

因CRC算法的檢測(cè)成本低、檢錯(cuò)能力強(qiáng)等優(yōu)勢(shì)，使之廣泛應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)通信過(guò)程，下面將從CRC算法的應(yīng)用過(guò)程、校驗(yàn)碼生成、優(yōu)劣勢(shì)等角度，重點(diǎn)闡述計(jì)算機(jī)網(wǎng)絡(luò)通信中CRC算法的應(yīng)用。

3.1 CRC算法的應(yīng)用過(guò)程

為實(shí)現(xiàn)計(jì)算機(jī)網(wǎng)絡(luò)通信，CRC算法通過(guò)在計(jì)算機(jī)網(wǎng)絡(luò)各數(shù)據(jù)間建立編碼關(guān)系，設(shè)置編碼數(shù)據(jù)庫(kù)（如圖1所示），并將校驗(yàn)碼加入數(shù)據(jù)包的末端部分，以此實(shí)現(xiàn)計(jì)算機(jī)網(wǎng)絡(luò)信息的傳輸與共享。當(dāng)校驗(yàn)碼與計(jì)算機(jī)數(shù)據(jù)產(chǎn)生聯(lián)系后，可以實(shí)現(xiàn)數(shù)據(jù)的流通與傳輸，數(shù)據(jù)可以從起始位置傳輸?shù)綌?shù)據(jù)終端接收部位，終端接收數(shù)據(jù)后通過(guò)一系列“譯碼”判斷是否能夠?qū)⑹斋@的數(shù)據(jù)對(duì)外共享。如果在“譯碼”過(guò)程中，發(fā)現(xiàn)數(shù)據(jù)運(yùn)算結(jié)果不正確，說(shuō)明數(shù)據(jù)存在傳輸過(guò)程中出現(xiàn)誤碼問(wèn)題，仍需進(jìn)一步“譯碼”循環(huán)往復(fù)，直至最終的計(jì)算結(jié)果與源地址的結(jié)果相符，才能夠說(shuō)明數(shù)據(jù)在傳輸過(guò)程中未出現(xiàn)錯(cuò)誤，終端接收的數(shù)據(jù)才能進(jìn)入下一環(huán)節(jié)，實(shí)現(xiàn)數(shù)據(jù)共享［4］。

圖1 編碼數(shù)據(jù)庫(kù)示意圖

如前文所述，CRC算法是通過(guò)發(fā)送數(shù)據(jù)包形式實(shí)現(xiàn)數(shù)據(jù)傳輸和數(shù)據(jù)共享的，數(shù)據(jù)包中的段開(kāi)銷及數(shù)據(jù)均已代碼組的形式呈現(xiàn)，通過(guò)二進(jìn)制運(yùn)算，完成數(shù)據(jù)傳輸目的。二進(jìn)制計(jì)算過(guò)程中，通過(guò)多項(xiàng)式除法運(yùn)算，依據(jù)計(jì)算結(jié)果判斷數(shù)據(jù)傳輸過(guò)程中有無(wú)誤碼問(wèn)題，如果不能被多項(xiàng)式除盡，有余數(shù)出現(xiàn)，說(shuō)明數(shù)據(jù)傳輸過(guò)程中存在誤碼問(wèn)題，影響計(jì)算機(jī)網(wǎng)絡(luò)信息傳輸準(zhǔn)確性和傳輸質(zhì)量，需要再通過(guò)減法運(yùn)算，再進(jìn)行除法運(yùn)算，直至算出的結(jié)果為整數(shù)時(shí)才能終止校驗(yàn)。如果可以被多項(xiàng)式除盡，說(shuō)明數(shù)據(jù)傳輸過(guò)程較順利，沒(méi)有出現(xiàn)誤碼問(wèn)題。上述計(jì)算中，模2是常用的運(yùn)算方法，便于操作、計(jì)算準(zhǔn)確，能夠真實(shí)反映計(jì)算機(jī)網(wǎng)絡(luò)通信情況。

3.2 校驗(yàn)碼生成

計(jì)算機(jī)網(wǎng)絡(luò)通信中CRC算法的應(yīng)用以校驗(yàn)碼的生成為主，其原理大體可以概括為：可以將被校驗(yàn)的n位數(shù)據(jù)塊看做n階二進(jìn)制的多項(xiàng)式：

發(fā)送方和接收方約定以r階生成多項(xiàng)式G（x），將G（x）作為除數(shù)，帶入除法運(yùn)算中，無(wú)法除盡生成余數(shù)多項(xiàng)式 y（x），y（x）即 m（x）的校驗(yàn)碼，再將 m（x）附在n位數(shù)據(jù)塊之后一并發(fā)送至接收方，以接收方最終收到的多項(xiàng)式為準(zhǔn)，作為被除數(shù)，除以除數(shù)G（x），可以被整除即可說(shuō)明校驗(yàn)成功。表1為16位CRC校驗(yàn)原理及算法，將相關(guān)數(shù)字帶入式（2）即可得到如表1所示的相關(guān)數(shù)據(jù)。

表1 16位CRC校驗(yàn)原理及算法

CRC校驗(yàn)流程如下：

（1）將所有編碼數(shù)據(jù)做初始化處理，使之回歸初始階段，并設(shè)置循環(huán)變量的初始值。

（2）實(shí)現(xiàn)數(shù)據(jù)信息傳輸，將數(shù)據(jù)信息按照設(shè)置的傳輸路徑，將其輸送至余數(shù)數(shù)據(jù)空間，原有的余數(shù)數(shù)據(jù)產(chǎn)生相應(yīng)位移，向左移動(dòng)8位或1位。

（3）將余數(shù)數(shù)據(jù)的最高位與“1”對(duì)比，判斷余數(shù)數(shù)據(jù)的為高危是否為1，如果等于1，可以將其代入多項(xiàng)式進(jìn)行除法計(jì)算，判斷是否能夠整除。

（4）這一階段還需判斷循環(huán)冗余算法是否經(jīng)過(guò)8次循環(huán)，256次反復(fù)校驗(yàn)編碼，最后將已經(jīng)完成8次循環(huán)的余數(shù)數(shù)據(jù)進(jìn)行存儲(chǔ)。

（5）余數(shù)數(shù)據(jù)最高位經(jīng)與“1”對(duì)比后，發(fā)現(xiàn)不等于1，且未經(jīng)過(guò)8次循環(huán)，針對(duì)這種情況，需要重新啟動(dòng)CRC算法，重新整理并收集數(shù)據(jù)，傳輸至余數(shù)單元，重復(fù)計(jì)算［5］。

通過(guò)以上校驗(yàn)碼的生成方法能夠有效判斷出數(shù)據(jù)傳輸中的錯(cuò)誤，進(jìn)而及時(shí)更正數(shù)據(jù)信息，在實(shí)際應(yīng)用中，可有效提升計(jì)算機(jī)網(wǎng)絡(luò)信息傳輸效率，保證數(shù)據(jù)信息傳輸質(zhì)量。

3.3 CRC算法的優(yōu)缺點(diǎn)

在計(jì)算機(jī)網(wǎng)絡(luò)通信過(guò)程中，CRC算法具有明顯優(yōu)勢(shì)，但從糾錯(cuò)差錯(cuò)這一項(xiàng)功能來(lái)看，就是其他算法無(wú)法比擬的。CRC算法可以在短時(shí)間，通過(guò)調(diào)動(dòng)軟件系統(tǒng)的各種程序，經(jīng)過(guò)一系列運(yùn)算，判斷整個(gè)數(shù)據(jù)傳輸過(guò)程中有無(wú)出現(xiàn)誤碼，提高了網(wǎng)絡(luò)信息傳輸?shù)募m錯(cuò)率，保證了通信效率，與傳統(tǒng)的糾錯(cuò)算法相比，具有成本低、糾錯(cuò)質(zhì)量高等優(yōu)勢(shì)，具有較強(qiáng)的應(yīng)用價(jià)值。

CRC算法在具有較強(qiáng)優(yōu)勢(shì)的同時(shí)，也存在一定缺陷，如數(shù)據(jù)存儲(chǔ)量大，存儲(chǔ)空間不足，一定程度影響算法的糾錯(cuò)效率，因此，在未來(lái)的發(fā)展中，研究人員還應(yīng)在擴(kuò)大數(shù)據(jù)存儲(chǔ)空間上狠下功夫。

4 CRC算法糾錯(cuò)條件與注意事項(xiàng)

4.1 糾錯(cuò)條件

CRC算法需要滿足的糾錯(cuò)條件主要包含以下三個(gè)方面：一是針對(duì)數(shù)據(jù)傳輸過(guò)程中存在的奇數(shù)個(gè)錯(cuò)誤做糾錯(cuò)處理；二是對(duì)于單個(gè)突發(fā)性的錯(cuò)誤做到有效糾正；三是對(duì)于兩個(gè)或兩個(gè)以上的偶數(shù)個(gè)錯(cuò)誤進(jìn)行有效的糾錯(cuò)處理。

對(duì)于滿足以上三個(gè)條件的通信過(guò)程進(jìn)行CRC算法校驗(yàn)，檢測(cè)計(jì)算機(jī)網(wǎng)絡(luò)通信過(guò)程中存在的無(wú)差問(wèn)題，以充分滿足計(jì)算機(jī)網(wǎng)絡(luò)通信對(duì)數(shù)據(jù)準(zhǔn)確性的要求，推動(dòng)計(jì)算機(jī)網(wǎng)絡(luò)整體通信水平的提升。

4.2 注意事項(xiàng)

4.2.1 多項(xiàng)式選擇

在CRC算法的實(shí)際應(yīng)用中，為有效判斷計(jì)算機(jī)網(wǎng)絡(luò)通信傳輸過(guò)程中存在的問(wèn)題，需進(jìn)行糾錯(cuò)校驗(yàn)，通過(guò)以二進(jìn)制位代表的數(shù)據(jù)包與多項(xiàng)式相除形式，計(jì)算是否得到整數(shù)，通過(guò)對(duì)能都整除的判斷，正確了解計(jì)算機(jī)網(wǎng)絡(luò)通信過(guò)程中存在的問(wèn)題。但這一過(guò)程對(duì)多項(xiàng)式的選取要求較高，多項(xiàng)式條件的優(yōu)劣關(guān)系著最終計(jì)算結(jié)果正確與否，因此，在CRC算法應(yīng)用過(guò)程中，更應(yīng)重視多項(xiàng)式的選擇。

一般情況，多項(xiàng)式大都由系統(tǒng)設(shè)定的程序自動(dòng)生成，在整個(gè)CRC算法應(yīng)用過(guò)程中，按照數(shù)據(jù)傳輸規(guī)律設(shè)計(jì)多項(xiàng)式生成公式，其中，差錯(cuò)及誤碼檢測(cè)特點(diǎn)是影響多項(xiàng)式生成的主要原因，所以為充分保證多項(xiàng)式的準(zhǔn)確可靠性，必須保證數(shù)據(jù)包能被整除，也就是沒(méi)有余數(shù)，只有滿足這些條件，才能確保多項(xiàng)式的生成效果。

4.2.2 算法編碼方式

通過(guò)對(duì)CRC算法的分析，了解到該算法在應(yīng)用過(guò)程中需要將數(shù)據(jù)包編碼處理，用生成多項(xiàng)式G（x）去除待發(fā)送的數(shù)據(jù)串，最終得到的余數(shù)就是CRC校驗(yàn)碼。算法編碼的主要目的在于將第k位的有效信息實(shí)現(xiàn)移位，如向做移位r個(gè)單位，從而得到余數(shù)的過(guò)程［6］。采用模2的計(jì)算公式，對(duì)于所得余數(shù)代入多項(xiàng)式進(jìn)行云端，最終得到準(zhǔn)確的校驗(yàn)碼的過(guò)程。

5 結(jié)論

綜上所述，在計(jì)算機(jī)網(wǎng)絡(luò)通信過(guò)程中，與傳統(tǒng)算法相比，CRC算法有較大的應(yīng)用價(jià)值，具有糾錯(cuò)率高、成本低、行速度快等特點(diǎn)，能夠通過(guò)發(fā)送數(shù)據(jù)包的形式，將數(shù)據(jù)包與多項(xiàng)式進(jìn)行除法運(yùn)算，從而有效檢測(cè)數(shù)據(jù)傳輸過(guò)程中的錯(cuò)誤，并能及時(shí)糾正，提高網(wǎng)絡(luò)通信質(zhì)量和通信效率，對(duì)今后計(jì)算機(jī)網(wǎng)絡(luò)通信整體效率的提高具有明顯的推動(dòng)作用。需要注意的是，在該算法的具體應(yīng)用過(guò)程中，應(yīng)注意多項(xiàng)式的選擇和算法編碼方式問(wèn)題，以更好地提升該算法的應(yīng)用效率。