計算機通信中的crc

計算機通信中的crc

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