CRC检验原理及程序实现(1).doc

CRC检验原理及程序实现引言： 循环冗余检验CRC(Cyclic Redundancy Check)的检错技术应用较为广泛，由于实际的通信线路并非是理想的，它不可能将误码率（在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率BER）下降到零。因此，为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用检错措施。目前在数据链路中广泛采用循环冗余检验CRC检测技术。 1、循环冗余检验CRC的原理 利用CRC进行检错的过程可简单描述为：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的n位监督码(CRC码)，附在原始信息后边，构成一个新的二进制码序列数共k+n位，然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”。 代数学的一般性算法： 在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如 1100101 表示为 1x6+1x5+0x4+0x3+1x2+0x+1，即 x6+x5+x2+1。 设编码前的原始信息多项式为G(x)，G(x)的最高幂次加1等于k；生成多项式为P(x)，P(x)的最高幂次等于r；CRC多项式为R(x)；编码后的带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)最高幂次r=3，得出CRC为001。 如果用竖式除法，计算过程为（用异或计算）以(x)为准，（x）左移P(x)的最高次位（r）再除以P(x)本身求余可得一个的位的CRC码: 1 1 0 1 0 1 （商） P（除数） 1 1 0 1 ) 1 1 0 1 1 1 1 0 1 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 1 R（余数）即检验码因此，T(x)=XrG(x)+R(x), 即 1100000+010=1100010 如果传输无误，T(x)除以P(x) 无余式。回头看一下上面的竖式除法，如果被除数是101001001，除数是P=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)转换成对应的R+1位二进制数；2） 码左移R位，相当于对应的信息多项式K(x)*2R；3） 多项式（二进制）对信息码做模2除，得到R位的余数；4） 拼到信息码左移后空出的位置，得到完整的CRC码。C语言源程序代码：#include void main() unsigned int g,k,r,l,n,b,c,d,e,p,i,s,j,cont; register s1; printf(以下数据一十六进制计数方式输入n); printf(请输入生成码的值：n); scanf(%d,&g); printf(请输入信息码的值：n); scanf(%d,&k); unsigned int m,w=0; /* 测量生成码的长度r*/ m=g; do m=1;w+; while (m!=0); r=w; unsigned int m,w=0; /* 测量信息码的长度n*/m=k; do m=1;w+; while (m!=0); n=w; k=(n-1); /* 取被除数信息码的高r+1 位，即和生成码的位数相同*/ do s=ig; /* 被除数信息码与生成码异或运算*/ p=r;c=0; /* 统计余数s 高位零的个数，保存到c */ for(j=0;j=(p-1); if(s1&01)=0) p-;c+; else break; if (cl-cont)break; /* 余数s 高位零的个数高于信息码没有被除的位数，跳出循环，不再做异或运算*/ s(n-1-c); /* 取信息码K 的从右端开始的(n+r-1)-r-c=n-1-c的C 位*/ d=(0c); e=b&d; s=s|e; /* 取s 的高位与信息码没被除的高位合成被除数*/ i=s; cont+=c; while (cont=l); s=s|k; /* 将最后余数和信息码