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

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

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

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

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

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

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

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

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

9、M后面添加n個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這個商并沒有什么用處），而余數(shù)R=001。 這個余數(shù)R就作為冗余碼拼接在數(shù)據(jù) M的后面發(fā)送出去。這種為了進(jì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)冗余檢驗原理的例子在接收端把接受到的數(shù)據(jù)以幀為單位進(jìn)行CRC檢驗：把收到的每一個幀都除以同樣的除數(shù)P （模2運(yùn)算），然后檢查得到余數(shù)Ro如果在傳輸過程中無差錯，那么經(jīng)過 CRC僉驗后得到的余數(shù)R肯定是0。但 如果出現(xiàn)誤碼，那么余數(shù) R仍等于零的概率是非常非常小的。總之，在接收端對收到的每一幀經(jīng)過 CRC檢驗后，有以下兩種情況：（1）若得到的余數(shù)R等于0，則判定這個幀沒有差錯，就接受（accept ）。(2)若余數(shù)R不等于0,則判定這個幀有差錯(但無法確定

11、究竟是哪一位 或哪幾位出現(xiàn)了差錯)，就丟棄。一種較方便的方法是用多項式來表示循環(huán)冗余檢驗過程。在上面的例子中，用多項式P(X)=XA3+XA2+1表示上面的除數(shù)P=1101(最高位對應(yīng)于XA3,最低位對 應(yīng)于XA0)。多項式P(X)稱為生成多項式。現(xiàn)在廣泛使用的生成多項式 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ā)送端幀檢驗序列FCS的生成和接收端的CRC檢驗都是用

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

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

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

15、設(shè)數(shù)據(jù)傳輸過程中需要發(fā)送15位的二進(jìn)制信息g=101001110100001,這串二進(jìn)制碼可表示為代數(shù)多項式 g(x)=xA14+xA12+xA9+xA8+xA7+xA5+1，其中g(shù) 中第k位的值，對應(yīng)g(x)中xAk的系數(shù)。將g(x)乘以xAm,既將g后加m個0， 然后除以m階多項式h(x)，得到的(m-1)階余項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)算法則后，舉一個例子使用 CRC-8算法求101001110100001的效驗碼如圖 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的效驗碼經(jīng)過迭代運(yùn)算后，最終得到的r是10001100,這就是CRC效驗碼。通過示例，可以發(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時的情況甌首位是0gk01111011000b = 00r01111011000圖2-5 gk首位為0時的情況(2)每次迭代，gk的首位將會被移出，如圖2-6所示，所以只需考慮第2 位后計算即可。這樣就可以舍棄 h的首位，將b取h的后m位。比如CRC-8的h 是 111010101，

19、b 只需是 11010101。M1U011000b11010101r0010001100圖2-6首位移出過程(3)每次迭代，受到影響的是gk的前m位，所以構(gòu)建一個m位的寄存器S,此 寄存器儲存gk的前m位。每次迭代計算前先將S的首位拋棄，將寄存器左移一 位，同時將g的后一位加入寄存器。若使用此種方法，計算步驟如圖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使用寄存器計算的步驟三、過程論述了解到CRC勺具體計算過程后，可以開始構(gòu)造基本程序架構(gòu)。以for循環(huán)來 建立迭代運(yùn)算，按照題目要求，可將程序分為四個部分進(jìn)行編寫。1、第一部分該部分利用數(shù)組模擬網(wǎng)絡(luò)數(shù)據(jù)包結(jié)構(gòu)， 編碼實現(xiàn)CRC求余算法。程序流程圖如圖3-1所示圖3-1第一部分程序流程圖

21、2、第二部分該部分將得到的校驗位附加到網(wǎng)絡(luò)數(shù)據(jù)包相應(yīng)的位置，并將添加了幀檢驗序列FCS的數(shù)據(jù)繼續(xù)以模2除法進(jìn)行CRC僉驗。程序流程圖如圖3-2所示11武漢理工大學(xué)計算機(jī)網(wǎng)絡(luò)課程論文12武漢理工大學(xué)計算機(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ā)生錯誤（結(jié)束一）3-2第二部分程序流程圖圖13武漢理工大學(xué)計算機(jī)網(wǎng)絡(luò)課程論文

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

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

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

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

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

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

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

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

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

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

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

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

34、A去實現(xiàn)題目要求的過程特別有趣，培養(yǎng)了我的設(shè)計思維；無論是對所學(xué)課本知識的運(yùn) 用還是對軟件系統(tǒng)的了解，我都有了很大程度的提高，提高了理論用于實踐的能 力，掌握了更多專業(yè)相關(guān)的使用知識與技能。 在程序運(yùn)行過程中曾遇到許多困難 和錯誤，最后通過不斷查閱資料和向同學(xué)請教一一解決。當(dāng)最終完成本次課程設(shè) 計時，我深刻體會到成功的喜悅和快樂。參考文獻(xiàn)1 .謝希仁等計算機(jī)網(wǎng)絡(luò)（第六版）M.北京：電子工業(yè)出版社，2013.6 ；2 .王虹等.通信系統(tǒng)原理M.北京：國防工業(yè)出版社，2014.8;3 .孫麗華.信息論與糾錯編碼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(生成多項式 P(X)=XA3+1n = zeros(1,3);%添加3位冗余碼crc_M = M zeros(1,3);%初始化輸出檢錯碼序列M = M n; %在數(shù)據(jù)M后面添加供差錯檢測用的n位冗余碼R = M; %初始化余數(shù)數(shù)組Rfor k = 1:L%利用循環(huán)語句計算求余數(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(生成多項式 P(X)=XA3+1R = crc_M; %初始化余數(shù)數(shù)組T = L-le ngth(CRC_P)+1; % T為長除法的循環(huán)周期for k = 1:T%利用循環(huán)語句計算求余數(shù)add_zeros = zeros(1,T-k);P = CRC_P add_zeros;if R(1) = 0P =