循环冗余校验(CRC)算法的实现

武汉理工大学《计算机网络》课程论文武汉理工大学计算机网络课程论文题目循环冗余校验（CRC）算法的实现作者学院信息工程学院专业电子信息工程学号指导教师二〇一六年四月十四日武汉理工大学《计算机网络》课程论文I武汉理工大学信息工程学院课程论文诚信声明本人声明：所呈交的课程论文，是本人在指导老师的指导下，独立开展工作所取得的成果，成果不存在知识产权争议，除文中已经注明引用的内容外，本课程论文不含任何其他个人或集体已经发表或创作过的作品成果。对本文工作做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。本科课程论文作者签名：二○一六年四月十四日武汉理工大学《计算机网络》课程论文II课程论文成绩评定表质量评价指标（在相应栏目打√）评价项目论文与设计评价质量按对应项目打分工作量和态度（10分）分析问题能力（10分）解决问题能力（10分）内容完整层次分明（10分）设计、实验正确性（10分）书写规范（10分）流程图或拓扑图（10分）论证充分（10分）测试结果情况（10分）总体评价（10分）评定成绩（100分制）指导教师签名年月日武汉理工大学《计算机网络》课程论文III目录一、选题背景.......................................................11.设计要求......................................................12.循环冗余CRC简介..............................................13.应解决的主要问题..............................................2二、方案论证.......................................................21.循环冗余检验的原理............................................22.方案的选择及特点..............................................4三、过程论述.......................................................81.第一部分......................................................82.第二部分......................................................93.第三部分.....................................................114.第四部分.....................................................11四、结果分析......................................................121.CRC算法的实现...............................................122.突变的产生和校验结果.........................................133.无法检错的实例...............................................14五、总结..........................................................15心得体会..........................................................17参考文献..........................................................17附件一：程序源代码................................................18一、武汉理工大学《计算机网络》课程论文1一、选题背景题目17循环冗余校验（CRC）算法的实现1、设计要求（1）利用结构体或数组模拟网络数据包结构。（2）编码实现CRC算法，并将得到的校验位附加到网络数据包相应的位置。（3）根据数据包的长度，随机生成一个数据包产生突变的位置，并对该位置的bit位模拟突变的产生。（4）重新利用CRC算法校验该数据包，并指出产生的结果。（5）CRC能够检出所有的错误吗？如果不能，你能构造出无法检错的实例吗？2、循环冗余CRC简介循环冗余校验码（CRC码，CRC=CyclicRedundancyCheck）：是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。CRC码是由两部分组成，前部分是信息码，就是需要检验的信息，后部分是检验码，采用的是一种多项式的编码方法。循环码和码字多项式是CRC中的两个基本概念。CRC校验的基本思想是利用线性编码理论，在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（CRC码）n位，并附在信息后边，构成一个新的二进制码序列数共(k+n)位，最后发送出去。在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。循环冗余校验码CRC是一种高效率且可靠的方法,由线性分组码分支而来的,是一种通过多项式除法检测错误的很不寻常而又巧妙的方法,一方面它有很强的检测能力,二是它的编码器电路及错误检测器电路都很容易实现,它的优点使它在通信系统中得到了广泛的应用。现实的通信链路都不会是理想的。这就是说，比特在传输过程中可能会产生差错:1可能会变成0，而0也可能变成1。这就叫做比特差错。比特差错是传输差错中的一种。在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率BEG。误码率与信噪比有很大的关系。武汉理工大学《计算机网络》课程论文2如果设法提高信噪比，就可以使误码率减小。实际的通信链路并非是理想的，它不可能使误码率下降到零。因此，为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。目前在数据链路层广泛使用了循环冗余检验CRC的检错技术。3、应解决的主要问题（1）选用哪种软件实现编程：MATLAB具有程序结构控制、函数调用、数据结构、输入输出、面向对象等程序语言特征，而且简单易学、编程效率高。MATLAB提供了一个人机交互的数学系统环境，该系统的基本数据结构是矩阵，在生成矩阵对象时，不要求明确的维数说明。与利用C语言作数值计算的程序设计相比，利用MATLAB可以节省大量的编程时间。本次大作业采用数组模拟网络数据包结构，采用MATLAB操作简单，结果明了，故用MATLAB程序语言实现CRC校验的程序设计。（2）理想的循环冗余校验算法应具有以下特征：CRC相同的数据多次，每次得到的CRC值应该相同。这也是通信过程中通过CRC校验数据在收发过程中是否出错的基本依据。CRC不同的数据得到的CRC值应该不等。(尽管通过估计伪造可能得到相同的CRC值，但要确保这种概率很小)对于32位的CRC来说，它能区分2^32的数据，即长度为2^32的两个数据，只要有任何两位的值不同，它们分别经过CRC后得到的CRC值就不同。（3）如何实现CRC算法过程：本次设计采用模2除法运算求余数，程序中可表示为将待传送数据与生成多项式逐位异或。因为待传送数据的位数不确定，一一编写容易出错且麻烦，不易于修改数据，因此在程序中采用for循环语句来逐位求解最终得到余数。二、方案论证1、循环冗余检验的原理在发送端，先把数据划分为组，假定每组k个比特。现假定待传送的数据M=101001（k=6）。CRC运算就是在数据M的后面添加供差错检测用的n位冗余武汉理工大学《计算机网络》课程论文3码，然后构成一个帧发送出去，一共发送（k+n）位。在所要发送的数据后面增加n位的冗余码，虽然增大了数据传输的开销，但却可以进行差错检测。当传输可能出现差错时，付出这种代价往往是很值得的。这n位冗余码可用以下方达得出。用二进制的模2运算进行2^n乘M的运算，这相当于在M后面添加n个0。得到的（k+n）位的数除以收发双方事先商定的长度为(n+1)位的除数P，得到商是Q而余数是R(n位，比P少一位)。关于除数P，在图2-1所示的例子中，M=101001(即k=6)。假定除数P=1101(即n=3)。经模2除法运算后的结果是:商Q=110101(这个商并没有什么用处)，而余数R=001。这个余数R就作为冗余码拼接在数据M的后面发送出去。这种为了进行检错而添加的冗余码常称为帧检验序列FCS。因此加上FCS后发送的帧是101001001(即2^n*M+FCS)，共有(k+n)位。110101←Q（商）P(除数)→1101√101001000←2^n*M(被除数)11011110110101110000111011010110000011001101001←R（余数),作为FCS图2-1说明循环冗余检验原理的例子在接收端把接受到的数据以帧为单位进行CRC检验:把收到的每一个帧都除以同样的除数P（模2运算），然后检查得到余数R。如果在传输过程中无差错，那么经过CRC检验后得到的余数R肯定是0。但如果出现误码，那么余数R仍等于零的概率是非常非常小的。总之，在接收端对收到的每一帧经过CRC检验后，有以下两种情况：（1）若得到的余数R等于0，则判定这个帧没有差错，就接受（accept）。武汉理工大学《计算机网络》课程论文4（2）若余数R不等于0，则判定这个帧有差错（但无法确定究竟是哪一位或哪几位出现了差错），就丢弃。一种较方便的方法是用多项式来表示循环冗余检验过程。在上面的例子中，用多项式P(X)=X^3+X^2+1表示上面的除数P=1101（最高位对应于X^3,最低位对应于X^0）。多项式P(X)称为生成多项式。现在广泛使用的生成多项式P(X)有以下几种：CRC-16=X^16+X^15+X^2+1CRC-CCITT=X^16+X^12+X^5+1CRC-32=X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X+1在数据链路层，发送端帧检验序列FCS的生成和接收端的CRC检验都是用硬件完成的，处理很迅速，因此并不会延误数据的传输。如果在传送数据时不以帧为单位来传送，那么就无法加入冗余码以进行差错检验。因此，如果要在数据链路层进行差错检验，就必须把数据划分为帧，每一帧都加上冗余码，一帧接一帧地传送，然后在接收方逐帧进行差错检验。2、方案的选择及特点由于本次编程需要达到五点要求，因此进行逐一分析。在MATLAB中，数组的表现方式很简单，故采用数组模拟网络数据包结构。要实现题目的五点要求，必须先理清循环冗余检验CRC算法的具体计算过程，以此为基础编写程序，再在初始算法程序上继续修改和添加来实现产生突变等的情况。关于CRC算法过程，在阐述原理时已有大致讲到，一下是统一细致的分析。2.1CRC编码规则CRC码是由两部分组成，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码共长n个bit，信息码长k个bit，就称为(n,k)码。它的编码规则是：（1）移位武汉理工大学《计算机网络》课程论文5将原信息码(kbit)左移r位(k+r=n)（2）相除运用一个生成多项式g(x)（也可看成二进制数）用模2除上面的式子，得到的余数就是校验码。非常简单，要说明的：模2除就是在除的过程中用模2加，模2加实际上就是我们熟悉的异或运算，就是加法不考虑进位，公式是：0+0=1+1=0,1+0=0+1=1即‘异’则真，‘非异’则假。由此得到定理：a+b+b=a也就是‘模2减’和‘模2加’直值表完全相同。有了加减法就可以用来定义模2除法，于是就可以用生成多项式g(x)生成CRC校验码。2.2CRC码的生成步骤第一步：在数据单元（k位）的末尾加上n个0。