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

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

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

4、數(shù)據(jù)通信領(lǐng)域中最常用的一種差錯(cuò)校驗(yàn)碼，其特征是信息字段和校驗(yàn)字段的長(zhǎng)度可以任意選定。CRC碼是由兩部分組成，前部分是信息碼，就是需要檢驗(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ù)信息碼和CRC 碼之間所遵循的規(guī)則進(jìn)行檢驗(yàn)，以確定傳送中是否出錯(cuò)。循環(huán)冗余校驗(yàn)碼CRC是一種高效率且可靠的方法, 由線性分組碼分支而來(lái)的

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

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

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

8、的原理在發(fā)送端，先把數(shù)據(jù)劃分為組，假定每組k個(gè)比特。現(xiàn)假定待傳送的數(shù)據(jù)M=101001（k=6）。CRC運(yùn)算就是在數(shù)據(jù)M的后面添加供差錯(cuò)檢測(cè)用的n位冗余碼，然后構(gòu)成一個(gè)幀發(fā)送出去，一共發(fā)送（k+n）位。在所要發(fā)送的數(shù)據(jù)后面增加n位的冗余碼，雖然增大了數(shù)據(jù)傳輸?shù)拈_(kāi)銷，但卻可以進(jìn)行差錯(cuò)檢測(cè)。當(dāng)傳輸可能出現(xiàn)差錯(cuò)時(shí)，付出這種代價(jià)往往是很值得的。這n位冗余碼可用以下方達(dá)得出。用二進(jìn)制的模2運(yùn)算進(jìn)行2n乘M的運(yùn)算，這相當(dāng)于在M后面添加n個(gè)0。得到的（k+n）位的數(shù)除以收發(fā)雙方事先商定的長(zhǎng)度為(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除法運(yùn)算后的結(jié)果是:商Q=110101(這個(gè)商并沒(méi)有什么用處)，而余數(shù)R=001。這個(gè)余數(shù)R就作為冗余碼拼接在數(shù)據(jù)M的后面發(fā)送出去。這種為了進(jìn)行檢錯(cuò)而添加的冗余碼常稱為幀檢驗(yàn)序列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 說(shuō)明循環(huán)冗余檢驗(yàn)原理的例子在接收端把接受到的數(shù)據(jù)以幀

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

11、應(yīng)于X0）。多項(xiàng)式P(X)稱為生成多項(xiàng)式。現(xiàn)在廣泛使用的生成多項(xiàng)式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ā)送端幀檢驗(yàn)序列FCS的生成和接收端的CRC檢驗(yàn)都是用硬件完成的，處理很迅速，因此并不會(huì)延誤數(shù)據(jù)的傳輸。如果在傳送數(shù)據(jù)時(shí)不以幀為單位來(lái)傳送，那么就無(wú)法加入冗余碼以進(jìn)行差錯(cuò)檢驗(yàn)。因此，如果要在數(shù)據(jù)鏈路層進(jìn)行差錯(cuò)檢驗(yàn)，就必須把數(shù)據(jù)劃分為幀，每一幀都加上冗余碼，一幀接一幀地傳送，然后在接收方逐幀進(jìn)行差錯(cuò)檢驗(yàn)。

12、2、 方案的選擇及特點(diǎn)由于本次編程需要達(dá)到五點(diǎn)要求，因此進(jìn)行逐一分析。在MATLAB中，數(shù)組的表現(xiàn)方式很簡(jiǎn)單，故采用數(shù)組模擬網(wǎng)絡(luò)數(shù)據(jù)包結(jié)構(gòu)。要實(shí)現(xiàn)題目的五點(diǎn)要求，必須先理清循環(huán)冗余檢驗(yàn)CRC算法的具體計(jì)算過(guò)程，以此為基礎(chǔ)編寫程序，再在初始算法程序上繼續(xù)修改和添加來(lái)實(shí)現(xiàn)產(chǎn)生突變等的情況。關(guān)于CRC算法過(guò)程，在闡述原理時(shí)已有大致講到，一下是統(tǒng)一細(xì)致的分析。2.1 CRC編碼規(guī)則CRC碼是由兩部分組成，前部分是信息碼，就是需要校驗(yàn)的信息，后部分是校驗(yàn)碼，如果CRC碼共長(zhǎng)n個(gè)bit，信息碼長(zhǎng)k個(gè)bit，就稱為(n,k)碼。 它的編碼規(guī)則是：（1）移位將原信息碼(kbit)左移r位(k+r=n)（2）相

