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

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

2、在相應(yīng)欄目打）評 價 項 目論文與設(shè)計評價質(zhì)量按對應(yīng)項目打分工作量和態(tài)度（10分）分析問題能力（10分）解決問題能力（10分）內(nèi)容完整層次分明（10分）設(shè)計、實驗正確性（10分）書寫規(guī)范（10分）流程圖或拓撲圖（10分）論證充分（10分）測試結(jié)果情況（10分）總體評價（10分）評定成績（100分制）指導(dǎo)教師簽名年 月 日目 錄一、選題背景11.設(shè)計要求12.循環(huán)冗余CRC簡介13.應(yīng)解決的主要問題2二、方案論證21.循環(huán)冗余檢驗的原理22.方案的選擇及特點4三、過程論述81.第一部分82.第二部分93.第三部分114.第四部分11四、結(jié)果分析121.CRC算法的實現(xiàn)122.突變的產(chǎn)生和校驗結(jié)果

3、133.無法檢錯的實例14五、總結(jié)15心得體會17參考文獻17附件一：程序源代碼181、VI一、選題背景題目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ù)包的長度，隨機生成一個數(shù)據(jù)包產(chǎn)生突變的位置，并對該位置的bit位模擬突變的產(chǎn)生。（4）重新利用CRC算法校驗該數(shù)據(jù)包，并指出產(chǎn)生的結(jié)果。（5）CRC能夠檢出所有的錯誤嗎？如果不能，你能構(gòu)造出無法檢錯的實例嗎？2、循環(huán)冗余CRC簡介循環(huán)冗余校驗碼（CRC碼，CRC=Cyclic Redundancy Check）：是

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

5、, 是一種通過多項式除法檢測錯誤的很不尋常而又巧妙的方法, 一方面它有很強的檢測能力, 二是它的編碼器電路及錯誤檢測器電路都很容易實現(xiàn), 它的優(yōu)點使它在通信系統(tǒng)中得到了廣泛的應(yīng)用?，F(xiàn)實的通信鏈路都不會是理想的。這就是說，比特在傳輸過程中可能會產(chǎn)生差錯:1可能會變成0，而0也可能變成1。這就叫做比特差錯。比特差錯是傳輸差錯中的一種。在一段時間內(nèi)，傳輸錯誤的比特占所傳輸比特總數(shù)的比率稱為誤碼率BEG。誤碼率與信噪比有很大的關(guān)系。如果設(shè)法提高信噪比，就可以使誤碼率減小。實際的通信鏈路并非是理想的，它不可能使誤碼率下降到零。因此，為了保證數(shù)據(jù)傳輸?shù)目煽啃?，在計算機網(wǎng)絡(luò)傳輸數(shù)據(jù)時，必須采用各種差錯檢測措

6、施。目前在數(shù)據(jù)鏈路層廣泛使用了循環(huán)冗余檢驗CRC的檢錯技術(shù)。3、 應(yīng)解決的主要問題（1）選用哪種軟件實現(xiàn)編程：MATLAB具有程序結(jié)構(gòu)控制、函數(shù)調(diào)用、數(shù)據(jù)結(jié)構(gòu)、輸入輸出、面向?qū)ο蟮瘸绦蛘Z言特征，而且簡單易學(xué)、編程效率高。MATLAB提供了一個人機交互的數(shù)學(xué)系統(tǒng)環(huán)境，該系統(tǒng)的基本數(shù)據(jù)結(jié)構(gòu)是矩陣，在生成矩陣對象時，不要求明確的維數(shù)說明。與利用C語言作數(shù)值計算的程序設(shè)計相比，利用MATLAB可以節(jié)省大量的編程時間。本次大作業(yè)采用數(shù)組模擬網(wǎng)絡(luò)數(shù)據(jù)包結(jié)構(gòu)，采用MATLAB操作簡單，結(jié)果明了，故用MATLAB程序語言實現(xiàn)CRC校驗的程序設(shè)計。（2）理想的循環(huán)冗余校驗算法應(yīng)具有以下特征：CRC相同的數(shù)據(jù)多次

