循環(huán)冗余校驗(yàn)(CRC)算法的實(shí)現(xiàn)

1、武漢理工大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)課程論文武漢理工大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)課程論文題目循環(huán)冗余校驗(yàn)（CRC算法的實(shí)現(xiàn)作 者 學(xué)院信息工程學(xué)院專業(yè)電子信息工程學(xué)號指導(dǎo)教師二一六年四月十四日武漢理工大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)課程論文武漢理工大學(xué)信息工程學(xué)院課程論文誠信聲明本人聲明：所呈交的課程論文，是本人在指導(dǎo)老師的指導(dǎo)下, 獨(dú)立開展工作所取得的成果，成果不存在知識產(chǎn)權(quán)爭議，除文中 已經(jīng)注明引用的內(nèi)容外，本課程論文不含任何其他個(gè)人或集體已 經(jīng)發(fā)表或創(chuàng)作過的作品成果。對本文工作做出重要貢獻(xiàn)的個(gè)人和 集體均已在文中以明確方式標(biāo)明。本人完全意識到本聲明的法律 結(jié)果由本人承擔(dān)。本科課程論文作者簽名：二C一六年四月十四日課程論文成績評定表質(zhì)

2、量評價(jià)指標(biāo)（在相應(yīng)欄目打"）評價(jià)項(xiàng)目論文與設(shè)計(jì)評價(jià)質(zhì)量按對應(yīng)項(xiàng)目打分工作量和態(tài)度（10分）分析問題能力（10分）解決問題能力（10分）內(nèi)容完整層次分明（10分）設(shè)計(jì)、實(shí)驗(yàn)正確性（10分）書寫規(guī)范（10分）流程圖或拓?fù)鋱D（10分）論證充分（10分）測試結(jié)果情況（10分）總體評價(jià)（10分）評定成績（100分制）指導(dǎo)教師簽名年 月日II武漢理工大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)課程論文目錄、選題背景 1. 設(shè)計(jì)要求 12. 循環(huán)冗余CRC簡介 13. 應(yīng)解決的主要問題 2、方案論證1. 循環(huán)冗余檢驗(yàn)的原理 22. 方案的選擇及特點(diǎn) 4三、過程論述 81. 第一部分 82. 第二部分 93. 第三部分 114.

3、 第四部分 11四、結(jié)果分析 121. CRC算法的實(shí)現(xiàn) 122. 突變的產(chǎn)生和校驗(yàn)結(jié)果 133. 無法檢錯(cuò)的實(shí)例 14五、總結(jié) 15心得體會 17參考文獻(xiàn) 17附件一：程序源代碼 18iii武漢理工大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)課程論文一、選題背景題目17循環(huán)冗余校驗(yàn)（CRC算法的實(shí)現(xiàn)1、設(shè)計(jì)要求（1）利用結(jié)構(gòu)體或數(shù)組模擬網(wǎng)絡(luò)數(shù)據(jù)包結(jié)構(gòu)。（2）編碼實(shí)現(xiàn)CRC算法，并將得到的校驗(yàn)位附加到網(wǎng)絡(luò)數(shù)據(jù)包相應(yīng)的位置（3）根據(jù)數(shù)據(jù)包的長度，隨機(jī)生成一個(gè)數(shù)據(jù)包產(chǎn)生突變的位置，并對該位 置的bit位模擬突變的產(chǎn)生。（4）重新利用CRC算法校驗(yàn)該數(shù)據(jù)包，并指出產(chǎn)生的結(jié)果。（5）CRC能夠檢出所有的錯(cuò)誤嗎？如果不能，你能構(gòu)造出

4、無法檢錯(cuò)的實(shí)例 嗎？2、循環(huán)冗余CRC簡介循環(huán)冗余校驗(yàn)碼（CRC碼，CRC=Cyclic Redundancy Check）:是數(shù)據(jù)通信領(lǐng)域中最常用的一種差錯(cuò)校驗(yàn)碼，其特征是信息字段和校驗(yàn)字段的長度可以任意 選定。CR（碼是由兩部分組成，前部分是信息碼，就是需要檢驗(yàn)的信息，后部分 是檢驗(yàn)碼，采用的是一種多項(xiàng)式的編碼方法。 循環(huán)碼和碼字多項(xiàng)式是 CRC中的兩 個(gè)基本概念。CRC校驗(yàn)的基本思想是利用線性編碼理論，在發(fā)送端根據(jù)要傳送的 k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個(gè)校驗(yàn)用的監(jiān)督碼（CRC碼）n位，并附在信息后邊，構(gòu)成一個(gè)新的二進(jìn)制碼序列數(shù)共 （k+n）位，最后發(fā)送出去。在 接收端，則根據(jù)信息

