课程设计报告用模2除法计算CRC码的CRC校验软件设计

1、用模2除法计算CRC码的CRC校验软件设计一、设计目标1）掌握用模二除法实现CRC码的计算方法； 2）掌握用C语言计算CRC码的算法； 3）熟练并掌握C语言在通信网络中的编程实现方式及功能；4) 学会用C语言实现文件之间的读取和写入，实现共享传送功能；5）熟悉VC6.0的运行环境，熟练掌握在其中运行编译的各个步骤。二、设计原理和方法1、CRC简介及原理：CRC码为循环冗余校验码，基本表示方式为(n,k)，其中n为数据位数，k为校验码位数。CRC码校验的基本思想是利用线性编码理论,在发送端根据要传送的(n,k)位二进制码序列,以一定的规则产生一个校验用的监督码（既CRC码）r位,并附在信息后边,

2、构成一个新的二进制码序列数共(k+r)位,最后发送出去。在接收端,则根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。采用CRC校验时，发送方和接收方用同一个生成多项式g（x）,并且g（x）的首位和最后一位的系数必须为1。CRC的处理方法是：发送方以g（x）去除t（x），得到余数作为CRC校验码。校验时，以计算的校正结果是否为0为据，判断数据帧是否出错。CRC校验可以100地检测出所有奇数个随机错误和长度小于等于k（k为g（x）的阶数）的突发错误。所以CRC的生成多项式的阶数越高，那么误判的概率就越小。CCITT建议：2048 kbit/s的PCM基群设备采用CRC-4方案，

3、使用的CRC校验采用16位CRC校验。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中，使用CRC-16。CRC的本质是模-2除法的余数，采用的除数不同，CRC的类型也就不一样。通常，CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式有CRC16,CRC32. 32位CRC码的产生的规则是先将要发送的二进制序列数左移32位后,再除以一个多项式（生成多项式G(x)）,最后得到的余数既是CRC码,如式（2-1）式所示，其中C(X)表示(n-k)位的二进制序列数，G(X)为多项式，Q(X)为商（整数），R(X)是余数（既CRC码）。（2-1） 求CRC码所采用模2加减运算法则,既

4、是不带进位和借位的按位加减,这种加减运算实际上就是逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。本课程设计中使用的生成多项式是由欧洲CRC32，即： g(x)= x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1接收方将接收到的二进制序列数（包括信息码和CRC码）除以多项式,如果余数为0,则说明传输中无错误发生,否则说明传输有误。用软件计算CRC码时,接收方可以根据接收到的信息码求CRC码,比较结果和接收到的CRC码是否相同。例如信息位是“11011011”、多项式g(x)=1001,用模二除法

5、生成CRC码的过程如下所示：在信息位“11011011”后面增加3个“0”，即“”用“”模二除g(x)=1001，r(x)=011;得到的余数“011”即为“11011011”的CRC校验码；将其加在原数据后面，即“”，通过发送端发送，在接收端收到数据再除以多项式g(x),若余数为0，则传输正确，去掉后三位即得到需要的数据“11011011”；若信道有干扰，使接收到的数据不是“11011011”，除以多项式g(x)后余数不为0，则传输失败，等待重传。2、模二除法实现CRC校验的基本原理用计算机编程实现CRC校验码，采用寄存器移位的方法。假设待测数据是1101 0110 11，生成项是10011

6、，假设有一个4 bits的寄存器，通过反复的移位和进行CRC的除法，最终该寄存器中的值就是我们所要求的余数。 3 2 1 0 Bits +-+-+-+-+ Pop <- | | | | | <- Augmented message（已加0扩张的原始数据） +-+-+-+-+ 1 0 0 1 1 = The Poly 生成项依据这个模型，我们得到了一个最最简单的算法：把register中的值置0.把原始的数据后添加w个0.While (还有剩余没有处理的数据)Begin把register中的值左移一位，读入一个新的数据并置于register最低位的位置。If (如果上一步的左移操作中

7、的移出的一位是1)register = register XOR Poly.End实际上就是模拟XOR除法的过程，即被测数据一位一位放到寄存器中来做除法。比如生成项是10011，则生成的余数是4位XXXX，所以寄存器是4位。待测数据是1101 0110 11，后面加上0000，即扩张4位，以容纳余数。只要与生成项的0011做XOR就好了，最高位经过XOR肯定出0，可不用最高位。过程如下：待测数据先移4位即1101到寄存器中，准备开始除法。第 1 次除法：寄存器中是1101，先从寄存器移出最高位1，移进下一位待测数据位0，则寄存器中是1010，由于移出的位是1，则需要与生成项的0011做XOR，

