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

CRC检验原理及程序实现 引言： 循环冗余检验CRC(Cyclic Redundancy Check)的检错技术应用较为广泛，由于实际的通信线路并非是理想的，它不可能将误码率（在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率BER）下降到零。因此，为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用检错措施。目前在数据链路中广泛采用循环冗余检验CRC检测技术。 1、循环冗余检验CRC的原理 利用CRC进行检错的过程可简单描述为：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的n位监督码(CRC码)，附在原始信息后边，构成一个新的二进制码序列数共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)；编码后的带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