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

武汉理工大学计算机网络课程论文武汉理工大学计算机网络课程论文题目循环冗余校验（CRC）算法的实现作者学院信息工程学院专业电子信息工程学号指导教师二一六年四月十四日武汉理工大学计算机网络课程论文武汉理工大学信息工程学院课程论文诚信声明本人声明：所呈交的课程论文，是本人在指导老师的指导下，独立开展工作所取得的成果，成果不存在知识产权争议，除文中已经注明引用的内容外，本课程论文不含任何其他个人或集体已经发表或创作过的作品成果。对本文工作做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 本科课程论文作者签名：二一六年四月十四日课程论文成绩评定表质量评价指标（在相应栏目打）评 价 项 目论文与设计评价质量按对应项目打分工作量和态度（10分）分析问题能力（10分）解决问题能力（10分）内容完整层次分明（10分）设计、实验正确性（10分）书写规范（10分）流程图或拓扑图（10分）论证充分（10分）测试结果情况（10分）总体评价（10分）评定成绩（100分制）指导教师签名年 月 日目 录一、选题背景11.设计要求12.循环冗余CRC简介13.应解决的主要问题2二、方案论证21.循环冗余检验的原理22.方案的选择及特点4三、过程论述81.第一部分82.第二部分93.第三部分114.第四部分11四、结果分析121.CRC算法的实现122.突变的产生和校验结果133.无法检错的实例14五、总结15心得体会17参考文献17附件一：程序源代码181、VI一、选题背景题目17 循环冗余校验（CRC）算法的实现1、设计要求（1）利用结构体或数组模拟网络数据包结构。（2）编码实现CRC算法，并将得到的校验位附加到网络数据包相应的位置。（3）根据数据包的长度，随机生成一个数据包产生突变的位置，并对该位置的bit位模拟突变的产生。（4）重新利用CRC算法校验该数据包，并指出产生的结果。（5）CRC能够检出所有的错误吗？如果不能，你能构造出无法检错的实例吗？2、循环冗余CRC简介循环冗余校验码（CRC码，CRC=Cyclic Redundancy Check）：是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。CRC码是由两部分组成，前部分是信息码，就是需要检验的信息，后部分是检验码，采用的是一种多项式的编码方法。循环码和码字多项式是CRC中的两个基本概念。CRC 校验的基本思想是利用线性编码理论，在发送端根据要传送的k 位二进制码序列，以一定的规则产生一个校验用的监督码（CRC 码）n 位，并附在信息后边，构成一个新的二进制码序列数共 (k+n) 位，最后发送出去。在接收端，则根据信息码和CRC 码之间所遵循的规则进行检验，以确定传送中是否出错。循环冗余校验码CRC是一种高效率且可靠的方法, 由线性分组码分支而来的, 是一种通过多项式除法检测错误的很不寻常而又巧妙的方法, 一方面它有很强的检测能力, 二是它的编码器电路及错误检测器电路都很容易实现, 它的优点使它在通信系统中得到了广泛的应用。现实的通信链路都不会是理想的。这就是说，比特在传输过程中可能会产生差错:1可能会变成0，而0也可能变成1。这就叫做比特差错。比特差错是传输差错中的一种。在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率BEG。误码率与信噪比有很大的关系。如果设法提高信噪比，就可以使误码率减小。实际的通信链路并非是理想的，它不可能使误码率下降到零。因此，为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。目前在数据链路层广泛使用了循环冗余检验CRC的检错技术。3、 应解决的主要问题（1）选用哪种软件实现编程：MATLAB具有程序结构控制、函数调用、数据结构、输入输出、面向对象等程序语言特征，而且简单易学、编程效率高。MATLAB提供了一个人机交互的数学系统环境，该系统的基本数据结构是矩阵，在生成矩阵对象时，不要求明确的维数说明。与利用C语言作数值计算的程序设计相比，利用MATLAB可以节省大量的编程时间。本次大作业采用数组模拟网络数据包结构，采用MATLAB操作简单，结果明了，故用MATLAB程序语言实现CRC校验的程序设计。（2）理想的循环冗余校验算法应具有以下特征：CRC相同的数据多次，每次得到的CRC值应该相同。这也是通信过程中通过CRC校验数据在收发过程中是否出错的基本依据。CRC不同的数据得到的CRC值应该不等。(尽管通过估计伪造可能得到相同的CRC值，但要确保这种概率很小)对于32位的CRC来说，它能区分232的数据，即长度为232的两个数据，只要有任何两位的值不同，它们分别经过CRC后得到的CRC值就不同。（3） 如何实现CRC算法过程：本次设计采用模2除法运算求余数，程序中可表示为将待传送数据与生成多项式逐位异或。因为待传送数据的位数不确定，一一编写容易出错且麻烦，不易于修改数据，因此在程序中采用for循环语句来逐位求解最终得到余数。二、方案论证1、循环冗余检验的原理在发送端，先把数据划分为组，假定每组k个比特。现假定待传送的数据M=101001（k=6）。CRC运算就是在数据M的后面添加供差错检测用的n位冗余码，然后构成一个帧发送出去，一共发送（k+n）位。在所要发送的数据后面增加n位的冗余码，虽然增大了数据传输的开销，但却可以进行差错检测。当传输可能出现差错时，付出这种代价往往是很值得的。这n位冗余码可用以下方达得出。用二进制的模2运算进行2n乘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(即2n*M+FCS)，共有(k+n)位。 110101Q（商）P(除数)11011010010002n*M(被除数) 1101 1110 1101 0111 000011101101 0110 0000 1100 1101 001R（余数),作为FCS图2-1 说明循环冗余检验原理的例子在接收端把接受到的数据以帧为单位进行CRC检验:把收到的每一个帧都除以同样的除数P（模2运算），然后检查得到余数R。如果在传输过程中无差错，那么经过CRC检验后得到的余数R肯定是0。但如果出现误码，那么余数R仍等于零的概率是非常非常小的。总之，在接收端对收到的每一帧经过CRC检验后，有以下两种情况：（1） 若得到的余数R等于0，则判定这个帧没有差错，就接受（accept）。（2） 若余数R不等于0，则判定这个帧有差错（但无法确定究竟是哪一位或哪几位出现了差错），就丢弃。一种较方便的方法是用多项式来表示循环冗余检验过程。在上面的例子中，用多项式P(X)=X3+X2+1表示上面的除数P=1101（最高位对应于X3,最低位对应于X0）。多项式P(X)称为生成多项式。现在广泛使用的生成多项式P(X)有以下几种：CRC-16=X16+X15+X2+1CRC-CCITT=X16+X12+X5+1CRC-32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1在数据链路层，发送端帧检验序列FCS的生成和接收端的CRC检验都是用硬件完成的，处理很迅速，因此并不会延误数据的传输。如果在传送数据时不以帧为单位来传送，那么就无法加入冗余码以进行差错检验。因此，如果要在数据链路层进行差错检验，就必须把数据划分为帧，每一帧都加上冗余码，一帧接一帧地传送，然后在接收方逐帧进行差错检验。2、 方案的选择及特点由于本次编程需要达到五点要求，因此进行逐一分析。在MATLAB中，数组的表现方式很简单，故采用数组模拟网络数据包结构。要实现题目的五点要求，必须先理清循环冗余检验CRC算法的具体计算过程，以此为基础编写程序，再在初始算法程序上继续修改和添加来实现产生突变等的情况。关于CRC算法过程，在阐述原理时已有大致讲到，一下是统一细致的分析。2.1 CRC编码规则CRC码是由两部分组成，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码共长n个bit，信息码长k个bit，就称为(n,k)码。 它的编码规则是：（1）移位将原信息码(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.2 CRC码的生成步骤第一步：在数据单元（k位）的末尾加上n个0。n是一个比预定除数的比特位数（n+1）少1的数。第二步：采用二进制除法将新的加长的数据单元（k+n位）除以除数。由此除法产生的余数就是循环冗余码校验码。第三步：用从第二步得到的n个比特的CRC码替换数据单元末尾附加的n个0。如果余数位数小于n，最左的缺省位数为0。如果除法过程根本未产生余数（也就是说，原始的数据单元本身就可以被除数整除）那么以n个0作为CRC码替换余数所在的位置。产生的比特模式正好能被除数整除。2.3 CRC校验过程展示假设数据传输过程中需要发送15位的二进制信息g=101001110100001，这串二进制码可表示为代数多项式g(x)=x14+x12+x9+x8+x7+x5+1，其中g中第k位的值，对应g(x)中xk的系数。将g(x)乘以xm，既将g后加m个0，然后除以m阶多项式h(x)，得到的(m-1)阶余项r(x)对应的二进制码r就是CRC编码。h(x)可以自由选择或者使用国际通行标准，一般按照h(x)的阶数m，将CRC算法称为CRC-m，比如CRC-32、CRC-64等。g(x)和h(x)的除运算，可以通过g和h做xor（异或）运算。比如将11001与10101做xor运算如图2-2：图2-2 11001与10101做xor运算所得结果明白了xor运算法则后，举一个例子使用CRC-8算法求101001110100001的效验码如图2-3所示。CRC-8标准的h(x) = x8 + x7 + x6 + x4 + x2 + 1，既h是9位的二进制串111010101。图2-3 使用CRC-8算法求101001110100001的效验码经过迭代运算后，最终得到的r是10001100，这就是CRC效验码。通过示例，可以发现一些规律，依据这些规律调整算法：（1）每次迭代，根据gk的首位决定b，b是与gk进行运算的二进制码。若gk的首位是1，则b=h，如图2-4所示；若gk的首位是0，则b=0，或者跳过此次迭代，如图2-5所示，上面的例子中就是碰到0后直接跳到后面的非零位。图2-4 gk首位为1时的情况图2-5 gk首位为0时的情况（2）每次迭代，gk的首位将会被移出，如图2-6所示，所以只需考虑第2位后计算即可。这样就可以舍弃h的首位，将b取h的后m位。比如CRC-8的h是111010101，b只需是11010101。图2-6 首位移出过程 （3）每次迭代，受到影响的是gk的前m位，所以构建一个m位的寄存器S，此寄存器储存gk的前m位。每次迭代计算前先将S的首位抛弃，将寄存器左移一位，同时将g的后一位加入寄存器。若使用此种方法，计算步骤如图2-7所示：图2-7 使用寄存器计算的步骤三、过程论述了解到CRC的具体计算过程后，可以开始构造基本程序架构。以for循环来建立迭代运算，按照题目要求，可将程序分为四个部分进行编写。1、 第一部分该部分利用数组模拟网络数据包结构，编码实现CRC求余算法。程序流程图如图3-1所示。开始构建数组M、取其长度L、构建生成多项式添加冗余位、k=0初始化余数数组Rk=k+1构造与R等长度的除数数组PY判断R的首位是否为0被除数所有位置0NR = P xor R恢复除数数组去除被除数第一位NkL?Y结束图3-1 第一部分程序流程图2、 第二部分该部分将得到的校验位附加到网络数据包相应的位置，并将添加了帧检验序列FCS的数据继续以模2除法进行CRC检验。程序流程图如图3-2所示。NY显示码元传输发生错误结束输出原始序列YN判断余数是否为0kL-length(CRC_P)+1恢复除数数组、去除被除数第一位R = P xor R被除数所有位置0NY判断R的首位是否为0构造与R等长度的除数数组Pk=k+1取冗余编码长度L、初始化余数数组R、令k=0将生成余数序列的冗余位叠加到编码序列开始图3-2 第二部分程序流程图3、 第三部分该部分实现了根据数据包的长度，随机生成一个数据包产生突变的位置，并对该位置的bit位模拟突变产生的过程。按照要求，先利用i=ceil(rand(1,1)*r)函数来随机抽取数组中的一个位，其中r为该数组的长度。再将该位的值进行取反再放回，生成一个某位发生突变的新数组。重新利用CRC算法校验该数据包，并指出产生的结果。由于检验方法与第二部分一致，因此程序流程图与第二部分的流程图（图3-2）基本一致，此处不再绘制。4、第四部分该部分构造出了一个无法被CRC检错的实例，来验证CRC是否能够检出所有的错误。通过查阅资料，我了解到了CRC校验的检错性能。CRC校验码的检错能力与其生成多项式密切相关。生成多项式的次数越高，其检错能力越强。若CRC校验的生成多项式的最高次幂为r，则该CRC校验码的检错性能如下：（1） 可检出所有奇数个错误；（2） 可检出所有2bit个错误；（3） 可检出所有长度（r+1)个bit的突发错，其漏检率仅为：1/2r。事实证明CRC虽具有良好的检错能力，但不能够检出所有的错误。构造该无法检错的实例的思路：由于生成多项式的次数越高，CRC的检错能力越强，故我在程序中自主构建一个相对简单的生成多项式便于实例的构造。回顾CRC检验的方法，先将添加了冗余码FCS后发送的序列与求余过程中的生成多项式进行模2运算，再来判断求得的余数是否为0？若为0则证明传输过程无差错；若不为0则证明传输过程中有差错。因此我进行大胆猜测：如若添加了冗余码FCS后发送的数据发生突变，但突变后的数据恰巧也能被原生成多项式整除，即存在“同余”的错误，是不是CRC便无法检测出该已经发生了突变的错误数据？因此我在该部分构造了一个与原发送数据不同的错误序列，经验算，该错误序列也能被原定的生成多项式整除。再利用第二部分的检验方式，观察最终输出结果与预测是否一致，最后加上一个判断语句显示最终结果。由于检验方式与第二部分一致，故对于检验的流程图不再绘制，对于判断结果的程序流程图如图3-3所示。结束实际传输数据错误实际传输数据正确NYerror_sequence = M？已知错误序列error_sequence编写原序列M开始图3-3 第四部分判断结果的程序流程图4、 结果分析将程序运行后可以得到所有的输出，现将输出分三个部分展示。1、 CRC算法的实现编程实现利用数组模拟网络数据包结构实现CRC算法，并将得到的校验位附加到网络数据包相应的位置。程序中，M表示原始带传送数据；CRC_P表示生成多项式；crc_M表示经计算得到的添加了冗余码FCS后的数据。若输出一组名为original_sequence的数据则表明本次校验结果正确；若输出err=1则表明本次校验结果错误。令M=101110；生成多项式P(X)=X3+1。结果如图4-1所示。图4-1 CRC校验结果展示分析：从结果中看出crc_M的结果为101110011，即所得冗余码FCS=011，与验算结果一致。且经校验后输出了一组名为original_sequence的数据，该数据与M一致，说明校验结果正确。这也证实了此次编程实现了循环冗余校验CRC算法的要求。2、突变的产生和校验结果根据数据包的长度，编程实现随机生成一个数据包产生突变的位置，并对该位置的bit位模拟突变的产生；再重新利用CRC算法校验该数据包，并指出产生的结果。程序中，i为一个随机数，代表着原冗余数组crc_M中的某一位的位序；程序中还会输出该随机位的值；随后会得到该随机位的值发生突变后的突变数组，此时用crc_M表示这个突变的数组；在进行校验后若输出一组名为original_sequence的数据则表明本次校验结果正确；若输出err=1则表明本次校验结果错误。突变及其校验结果如图4-2所示。图4-2 突变及其校验结果展示分析：由结果可知随机抽到的位序为9，从图4-1中看出原冗余数组的第九位为1。在发生突变后的新数组crc_M=101110010，刚好与图4-1中原冗余数组的第九位不同，其余位均相同。表明随机生成一个数据包产生突变的位置，并对该位置的bit位模拟突变的产生的设计是正确的。再来看校验的结果是输出了err=1，这说明突变后的数组成功被CRC校验检出错误，证实了CRC检验算法的检错能力。3、 无法检错的实例在过程论证模块，对于程序的第四部分，已经表明了对于如何构造无法检错实例的设计思路。在程序中，先编写一个与原冗余数组crc_M不同但位数相同，同时也能被生成多项式整除的数组N；已知N并不是正确的传输数据，对N进行CRC算法检验，若输出一组名为error_sequence的数据则表明实际传输的数据错误，CRC无法检错；若输出err=1则表明CRC算法依旧能够检出该错误。对于该实例的校验结果如图4-3所示。图4-3 无法检错实例的校验结果展示分析：从结果中可能看出，N与原冗余数组crc_M是不同的。但最后经同一生成多项式检验得到的结果并没有输出err=1的字眼，而是输出了一组名为error_sequence的数组，很明显，这一组数据与最原始的待传送数据M不同，是错误数据，而检验结果未报错说明没有检验到该错误。最终的显示也是“实际传输数据错误，无法检错”，这也证实了构造无法检错实例的思路和该段程序的编译都是正确的。从而证明，CRC并不能够检出所有的错误。5、 总结CRC校验码是基于将位串看作是系数为0或1的多项式，一个k位的数据流可以看作是关于x的从k-1阶到0阶的k-1次多项式的系数序列。采用此编码，发送方和接收方必须事先商定一个生成多项式G(x)，其高位和低位必须是1。要计算m位的帧M(x)的校验和，基本思想是将校验和加在帧的末尾，使这个带校验和的帧的多项式能被G(x)除尽。当接收方收到加有校验和的帧时，用G(x)去除它，如果有余数，则CRC校验错误，只有没有余数的校验才是正确的。二进制多项式的加减运算为模2加减运算，即两个码多项式相加时，对应系数进行模2加减。所谓模2加减就是各位做不带进位、借位的按位加减。这种加减运算实际上是逻辑上的异或运算，即加法和减法等价。信息多项式和余数多项式可以合并成一个新的多项式（称为循环码的码多项式），则该多项式是生成多项式的整数倍，即能被生成多项式整除。根据这一原理，在发送端用信息码多项式除以生成多项式所得的余数多项式就是所要加的监督位。将循环码的码多项式除以生成多项式，若能除尽，说明传输正确，否则说明出错。CRC校验的关键是如何求出余数，此余数即为校验码（CRC校验码）。为了传输的正确性，在接收端要有一个CRC检验器。它的功能和发生器一样，当收到CRC冗余校验码后，做同样的模2除法（注意，这里采用的生成多项式一定要与发送端相同）。如果余数是0，则说明传输正确；否则传输错误。CRC校验的检错能力极强，但并不能检出所有的错误。当冗余数组发生突变，生成一个与原数组存在“同余”现象的新数组，CRC是无法检出此种错误的。心得体会经历了近两个星期的查阅资料和理论分析，终于完成了循环冗余校验CRC算法编程和报告。经历了这次计算机网络的大作业设计，大大的提高了我的操作能力以及分析问题的能力，从中也学到了很多书面上关于CRC校验所没有搞清楚的问题，也熟悉了应用MATLAB这个软件来进行程序编程。通过这次大作业设计，我学到了很多有用的知识，并加强了自己掌握和理解书本知识的能力，培养了自己的实际动手能力与综合设计能力，提高了自己的技术素质，这对以后的学习和工作都是非常有益的。在此次设计中，我先大量查阅CRC算法的具体过程，逐一分析题目要求，通过动手实践操作，进一步学习和掌握了有关CRC原理的知识，加深了对纠错技术的认识。在设计过程中我复习了相关知识，还查阅了相当多的资料，这也在一定程度上拓宽了我的视野，丰富了我的知识。现如今我对CRC算法有了非常深刻的理解，这次的大作业设计不止是对所学知识的一次重要巩固，更是从查阅资料、逐一分析题目要求、动手编写程序到不断地修改和完善等方面锻炼了我的综合能力。总之，通过这次大作业设计我有了很多收获。摸索该如何使用MATLAB去实现题目要求的过程特别有趣，培养了我的设计思维；无论是对所学课本知识的运用还是对软件系统的了解，我都有了很大程度的提高，提高了理论用于实践的能力，掌握了更多专业相关的使用知识与技能。在程序运行过程中曾遇到许多困难和错误，最后通过不断查阅资料和向同学请教一一解决。当最终完成本次课程设计时，我深刻体会到成功的喜悦和快乐。参考文献1.谢希仁等. 计算机网络（第六版） M. 北京:电子工业出版社,2013.6；2.王虹等. 通信系统原理 M. 北京：国防工业出版社，2014.8;3.孙丽华. 信息论与纠错编码 M. 电子工业出版社，2005.3.附件一：程序源代码%第一部分M=1,0,1,1,1,0 % M为待传送数据L= length(M); % L为数据M的长度CRC_P = 1 0 0 1;% CRC生成多项式P(X)=X3+1n = zeros(1,3); % 添加3位冗余码crc_M = M zeros(1,3);% 初始化输出检错码序列 M = M n;% 在数据M后面添加供差错检测用的n位冗余码R = M; % 初始化余数数组R for k = 1:L % 利用循环语句计算求余数 add_zeros = zeros(1,L-k); % 设置冗余位参与模2运算 P = CRC_P add_zeros; % 构造与R等长度的除数数组P if R(1) = 0 P = zeros(1,length(P); % 若R首位为0则将除数所有位置0 end R = bitxor(P,R); % 将除数与被除数进行异或操作 P = CRC_P; % 将寄存器恢复为除数数组 R(1) = ; % 去除模2运算后得到的被除数的第1位 end %第二部分add_len = length(crc_M) - length(R); % 生成余数序列的冗余位以叠加到编码序列R = zeros(1,add_len),R; % 将所得余数序列添加冗余至与crc_M等长度crc_M =crc_M + R % 合成编码序列L = length(crc_M); % 得到冗余编码的长度 original_sequence = crc_M; % 初始化输出序列 CRC_P = 1 0 0 1;% CRC生成多项式P(X)=X3+1R = crc_M; % 初始化余数数组 T = L-length(CRC_P)+1;% T为长除法的循环周期 for k = 1:T % 利用循环语句计算求余数 add_zeros = zeros(1,T-k);% 设置冗余位参与模2运算 P = CRC_P add_zeros; % 构造除数数组P if R(1) = 0 P = zeros(1,length(P); % 若R首位为0则将除数所有位置0 end R = bitxor(P,R);% 将除数与被除数进行异或操作 P= CRC_P; % 将寄存器恢复为除数数组 R(1) = ; % 去