5、碼和 CRC碼之間所遵循的規(guī)則進(jìn)行檢驗(yàn)，以確定傳送中是 否出錯(cuò)。循環(huán)冗余校驗(yàn)碼CRC是一種高效率且可靠的方法,由線性分組碼分支而來 的，是一種通過多項(xiàng)式除法檢測錯(cuò)誤的很不尋常而又巧妙的方法，一方面它有很強(qiáng)的檢測能力，二是它的編碼器電路及錯(cuò)誤檢測器電路都很容易實(shí)現(xiàn) ，它的 優(yōu)點(diǎn)使它在通信系統(tǒng)中得到了廣泛的應(yīng)用?，F(xiàn)實(shí)的通信鏈路都不會是理想的。這 就是說，比特在傳輸過程中可能會產(chǎn)生差錯(cuò):1可能會變成0,而0也可能變成1。 這就叫做比特差錯(cuò)。比特差錯(cuò)是傳輸差錯(cuò)中的一種。 在一段時(shí)間內(nèi)，傳輸錯(cuò)誤的 比特占所傳輸比特總數(shù)的比率稱為誤碼率 BEG誤碼率與信噪比有很大的關(guān)系。 如果設(shè)法提高信噪比，就可以使誤碼

6、率減小。實(shí)際的通信鏈路并非是理想的，它 不可能使誤碼率下降到零。因此，為了保證數(shù)據(jù)傳輸?shù)目煽啃裕谟?jì)算機(jī)網(wǎng)絡(luò)傳 輸數(shù)據(jù)時(shí)，必須采用各種差錯(cuò)檢測措施。目前在數(shù)據(jù)鏈路層廣泛使用了循環(huán)冗余 檢驗(yàn)CRC勺檢錯(cuò)技術(shù)。3、應(yīng)解決的主要問題(1) 選用哪種軟件實(shí)現(xiàn)編程：MATLA具有程序結(jié)構(gòu)控制、函數(shù)調(diào)用、數(shù)據(jù)結(jié)構(gòu)、輸入輸出、面向?qū)ο蟮?程序語言特征，而且簡單易學(xué)、編程效率高。MATLA提供了一個(gè)人機(jī)交互的數(shù)學(xué)系統(tǒng)環(huán)境，該系統(tǒng)的基本數(shù)據(jù)結(jié)構(gòu)是矩陣，在生成矩陣對象時(shí)，不要求明確的 維數(shù)說明。與利用C語言作數(shù)值計(jì)算的程序設(shè)計(jì)相比，利用 MATLA可以節(jié)省大 量的編程時(shí)間。本次大作業(yè)采用數(shù)組模擬網(wǎng)絡(luò)數(shù)據(jù)包結(jié)構(gòu)，采

7、用MATLA操作簡單，結(jié)果明了，故用MATLA程序語言實(shí)現(xiàn)CRC校驗(yàn)的程序設(shè)計(jì)。(2) 理想的循環(huán)冗余校驗(yàn)算法應(yīng)具有以下特征：CRC!同的數(shù)據(jù)多次，每次得到的 CRCfi應(yīng)該相同。這也是通信過程中通過 CRC校驗(yàn)數(shù)據(jù)在收發(fā)過程中是否出錯(cuò)的基本依據(jù)。CRC不同的數(shù)據(jù)得到的CRCS應(yīng)該不等。(盡管通過估計(jì)偽造可能得到相同 的CRCfi，但要確保這種概率很小)對于32位的CRC來說，它能區(qū)分2A32的數(shù)據(jù)，即長度為2A32的兩個(gè)數(shù)據(jù)， 只要有任何兩位的值不同，它們分別經(jīng)過 CRC后得到的CRCfi就不同。(3) 如何實(shí)現(xiàn)CRC算法過程：本次設(shè)計(jì)采用模2除法運(yùn)算求余數(shù)，程序中可表示為將待傳送數(shù)據(jù)與生成

8、多 項(xiàng)式逐位異或。因?yàn)榇齻魉蛿?shù)據(jù)的位數(shù)不確定，一一編寫容易出錯(cuò)且麻煩，不易 于修改數(shù)據(jù)，因此在程序中采用for循環(huán)語句來逐位求解最終得到余數(shù)。二、方案論證1、循環(huán)冗余檢驗(yàn)的原理在發(fā)送端，先把數(shù)據(jù)劃分為組，假定每組 k個(gè)比特。現(xiàn)假定待傳送的數(shù)據(jù) M=101001(k=6)。CRC運(yùn)算就是在數(shù)據(jù)M的后面添加供差錯(cuò)檢測用的n位冗余 碼，然后構(gòu)成一個(gè)幀發(fā)送出去，一共發(fā)送（k+n）位。在所要發(fā)送的數(shù)據(jù)后面增 加n位的冗余碼，雖然增大了數(shù)據(jù)傳輸?shù)拈_銷，但卻可以進(jìn)行差錯(cuò)檢測。當(dāng)傳輸 可能出現(xiàn)差錯(cuò)時(shí)，付出這種代價(jià)往往是很值得的。這n位冗余碼可用以下方達(dá)得出。用二進(jìn)制的模2運(yùn)算進(jìn)行2An乘M的運(yùn)算， 這相當(dāng)于在

