课程设计报告--用模2除法计算CRC码的CRC校验软件设计
通信网络设计课程设计 题号:C2 设计日期
用模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位,并附在信息后边,构成一个新的二进制码序列数共(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
,使用的CRC校验采用16位CRC校验。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中,使用CRC-16。CRC的本质是模-2除法的余数,采用的除数不同,CRC的类型也就不一样。通常,CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式有CRC16,CRC32.
32位CRC码的产生的规则是先将要发送的二进制序列数左移32位后,再除以一
,如式(2-1)式所示,个多项式(生成多项式G(x)),最后得到的余数既是CRC码
其中C(X)表示(n-k)位的二进制序列数,G(X)为多项式,Q(X)为商(整数),R(X)是余数(既CRC码)。(2-1)
求CRC码所采用模2加减运算法则,既是不带进位和借位的按位加减,这种加减运算实际上就是逻辑上的异或运算,加法和减法等价,乘法和除法运算与普通代数式的乘除法运算是一样,符
样的规律。
本课程设计中使用的生成多项式是由欧洲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,用模二除法生成CRC码的过程如下所示:
第 1 页 共 11 页
通信网络设计课程设计 题号:C2 设计日期
?在信息位“11011011”后面增加3个“0”,即“11011011000”
?用“11011011000”模二除g(x)=1001,r(x)=011;
?得到的余数“011”即为“11011011”的CRC校验码;将其加在原数据后面,即“11011011011”,通过发送端发送,在接收端收到数据再除以多项式g(x),若余数为0,则传输正确,去掉后三位即得到需要的数据“11011011”;若信道有干扰,使接收到的数据不是“11011011”,除以多项式g(x)后余数不为0,则传输失败,等待重传。
2、模二除法实现CRC校验的基本原理
用计算机编程实现CRC校验码,采用寄存器移位的方法。
假设待测数据是1101 0110 11,生成项是10011,假设有一个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 (如果上一步的左移操作中的移出的一位是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,得到1001,即做了第1 次除法后,寄存器中是
1001,这个就是余数。
第 2 页 共 11 页
通信网络设计课程设计 题号:C2 设计日期
第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,这个就
是余数。
第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字节32位,正好可存放CRC码。
其次,要解决生成多项式的表示问题,CRC-32共有33位,大于无符号的长整数的数据范围,由于CRC(32的最高位为i, 由第2节CRC码的模2除法计算过程的分析可知,可以省去此位(用一个无符号长整数常量表示之。
第三,要解决被除数的表示,我们把被除数看成是一个无符号整数和一些字节组成,每次除时,参加运算的是这个无符号整数和这些字节的最左边一个位组成, 当这个无符号整数的最高位为1时,需要作模2运算:移出这个最高位,从字节中补上一位,进行异或运算。
我选用的编译软件Visual C++6.0中的_int64能够容纳64位数据,因此以上问题可以很轻松的解决。超出32位范围的数据定义为_int64的变量即可解决溢出的问题。
三、设计的功能
1、环境要求:Windows2000/XP/7;C;信息交换内容为文本文件;信息交换方式为共享文件
2、编码要求:生成多项式为CRC-32
3、功能要求:能在两台计算机机上运行程序,一台产生CRC码,另一台校验。
第 3 页 共 11 页
通信网络设计课程设计 题号:C2 设计日期
四、程序
图
接收端(电脑乙) 发送端(电脑甲) ---------文件共享----------
开始 开始
读取code.txt到code 输入数据存入code
接收的数据模二除多项式计算CRC余项 g(x)得到余项result
将CRC余项接在 code的后面赋给code result=0?
CRC存入crc.txt
传输正确,显示传输失败 code存入code.txt
信息码
结束
结束
五、程序清单
1.发送端电脑甲源程序:
#include
#include #include #include #include #include #include
_int64 crc; //定义全局变量crc
第 4 页 共 11 页
通信网络设计课程设计 题号:C2 设计日期
_int64 create(_int64 data,_int64 POLY,int crcbitnumber) //生成crc码子函数
{
_int64 regi = 0x0; // 使寄存器为0
_int64 data_temp;
data_temp=data;
int databitnumber=32; //定义数据位数
data<<= crcbitnumber; //在数据位后添加32个0
// we do it bit after bit
for ( int cur_bit = databitnumber+crcbitnumber-1; cur_bit >= 0; -- cur_bit )
//处理64 次(32 比特待测数据,32 比特扩展0),前32次是加载数据 {
if ( ( ( regi >> crcbitnumber ) & 0x0001 ) == 0x1 ) 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; //做最后一次XOR
printf("crc=%x\n",regi);
crc=regi;
data_temp<<=32;
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=%I64x\n",code);
第 5 页 共 11 页
通信网络设计课程设计 题号:C2 设计日期
lp_code=fopen("D:\\FS\\code.txt","w"); //建立文件
lp_crc = fopen("D:\\FS\\crc.txt","w");
fprintf(lp_code,"%I64x",code);
fprintf(lp_crc,"%I64x",crc); getchar();
fclose(lp_code);
fclose(lp_crc);
system("pause");
}
2.接收端电脑乙源程序:
#include
#include
#include
#include
#include
#include
#include
_int64 exam(_int64 data,_int64 POLY,int crcbitnumber)
{
_int64 regi = 0x0; // load the register with zero bits
_int64 data_temp;
data_temp=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; //这1比特加载到寄存器中
}
if ( ( ( regi >> crcbitnumber ) & 0x0001 ) == 0x1 )
regi = regi ^ POLY; //做最后一次XOR
return(regi);
}
第 6 页 共 11 页
通信网络设计课程设计 题号:C2 设计日期
void main()
{FILE* lp_code;
_int64 code;
_int64 result;
_int64 POLY=0x104C11DB7;
int crcbitnumber=32;
printf("**************CRC exam****************\n");
lp_code=fopen("D:\\FS\\code.txt","r"); fscanf(lp_code,"%I64x",code); /*输出code.txt的内容给字符串code*/
printf("code:%I64x\n",code); /*输出传输数据的植*/ fclose(lp_code); /*关文件code.txt*/ result=exam(code,POLY,crcbitnumber); printf("result=%I64x",result); if (result==0)
{printf("数据传输正确\n");
code>>=32;
printf("去除CRC校验码后数据是%I64x\n",code); }
else printf("数据传输失败");
getchar();
}
第 7 页 共 11 页
通信网络设计课程设计 题号:C2 设计日期
六、测试数据及其结果
发送端:
第 8 页 共 11 页
通信网络设计课程设计 题号:C2 设计日期
接收端:
第 9 页 共 11 页
通信网络设计课程设计 题号:C2 设计日期
七、
此次课程设计历时两周,在两周中我遇到了不少问题,程序也历经了多次的调整。
CRC码又称循环冗余码,其编码是根据输入信息的多项式对生成多项式的余式作为校验码,来检测和纠正信息在传输过程中的错误,以达到减少误码和信息传输安全的目的。
在做课程设计的过程中我经过了几次的调整。我通过查资料得到了CRC32的算法,开始以为很简单,只要把生成多项式g(x)变化一下就可以了,可是实际操作中显示不出来。通过我自己分析问题、查找资料,了解到int在visual c++中是4个字节,也就是32为,因此数据data加上32个0后超出范围,而_int64可以表示8个字节,即64位,可以满足要求。然而简单地将int改为_int64之后程序运行结果还是有问题。通过进一步分析以及向老师请教,得知使用_int64中的输入输出语句不能用“printf(“data=%x\n”,data)”而要改成用%I64x这种形式表示的,即表示为“printf(“data=%I64x\n”,data)”。再经过部分修改,程序终于能够成功运行起来~
但在接收端运行的时候,只能出现一个窗口,并不能显示输出的结果正确与否,经过一番仔细的检查,最后在接收端程序末尾加入了一个getchar()语句,就可以运行了,而且显示结果是正确的。
至于文件共享就相当简单了,在甲机器中建立一个文件夹,设为共享,则在网络内的所有计算机都能访问这个文件夹。然后用C语言中的文件操作函数就能轻松解决文件的写入和读取。但是这次实际操作过程中并没有实现共享,只是在一台电脑上分为了发送端和接收端。这样其实也能检测出最后的结果正确与否。
总的说来,这次课程设计有一定的难度。CRC本身在教学上涉及的并不多,可是却很有用,现在很多文件的传输和压缩技术都用到了CRC。通过相关书籍和网上的资料,很快就能了解CRC的原理,可是具体的实现又是另外一回事。这几天基本上每天都有在调程序,每天都会有新的进展,发现的问题也很多。
现在我对C语言又有了一个重新掌握与重新学习的过程,相信加上我的不断使用与不断加强,我对C语言将更加熟悉。C语言在高级语言中属于比较低层的,在算法的实现上需要注意更多的细节。
感谢在这次课程设计中老师以及老师对我的帮助,感谢老师在我设计过程中所提出的建设性建议,让我受益非浅,最终顺利地完成了设计任务。
第 10 页 共 11 页
通信网络设计课程设计 题号:C2 设计日期
八、参考文献
谭浩强编著,C程序设计(第三版),清华大学出版社,2005年 施荣华、王国才编著,计算机网络技术与应用,中国铁道出版社,2009年 高传善等编著,计算机网络教程, 复旦大学出版社, 1994年 互连网上相关资料等
第 11 页 共 11 页