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

武汉理工大学计算机网络课程论文主题循环冗馀校验(CRC )算法的实现作者大学信息工程学院专家电子信息工程学号指导教师二一六年四月十四日武汉理工大学信息工程学院课程论文诚信声明本人声明：提出的课文是本人在指导老师的指导下独立开展工作的成果，成果中不存在知识产权争议，除本文引用的内容外，本课文不包括其他个人或集体发表的作品成果。 对本文工作作出重要贡献的个人和集体已在文章中以明确的方式显示出来。 本人完全意识到本声明的法律结果由本人承担。本科课程论文作者签字：二一六年四月十四日课程论文成绩评定表质量评价指标(对应栏)评价项目论文与设计评价质量在该项目上打分工作量和态度(十分)分析问题的能力(十分)问题解决能力(10分)内容完整水平清楚(十分)设计，实验准确性(十分)书写规则(10分)流程图或拓扑图(10分)论证充分(十分)测试结果情况(10分)综合评价(10分)评定成绩(百分制)指导教师签字年月日目录一、选题背景11 .设计要求12 .循环冗馀CRC概述1三.需要解决的主要问题2二、方案论二1 .循环冗馀检验原理22 .方案的选择和特点4三、过程论述81 .第一部分82 .第二部分93 .第三部分114 .第四部分11四、结果分析121.CRC算法的实现122 .突变的发生和检查结果133 .无法检测错误的情况14五、总结15心得17参考文献17附件一：程序源代码181，一、选题背景主题17循环冗馀校验(CRC )算法的实现1 .设计要求(1)利用结构体或排列模拟网络数据包结构。(2)编码实现CRC算法，并且将所获得的奇偶校验比特添加到与网络分组对应的位置。(3)根据数据包的长度，随机生成一个数据包发生突变的位置，对该位置的比特模拟突变的发生。(4)重用CRC算法验证该包并指出结果。(5)CRC能检测出所有的错误吗？ 如果不行的话，能制造出不能检测出错误的案例吗？2 .循环冗馀CRC概述循环冗馀校验码(CRC码、CRC=Cyclic Redundancy Check ) :数据通信领域最常用的错误校验码，其特征在于，可以任意选择信息字段和校验字段的长度。 CRC码由2个部分构成，前一部分是信息码，是需要检查的信息，后一部分是检查码，采用多项式的编码方法。 循环码和码字多项式是CRC中的两个基本概念。 CRC校验的基本思想是利用线性编码理论，根据在发送端传输的k比特的二进制码序列，以一定的规则生成校验用的监视码(CRC码) n比特，在信息的后面相加，构成新的二进制码序列数的合计(k-n )比特，最后进行传输。 在接收端，根据信息代码和CRC代码之间的规则进行验证，决定发送中是否有错误。循环冗馀校验码CRC是一种高效、可靠的方法，线性分组码被分岔是一种通过多项式除法来检测差错的罕见方法，而另一方面具有非常强的检测能力，第二是编码器电路和差错检测电路易于实现，其优点被广泛应用于通信系统中。 现实的通信链路是不理想的。 也就是说，在比特的传输中有可能发生错误的：1为0，0也有可能为1。 我把这个称为比特错误。 比特错误是传输错误之一。 在一定期间，将传输错误比特数在所传输的比特数中所占的比率称为错误率BEG。 差错率与信噪比有很大的关系。 通过增加信噪比可减少错误率。 实际通信链路不理想，错误率不能降低到零。 因此，为了保证数据传输的可靠性，在通过计算机网络传输数据时，必须采取各种检错措施。 现在在数据链路层广泛使用循环冗馀校验CRC的检错技术。三.需要解决的主要问题(1)选择实现编程的软件MATLAB具有程序结构控制、函数调用、数据结构、输入输出、面向对象等程序语言特点，易于学习，编程效率高。 MATLAB提供了一种交互式数学系统环境，该系统的基本数据结构是矩阵，在产生矩阵对象时不需要明确的维描述。 与使用c语言进行数值计算的编程相比，MATLAB可大幅节省编程时间。 本次大作业采用阵列仿真网络的数据包结构，MATLAB操作简单，结果用MATLAB程序语言实现了CRC检测的程序设计。(2)理想的循环冗馀校验算法应具有以下特点具有相同的CRC数据必须是相同的，每次获得相同的CRC值。 这也是在通信中用CRC检查数据收发中是否出错的基本依据。从CRC的不同数据得到的CRC值应该不同。 (估计伪造可能获得相同CRC值，但需要保证较小的这种概率)对于32比特CRC，它能够区分232的数据，即长度为232的两个数据，只要2比特的值不同，经由CRC获得的CRC值就不同。(3)实现CRC算法过程的方法：在此次的设计中，使用模式2除法求馀数，在程序中，能够以每比特为单位用异或表现所传输的数据和生成多项式。 由于要传输的数据的位数还没有确定，因此容易一个一个地写错，很麻烦，很难修改数据，因此在程序中使用for循环语句按位求解，最终得到馀数。二、方案论1 .循环冗馀检验原理在发送侧，首先将数据分割为组，假设每组k比特。 假设M=(k=6)待传输的数据量。 CRC运算在数据m后附加检错用n位冗馀码，构成一帧进行发送，总共发送(k-n )位。 当在发送的数据的前后追加n位的冗馀码时，数据传输的开销变大，但是能够进行错误检测。 当传输可能发生错误时，付出这种代价是值得的。该n位冗馀编码可通过以下的方法得到。 使用二进制模型2演算进行2n次方m演算对应于m后加n个0。 如果所获得的(k-n )位的数目除以由收发机双方事先协商好的长度(n-1 )位的除数p，则商为q，馀数为R(n位，比p少1位)。 对于除数p，在图21所示的示例中，M=(即，k=6)。 假设除数p=1101(n=3)。 用模型2除的结果是：商Q=(这个商没有什么用)，馀数R=001。 馀数r作为冗馀编码发送在数据m的后面。 附加用于这种错误检测的冗馀编码常常被称为帧校验序列FCS。 因此，添加了FCS要发送的帧是(即，2n*M FCS )位，其共享(k-n )位。Q (商)p (除数)11012n*M (被除数)11011110110101110000111011010110000011001101001R (馀数)、FCS图2-1表示循环冗馀校验的原理的例子在接收侧，接收数据以帧为单位进行CRC校验：接收的帧被除以相同的除数p (模式2的运算)，并且馀数r被校验。如果在传输过程中没有错误，经过CRC检验获得的馀数r总是0。 然而，在产生错误码的情况下，馀数r变为零的概率非常小。总而言之，在对接收侧接收的每个帧进行CRC校验后，有以下两种情况(1)如果获得的馀数r为0，则确定该帧没有错误并且接受该帧。(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=x 32x 26x 23x 22x 16x 12x 11x 10x 8x 7x 5x 4x 2x 1在数据链路层，由于发送侧帧校验序列FCS的生成和接收侧的CRC校验是用硬件进行的，处理是迅速的，因此数据的传输不会延迟。传送数据时，如果不以帧为单位进行传送，就不能加入冗馀编码进行错误检查。 因此，为了在数据链路层中执行错误检查，有必要将数据分割成各个帧，将冗馀编码附加到各个帧上，并且在接收侧对各个帧执行错误检查。2 .方案的选择和特点这次的编程需要满足5个要求，所以要逐一分析。 在MATLAB中，由于数组的表现简单，所以用数组来模拟网络数据包构造。实现主题5个要求，首先要整理循环冗馀校验CRC算法的具体计算过程，以此为基础编制程序，继续对初始算法程序进行修正和追加，以实现发生突变等情况。 对CRC算法的过程，在阐述原理的时候作了一个大致的阐述，以下是一个统一、细致的分析。2.1 CRC编码规则CRC码包括两个部分，前一部分是信息码，需要校验的信息，后一部分是校验码，如果CRC码是合计n位长，信息码长度k位长，则称为(n，k )码。 编码规则包括(1)换档将原始信息代码(kbit )向左移动r位(k r=n )(2)除法使用一个生成多项式g (x ) (也可视为二进制数)，将上式除以模型2，得到的馀数为校验码。简单地说，通过在除模型2的过程中对模型2进行加法运算，对模型2进行加法运算实际上是熟悉的异或运算，在加法运算不考虑进位的情况下，式子如下0=1=0，1=0=1=1也就是说“异”是真的，“非异”是假的。由此得出定理： a b b=a即“模2减”和“模2加”的直值表示完全相同。 有加减运算时，因为可定义模式2除法，所以可使用生成多项式g(x )生成CRC校验码。2.2生成CRC码的过程步骤1 :在数据单元(k位)的末尾加上n个0。 n是比预定除数的比特数(n 1)少1的整数。步骤2 :使用二进制除法将新增长的数据单元(k n位)除以除数。 通过该除法得到的馀数是循环冗馀编码校验码。第三步骤：用从第二步骤获得的n位CRC码代替附加在所述数据单元的末尾的n个零。 如果馀数小于n，则最左边的默认位数为0。 如果没有产生任何除法过程(即，能够被原始数据单元本身除以除数)，则用n个0代替剩馀的位置作为CRC码。 生成的位模式正好能被除数除尽。2.3 CRC检查过程演示假设在数据传输期间需要传输15比特的二进制信息g=0001，此二进制码可表示为代数多项式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 )可以被自由地选择和使用国际通行标准，并且一般的CRC算法在h(x )的m阶上被称为CRC-m，例如，CRC-32、CRC-64等。g(x )和h(x )的除法可以用g和h进行xor (异或)运算。 例如对11001和10101进行xor运算时，如图2-2所示图2-2 11001和10101的xor运算结果在理解xor算法之后，图2-3给出了通过使用CRC-8算法的示例来确定0001的有效代码。 CRC-8标准h(x)=x8 x7 x6 x4 x2 1，h是9位二进制串。图2 -使用2-3CRC-8算法确定0001验证码经过迭代运算最终获得的r是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可以是b。图26最初的位移过程(3)因为每次重复时受到影响的是gk的高位m位，所以构筑m位的寄存器s，该寄存器存储gk的高位m位。 每次反复计算时首先丢弃s的首位，将寄存器向左移动1位，并且将g的低位放入寄存器。 使用此方法时，计算步骤如图2图7所示图2-7使用寄存器计算的步骤三、过程论述了解了CRC的具体计算过程后，就可以开始构建基本程序体系结构。 在for循环中建立迭代运算，可根据主题的要求将程序分为4个部分写入。一、第一部分这一部分利用该阵列来模拟网络分组结构，编码以实现CRC请求馀数算法。 程序的流程图如图3-1所示。开始构造数组m，取其长度l，构造生成多项式添加冗馀位，k=0初始化馀数阵