9、M后面添加n個(gè)0。得到的（k+n）位的數(shù)除以收發(fā)雙方事先商定的 長度為（n+1）位的除數(shù)P，得到商是Q而余數(shù)是R（n位，比P少一位）。關(guān)于除數(shù) P,在圖2-1所示的例子中，M=101001即k=6）。假定除數(shù)P=1101（即 n=3）。經(jīng) 模2除法運(yùn)算后的結(jié)果是：商Q=110101這個(gè)商并沒有什么用處），而余數(shù)R=001。 這個(gè)余數(shù)R就作為冗余碼拼接在數(shù)據(jù) M的后面發(fā)送出去。這種為了進(jìn)行檢錯(cuò)而添 加的冗余碼常稱為幀檢驗(yàn)序列 FCS因此加上FCS后發(fā)送的幀是101001001（即 2八門*M+FCS）共有（k+n）位。110101 Q （商）P（除數(shù)）1101V101001000 2An*M（

10、被除數(shù)）11011110110101110000 而011010110000011001101001 R （余數(shù)），作為FCS圖2-1說明循環(huán)冗余檢驗(yàn)原理的例子在接收端把接受到的數(shù)據(jù)以幀為單位進(jìn)行CRC檢驗(yàn)：把收到的每一個(gè)幀都除以同樣的除數(shù)P （模2運(yùn)算），然后檢查得到余數(shù)Ro如果在傳輸過程中無差錯(cuò)，那么經(jīng)過 CRC僉驗(yàn)后得到的余數(shù)R肯定是0。但 如果出現(xiàn)誤碼，那么余數(shù) R仍等于零的概率是非常非常小的?？傊诮邮斩藢κ盏降拿恳粠?jīng)過 CRC檢驗(yàn)后，有以下兩種情況：（1）若得到的余數(shù)R等于0，則判定這個(gè)幀沒有差錯(cuò)，就接受（accept ）。(2)若余數(shù)R不等于0,則判定這個(gè)幀有差錯(cuò)(但無法確定

11、究竟是哪一位 或哪幾位出現(xiàn)了差錯(cuò))，就丟棄。一種較方便的方法是用多項(xiàng)式來表示循環(huán)冗余檢驗(yàn)過程。在上面的例子中，用多項(xiàng)式P(X)=XA3+XA2+1表示上面的除數(shù)P=1101(最高位對應(yīng)于XA3,最低位對 應(yīng)于XA0)。多項(xiàng)式P(X)稱為生成多項(xiàng)式?，F(xiàn)在廣泛使用的生成多項(xiàng)式 P(X)有 以下幾種：CRC-16=XA16+XA15+XA2+1CRC-CCITT=XA16+XA12+XA5+1CRC-32=XA32+XA26+XA23+XA22+XA16+XA12+XA11+XA10+XA8+XA7+XA5+XA4+XA 2+X+1在數(shù)據(jù)鏈路層，發(fā)送端幀檢驗(yàn)序列FCS的生成和接收端的CRC檢驗(yàn)都是用

12、硬 件完成的，處理很迅速，因此并不會延誤數(shù)據(jù)的傳輸。如果在傳送數(shù)據(jù)時(shí)不以幀為單位來傳送，那么就無法加入冗余碼以進(jìn)行差錯(cuò) 檢驗(yàn)。因此，如果要在數(shù)據(jù)鏈路層進(jìn)行差錯(cuò)檢驗(yàn)，就必須把數(shù)據(jù)劃分為幀，每一 幀都加上冗余碼，一幀接一幀地傳送，然后在接收方逐幀進(jìn)行差錯(cuò)檢驗(yàn)。2、方案的選擇及特點(diǎn)由于本次編程需要達(dá)到五點(diǎn)要求，因此進(jìn)行逐一分析。在MATLAB，數(shù)組的表現(xiàn)方式很簡單，故采用數(shù)組模擬網(wǎng)絡(luò)數(shù)據(jù)包結(jié)構(gòu)。要實(shí)現(xiàn)題目的五點(diǎn)要求，必須先理清循環(huán)冗余檢驗(yàn)CRC算法的具體計(jì)算過程，以此為基礎(chǔ)編寫程序，再在初始算法程序上繼續(xù)修改和添加來實(shí)現(xiàn)產(chǎn)生突變 等的情況。關(guān)于CRC算法過程，在闡述原理時(shí)已有大致講到，一下是統(tǒng)一細(xì)致

13、的 分析。2.1 CRC編碼規(guī)則CRC碼是由兩部分組成，前部分是信息碼，就是需要校驗(yàn)的信息，后部分是 校驗(yàn)碼，如果CRC碼共長n個(gè)bit，信息碼長k個(gè)bit，就稱為(n,k)碼。它的 編碼規(guī)則是：(1)移位將原信息碼(kbit)左移r位(k+r= n)(2)相除運(yùn)用一個(gè)生成多項(xiàng)式g(x)(也可看成二進(jìn)制數(shù))用模2除上面的式子，得到的余數(shù)就是校驗(yàn)碼。非常簡單，要說明的：模2除就是在除的過程中用模2加，模2加實(shí)際上就 是我們熟悉的異或運(yùn)算，就是加法不考慮進(jìn)位，公式是：0+0=1+1=0,1+0=0+1=1即異則真，非異則假。由此得到定理：a+b+b=a也就是模2減和模2加直值表完全相同。有了加減法