7、，每次得到的CRC值應(yīng)該相同。這也是通信過程中通過CRC校驗數(shù)據(jù)在收發(fā)過程中是否出錯的基本依據(jù)。CRC不同的數(shù)據(jù)得到的CRC值應(yīng)該不等。(盡管通過估計偽造可能得到相同的CRC值，但要確保這種概率很小)對于32位的CRC來說，它能區(qū)分232的數(shù)據(jù)，即長度為232的兩個數(shù)據(jù)，只要有任何兩位的值不同，它們分別經(jīng)過CRC后得到的CRC值就不同。（3） 如何實現(xiàn)CRC算法過程：本次設(shè)計采用模2除法運算求余數(shù)，程序中可表示為將待傳送數(shù)據(jù)與生成多項式逐位異或。因為待傳送數(shù)據(jù)的位數(shù)不確定，一一編寫容易出錯且麻煩，不易于修改數(shù)據(jù)，因此在程序中采用for循環(huán)語句來逐位求解最終得到余數(shù)。二、方案論證1、循環(huán)冗余檢驗

8、的原理在發(fā)送端，先把數(shù)據(jù)劃分為組，假定每組k個比特。現(xiàn)假定待傳送的數(shù)據(jù)M=101001（k=6）。CRC運算就是在數(shù)據(jù)M的后面添加供差錯檢測用的n位冗余碼，然后構(gòu)成一個幀發(fā)送出去，一共發(fā)送（k+n）位。在所要發(fā)送的數(shù)據(jù)后面增加n位的冗余碼，雖然增大了數(shù)據(jù)傳輸?shù)拈_銷，但卻可以進行差錯檢測。當傳輸可能出現(xiàn)差錯時，付出這種代價往往是很值得的。這n位冗余碼可用以下方達得出。用二進制的模2運算進行2n乘M的運算，這相當于在M后面添加n個0。得到的（k+n）位的數(shù)除以收發(fā)雙方事先商定的長度為(n+1)位的除數(shù)P，得到商是Q而余數(shù)是R(n位，比P少一位)。關(guān)于除數(shù)P，在圖2-1所示的例子中，M=101001

9、(即k=6)。假定除數(shù)P=1101(即n=3)。經(jīng)模2除法運算后的結(jié)果是:商Q=110101(這個商并沒有什么用處)，而余數(shù)R=001。這個余數(shù)R就作為冗余碼拼接在數(shù)據(jù)M的后面發(fā)送出去。這種為了進行檢錯而添加的冗余碼常稱為幀檢驗序列FCS。因此加上FCS后發(fā)送的幀是101001001(即2n*M+FCS)，共有(k+n)位。 110101Q（商）P(除數(shù))11011010010002n*M(被除數(shù)) 1101 1110 1101 0111 000011101101 0110 0000 1100 1101 001R（余數(shù)),作為FCS圖2-1 說明循環(huán)冗余檢驗原理的例子在接收端把接受到的數(shù)據(jù)以幀

10、為單位進行CRC檢驗:把收到的每一個幀都除以同樣的除數(shù)P（模2運算），然后檢查得到余數(shù)R。如果在傳輸過程中無差錯，那么經(jīng)過CRC檢驗后得到的余數(shù)R肯定是0。但如果出現(xiàn)誤碼，那么余數(shù)R仍等于零的概率是非常非常小的?？傊?，在接收端對收到的每一幀經(jīng)過CRC檢驗后，有以下兩種情況：（1） 若得到的余數(shù)R等于0，則判定這個幀沒有差錯，就接受（accept）。（2） 若余數(shù)R不等于0，則判定這個幀有差錯（但無法確定究竟是哪一位或哪幾位出現(xiàn)了差錯），就丟棄。一種較方便的方法是用多項式來表示循環(huán)冗余檢驗過程。在上面的例子中，用多項式P(X)=X3+X2+1表示上面的除數(shù)P=1101（最高位對應(yīng)于X3,最低位對

