0904C10课程设计报告

通信网络设计课程设计题号：C10设计日期20120904----20120916第1页共10页用查表法计算CRC码的C程序设计，生成多项式为CRC-CCITT指导老师：王国才(旺才)一、设计目标1）了解CRC循环冗余校验码的功能及计算原理；2）掌握用查表法计算CRC校验码的原理及过程；3)能用C语言编程实现查表法计算CRC校验码的过程3）了解C语言在通信网络中的编程实现方式及功能；二、设计原理和方法1.什么是CRC？CRC即循环冗余校验码（CyclicRedundancyCheck）：是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。利用CRC进行检错的过程可简单描述为：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位监督码(CRC码)，附在原始信息后边，构成一个新的二进制码序列数共k+r位，然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”。2.CRC的计算过程（直接计算法）计算CRC的过程，就是用一个特殊的“除法”，来得到余数，这个余数就是CRC。它不是真正的算术上的除法,过程和算术除法过程一样，只是加减运算变成了XOR（异或）运算.举例说明:被除数1111000,除数1001,以二进制模拟这个计算过程：1110________1001/11110001001^----1100第一次XOR后得到011，加入下一位0。最高位的0可以消掉了，这样最高位是1,所以下个商是11001^----1010第二次XOR后得到0101，加入下一位0。最高位的0可以消掉了，这样最高位是1,所以下个商是11001^----0110第三次XOR后得到0011，加入下一位0。最高位的0可以消掉了，这样最高位是0,所以下个商是00000^----110-最后一次XOR后得到0110，最高位的0可以消掉了，得到余数为110可见，除法（XOR）的目的是逐步消掉最高位的1或0.生成项(就是除数)的最高位实际上在除法的每次XOR时都要消掉，所以最高位可不做参考，余下位才是最重要的.所以编程实现时寄存器的位数比生成项位数少一位.通信网络设计课程设计题号：C10设计日期20120904----20120916第2页共10页“直接计算法”就是直接模拟上面的除法的过程，来得到余数即CRC,过程如下:我们假设待测数据是1101011011，生成项是10011，假设有一个4bits的寄存器，通过反复的移位和进行CRC的除法，最终该寄存器中的值就是我们所要求的余数。依据这个模型，我们得到了一个最最简单的算法：把register中的值置0.把原始的数据后添加w个0.While(还有剩余没有处理的数据)Begin把register中的值左移一位，读入一个新的数据并置于register最低位的位置。If(如果上一步的左移操作中的移出的一位是1)register=registerXORPoly.End3.更高效的CRC计算方法—查表法上面的“直接计算法”很直观，却非常的低效。为了加快它的速度，我们使它一次能处理大于4bit的数据。一次能处理一个字节的数据的话，那就方便多了。我们想要实现的16bit的CRC校验。我们还是假设有和原来一样的一个4bit的register，但它的每一位是一个8bit的字节。根据同样的原理我们可以得到如下的算法：While(还有剩余没有处理的数据)Begin检查register头字节，并取得它的值求不同偏移处多项式的XORregister左移一个字节，最右处存入新读入的一个字节把register的值和多项式的XOR结果进行XOR运算End可是为什么要这样作呢？同样我们还是以一个简单的例子说明问题：为了简单起见，我们假设一次只移出4个比特！而不是8个比特。生成多项式为：101011100，即宽度W=8，即CRC8，这样寄存器为8位待测数据是101101001101按正常的算法做：通信网络设计课程设计题号：C10设计日期20120904----20120916第3页共10页将10110100放入寄存器中，然后开始计算CRC。先将高4位移出寄存器：当前register中的值：010011014bit应该被移出的值：1011生成多项式为：101011100第一步：TopRegister（top指移出的数据）------------101101001101待测数101011100+(CRCXOR)POLY-------------000110101101第一次XOR后的值第二步：这时，首4bits不为0说明没有除尽，要继续除:000110101101101011100+(CRCXOR)将POLY右移3位后，再做XOR-------------000011110001第二次XOR后的值^^^^这时，首4bits全0说明不用继续除了，结果满足要求了。也就是说：待测数据与POLY相XOR，得到的结果再与POLY相XOR，POLY要适当移位，以消掉1。重复进行，直到结果满足要求。下面，我们换一种算法，来达到相同的目的：POLY与POLY自已先进行XOR，当然POLY要进行适当移位。使得得到的结果值的高4位与待测数据相同。第一步：101011100POLY101011100+右移3位后的POLY-------------101110111100POLY与POLY自已进行XOR后得到的值第二步：101110111100POLY相XOR后得到的值101101001101+待测数据-------------000011110001得到的结果值和上面是一样的（说明可以先把POLY预先XOR好，再与待测数据XOR，就能得到结果）结论：现在我们看到，这二种算法计算的结果是一致的,这是基于异或的交换律，即(aXORb)XORc=aXOR(bXORc)。而后一种算法可以通过查表来快速完成，叫做“驱动表法”算法。也就是说，根据4bit被移出的值1011，我们就可以知道要用POLY自身XOR后得到的101110111100来对待测数据101101001101进行XOR，这样一次就能消掉4bit待测数据。即1011对应101110111100，实际只需要用到后8位，即1011对应10111100用查表法来得到，即1011作为索引值，查表，得到表值10111100。表格可以预先生成。通信网络设计课程设计题号：C10设计日期20120904----20120916第4页共10页这里是每次移出4位，则POLY与POLY进行XOR的组合有2^4＝16种，即从0000到1111。注意，POLY自身与自身相XOR时，要先对齐到和寄存器一样的长度，再XOR。相当于有12位进行XOR。组合后的结果有16种：1.000000000000前4位为00002.000101011100前4位为00013.001010111000前4位为00104.001010111000与000101011100相XOR，XOR后前4位为00115.010101110000与000101011100相XOR，XOR后前4位为01006.010101110000，前4位为01017.010101110000与001010111000、000101011100相XOR，XOR后前4位为01108.010101110000与001010111000，XOR后前4位为01119.101011100000与001010111000相XOR，XOR后前4位为100010.101011100000与001010111000、000101011100相XOR，XOR后前4位为100111.101011100000，前4位为101012.101011100000与000101011100相XOR，XOR后前4位为101113.101011100000与010101110000、001010111000、000101011100相XOR，XOR后前4位为110014.101011100000与010101110000、001010111000相XOR，XOR后前4位为110115.101011100000与010101110000、000101011100相XOR，XOR后前4位为111016.101011100000与010101110000相XOR，XOR后前4位为1111上面就是以XOR后得到的结果的前4位做为索引值，以XOR后得到的结果的后8位做为表值生成的一张表就是说，一次移出的待测数据的4bit，有2^4个值，即0000,0001,0010,....,1111，根据这个值来查表，找到相应的表值，再用表值来XOR寄存器中的待测数据。所以，如果一次移出待测数据的8bit，即一次进行一个字节的计算，则表格有2^8＝256个表值。CRC—CCITT是一次处理一个字节的，所以它的查询表有256个表值。描述：1：register左移一个字节,从原始数据中读入一个新的字节.2：利用刚从register移出的字节作为下标定位table中的一个16位的值3：把这个值XOR到register中。4：如果还有未处理的数据则回到第一步继续执行。crc=0;//r是寄存器，先初始化为0while(len--!=0)//len是已扩展0之后的待测数据的长度{da=(unsignedchar)(crc/256);/*以8位二进制数的形式暂存CRC的高8位*/crc=8;/*左移8位，相当于CRC的低8位乘以*/crc^=crc_ta[da^*ptr];/*高8位和当前字节相加后再查表求CRC，再加上以前的CRC*/ptr++;}通信网络设计课程设计题号：C10设计日期20120904----20120916第5页共10页return(crc);}三、设计的功能1.用查表法计算CRC码，编码方式：生成多项式为CRC-CCITT。2.环境要求：系统Windows2000/XP/7；C语言；编译环境为C-Free或VC++6.03.信息交换内容为文本文件；信息交换方式为共享文件4.功能：能在两台计算机机上运行程序，一台产生CRC码，另一台校验。四、程序框图PCA----------文件共享---------PCB五、程序源代码1.PCA程序源代码如下#includestdio.h开始读取共享文档code.txt计算CRC校验码并存入test.txt分别读取crc.txt和test.txt内容到变量crc和test结束crc=test?输出“传输正确”输出“传输错误”是否开始输入信息存入code.txt计算CRC码在屏幕上显示计算出来的CRC校验码将CRC码存入crc.txt结束通信网络设计课程设计题号：C10设计日期20120904----20120916第6页共10页#includestdlib.h#includestring.hunsignedshortcal_crc(char*ptr,intlen){unsignedshortcrc;unsignedcharda;intcrc_ta[256]={/*CRC余式表*/0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,0x72f7,0x62d6,0x9339,0x8318,0xb37b,0xa35a,0xd3bd,0xc39c,0xf3ff,0xe3de,0x2462,0x3443,0x0420,0x1401,0x64e6,0x74c7,0x44a4,0x5485,0xa56a,0xb54b,0x8528,0x9509,0xe5ee,0xf5cf,0xc5ac,0xd58d,0x3653