14、就可以用來定義模 2除法，于是就可以用生成多項(xiàng)式g(x)生成CRC 校驗(yàn)碼。2.2 CRC碼的生成步驟第一步：在數(shù)據(jù)單元(k位)的末尾加上n個(gè)0。n是一個(gè)比預(yù)定除數(shù)的比 特位數(shù)(n+1 )少1的數(shù)。第二步：采用二進(jìn)制除法將新的加長的數(shù)據(jù)單元(k+n位)除以除數(shù)。由此 除法產(chǎn)生的余數(shù)就是循環(huán)冗余碼校驗(yàn)碼。第三步：用從第二步得到的n個(gè)比特的CRC碼替換數(shù)據(jù)單元末尾附加的n個(gè)0。如果余數(shù)位數(shù)小于n,最左的缺省位數(shù)為0。如果除法過程根本未產(chǎn)生余 數(shù)(也就是說，原始的數(shù)據(jù)單元本身就可以被除數(shù)整除)那么以 n個(gè)0作為CRC 碼替換余數(shù)所在的位置。產(chǎn)生的比特模式正好能被除數(shù)整除。2.3 CRC校驗(yàn)過程展示假

15、設(shè)數(shù)據(jù)傳輸過程中需要發(fā)送15位的二進(jìn)制信息g=101001110100001,這串二進(jìn)制碼可表示為代數(shù)多項(xiàng)式 g(x)=xA14+xA12+xA9+xA8+xA7+xA5+1，其中g(shù) 中第k位的值，對應(yīng)g(x)中xAk的系數(shù)。將g(x)乘以xAm,既將g后加m個(gè)0， 然后除以m階多項(xiàng)式h(x)，得到的(m-1)階余項(xiàng)r(x)對應(yīng)的二進(jìn)制碼r就是CRC 編碼。h(x)可以自由選擇或者使用國際通行標(biāo)準(zhǔn)，一般按照h(x)的階數(shù)m將CRC算法稱為 CRC-m 比女口 CRC-32 CRC-64等。g(x)和h(x)的除運(yùn)算，可以通過g和h做xor (異或)運(yùn)算。比如將11001 與10101做xor運(yùn)

16、算如圖2-2 :：1! 1 i 0 !0；1丨I 1C 1 10111 0 i0 ： 0 廠1*111圖2-2 11001與10101做xor運(yùn)算所得結(jié)果明白了 xor運(yùn)算法則后，舉一個(gè)例子使用 CRC-8算法求101001110100001的效驗(yàn)碼如圖 2-3 所示。CRC-8標(biāo)準(zhǔn)的 h(x) = xA8 + xA7 + xA6 + xA4 + xA2 + 1，既h是9位的二進(jìn)制串111010101。§010100111010000100000000h111010101Si01001101110000100000000h1110101010111000100000100000000

17、h111010101g3©W10001000100000000h111010101§401100010000000000h111010101gs0010111010000000h111010101©1010000100000h111010101g?0100101110000h111010101gs011111011000h111010101r00010001100圖2-3使用CRC-8算法求101001110100001的效驗(yàn)碼經(jīng)過迭代運(yùn)算后，最終得到的r是10001100,這就是CRC效驗(yàn)碼。通過示例，可以發(fā)現(xiàn)一些規(guī)律，依據(jù)這些規(guī)律調(diào)整算法：（1）每次迭代，根據(jù)

18、gk的首位決定b，b是與gk進(jìn)行運(yùn)算的二進(jìn)制碼。若 gk的首位是1，則b=h，如圖2-4所示；若gk的首位是0，則b=0,或者跳過此 次迭代，如圖2-5所示，上面的例子中就是碰到0后直接跳到后面的非零位。戰(zhàn)首位是1gk b = h11111011000111010101r00010001100圖2-4 gk首位為1時(shí)的情況甌首位是0gk01111011000b = 00r01111011000圖2-5 gk首位為0時(shí)的情況(2)每次迭代，gk的首位將會被移出，如圖2-6所示，所以只需考慮第2 位后計(jì)算即可。這樣就可以舍棄 h的首位，將b取h的后m位。比如CRC-8的h 是 111010101，

19、b 只需是 11010101。M1U011000b11010101r0010001100圖2-6首位移出過程(3)每次迭代，受到影響的是gk的前m位，所以構(gòu)建一個(gè)m位的寄存器S,此 寄存器儲存gk的前m位。每次迭代計(jì)算前先將S的首位拋棄，將寄存器左移一 位，同時(shí)將g的后一位加入寄存器。若使用此種方法，計(jì)算步驟如圖2-7所示：S 1L0100111g=10100111010000100000000s' 01001110b11010101S首位：1S 1L0011011g:10100111010000100000000s 00110111b11010101S首位：1S 1L1100010g