11、應(yīng)于X0）。多項式P(X)稱為生成多項式?，F(xiàn)在廣泛使用的生成多項式P(X)有以下幾種：CRC-16=X16+X15+X2+1CRC-CCITT=X16+X12+X5+1CRC-32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1在數(shù)據(jù)鏈路層，發(fā)送端幀檢驗序列FCS的生成和接收端的CRC檢驗都是用硬件完成的，處理很迅速，因此并不會延誤數(shù)據(jù)的傳輸。如果在傳送數(shù)據(jù)時不以幀為單位來傳送，那么就無法加入冗余碼以進行差錯檢驗。因此，如果要在數(shù)據(jù)鏈路層進行差錯檢驗，就必須把數(shù)據(jù)劃分為幀，每一幀都加上冗余碼，一幀接一幀地傳送，然后在接收方逐幀進行差錯檢驗。

12、2、 方案的選擇及特點由于本次編程需要達到五點要求，因此進行逐一分析。在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)一細致的分析。2.1 CRC編碼規(guī)則CRC碼是由兩部分組成，前部分是信息碼，就是需要校驗的信息，后部分是校驗碼，如果CRC碼共長n個bit，信息碼長k個bit，就稱為(n,k)碼。 它的編碼規(guī)則是：（1）移位將原信息碼(kbit)左移r位(k+r=n)（2）相

13、除運用一個生成多項式g(x)（也可看成二進制數(shù)）用模2除上面的式子，得到的余數(shù)就是校驗碼。非常簡單，要說明的：模2除就是在除的過程中用模2加，模2加實際上就是我們熟悉的異或運算，就是加法不考慮進位，公式是：0+0=1+1=0,1+0=0+1=1即異則真，非異則假。由此得到定理：a+b+b=a 也就是模2減和模2加直值表完全相同。 有了加減法就可以用來定義模2除法，于是就可以用生成多項式g(x)生成CRC校驗碼。2.2 CRC碼的生成步驟第一步：在數(shù)據(jù)單元（k位）的末尾加上n個0。n是一個比預(yù)定除數(shù)的比特位數(shù)（n+1）少1的數(shù)。第二步：采用二進制除法將新的加長的數(shù)據(jù)單元（k+n位）除以除數(shù)。由此