8、得到1001，即做了第1 次除法后，寄存器中是1001，这个就是余数。第2次除法：寄存器中是1001，从寄存器移出最高位1，移进下一位待测数据位1，则寄存器中是0011，由于移出的位是1，则需要与生成项的0011做XOR，得到0000，即做了第2次除法后，寄存器中是0000，这个就是余数。第3次除法：寄存器中是0000，从寄存器移出最高位0，移进下一位待测数据位1，则寄存器中是0001，由于移出的位是0，则需要不做XOR，直接下一步移位。也可以等同于：本次的商是0,0*生成项0，即是0000与寄存器做XOR，得到寄存器的数不变，还是0001，即做了第3次除法后，寄存器中是0001，这个就是余数

9、。第4次除法：寄存器中是0001，从寄存器移出最高位0，移进下一位待测数据位0，则寄存器中是0010，由于移出的位是0，则需要不做XOR，直接下一步移位。第5次除法：移位，不用做XOR，得到寄存器中是0101第6次除法：移位，不用做XOR，得到寄存器中是1011第7次除法：移位，移出的位是1，又要与生成项做XOR了一直做下去。直到最后，寄存器中的就是整个计算后的余数了。即CRC值。3、用模二除法实现CRC32的要解决的问题首先，要实现CRC32的计算，要解决CRC码的存放问题，而目前的微机高级语言，如Ansi C、Bland C、Mieromfl C，整数类型的数据最大为无符号的长整数仅4字节

10、32位，正好可存放CRC码。其次，要解决生成多项式的表示问题，CRC-32共有33位，大于无符号的长整数的数据范围，由于CRC32的最高位为i，由第2节CRC码的模2除法计算过程的分析可知，可以省去此位用一个无符号长整数常量表示之。第三，要解决被除数的表示，我们把被除数看成是一个无符号整数和一些字节组成，每次除时，参加运算的是这个无符号整数和这些字节的最左边一个位组成，当这个无符号整数的最高位为1时，需要作模2运算：移出这个最高位，从字节中补上一位，进行异或运算。 我选用的编译软件Visual C+6.0中的_int64能够容纳64位数据，因此以上问题可以很轻松的解决。超出32位范围的数据定义

11、为_int64的变量即可解决溢出的问题。三、设计的功能1、环境要求：Windows2000/XP/7；C；信息交换内容为文本文件；信息交换方式为共享文件2、编码要求：生成多项式为CRC-323、功能要求：能在两台计算机机上运行程序，一台产生CRC码，另一台校验。四、程序流程图发送端（电脑甲）-文件共享-接收端（电脑乙）开始开始读取code.txt到code输入数据存入code接收的数据模二除多项式g(x)得到余项result计算CRC余项result=0?将CRC余项接在code的后面赋给codeCRC存入crc.txtcode存入code.txt传输失败传输正确，显示信息码结束结束五、程序清

12、单1.发送端电脑甲源程序：#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码子函数_int64 regi = 0x0; / 使寄存器

13、为0_int64 data_temp;data_temp=data;int databitnumber=32; /定义数据位数data<<= crcbitnumber; /在数据位后添加32个0/ we do it bit after bitfor ( int cur_bit = databitnumber+crcbitnumber-1; cur_bit >= 0; - cur_bit ) /处理64 次（32 比特待测数据32 比特扩展0），前32次是加载数据 if ( ( ( regi >> crcbitnumber ) & 0x0001 ) = 0x

14、1 ) regi = regi POLY; regi <<= 1; unsigned short tmp = ( data >> cur_bit ) & 0x0001; /加载待测数据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("请输入数据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; /加载待测数据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的内容给字符串code*/printf("code:%I64xn",code); /*输出传输数据的植*/fclose(lp_code); /*关文件code.txt*/ result=exam(code,POLY,crcbitnumber);printf("result=%I64x",result);if (result=0)printf("数据传输正确n");code>>=32;printf("去除CRC校验码后数

21、据是%I64xn",code);else printf("数据传输失败");getchar();六、测试数据及其结果发送端：接收端：七、总结此次课程设计历时两周，在两周中我遇到了不少问题，程序也历经了多次的调整。CRC码又称循环冗余码，其编码是根据输入信息的多项式对生成多项式的余式作为校验码，来检测和纠正信息在传输过程中的错误，以达到减少误码和信息传输安全的目的。在做课程设计的过程中我经过了几次的调整。我通过查资料得到了CRC32的算法，开始以为很简单，只要把生成多项式g(x)变化一下就可以了，可是实际操作中显示不出来。通过我自己分析问题、查找资料，了解到int在visual c+中是4个字节，也就是32为，因此数据data加上32个0后超出范围，而_int64可以表示8个字节，即64位，可以满足要求。然而简单地将int改为_int64之后程序运行结果还是有问题。通过进一步分析以及向老师请教，得知使用_int64中的输入输出语句不能用“print