13、除運(yùn)用一個(gè)生成多項(xiàng)式g(x)（也可看成二進(jìn)制數(shù)）用模2除上面的式子，得到的余數(shù)就是校驗(yàn)碼。非常簡(jiǎn)單，要說(shuō)明的：模2除就是在除的過(guò)程中用模2加，模2加實(shí)際上就是我們熟悉的異或運(yùn)算，就是加法不考慮進(jìn)位，公式是：0+0=1+1=0,1+0=0+1=1即異則真，非異則假。由此得到定理：a+b+b=a 也就是模2減和模2加直值表完全相同。 有了加減法就可以用來(lái)定義模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)制除法將新的加長(zhǎng)的數(shù)據(jù)單元（k+n位）除以除數(shù)。由此

14、除法產(chǎn)生的余數(shù)就是循環(huán)冗余碼校驗(yàn)碼。第三步：用從第二步得到的n個(gè)比特的CRC碼替換數(shù)據(jù)單元末尾附加的n個(gè)0。如果余數(shù)位數(shù)小于n，最左的缺省位數(shù)為0。如果除法過(guò)程根本未產(chǎn)生余數(shù)（也就是說(shuō)，原始的數(shù)據(jù)單元本身就可以被除數(shù)整除）那么以n個(gè)0作為CRC碼替換余數(shù)所在的位置。產(chǎn)生的比特模式正好能被除數(shù)整除。2.3 CRC校驗(yàn)過(guò)程展示假設(shè)數(shù)據(jù)傳輸過(guò)程中需要發(fā)送15位的二進(jìn)制信息g=101001110100001，這串二進(jìn)制碼可表示為代數(shù)多項(xiàng)式g(x)=x14+x12+x9+x8+x7+x5+1，其中g(shù)中第k位的值，對(duì)應(yīng)g(x)中xk的系數(shù)。將g(x)乘以xm，既將g后加m個(gè)0，然后除以m階多項(xiàng)式h(x)，

15、得到的(m-1)階余項(xiàng)r(x)對(duì)應(yīng)的二進(jìn)制碼r就是CRC編碼。h(x)可以自由選擇或者使用國(guó)際通行標(biāo)準(zhǔn)，一般按照h(x)的階數(shù)m，將CRC算法稱為CRC-m，比如CRC-32、CRC-64等。g(x)和h(x)的除運(yùn)算，可以通過(guò)g和h做xor（異或）運(yùn)算。比如將11001與10101做xor運(yùn)算如圖2-2：圖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) = x8 + x7 + x6 + x4 + x2 + 1，既h是9位的二進(jìn)制串111010101。

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

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