14、除法產(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校驗過程展示假設(shè)數(shù)據(jù)傳輸過程中需要發(fā)送15位的二進制信息g=101001110100001，這串二進制碼可表示為代數(shù)多項式g(x)=x14+x12+x9+x8+x7+x5+1，其中g(shù)中第k位的值，對應(yīng)g(x)中xk的系數(shù)。將g(x)乘以xm，既將g后加m個0，然后除以m階多項式h(x)，

15、得到的(m-1)階余項r(x)對應(yīng)的二進制碼r就是CRC編碼。h(x)可以自由選擇或者使用國際通行標準，一般按照h(x)的階數(shù)m，將CRC算法稱為CRC-m，比如CRC-32、CRC-64等。g(x)和h(x)的除運算，可以通過g和h做xor（異或）運算。比如將11001與10101做xor運算如圖2-2：圖2-2 11001與10101做xor運算所得結(jié)果明白了xor運算法則后，舉一個例子使用CRC-8算法求101001110100001的效驗碼如圖2-3所示。CRC-8標準的h(x) = x8 + x7 + x6 + x4 + x2 + 1，既h是9位的二進制串111010101。

16、0;圖2-3 使用CRC-8算法求101001110100001的效驗碼經(jīng)過迭代運算后，最終得到的r是10001100，這就是CRC效驗碼。通過示例，可以發(fā)現(xiàn)一些規(guī)律，依據(jù)這些規(guī)律調(diào)整算法： （1）每次迭代，根據(jù)gk的首位決定b，b是與gk進行運算的二進制碼。若gk的首位是1，則b=h，如圖2-4所示；若gk的首位是0，則b=0，或者跳過此次迭代，如圖2-5所示，上面的例子中就是碰到0后直接跳到后面的非零位。圖2-4 gk首位為1時的情況圖2-5 gk首位為0時的情況（2）每次迭代，gk的首位將會被移出，如圖2-6所示，所以只需考慮第2位后計算即可。這樣就可以舍棄h的首位，將b取h的

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

18、示。開始構(gòu)建數(shù)組M、取其長度L、構(gòu)建生成多項式添加冗余位、k=0初始化余數(shù)數(shù)組Rk=k+1構(gòu)造與R等長度的除數(shù)數(shù)組PY判斷R的首位是否為0被除數(shù)所有位置0NR = P xor R恢復(fù)除數(shù)數(shù)組去除被除數(shù)第一位Nk>L?Y結(jié)束圖3-1 第一部分程序流程圖2、 第二部分該部分將得到的校驗位附加到網(wǎng)絡(luò)數(shù)據(jù)包相應(yīng)的位置，并將添加了幀檢驗序列FCS的數(shù)據(jù)繼續(xù)以模2除法進行CRC檢驗。程序流程圖如圖3-2所示。NY顯示碼元傳輸發(fā)生錯誤結(jié)束輸出原始序列YN判斷余數(shù)是否為0k>L-length(CRC_P)+1恢復(fù)除數(shù)數(shù)組、去除被除數(shù)第一位R = P xor R被除數(shù)所有位置0NY判斷R的首位是否為

19、0構(gòu)造與R等長度的除數(shù)數(shù)組Pk=k+1取冗余編碼長度L、初始化余數(shù)數(shù)組R、令k=0將生成余數(shù)序列的冗余位疊加到編碼序列開始圖3-2 第二部分程序流程圖3、 第三部分該部分實現(xiàn)了根據(jù)數(shù)據(jù)包的長度，隨機生成一個數(shù)據(jù)包產(chǎn)生突變的位置，并對該位置的bit位模擬突變產(chǎn)生的過程。按照要求，先利用i=ceil(rand(1,1)*r)函數(shù)來隨機抽取數(shù)組中的一個位，其中r為該數(shù)組的長度。再將該位的值進行取反再放回，生成一個某位發(fā)生突變的新數(shù)組。重新利用CRC算法校驗該數(shù)據(jù)包，并指出產(chǎn)生的結(jié)果。由于檢驗方法與第二部分一致，因此程序流程圖與第二部分的流程圖（圖3-2）基本一致，此處不再繪制。4、第四部分該部分構(gòu)造

20、出了一個無法被CRC檢錯的實例，來驗證CRC是否能夠檢出所有的錯誤。通過查閱資料，我了解到了CRC校驗的檢錯性能。CRC校驗碼的檢錯能力與其生成多項式密切相關(guān)。生成多項式的次數(shù)越高，其檢錯能力越強。若CRC校驗的生成多項式的最高次冪為r，則該CRC校驗碼的檢錯性能如下：（1） 可檢出所有奇數(shù)個錯誤；（2） 可檢出所有2bit個錯誤；（3） 可檢出所有長度<=r個bit的突發(fā)錯誤；（4） 對于長度=（r+1)個bit的突發(fā)錯，其漏檢率僅為：1/2(r-1）;（5） 對于長度>（r+1)個bit的突發(fā)錯，其漏檢率僅為：1/2r。事實證明CRC雖具有良好的檢錯能力，但不能夠檢出所有的錯誤

21、。構(gòu)造該無法檢錯的實例的思路：由于生成多項式的次數(shù)越高，CRC的檢錯能力越強，故我在程序中自主構(gòu)建一個相對簡單的生成多項式便于實例的構(gòu)造?；仡機RC檢驗的方法，先將添加了冗余碼FCS后發(fā)送的序列與求余過程中的生成多項式進行模2運算，再來判斷求得的余數(shù)是否為0？若為0則證明傳輸過程無差錯；若不為0則證明傳輸過程中有差錯。因此我進行大膽猜測：如若添加了冗余碼FCS后發(fā)送的數(shù)據(jù)發(fā)生突變，但突變后的數(shù)據(jù)恰巧也能被原生成多項式整除，即存在“同余”的錯誤，是不是CRC便無法檢測出該已經(jīng)發(fā)生了突變的錯誤數(shù)據(jù)？因此我在該部分構(gòu)造了一個與原發(fā)送數(shù)據(jù)不同的錯誤序列，經(jīng)驗算，該錯誤序列也能被原定的生成多項式整除。再

