资源描述：
《CRC检验原理及程序实现.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、CRC检验原理及程序实现引言：循环冗余检验CRC(CyclicRedundancyCheck)的检错技术应用较为广泛，由于实际的通信线路并非是理想的，它不可能将误码率（在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率BER）下降到零。因此，为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用检错措施。目前在数据链路中广泛采用循环冗余检验CRC检测技术。1、循环冗余检验CRC的原理利用CRC进行检错的过程可简单描述为：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的n位监督码(CRC码)，附在原始信
2、息后边，构成一个新的二进制码序列数共k+n位，然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”。代数学的一般性算法：在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如1100101表示为1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1，即x6+x5+x2+1。设编码前的原始信息多项式为G(x)，G(x)的最高幂次加1等于k；生成多项式为P(x)，P(x)的最高幂次等于r；CRC多项式为R(x)；编码后的带
3、CRC的信息多项式为T(x)。发送方编码方法：将Ｇ(x)乘以xr(即对应的二进制码序列左移r位)，再除以Ｐ(x)，所得余式即为R(x)。用公式表示为T(x)=xrＧ(x)+R(x)接收方解码方法：将T(x)除以G(x)，如果余数为0，则说明传输中无错误发生，否则说明传输有误。2、循环冗余码的产生及正确性检验的例子举例来说，设信息码为101001，生成多项式为1101，即P(x)=x3+x2+1，G(x)=x5+x3+1，计算CRC的过程为xrP(x)即左移三位101001000Ｐ(x)=x3+x2+1即R(x)=１。注意到G(x)最
4、高幂次r=3，得出CRC为001。如果用竖式除法，计算过程为（用异或计算）以Ｐ(x)为准，Ｇ（x）左移P(x)的最高次位（r）再除以P(x)本身求余可得一个的位的CRC码:110101（商）P（除数）1101)1101 1110110101110000111011010110000011001101001R（余数）即检验码因此，T(x)=XrG(x)+R(x),即1100000+010=1100010如果传输无误，T(x)除以P(x)无余式。回头看一下上面的竖式除法，如果被除数是101001001，除数是P
5、=1101，显然就能除尽。总之，在接收端对收到的每一帧经过CRC检验后，（1）若得出的余数R=0，则判断这个帧没有差错，就接受。（2）若余数R不等于0，则判断这个帧有差错（但无法确定究竟是哪一位或那几位出现了差错），就丢弃。3、用C语言程序实现下面以最常见的CRC-16为例说明生成过程，假设发送信息用信息多项式K(x)表示，将K(x)左移R位，则可以表示成K(x)*2R，这样K(x)的右边就会生成R位，这就是检验码的位置，通过K(x)*2R除以生成多项式G(x)得到的余数就是检验码。实现方法：1）最高幂次为R的生成多项式G(x)转换
6、成对应的R+1位二进制数；2）码左移R位，相当于对应的信息多项式K(x)*2R；3）多项式（二进制）对信息码做模2除，得到R位的余数；4）拼到信息码左移后空出的位置，得到完整的CRC码。C语言源程序代码：#includevoidmain(){unsignedintg,k,r,l,n,b,c,d,e,p,i,s,j,cont;registers1;printf("以下数据一十六进制计数方式输入");printf("请输入生成码的值：");scanf("%d",&g);printf("请输入信息码的值：")
7、;scanf("%d",&k);{unsignedintm,w=0;/*测量生成码的长度r*/m=g;do{m>>=1;w++;}while(m!=0);r=w;}{unsignedintm,w=0;/*测量信息码的长度n*/m=k;do{m>>=1;w++;}while(m!=0);n=w;}k<<=r-1;/*信息码左移r-1位，相当于K(x)*Xr*/l=n+r-1;/*信息总长度*/cont=r;/*cont作为已被除信息位数的计数器*/i=k;i>>=(n-1);/*取被除数信息码的高r+1位，即和生成码的位数相同*/do
8、{s=i^g;/*被除数信息码与生成码异或运算*/p=r;c=0;/*统计余数s高位零的个数，保存到c*/for(j=0;j>=(p-1);if((s1&01)==0){p--;c++;}elsebre