20、:10100111010000100000000s 11000100b11010101S首位：1S ()0010001g:10100111010000100000000s 00100010b0S首位：0S ()0100010g:10100111010000100000000s 01000100b0s首位：0圖2-7使用寄存器計(jì)算的步驟三、過程論述了解到CRC勺具體計(jì)算過程后，可以開始構(gòu)造基本程序架構(gòu)。以for循環(huán)來 建立迭代運(yùn)算，按照題目要求，可將程序分為四個(gè)部分進(jìn)行編寫。1、第一部分該部分利用數(shù)組模擬網(wǎng)絡(luò)數(shù)據(jù)包結(jié)構(gòu)， 編碼實(shí)現(xiàn)CRC求余算法。程序流程圖如圖3-1所示圖3-1第一部分程序流程圖

21、2、第二部分該部分將得到的校驗(yàn)位附加到網(wǎng)絡(luò)數(shù)據(jù)包相應(yīng)的位置，并將添加了幀檢驗(yàn)序列FCS的數(shù)據(jù)繼續(xù)以模2除法進(jìn)行CRC僉驗(yàn)。程序流程圖如圖3-2所示11武漢理工大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)課程論文12武漢理工大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)課程論文將生成余數(shù)序列的冗余位疊加到編碼序列取冗余編碼長度L、初始化余數(shù)數(shù)組R、令k=0fk=k+1開始構(gòu)造與R等長度的除數(shù)數(shù)組PYN判斷R的首 位是否為0R = P xor R恢復(fù)除數(shù)數(shù)組、去除被除數(shù)第一位NYk>L-length(CRC P)+1被除數(shù)所有位置0判斷余數(shù)是否為1Y5輸出原始序列顯示碼元傳輸發(fā)生錯(cuò)誤（結(jié)束一）3-2第二部分程序流程圖圖13武漢理工大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)課程論文

22、3、第三部分該部分實(shí)現(xiàn)了根據(jù)數(shù)據(jù)包的長度，隨機(jī)生成一個(gè)數(shù)據(jù)包產(chǎn)生突變的位置，并 對該位置的bit位模擬突變產(chǎn)生的過程。按照要求，先利用i=ceil（rand（1,1）*r）函數(shù)來隨機(jī)抽取數(shù)組中的一個(gè)位，其中r為該數(shù)組的長度。再將該位的值進(jìn)行取反再放回，生成一個(gè)某位發(fā)生突變 的新數(shù)組。重新利用CRC算法校驗(yàn)該數(shù)據(jù)包，并指出產(chǎn)生的結(jié)果。由于檢驗(yàn)方法 與第二部分一致，因此程序流程圖與第二部分的流程圖（圖3-2 ）基本一致，此處不再繪制。4、第四部分該部分構(gòu)造出了一個(gè)無法被CRC檢錯(cuò)的實(shí)例，來驗(yàn)證CRC是否能夠檢出所有 的錯(cuò)誤。通過查閱資料，我了解到了 CRC校驗(yàn)的檢錯(cuò)性能。CRC校驗(yàn)碼的檢錯(cuò)能力與

23、其生成多項(xiàng)式密切相關(guān)。生成多項(xiàng)式的次數(shù)越高，其檢錯(cuò)能力越強(qiáng)。若CRC校驗(yàn) 的生成多項(xiàng)式的最高次幕為r，則該CRC校驗(yàn)碼的檢錯(cuò)性能如下：（1）可檢出所有奇數(shù)個(gè)錯(cuò)誤；（2）可檢出所有2bit個(gè)錯(cuò)誤；（3）可檢出所有長度<=r個(gè)bit的突發(fā)錯(cuò)誤；（4） 對于長度=（葉1）個(gè)bit的突發(fā)錯(cuò)，其漏檢率僅為：1/2A（r-1 ）;（5） 對于長度 > （葉1）個(gè)bit的突發(fā)錯(cuò)，其漏檢率僅為：1/2Ar。事實(shí)證明CRC雖具有良好的檢錯(cuò)能力，但不能夠檢出所有的錯(cuò)誤。構(gòu)造該無 法檢錯(cuò)的實(shí)例的思路：由于生成多項(xiàng)式的次數(shù)越高，CRC勺檢錯(cuò)能力越強(qiáng)，故我在程序中自主構(gòu)建一個(gè)相對簡單的生成多項(xiàng)式便于實(shí)例的構(gòu)