22、利用第二部分的檢驗方式，觀察最終輸出結(jié)果與預(yù)測是否一致，最后加上一個判斷語句顯示最終結(jié)果。由于檢驗方式與第二部分一致，故對于檢驗的流程圖不再繪制，對于判斷結(jié)果的程序流程圖如圖3-3所示。結(jié)束實際傳輸數(shù)據(jù)錯誤實際傳輸數(shù)據(jù)正確NYerror_sequence = M？已知錯誤序列error_sequence編寫原序列M開始圖3-3 第四部分判斷結(jié)果的程序流程圖4、 結(jié)果分析將程序運行后可以得到所有的輸出，現(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_P表示生成多項式；

23、crc_M表示經(jīng)計算得到的添加了冗余碼FCS后的數(shù)據(jù)。若輸出一組名為original_sequence的數(shù)據(jù)則表明本次校驗結(jié)果正確；若輸出err=1則表明本次校驗結(jié)果錯誤。令M=101110；生成多項式P(X)=X3+1。結(jié)果如圖4-1所示。圖4-1 CRC校驗結(jié)果展示分析：從結(jié)果中看出crc_M的結(jié)果為101110011，即所得冗余碼FCS=011，與驗算結(jié)果一致。且經(jīng)校驗后輸出了一組名為original_sequence的數(shù)據(jù)，該數(shù)據(jù)與M一致，說明校驗結(jié)果正確。這也證實了此次編程實現(xiàn)了循環(huán)冗余校驗CRC算法的要求。2、突變的產(chǎn)生和校驗結(jié)果根據(jù)數(shù)據(jù)包的長度，編程實現(xiàn)隨機生成一個數(shù)據(jù)包產(chǎn)生突變

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

25、4-1中原冗余數(shù)組的第九位不同，其余位均相同。表明隨機生成一個數(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進行CRC算法檢驗，若輸出一組名為error_sequence的數(shù)據(jù)則表明實際傳輸?shù)臄?shù)據(jù)錯誤，CRC無法檢錯；若輸出err=1則

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

27、流可以看作是關(guān)于x的從k-1階到0階的k-1次多項式的系數(shù)序列。采用此編碼，發(fā)送方和接收方必須事先商定一個生成多項式G(x)，其高位和低位必須是1。要計算m位的幀M(x)的校驗和，基本思想是將校驗和加在幀的末尾，使這個帶校驗和的幀的多項式能被G(x)除盡。當接收方收到加有校驗和的幀時，用G(x)去除它，如果有余數(shù)，則CRC校驗錯誤，只有沒有余數(shù)的校驗才是正確的。二進制多項式的加減運算為模2加減運算，即兩個碼多項式相加時，對應(yīng)系數(shù)進行模2加減。所謂模2加減就是各位做不帶進位、借位的按位加減。這種加減運算實際上是邏輯上的異或運算，即加法和減法等價。信息多項式和余數(shù)多項式可以合并成一個新的多項式（稱

28、為循環(huán)碼的碼多項式），則該多項式是生成多項式的整數(shù)倍，即能被生成多項式整除。根據(jù)這一原理，在發(fā)送端用信息碼多項式除以生成多項式所得的余數(shù)多項式就是所要加的監(jiān)督位。將循環(huán)碼的碼多項式除以生成多項式，若能除盡，說明傳輸正確，否則說明出錯。CRC校驗的關(guān)鍵是如何求出余數(shù)，此余數(shù)即為校驗碼（CRC校驗碼）。為了傳輸?shù)恼_性，在接收端要有一個CRC檢驗器。它的功能和發(fā)生器一樣，當收到CRC冗余校驗碼后，做同樣的模2除法（注意，這里采用的生成多項式一定要與發(fā)送端相同）。如果余數(shù)是0，則說明傳輸正確；否則傳輸錯誤。CRC校驗的檢錯能力極強，但并不能檢出所有的錯誤。當冗余數(shù)組發(fā)生突變，生成一個與原數(shù)組存在“同

