計(jì)算機(jī)通信中的crc

計(jì)算機(jī)通信中的crc

1不同通信線路傳輸質(zhì)量計(jì)算機(jī)網(wǎng)絡(luò)具有分布在不同地理位置的自治實(shí)體（用戶應(yīng)用程序、文件傳輸包、數(shù)據(jù)庫(kù)管理系統(tǒng)、電子郵件設(shè)備、終端等），并通過(guò)連接到統(tǒng)計(jì)數(shù)據(jù)網(wǎng)絡(luò)進(jìn)行通信，并通過(guò)通信協(xié)議進(jìn)行通信，以實(shí)現(xiàn)整個(gè)系統(tǒng)的資源共享。在網(wǎng)絡(luò)中交換信息,實(shí)體間必須建立數(shù)據(jù)通信線路,以便高效率而又準(zhǔn)確地傳輸信息。在實(shí)際應(yīng)用中,無(wú)論是遠(yuǎn)程數(shù)據(jù)通信線路還是局部數(shù)據(jù)通信線路,都不可避免地要受到各種干擾的影響,使接收端收到的信息與發(fā)送端發(fā)出的信息不一致,即接收端收到的信息產(chǎn)生了誤碼。用誤碼率(Pc)來(lái)度量數(shù)據(jù)通信線路傳輸信息的準(zhǔn)確度,則為了降低數(shù)據(jù)通信線路傳輸?shù)恼`碼率,通常有改善數(shù)據(jù)通信線路傳輸質(zhì)量和進(jìn)行差錯(cuò)檢測(cè)控制兩種方法。改善數(shù)據(jù)通信線路傳輸質(zhì)量就是引入新的交換設(shè)備、新的數(shù)據(jù)通信線路、新的技術(shù)等。但是,這種方法由于受到經(jīng)濟(jì)上和技術(shù)上的限制,要想做到很低的誤碼率,花費(fèi)代價(jià)大而收效甚微。實(shí)際上所有的計(jì)算機(jī)網(wǎng)絡(luò)通信系統(tǒng)都采用差錯(cuò)檢測(cè)控制,即承認(rèn)數(shù)據(jù)通信線路傳輸信息的出錯(cuò)情況,有效地檢測(cè)出錯(cuò)情況,并進(jìn)行糾正,以此提高數(shù)據(jù)通信線路傳輸?shù)馁|(zhì)量。差錯(cuò)檢測(cè)控制的方法很多,本文只介紹循環(huán)冗余碼校驗(yàn)CRC(CyclicRedundancyCheck)算法,它能在數(shù)據(jù)通信線路中很好地校驗(yàn)所傳輸?shù)男畔ⅰ?數(shù)據(jù)傳輸crc算法在計(jì)算機(jī)網(wǎng)絡(luò)的實(shí)體間進(jìn)行信息交換時(shí),先要將發(fā)送的較長(zhǎng)報(bào)文劃分成一個(gè)個(gè)更小的、等長(zhǎng)的數(shù)據(jù)段,在每個(gè)數(shù)據(jù)段的前面加上首部(Head),末尾加上校驗(yàn)碼,就構(gòu)成一個(gè)數(shù)據(jù)包(DataPacket)。在數(shù)據(jù)通信線路上傳輸?shù)氖菙?shù)據(jù)包,接收端計(jì)算機(jī)能從數(shù)據(jù)包中得到所需要的各種控制信息和傳輸?shù)挠杏眯畔?從而使傳輸中的差錯(cuò)檢測(cè)控制成為一項(xiàng)可管理的工作。數(shù)據(jù)包的格式如圖1所示。其中,SOH是包頭,通常包含有同步信息、源站地址和目的站地址等重要的控制信息;序號(hào)是報(bào)文分成數(shù)據(jù)包的組數(shù),即第幾組數(shù)據(jù)包;長(zhǎng)度是本數(shù)據(jù)包中數(shù)據(jù)的字節(jié)數(shù);數(shù)據(jù)是傳輸?shù)挠杏眯畔?校驗(yàn)碼是通過(guò)CRC算法計(jì)算出來(lái)的本數(shù)據(jù)包中數(shù)據(jù)的CRC碼。在報(bào)文的數(shù)據(jù)包傳輸協(xié)議中,發(fā)送端計(jì)算機(jī)運(yùn)用CRC算法從要發(fā)送的數(shù)據(jù)中計(jì)算出CRC碼(兩個(gè)字節(jié)),并把CRC碼作為校驗(yàn)碼加在數(shù)據(jù)包的末尾。接收端計(jì)算機(jī)接收到數(shù)據(jù)包后,也用CRC算法進(jìn)行相同的計(jì)算,并將計(jì)算得到的CRC碼與接收到的CRC碼進(jìn)行比較。若兩組CRC碼的值相等,則接著進(jìn)行下一個(gè)數(shù)據(jù)包的傳輸;若不相等,說(shuō)明傳輸中有誤碼,則通過(guò)ARQ(AutomaticRepeatreQuest)方式要求發(fā)送端計(jì)算機(jī)重發(fā)這個(gè)數(shù)據(jù)包。經(jīng)過(guò)CRC校驗(yàn)傳輸?shù)臄?shù)據(jù)包很可靠,且被大多數(shù)異步通信軟件采納。CRC校驗(yàn)技術(shù)把一個(gè)數(shù)據(jù)包中的數(shù)據(jù)作為位串來(lái)處理,它的校驗(yàn)范圍從數(shù)據(jù)包中數(shù)據(jù)的第一個(gè)字節(jié)的第一位開(kāi)始到最后一個(gè)字節(jié)的最后一位結(jié)束。CRC算法是計(jì)算機(jī)網(wǎng)絡(luò)通信中常用的差錯(cuò)檢測(cè)控制方法,其主要目的是減少數(shù)據(jù)通信線路的傳輸錯(cuò)誤。CRC算法的主要思想是:在發(fā)送端發(fā)送數(shù)據(jù)的同時(shí)增加CRC碼,在數(shù)據(jù)與CRC碼之間建立一定的數(shù)學(xué)關(guān)系(即編碼過(guò)程);當(dāng)這些數(shù)據(jù)和CRC碼一起被傳送到接收端時(shí),由接收端檢測(cè)數(shù)據(jù)和CRC碼之間的數(shù)學(xué)關(guān)系(譯碼過(guò)程)是否正確,若不正確,就說(shuō)明傳輸過(guò)程中有誤碼,通常通過(guò)發(fā)送端的重傳來(lái)校正錯(cuò)誤,直至傳送正確為止?？梢?jiàn),如何有效地檢測(cè)出錯(cuò)是這種方法的關(guān)鍵。3按位加/減的計(jì)算CRC算法的校驗(yàn)規(guī)則是讓被校驗(yàn)數(shù)據(jù)能為某一生成多項(xiàng)式所除,如果除得盡,表明代碼正確;如果除不盡,余數(shù)將指明出錯(cuò)位所在位置。任意一組被校驗(yàn)數(shù)據(jù),很可能除不盡,將產(chǎn)生一個(gè)余數(shù),如果讓被校驗(yàn)數(shù)據(jù)減去余數(shù),勢(shì)必能為生成多項(xiàng)式所除盡,但進(jìn)行減法操作時(shí),可能需要借位運(yùn)算,難以用簡(jiǎn)單的拼裝方法實(shí)現(xiàn)編碼。因此采用一種標(biāo)準(zhǔn)的模2運(yùn)算,即通過(guò)模2減法實(shí)現(xiàn)模2除法,以模2加法將所得余數(shù)拼接在被校驗(yàn)數(shù)據(jù)后面,形成一個(gè)能除盡的被校驗(yàn)數(shù)據(jù)。當(dāng)然,采用模2除法后,對(duì)生成多項(xiàng)式的選擇是有條件的。CRC算法所進(jìn)行的模2運(yùn)算是一種以按位加/減為基礎(chǔ)的四則運(yùn)算,不考慮進(jìn)位和借位,它和以2為模的定點(diǎn)小數(shù)四則運(yùn)算是兩個(gè)不同的概念。因此,模2加/減即按位加/減,也就是異或運(yùn)算,可用異或門(mén)實(shí)現(xiàn)。被校驗(yàn)數(shù)據(jù)是一組信息代碼,可能是表示數(shù)值大小的數(shù)字,也可能是字符編碼或其它性質(zhì)的代碼,但它在傳輸中是以二進(jìn)制(0、1代碼)形式表示。在模2除中,暫將被校驗(yàn)數(shù)據(jù)視為數(shù)字,可用多項(xiàng)式來(lái)進(jìn)行描述。定義被校驗(yàn)數(shù)據(jù)(被除數(shù))為M(x);約定的生成多項(xiàng)式(除數(shù))為G(x),是用來(lái)產(chǎn)生余數(shù)的;所產(chǎn)生的余數(shù)為R(x),它相當(dāng)于所配的冗余校驗(yàn)位。CRC算法可以檢測(cè)被校驗(yàn)數(shù)據(jù)所有的一位或兩位錯(cuò)誤;所有具有奇數(shù)位錯(cuò)誤;所有低于16位的突發(fā)性錯(cuò)誤;且對(duì)大于16位的突發(fā)性錯(cuò)誤檢測(cè)出的概率為99.9%。這種級(jí)別的錯(cuò)誤檢測(cè)正是計(jì)算機(jī)網(wǎng)絡(luò)通信信息傳輸所需要的。編碼方法(1)將被校驗(yàn)數(shù)據(jù)的k位有效信息M(x)左移r位,得M(x)·xr。這樣做的目的是空出r位,以便拼裝將來(lái)求得的r位余數(shù)。(2)選取一個(gè)r+1位的生成多項(xiàng)式G(x)=(X16+X12+X5+1),對(duì)M(x)·xr作模2除法要產(chǎn)生r位余數(shù),所以生成多項(xiàng)式G(x)應(yīng)為r+1位。(3)將左移r位的待編有效信息與余數(shù)R(x)作模2加(減),即拼接為循環(huán)校驗(yàn)碼。在按位運(yùn)算中,模2加法與模2減法的結(jié)果是一致的,所以M(x)·xr-R(x)=M(x)·xr+R(x)。M(x)·xr的末尾r位是0,所以與余數(shù)R(x)的加/減實(shí)際上就是將M(x)與R(x)相拼接。拼接成的校驗(yàn)碼必定能為約定的G(x)所除盡。譯碼與糾錯(cuò)將收到的循環(huán)校驗(yàn)碼,用約定的生成多項(xiàng)式G(x)去除。如果碼字無(wú)誤,則余數(shù)為0;如果某一位出錯(cuò),則余數(shù)不為0,不同位出錯(cuò)則余數(shù)不同,余數(shù)代碼與出錯(cuò)位序號(hào)之間有唯一的對(duì)應(yīng)關(guān)系,可以通過(guò)查表來(lái)判斷。4計(jì)算crc碼生成學(xué)習(xí)數(shù)據(jù)CRC算法有一個(gè)512字節(jié)的參數(shù)表,可以從參數(shù)表中查到每個(gè)字節(jié)的參數(shù)值。在設(shè)計(jì)CRC算法時(shí),預(yù)先開(kāi)辟存放512字節(jié)的緩沖區(qū)存放參數(shù)表,令不同的變量存放CRC碼和中間結(jié)果。依次取數(shù)據(jù)包中數(shù)據(jù)的每一個(gè)字節(jié),從參數(shù)表中查到它的參數(shù)值1。本字節(jié)異或上一字節(jié)經(jīng)校驗(yàn)后的低8位,再異或本字節(jié)找出的高8位得到結(jié)果1,把結(jié)果1送高8位字節(jié)。本字節(jié)找出的低八位值異或上一字節(jié)經(jīng)校驗(yàn)后的高8位值得到結(jié)果2,把結(jié)果2送低8位字節(jié)。上一字節(jié)經(jīng)校驗(yàn)的低八位,再?gòu)膮?shù)表中找出其參數(shù)值2。把結(jié)果1、結(jié)果2和參數(shù)值2異或后,作為該字節(jié)的校驗(yàn)碼。直到此數(shù)據(jù)包數(shù)據(jù)被校驗(yàn)完,得到一個(gè)CRC碼。CRC算法采用for循環(huán)依次取數(shù)據(jù)包中數(shù)據(jù)的每一個(gè)字節(jié),然后對(duì)每個(gè)字節(jié)進(jìn)行計(jì)算,所以CRC算法的時(shí)間復(fù)雜度為O(n),大大地提高了校驗(yàn)的速度?？臻g復(fù)雜度為存放512字節(jié)參數(shù)表的緩沖區(qū)和存放中間結(jié)果的變量。相對(duì)于別的算法來(lái)說(shuō),CRC算法占用了更多的存儲(chǔ)空間,但隨著計(jì)算機(jī)性能的提高,內(nèi)存不斷增大,這種用空間換取時(shí)間的方法是值得提倡的。5crc算法的簡(jiǎn)介CRC算法的程序設(shè)計(jì)是根據(jù)CRC算法分析得到的,用戶可根據(jù)計(jì)算機(jī)網(wǎng)絡(luò)通信要求編寫(xiě)主程序,調(diào)用crc()子程序,計(jì)算一數(shù)據(jù)包的CRC碼,然后把CRC碼加在數(shù)據(jù)包后作為校驗(yàn)碼傳輸?shù)浇邮斩擞?jì)算機(jī)。接收端計(jì)算機(jī)接收到數(shù)據(jù)包后,也用CRC算法進(jìn)行相同的計(jì)算,并將計(jì)算得到的CRC碼與接收到的CRC碼進(jìn)行比較,由此判斷接收的數(shù)據(jù)包是否正確。CRC算法參數(shù)表(512字節(jié))省略表示如下:6crc算法控制擴(kuò)寬設(shè)備b用軟件實(shí)現(xiàn)的CRC算法,它的主要優(yōu)點(diǎn)是節(jié)省了硬件,不需要另外設(shè)計(jì)硬件電路,校驗(yàn)速度非常快。把參數(shù)表和應(yīng)用程序一起調(diào)入內(nèi)存中,當(dāng)需要進(jìn)行校驗(yàn)時(shí),對(duì)數(shù)據(jù)包用CRC算法進(jìn)行計(jì)算,就可以得到該數(shù)據(jù)包的校驗(yàn)碼。CRC算法提高了通信速度,較好地克服了異步傳輸中校驗(yàn)和發(fā)送時(shí)間很不匹配的矛盾,是計(jì)算機(jī)網(wǎng)絡(luò)通信中常用的差錯(cuò)檢測(cè)控制方法。CRC算法源程序如