24、造?；仡機(jī)RC僉驗(yàn)的方法，先將添加了冗余碼FCS后發(fā)送的序列與求余過程中的生成多項(xiàng)式進(jìn)行模2運(yùn)算，再來判斷求得的余數(shù)是否為 0?若為0則證明傳輸過程無差錯(cuò)；若不為 0 則證明傳輸過程中有差錯(cuò)。因此我進(jìn)行大膽猜測：如若添加了冗余碼FCS后發(fā)送的數(shù)據(jù)發(fā)生突變，但突 變后的數(shù)據(jù)恰巧也能被原生成多項(xiàng)式整除，即存在 ？同余？的錯(cuò)誤，是不是CRC便無法檢測出該已經(jīng)發(fā)生了突變的錯(cuò)誤數(shù)據(jù)？因此我在該部分構(gòu)造了一個(gè)與原發(fā)送數(shù)據(jù)不同的錯(cuò)誤序列，經(jīng)驗(yàn)算，該錯(cuò)誤序列也能被原定的生成多項(xiàng)式整除。再利用第二部分的檢驗(yàn)方式，觀察最終輸出結(jié)果與預(yù)測是否一致， 最后加上一個(gè) 判斷語句顯示最終結(jié)果。由于檢驗(yàn)方式與第二部分一致，故

25、對于檢驗(yàn)的流程圖不再繪制，對于判斷結(jié) 果的程序流程圖如圖3-3所示。開始16武漢理工大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)課程論文#武漢理工大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)課程論文已知錯(cuò)誤序列 error_sequenee編寫原序列M四、結(jié)果分析將程序運(yùn)行后可以得到所有的輸出，現(xiàn)將輸出分三個(gè)部分展示1、CRC算法的實(shí)現(xiàn)編程實(shí)現(xiàn)利用數(shù)組模擬網(wǎng)絡(luò)數(shù)據(jù)包結(jié)構(gòu)實(shí)現(xiàn) CRC算法，并將得到的校驗(yàn)位附加到網(wǎng)絡(luò)數(shù)據(jù)包相應(yīng)的位置。程序中， M表示原始帶傳送數(shù)據(jù)；CRC_表示生成 多項(xiàng)式；ere_M表示經(jīng)計(jì)算得到的添加了冗余碼 FCS后的數(shù)據(jù)。若輸出一組名為 original_sequenee 的數(shù)據(jù)則表明本次校驗(yàn)結(jié)果正確；若輸出err=1則表明本次 校

26、驗(yàn)結(jié)果錯(cuò)誤。令M=1O1110生成多項(xiàng)式P(X)=XA3+1。結(jié)果如圖4-1所示。Command Window10 1110CRC_P =I0 01crc_M =10 1II001original.sequence =10 1110fii圖4-1 CRC校驗(yàn)結(jié)果展示分析：從結(jié)果中看出crc_M的結(jié)果為101110011，即所得冗余碼FCS=011 與驗(yàn)算結(jié)果一致。且經(jīng)校驗(yàn)后輸出了一組名為original_sequenee 的數(shù)據(jù)，該數(shù) 據(jù)與M致，說明校驗(yàn)結(jié)果正確。這也證實(shí)了此次編程實(shí)現(xiàn)了循環(huán)冗余校驗(yàn)CRC算法的要求。2、突變的產(chǎn)生和校驗(yàn)結(jié)果根據(jù)數(shù)據(jù)包的長度，編程實(shí)現(xiàn)隨機(jī)生成一個(gè)數(shù)據(jù)包產(chǎn)生突變的

27、位置，并對該 位置的bit位模擬突變的產(chǎn)生；再重新利用CRC算法校驗(yàn)該數(shù)據(jù)包，并指出產(chǎn)生 的結(jié)果。程序中，i為一個(gè)隨機(jī)數(shù)，代表著原冗余數(shù)組crc_M中的某一位的位序； 程序中還會輸出該隨機(jī)位的值；隨后會得到該隨機(jī)位的值發(fā)生突變后的突變數(shù) 組，此時(shí)用crc_M表示這個(gè)突變的數(shù)組；在進(jìn)行校驗(yàn)后若輸出一組名為 original_sequenee 的數(shù)據(jù)則表明本次校驗(yàn)結(jié)果正確；若輸出err=1則表明本次 校驗(yàn)結(jié)果錯(cuò)誤。突變及其校驗(yàn)結(jié)果如圖4-2所示0 0 10Command Window=1crc_M =1 0 1 err =1A圖4-2突變及其校驗(yàn)結(jié)果展示分析：由結(jié)果可知隨機(jī)抽到的位序?yàn)?9,從圖4

28、-1中看出原冗余數(shù)組的第九 位為1。在發(fā)生突變后的新數(shù)組crc_M=101110010,剛好與圖4-1中原冗余數(shù)組 的第九位不同，其余位均相同。表明隨機(jī)生成一個(gè)數(shù)據(jù)包產(chǎn)生突變的位置，并對 該位置的bit位模擬突變的產(chǎn)生的設(shè)計(jì)是正確的。再來看校驗(yàn)的結(jié)果是輸出了err=1，這說明突變后的數(shù)組成功被 CRC校驗(yàn)檢出錯(cuò)誤，證實(shí)了 CRC檢驗(yàn)算法的 檢錯(cuò)能力。3、無法檢錯(cuò)的實(shí)例在過程論證模塊，對于程序的第四部分，已經(jīng)表明了對于如何構(gòu)造無法檢錯(cuò) 實(shí)例的設(shè)計(jì)思路。在程序中，先編寫一個(gè)與原冗余數(shù)組crc_M不同但位數(shù)相同，同時(shí)也能被生成多項(xiàng)式整除的數(shù)組 N;已知N并不是正確的傳輸數(shù)據(jù)，對 N進(jìn)行 CRC算法檢

