課程設(shè)計報告用模2除法計算CRC碼的CRC校驗軟件設(shè)計

1、用模2除法計算CRC碼的CRC校驗軟件設(shè)計一、設(shè)計目標(biāo)1）掌握用模二除法實現(xiàn)CRC碼的計算方法； 2）掌握用C語言計算CRC碼的算法； 3）熟練并掌握C語言在通信網(wǎng)絡(luò)中的編程實現(xiàn)方式及功能；4) 學(xué)會用C語言實現(xiàn)文件之間的讀取和寫入，實現(xiàn)共享傳送功能；5）熟悉VC6.0的運行環(huán)境，熟練掌握在其中運行編譯的各個步驟。二、設(shè)計原理和方法1、CRC簡介及原理：CRC碼為循環(huán)冗余校驗碼，基本表示方式為(n,k)，其中n為數(shù)據(jù)位數(shù)，k為校驗碼位數(shù)。CRC碼校驗的基本思想是利用線性編碼理論,在發(fā)送端根據(jù)要傳送的(n,k)位二進制碼序列,以一定的規(guī)則產(chǎn)生一個校驗用的監(jiān)督碼（既CRC碼）r位,并附在信息后邊,

2、構(gòu)成一個新的二進制碼序列數(shù)共(k+r)位,最后發(fā)送出去。在接收端,則根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進行檢驗,以確定傳送中是否出錯。采用CRC校驗時，發(fā)送方和接收方用同一個生成多項式g（x）,并且g（x）的首位和最后一位的系數(shù)必須為1。CRC的處理方法是：發(fā)送方以g（x）去除t（x），得到余數(shù)作為CRC校驗碼。校驗時，以計算的校正結(jié)果是否為0為據(jù)，判斷數(shù)據(jù)幀是否出錯。CRC校驗可以100地檢測出所有奇數(shù)個隨機錯誤和長度小于等于k（k為g（x）的階數(shù)）的突發(fā)錯誤。所以CRC的生成多項式的階數(shù)越高，那么誤判的概率就越小。CCITT建議：2048 kbit/s的PCM基群設(shè)備采用CRC-4方案，

3、使用的CRC校驗采用16位CRC校驗。在IBM的同步數(shù)據(jù)鏈路控制規(guī)程SDLC的幀校驗序列FCS中，使用CRC-16。CRC的本質(zhì)是模-2除法的余數(shù)，采用的除數(shù)不同，CRC的類型也就不一樣。通常，CRC的除數(shù)用生成多項式來表示。最常用的CRC碼的生成多項式有CRC16,CRC32. 32位CRC碼的產(chǎn)生的規(guī)則是先將要發(fā)送的二進制序列數(shù)左移32位后,再除以一個多項式（生成多項式G(x)）,最后得到的余數(shù)既是CRC碼,如式（2-1）式所示，其中C(X)表示(n-k)位的二進制序列數(shù)，G(X)為多項式，Q(X)為商（整數(shù)），R(X)是余數(shù)（既CRC碼）。（2-1） 求CRC碼所采用模2加減運算法則,既

4、是不帶進位和借位的按位加減,這種加減運算實際上就是邏輯上的異或運算，加法和減法等價，乘法和除法運算與普通代數(shù)式的乘除法運算是一樣，符合同樣的規(guī)律。本課程設(shè)計中使用的生成多項式是由歐洲CRC32，即： g(x)= x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1接收方將接收到的二進制序列數(shù)（包括信息碼和CRC碼）除以多項式,如果余數(shù)為0,則說明傳輸中無錯誤發(fā)生,否則說明傳輸有誤。用軟件計算CRC碼時,接收方可以根據(jù)接收到的信息碼求CRC碼,比較結(jié)果和接收到的CRC碼是否相同。例如信息位是“11011011”、多項式g(x)=1001,用模二除法

5、生成CRC碼的過程如下所示：在信息位“11011011”后面增加3個“0”，即“”用“”模二除g(x)=1001，r(x)=011;得到的余數(shù)“011”即為“11011011”的CRC校驗碼；將其加在原數(shù)據(jù)后面，即“”，通過發(fā)送端發(fā)送，在接收端收到數(shù)據(jù)再除以多項式g(x),若余數(shù)為0，則傳輸正確，去掉后三位即得到需要的數(shù)據(jù)“11011011”；若信道有干擾，使接收到的數(shù)據(jù)不是“11011011”，除以多項式g(x)后余數(shù)不為0，則傳輸失敗，等待重傳。2、模二除法實現(xiàn)CRC校驗的基本原理用計算機編程實現(xiàn)CRC校驗碼，采用寄存器移位的方法。假設(shè)待測數(shù)據(jù)是1101 0110 11，生成項是10011