29、余”現(xiàn)象的新數(shù)組，CRC是無法檢出此種錯誤的。心得體會經(jīng)歷了近兩個星期的查閱資料和理論分析，終于完成了循環(huán)冗余校驗CRC算法編程和報告。經(jīng)歷了這次計算機網(wǎng)絡(luò)的大作業(yè)設(shè)計，大大的提高了我的操作能力以及分析問題的能力，從中也學(xué)到了很多書面上關(guān)于CRC校驗所沒有搞清楚的問題，也熟悉了應(yīng)用MATLAB這個軟件來進行程序編程。通過這次大作業(yè)設(shè)計，我學(xué)到了很多有用的知識，并加強了自己掌握和理解書本知識的能力，培養(yǎng)了自己的實際動手能力與綜合設(shè)計能力，提高了自己的技術(shù)素質(zhì)，這對以后的學(xué)習(xí)和工作都是非常有益的。在此次設(shè)計中，我先大量查閱CRC算法的具體過程，逐一分析題目要求，通過動手實踐操作，進一步學(xué)習(xí)和掌握了

30、有關(guān)CRC原理的知識，加深了對糾錯技術(shù)的認識。在設(shè)計過程中我復(fù)習(xí)了相關(guān)知識，還查閱了相當多的資料，這也在一定程度上拓寬了我的視野，豐富了我的知識?，F(xiàn)如今我對CRC算法有了非常深刻的理解，這次的大作業(yè)設(shè)計不止是對所學(xué)知識的一次重要鞏固，更是從查閱資料、逐一分析題目要求、動手編寫程序到不斷地修改和完善等方面鍛煉了我的綜合能力?？傊?，通過這次大作業(yè)設(shè)計我有了很多收獲。摸索該如何使用MATLAB去實現(xiàn)題目要求的過程特別有趣，培養(yǎng)了我的設(shè)計思維；無論是對所學(xué)課本知識的運用還是對軟件系統(tǒng)的了解，我都有了很大程度的提高，提高了理論用于實踐的能力，掌握了更多專業(yè)相關(guān)的使用知識與技能。在程序運行過程中曾遇到許多

31、困難和錯誤，最后通過不斷查閱資料和向同學(xué)請教一一解決。當最終完成本次課程設(shè)計時，我深刻體會到成功的喜悅和快樂。參考文獻1.謝希仁等. 計算機網(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為待傳送數(shù)據(jù)L= length(M); % L為數(shù)據(jù)M的長度CRC_P = 1 0 0 1;% CRC生成多項式P(X)=X3+1n = zeros(1,3); % 添加3位冗余碼crc_M = M z

32、eros(1,3);% 初始化輸出檢錯碼序列 M = M n;% 在數(shù)據(jù)M后面添加供差錯檢測用的n位冗余碼R = M; % 初始化余數(shù)數(shù)組R for k = 1:L % 利用循環(huán)語句計算求余數(shù) add_zeros = zeros(1,L-k); % 設(shè)置冗余位參與模2運算 P = CRC_P add_zeros; % 構(gòu)造與R等長度的除數(shù)數(shù)組P if R(1) = 0 P = zeros(1,length(P); % 若R首位為0則將除數(shù)所有位置0 end R = bitxor(P,R); % 將除數(shù)與被除數(shù)進行異或操作 P = CRC_P; % 將寄存器恢復(fù)為除數(shù)數(shù)組 R(1) = ; %

33、去除模2運算后得到的被除數(shù)的第1位 end %第二部分add_len = length(crc_M) - length(R); % 生成余數(shù)序列的冗余位以疊加到編碼序列R = zeros(1,add_len),R; % 將所得余數(shù)序列添加冗余至與crc_M等長度crc_M =crc_M + R % 合成編碼序列L = length(crc_M); % 得到冗余編碼的長度 original_sequence = crc_M; % 初始化輸出序列 CRC_P = 1 0 0 1;% CRC生成多項式P(X)=X3+1R = crc_M; % 初始化余數(shù)數(shù)組 T = L-length(CRC_P)+1;% T為長除法的循環(huán)周期 for k = 1:T % 利用循環(huán)語句計算求余數(shù) add_zeros = zeros(1,T-k);% 設(shè)置冗余位參與模2運算 P = CRC_P add_zeros; % 構(gòu)造除數(shù)數(shù)組P if R(1) = 0 P = zeros(1,length(P); % 若R首位為0則將除數(shù)所有位置0 end R = bitxor(P,R);% 將除數(shù)與被除數(shù)進行異或操作 P= CRC_P; % 將寄存器恢復(fù)為除數(shù)數(shù)組 R(1) = ; % 去除模2運算后得到