标签: 循环冗余校验码

CRC即循环冗余校验码（Cyclic Redundancy Check）：是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。 循环冗余校验码（CRC）的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码又叫（N，K）码。对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。 校验码的具体生成过程为：假设发送信息用信息多项式C(X)表示，将C(x)左移R位，则可表示成C(x)*2的R次方，这样C(x)的右边就会空出R位，这就是校验码的位置。通过C(x)*2的R次方除以生成多项式G(x)得到的余数就是校验码。 CRC码的生成步骤　 　1、将x的最高次幂为R的生成多项式G(x)转换成对应的R+1位二进制数。   　2、将信息码左移R位，相当与对应的信息多项式C(x)*2的R次方。   　3、用生成多项式（二进制数）对信息码做除，得到R位的余数。   　4、将余数拼到信息码左移后空出的位置，得到完整的CRC码。   　　【例】假设使用的生成多项式是G(x)=x^3+x+1。4位的原始报文为1010，求编码后的报文。   　　解：   　　1、将生成多项式G(x)=x^3+x+1转换成对应的二进制除数1011。   　　2、此题生成多项式有4位（R+1），要把原始报文C(x)左移3（R）位变成1010000   　　3、用生成多项式对应的二进制数对左移3位后的原始报文进行模2除，相当于按位异或：   　　1010000   　　1011   　　------------------   　　1000   　　1011   　　------------------   　　011   　　得到的余位011，所以最终编码为：1010011  代数学的一般性算法 　　在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如 1100101 表示为1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1，即 x6+x5+x2+1。   　设编码前的原始信息多项式为P(x)，P(x)的最高幂次加1等于k；生成多项式为G(x)，G(x)的最高幂次等于r；CRC多项式为R(x)；编码后的带CRC的信息多项式为T(x)。   　发送方编码方法：将P(x)乘以xr(即对应的二进制码序列左移r位)，再除以G(x)，所得余式即为R(x)。用公式表示为T(x)=xrP(x)+R(x)。 　接收方解码方法：将T(x)除以G(x)，得到一个数，如果这个余数为0，则说明传输中无错误发生，否则说明传输有误。   　　举例来说，设信息编码为1100，生成多项式为1011，即P(x)=x3+x2，G(x)=x3+x+1，计算CRC的过程为   　　xrP(x) =x3(x3+x2) = x6+x5 G(x)= x3+x+1 即 R(x)=x。注意到G(x)最高幂次r=3，得出CRC为010。   　　如果用竖式除法(计算机的模二，计算过程为   　　1110 ------- 1011 /1100000 (1100左移3位) 1011 ---- 1110 1011 ----- 1010 1011 ----- 0010 0000 ---- 010 因此，T(x)=(x6+x5)+(x)=x6+x5+x, 即 1100000+010=1100010   　　如果传输无误，   　　T(x)= （x6+x5+x）/G(x) = x3+x2+x, G(x)= x3+x+1 无余式。回头看一下上面的竖式除法，如果被除数是1100010，显然在商第三个1时，就能除尽。   　　上述推算过程，有助于我们理解CRC的概念。但直接编程来实现上面的算法，不仅繁琐，效率也不高。实际上在工程中不会直接这样去计算和验证CRC。