6、，假設(shè)有一個4 bits的寄存器，通過反復(fù)的移位和進行CRC的除法，最終該寄存器中的值就是我們所要求的余數(shù)。 3 2 1 0 Bits +-+-+-+-+ Pop <- | | | | | <- Augmented message（已加0擴張的原始數(shù)據(jù)） +-+-+-+-+ 1 0 0 1 1 = The Poly 生成項依據(jù)這個模型，我們得到了一個最最簡單的算法：把register中的值置0.把原始的數(shù)據(jù)后添加w個0.While (還有剩余沒有處理的數(shù)據(jù))Begin把register中的值左移一位，讀入一個新的數(shù)據(jù)并置于register最低位的位置。If (如果上一步的左移操作中

7、的移出的一位是1)register = register XOR Poly.End實際上就是模擬XOR除法的過程，即被測數(shù)據(jù)一位一位放到寄存器中來做除法。比如生成項是10011，則生成的余數(shù)是4位XXXX，所以寄存器是4位。待測數(shù)據(jù)是1101 0110 11，后面加上0000，即擴張4位，以容納余數(shù)。只要與生成項的0011做XOR就好了，最高位經(jīng)過XOR肯定出0，可不用最高位。過程如下：待測數(shù)據(jù)先移4位即1101到寄存器中，準(zhǔn)備開始除法。第 1 次除法：寄存器中是1101，先從寄存器移出最高位1，移進下一位待測數(shù)據(jù)位0，則寄存器中是1010，由于移出的位是1，則需要與生成項的0011做XOR，

8、得到1001，即做了第1 次除法后，寄存器中是1001，這個就是余數(shù)。第2次除法：寄存器中是1001，從寄存器移出最高位1，移進下一位待測數(shù)據(jù)位1，則寄存器中是0011，由于移出的位是1，則需要與生成項的0011做XOR，得到0000，即做了第2次除法后，寄存器中是0000，這個就是余數(shù)。第3次除法：寄存器中是0000，從寄存器移出最高位0，移進下一位待測數(shù)據(jù)位1，則寄存器中是0001，由于移出的位是0，則需要不做XOR，直接下一步移位。也可以等同于：本次的商是0,0*生成項0，即是0000與寄存器做XOR，得到寄存器的數(shù)不變，還是0001，即做了第3次除法后，寄存器中是0001，這個就是余數(shù)

9、。第4次除法：寄存器中是0001，從寄存器移出最高位0，移進下一位待測數(shù)據(jù)位0，則寄存器中是0010，由于移出的位是0，則需要不做XOR，直接下一步移位。第5次除法：移位，不用做XOR，得到寄存器中是0101第6次除法：移位，不用做XOR，得到寄存器中是1011第7次除法：移位，移出的位是1，又要與生成項做XOR了一直做下去。直到最后，寄存器中的就是整個計算后的余數(shù)了。即CRC值。3、用模二除法實現(xiàn)CRC32的要解決的問題首先，要實現(xiàn)CRC32的計算，要解決CRC碼的存放問題，而目前的微機高級語言，如Ansi C、Bland C、Mieromfl C，整數(shù)類型的數(shù)據(jù)最大為無符號的長整數(shù)僅4字節(jié)

10、32位，正好可存放CRC碼。其次，要解決生成多項式的表示問題，CRC-32共有33位，大于無符號的長整數(shù)的數(shù)據(jù)范圍，由于CRC32的最高位為i，由第2節(jié)CRC碼的模2除法計算過程的分析可知，可以省去此位用一個無符號長整數(shù)常量表示之。第三，要解決被除數(shù)的表示，我們把被除數(shù)看成是一個無符號整數(shù)和一些字節(jié)組成，每次除時，參加運算的是這個無符號整數(shù)和這些字節(jié)的最左邊一個位組成，當(dāng)這個無符號整數(shù)的最高位為1時，需要作模2運算：移出這個最高位，從字節(jié)中補上一位，進行異或運算。 我選用的編譯軟件Visual C+6.0中的_int64能夠容納64位數(shù)據(jù)，因此以上問題可以很輕松的解決。超出32位范圍的數(shù)據(jù)定義

11、為_int64的變量即可解決溢出的問題。三、設(shè)計的功能1、環(huán)境要求：Windows2000/XP/7；C；信息交換內(nèi)容為文本文件；信息交換方式為共享文件2、編碼要求：生成多項式為CRC-323、功能要求：能在兩臺計算機機上運行程序，一臺產(chǎn)生CRC碼，另一臺校驗。四、程序流程圖發(fā)送端（電腦甲）-文件共享-接收端（電腦乙）開始開始讀取code.txt到code輸入數(shù)據(jù)存入code接收的數(shù)據(jù)模二除多項式g(x)得到余項result計算CRC余項result=0?將CRC余項接在code的后面賦給codeCRC存入crc.txtcode存入code.txt傳輸失敗傳輸正確，顯示信息碼結(jié)束結(jié)束五、程序清