29、驗(yàn)，若輸出一組名為error_sequenee的數(shù)據(jù)則表明實(shí)際傳輸?shù)臄?shù)據(jù) 錯(cuò)誤，CRC無法檢錯(cuò)；若輸出err=1則表明CRC算法依舊能夠檢出該錯(cuò)誤。對于該實(shí)例的校驗(yàn)結(jié)果如圖4-3所示。圖4-3無法檢錯(cuò)實(shí)例的校驗(yàn)結(jié)果展示分析：從結(jié)果中可能看出，N與原冗余數(shù)組crc_M是不同的。但最后經(jīng)同一 生成多項(xiàng)式檢驗(yàn)得到的結(jié)果并沒有輸出err=1的字眼，而是輸出了一組名為error_sequenee的數(shù)組，很明顯，這一組數(shù)據(jù)與最原始的待傳送數(shù)據(jù)M不同，是錯(cuò)誤數(shù)據(jù)，而檢驗(yàn)結(jié)果未報(bào)錯(cuò)說明沒有檢驗(yàn)到該錯(cuò)誤。最終的顯示也是？實(shí)際傳輸數(shù)據(jù)錯(cuò)誤，無法檢錯(cuò)？，這也證實(shí)了構(gòu)造無法檢錯(cuò)實(shí)例的思路和該段程序的 編譯都是正確的。

30、從而證明，CRC并不能夠檢出所有的錯(cuò)誤。五、總結(jié)CR(校驗(yàn)碼是基于將位串看作是系數(shù)為 0或1的多項(xiàng)式，一個(gè)k位的數(shù)據(jù)流 可以看作是關(guān)于x的從k-1階到0階的k-1次多項(xiàng)式的系數(shù)序列。采用此編碼， 發(fā)送方和接收方必須事先商定一個(gè)生成多項(xiàng)式 G(x)，其高位和低位必須是1。要 計(jì)算m位的幀M(x)的校驗(yàn)和，基本思想是將校驗(yàn)和加在幀的末尾，使這個(gè)帶校 驗(yàn)和的幀的多項(xiàng)式能被 G(x)除盡。當(dāng)接收方收到加有校驗(yàn)和的幀時(shí)，用G(x)去除它，如果有余數(shù)，則CRC校驗(yàn)錯(cuò)誤，只有沒有余數(shù)的校驗(yàn)才是正確的。二進(jìn)制多項(xiàng)式的加減運(yùn)算為模2加減運(yùn)算，即兩個(gè)碼多項(xiàng)式相加時(shí)，對應(yīng)系 數(shù)進(jìn)行模2加減。所謂模2加減就是各位做不

31、帶進(jìn)位、借位的按位加減。這種加 減運(yùn)算實(shí)際上是邏輯上的異或運(yùn)算，即加法和減法等價(jià)。信息多項(xiàng)式和余數(shù)多項(xiàng)式可以合并成一個(gè)新的多項(xiàng)式（稱為循環(huán)碼的碼多項(xiàng) 式），則該多項(xiàng)式是生成多項(xiàng)式的整數(shù)倍，即能被生成多項(xiàng)式整除。根據(jù)這一原 理，在發(fā)送端用信息碼多項(xiàng)式除以生成多項(xiàng)式所得的余數(shù)多項(xiàng)式就是所要加的監(jiān) 督位。將循環(huán)碼的碼多項(xiàng)式除以生成多項(xiàng)式，若能除盡，說明傳輸正確，否則說 明出錯(cuò)。CRC校驗(yàn)的關(guān)鍵是如何求出余數(shù)，此余數(shù)即為校驗(yàn)碼（ CRC校驗(yàn)碼）。為了傳輸?shù)恼_性，在接收端要有一個(gè)CRC僉驗(yàn)器。它的功能和發(fā)生器一樣, 當(dāng)收到CRC冗余校驗(yàn)碼后，做同樣的模2除法（注意，這里采用的生成多項(xiàng)式一 定要與發(fā)送端