18、示。開(kāi)始構(gòu)建數(shù)組M、取其長(zhǎng)度L、構(gòu)建生成多項(xiàng)式添加冗余位、k=0初始化余數(shù)數(shù)組Rk=k+1構(gòu)造與R等長(zhǎng)度的除數(shù)數(shù)組PY判斷R的首位是否為0被除數(shù)所有位置0NR = P xor R恢復(fù)除數(shù)數(shù)組去除被除數(shù)第一位Nk>L?Y結(jié)束圖3-1 第一部分程序流程圖2、 第二部分該部分將得到的校驗(yàn)位附加到網(wǎng)絡(luò)數(shù)據(jù)包相應(yīng)的位置，并將添加了幀檢驗(yàn)序列FCS的數(shù)據(jù)繼續(xù)以模2除法進(jìn)行CRC檢驗(yàn)。程序流程圖如圖3-2所示。NY顯示碼元傳輸發(fā)生錯(cuò)誤結(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等長(zhǎng)度的除數(shù)數(shù)組Pk=k+1取冗余編碼長(zhǎng)度L、初始化余數(shù)數(shù)組R、令k=0將生成余數(shù)序列的冗余位疊加到編碼序列開(kāi)始圖3-2 第二部分程序流程圖3、 第三部分該部分實(shí)現(xiàn)了根據(jù)數(shù)據(jù)包的長(zhǎng)度，隨機(jī)生成一個(gè)數(shù)據(jù)包產(chǎn)生突變的位置，并對(duì)該位置的bit位模擬突變產(chǎn)生的過(guò)程。按照要求，先利用i=ceil(rand(1,1)*r)函數(shù)來(lái)隨機(jī)抽取數(shù)組中的一個(gè)位，其中r為該數(shù)組的長(zhǎng)度。再將該位的值進(jìn)行取反再放回，生成一個(gè)某位發(fā)生突變的新數(shù)組。重新利用CRC算法校驗(yàn)該數(shù)據(jù)包，并指出產(chǎn)生的結(jié)果。由于檢驗(yàn)方法與第二部分一致，因此程序流程圖與第二部分的流程圖（圖3-2）基本一致，此處不再繪制。4、第四部分該部分構(gòu)造

20、出了一個(gè)無(wú)法被CRC檢錯(cuò)的實(shí)例，來(lái)驗(yàn)證CRC是否能夠檢出所有的錯(cuò)誤。通過(guò)查閱資料，我了解到了CRC校驗(yàn)的檢錯(cuò)性能。CRC校驗(yàn)碼的檢錯(cuò)能力與其生成多項(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） 可檢出所有長(zhǎng)度<=r個(gè)bit的突發(fā)錯(cuò)誤；（4） 對(duì)于長(zhǎng)度=（r+1)個(gè)bit的突發(fā)錯(cuò)，其漏檢率僅為：1/2(r-1）;（5） 對(duì)于長(zhǎng)度>（r+1)個(gè)bit的突發(fā)錯(cuò)，其漏檢率僅為：1/2r。事實(shí)證明CRC雖具有良好的檢錯(cuò)能力，但不能夠檢出所有的錯(cuò)誤

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

22、利用第二部分的檢驗(yàn)方式，觀察最終輸出結(jié)果與預(yù)測(cè)是否一致，最后加上一個(gè)判斷語(yǔ)句顯示最終結(jié)果。由于檢驗(yàn)方式與第二部分一致，故對(duì)于檢驗(yàn)的流程圖不再繪制，對(duì)于判斷結(jié)果的程序流程圖如圖3-3所示。結(jié)束實(shí)際傳輸數(shù)據(jù)錯(cuò)誤實(shí)際傳輸數(shù)據(jù)正確NYerror_sequence = M？已知錯(cuò)誤序列error_sequence編寫原序列M開(kāi)始圖3-3 第四部分判斷結(jié)果的程序流程圖4、 結(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_P表示生成多項(xiàng)式；

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

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

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

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

27、流可以看作是關(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ò)誤，只有沒(méi)有余數(shù)的校驗(yàn)才是正確的。二進(jìn)制多項(xiàng)式的加減運(yùn)算為模2加減運(yùn)算，即兩個(gè)碼多項(xiàng)式相加時(shí)，對(duì)應(yīng)系數(shù)進(jìn)行模2加減。所謂模2加減就是各位做不帶進(jìn)位、借位的按位加減。這種加減運(yùn)算實(shí)際上是邏輯上的異或運(yùn)算，即加法和減法等價(jià)。信息多項(xiàng)式和余數(shù)多項(xiàng)式可以合并成一個(gè)新的多項(xiàng)式（稱

28、為循環(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)式，若能除盡，說(shuō)明傳輸正確，否則說(shuō)明出錯(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ā)送端相同）。如果余數(shù)是0，則說(shuō)明傳輸正確；否則傳輸錯(cuò)誤。CRC校驗(yàn)的檢錯(cuò)能力極強(qiáng)，但并不能檢出所有的錯(cuò)誤。當(dāng)冗余數(shù)組發(fā)生突變，生成一個(gè)與原數(shù)組存在“同

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

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

31、困難和錯(cuò)誤，最后通過(guò)不斷查閱資料和向同學(xué)請(qǐng)教一一解決。當(dāng)最終完成本次課程設(shè)計(jì)時(shí)，我深刻體會(huì)到成功的喜悅和快樂(lè)。參考文獻(xiàn)1.謝希仁等. 計(jì)算機(jī)網(wǎng)絡(luò)（第六版） M. 北京:電子工業(yè)出版社,2013.6；2.王虹等. 通信系統(tǒng)原理 M. 北京：國(guó)防工業(yè)出版社，2014.8;3.孫麗華. 信息論與糾錯(cuò)編碼 M. 電子工業(yè)出版社，2005.3.附件一：程序源代碼%第一部分M=1,0,1,1,1,0 % M為待傳送數(shù)據(jù)L= length(M); % L為數(shù)據(jù)M的長(zhǎng)度CRC_P = 1 0 0 1;% CRC生成多項(xiàng)式P(X)=X3+1n = zeros(1,3); % 添加3位冗余碼crc_M = M z

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

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