12、單1.發(fā)送端電腦甲源程序：#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#include <conio.h>#include <windows.h>#include <iostream.h>_int64 crc; /定義全局變量crc_int64 create(_int64 data,_int64 POLY,int crcbitnumber) /生成crc碼子函數(shù)_int64 regi = 0x0; / 使寄存器

13、為0_int64 data_temp;data_temp=data;int databitnumber=32; /定義數(shù)據(jù)位數(shù)data<<= crcbitnumber; /在數(shù)據(jù)位后添加32個0/ we do it bit after bitfor ( int cur_bit = databitnumber+crcbitnumber-1; cur_bit >= 0; - cur_bit ) /處理64 次（32 比特待測數(shù)據(jù)32 比特擴展0），前32次是加載數(shù)據(jù) if ( ( ( regi >> crcbitnumber ) & 0x0001 ) = 0x

14、1 ) regi = regi POLY; regi <<= 1; unsigned short tmp = ( data >> cur_bit ) & 0x0001; /加載待測數(shù)據(jù)1比特到tmp中，tmp只有1比特 regi |= tmp; /這1比特加載到寄存器中if ( ( ( regi >> crcbitnumber ) & 0x0001 ) = 0x1 ) regi = regi POLY; /做最后一次XORprintf("crc=%xn",regi);crc=regi;data_temp<<=3

15、2;data_temp=data_temp+regi;return data_temp;void main()FILE*lp_code,*lp_crc;_int64 code;_int64 data;_int64 POLY=0x104C11DB7;int crcbitnumber=32;printf("*CRC experiments*n");printf("請輸入數(shù)據(jù)n");scanf("%I64x",&data);code=create(data,POLY,crcbitnumber);printf("code=%

16、I64xn",code);lp_code=fopen("D:FScode.txt","w"); /建立文件lp_crc = fopen("D:FScrc.txt","w"); fprintf(lp_code,"%I64x",code); fprintf(lp_crc,"%I64x",crc); getchar(); fclose(lp_code);fclose(lp_crc);system("pause");2.接收端電腦乙源程序：#includ

17、e <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#include <conio.h>#include <windows.h>#include <iostream.h>_int64 exam(_int64 data,_int64 POLY,int crcbitnumber)_int64 regi = 0x0; / load the register with zero bits_int64 data_temp;data_temp=

18、data;int databitnumber=32; for ( int cur_bit = databitnumber+crcbitnumber-1; cur_bit >= 0; - cur_bit ) if ( ( ( regi >> crcbitnumber ) & 0x0001 ) = 0x1 ) regi = regi POLY; regi <<= 1; unsigned short tmp = ( data >> cur_bit ) & 0x0001; /加載待測數(shù)據(jù)1比特到tmp中，tmp只有1比特 regi |= tmp

19、; /這1比特加載到寄存器中if ( ( ( regi >> crcbitnumber ) & 0x0001 ) = 0x1 ) regi = regi POLY; /做最后一次XORreturn(regi);void main()FILE* lp_code;_int64 code;_int64 result;_int64 POLY=0x104C11DB7;int crcbitnumber=32;printf("*CRC exam*n");lp_code=fopen("D:FScode.txt","r");fsca

20、nf(lp_code,"%I64x",code); /*輸出code.txt的內(nèi)容給字符串code*/printf("code:%I64xn",code); /*輸出傳輸數(shù)據(jù)的植*/fclose(lp_code); /*關(guān)文件code.txt*/ result=exam(code,POLY,crcbitnumber);printf("result=%I64x",result);if (result=0)printf("數(shù)據(jù)傳輸正確n");code>>=32;printf("去除CRC校驗碼后數(shù)

21、據(jù)是%I64xn",code);else printf("數(shù)據(jù)傳輸失敗");getchar();六、測試數(shù)據(jù)及其結(jié)果發(fā)送端：接收端：七、總結(jié)此次課程設(shè)計歷時兩周，在兩周中我遇到了不少問題，程序也歷經(jīng)了多次的調(diào)整。CRC碼又稱循環(huán)冗余碼，其編碼是根據(jù)輸入信息的多項式對生成多項式的余式作為校驗碼，來檢測和糾正信息在傳輸過程中的錯誤，以達到減少誤碼和信息傳輸安全的目的。在做課程設(shè)計的過程中我經(jīng)過了幾次的調(diào)整。我通過查資料得到了CRC32的算法，開始以為很簡單，只要把生成多項式g(x)變化一下就可以了，可是實際操作中顯示不出來。通過我自己分析問題、查找資料，了解到int在visual c+中是4個字節(jié)，也就是32為，因此數(shù)據(jù)data加上32個0后超出范圍，而_int64可以表示8個字節(jié)，即64位，可以滿足要求。然而簡單地將int改為_int64之后程序運行結(jié)果還是有問題。通過進一步分析以及向老師請教，得知使用_int64中的輸入輸出語句不能用“print