32、相同）。如果余數(shù)是 0,則說明傳輸正確；否則傳輸錯(cuò)誤。CRC校驗(yàn)的檢錯(cuò)能力極強(qiáng)，但并不能檢出所有的錯(cuò)誤。當(dāng)冗余數(shù)組發(fā)生突變, 生成一個(gè)與原數(shù)組存在？同余?現(xiàn)象的新數(shù)組，CRC是無法檢出此種錯(cuò)誤的。21武漢理工大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)課程論文心得體會經(jīng)歷了近兩個(gè)星期的查閱資料和理論分析，終于完成了循環(huán)冗余校驗(yàn) CRC 算法編程和報(bào)告。經(jīng)歷了這次計(jì)算機(jī)網(wǎng)絡(luò)的大作業(yè)設(shè)計(jì)， 大大的提高了我的操作 能力以及分析問題的能力，從中也學(xué)到了很多書面上關(guān)于CRC校驗(yàn)所沒有搞清楚 的問題，也熟悉了應(yīng)用MATLA這個(gè)軟件來進(jìn)行程序編程。通過這次大作業(yè)設(shè)計(jì)，我學(xué)到了很多有用的知識，并加強(qiáng)了自己掌握和理解 書本知識的能力，培養(yǎng)了

33、自己的實(shí)際動手能力與綜合設(shè)計(jì)能力， 提高了自己的技 術(shù)素質(zhì)，這對以后的學(xué)習(xí)和工作都是非常有益的。 在此次設(shè)計(jì)中，我先大量查閱 CRC算法的具體過程，逐一分析題目要求，通過動手實(shí)踐操作，進(jìn)一步學(xué)習(xí)和掌 握了有關(guān)CRC原理的知識，加深了對糾錯(cuò)技術(shù)的認(rèn)識。在設(shè)計(jì)過程中我復(fù)習(xí)了相 關(guān)知識，還查閱了相當(dāng)多的資料，這也在一定程度上拓寬了我的視野， 豐富了我 的知識。現(xiàn)如今我對CRC算法有了非常深刻的理解，這次的大作業(yè)設(shè)計(jì)不止是對 所學(xué)知識的一次重要鞏固，更是從查閱資料、逐一分析題目要求、動手編寫程序 到不斷地修改和完善等方面鍛煉了我的綜合能力?？傊?，通過這次大作業(yè)設(shè)計(jì)我有了很多收獲。摸索該如何使用MATL

34、A去實(shí)現(xiàn)題目要求的過程特別有趣，培養(yǎng)了我的設(shè)計(jì)思維；無論是對所學(xué)課本知識的運(yùn) 用還是對軟件系統(tǒng)的了解，我都有了很大程度的提高，提高了理論用于實(shí)踐的能 力，掌握了更多專業(yè)相關(guān)的使用知識與技能。 在程序運(yùn)行過程中曾遇到許多困難 和錯(cuò)誤，最后通過不斷查閱資料和向同學(xué)請教一一解決。當(dāng)最終完成本次課程設(shè) 計(jì)時(shí)，我深刻體會到成功的喜悅和快樂。參考文獻(xiàn)1 .謝希仁等計(jì)算機(jī)網(wǎng)絡(luò)（第六版）M.北京：電子工業(yè)出版社，2013.6 ；2 .王虹等.通信系統(tǒng)原理M.北京：國防工業(yè)出版社，2014.8;3 .孫麗華.信息論與糾錯(cuò)編碼M.電子工業(yè)出版社，2005.3.附件一：程序源代碼M=1,0,1,1,1,0% M為待

35、傳送數(shù)據(jù)L= length(M);% L為數(shù)據(jù)M的長度CRC_P = 1 0 0 1;% CR(生成多項(xiàng)式 P(X)=XA3+1n = zeros(1,3);%添加3位冗余碼crc_M = M zeros(1,3);%初始化輸出檢錯(cuò)碼序列M = M n; %在數(shù)據(jù)M后面添加供差錯(cuò)檢測用的n位冗余碼R = M; %初始化余數(shù)數(shù)組Rfor k = 1:L%利用循環(huán)語句計(jì)算求余數(shù)add_zeros = zeros(1,L-k);P = CRC_P add_zeros;if R(1) = 0P = zeros(1,le ngth(P);%設(shè)置冗余位參與模2運(yùn)算%構(gòu)造與R等長度的除數(shù)數(shù)組P%若R首位為0

36、則將除數(shù)所有位置0endR = bitxor(P,R); %將除數(shù)與被除數(shù)進(jìn)行異或操作P = CRC_P; %將寄存器恢復(fù)為除數(shù)數(shù)組R(1) = ;%去除模2運(yùn)算后得到的被除數(shù)的第1位 end%第二部分add_le n = len gth(crc_M) - le ngth(R);%生成余數(shù)序列的冗余位以疊加到編碼序列R = zeros(1,add_len),R;%將所得余數(shù)序列添加冗余至與 crc_M等長度crc_M =crc_M + R %合成編碼序列L = len gth(crc_M);%得到冗余編碼的長度origi nal_seque nee = crc_M;% 初始化輸出序列CRC_P = 1 0 0 1;% CR(生成多項(xiàng)式 P(X)=XA3+1R = crc_M; %初始化余數(shù)數(shù)組T = L-le ngth(CRC_P)+1; % T為長除法的循環(huán)周期for k = 1:T%利用循環(huán)語句計(jì)算求余數(shù)add_zeros = zeros(1,T-k);P = CRC_P add_zeros;if R(1) = 0P =