CRC算法，从原理到实现

CRC，一种基于有限域GF(2)的多项式环的Hash算法。在GF(2)中，多项式系数只有0、1，加减运算等同于异或(XOR)运算，乘除运算与一般多项式运算一致（合并同类项时需要注意为XOR运算）

在GF(2)中，多项式系数只有0、1，加减运算等同于异或(XOR)运算，乘除运算与一般多项式运算一致（合并同类项时需要注意为XOR运算）。在CRC-n算法中，有M(x)·xn=Q(x)·G(x)+R(x)，M(x)为m位的数据，G(x)为一个GF(2)的n+1项的生成多项式(Poly)，M(x)·xn则是通过在数据M(x)后添加n个0形成的对应的m+n位多项式，而R(x)即为M(x)·xn除以G(x)的n位余数——即CRC校验码，Q(x)为商，直接丢弃。通过比较两次计算产生的Signature是否一致判断故障的发生

假定M(x)=11100110，G(x)=x3+x+1，其中n=3，则M(x)·xn=11100110000，将G(x)多项式中的各项系数取出，按降幂排列所对应的数据Poly=1011，然后对其进行除法运算：

所得n位余数即为CRC——100

根据定义可以建立一个简单的CRC实现算法，模型如下图所示：1)建立一个长度为r的CRCRegister，并初始化为02)在M(x)后添加r个0形成M(x)·xn3)将CRCRegister左移一位，将M(x)·xn的MSB移入CRCRegister的Bit04)第3步中的从CRCRegister移出的数，如果是1，则计算，CRCRegister=PolyXORCRCRegister5)重复第3步，直到M(x)·xn全部移入CRCRegister6)CRCRegister即为CRC校验值

根据定义所建立的算法模型存在明显缺陷，按位移动处理效率低下，为此我们探索如何实现更大处理单元的算法。这次我们以CRC-32为例，按照前面的算法思路构建的模型如下图所示：

设CRCRegister中的Byte3依次为：t7t6t5t4t3t2t1t0，Poly中的Bit31-Bit24依次为：g7g6g5g4g3g2g1g0，根据1.3.2可知，在第1次迭代中，CRCRegister的MSB:t7将会决定Poly与CRCRegister的异或，如果t7=1，这就会发生，反之就不会发生;在第2次迭代中，CRCRegister的MSB:t6XOR(t7*g7)将会决定本次Poly与CRCRegister的异或是否发生，即t7、t6控制第2XOR操作；同理，在第3次迭代中，CRCRegister的MSB也是通过t7、t6、t5决定，即t7、t6、t5控制第3次XOR操作。故我们可以得出下述结论：k次以后的迭代的最高位的值，可以由寄存器的前k位计算得到。根据这个结论，我们可以一次性取出CRCRegister的Byte3，提前计算出8次迭代后的寄存器余式，因为高位终将会在迭代中被移出，我们只需要关心余式即可。同时XOR运算满足结合律：AXORBXORC=AXOR(BXORC)

上图即为Byte3全部迭代移出的示意图，根据结合律可以看出，我们可以依据Byte3直接确定8次异或的与否及Poly的偏移量，从而提前计算出不同偏移量的Poly间XOR的值，令其为A，易知A的高8位和Byte3一定相等，Reg向左移出btye3，从M(x)·xn读取一个byte放在byte0，最后将A的低32位与Reg完成XOR操作。为避免与字节边界发生冲突，我们采用字节的整数倍——字节（1byte）、字（2byte）、双字（4byte），故一般不采用4bit作为处理单元。由于一个字节的取值是有限的——256种，我们只要提前计算一个字节全部的A值保存到表中。运行时以byte值为索引，直接从表里取出即可

至此我们完成基于1byte为处理单元的TableDriven，算法模型如下图所示：1)建立一个长度为r的CRCRegister，并初始化为02)在M(x)后添加r个0形成M(x)·xn3)将CRCRegister左移一个byte，从M(x)·xn读入一个byte至CRCRegister的byte0中4)以第3步中的从CRCRegister移出的byte为index，从表中取出对应的n位宽的值，将该值与CRCRegister进行XOR5)重复第3步，直到M(x)·xn全部移入CRCRegister6)CRCRegister即为CRC校验值

在上述的两种算法中，我们每次都需要在M(x)后添加n个0，其并不参与运算，目的只是为了将M(x)的全部推入CRCRegister而已，并且在有些情境下在M(x)后添0操作并不总是能够实现的，故通过改进计算步骤有了直接表法，避免了对原始数据的添0操作算法流程，算法模型如下图所示：1)建立一个长度为r的CRCRegister，按照Init值对其初始化2)将CRCRegister左移一个byte，从M(x)左移一个byte，两者进行XOR3)第2步中XOR后的值作为index，从表中取出对应的n位宽的值，将该值与CRCRegister进行XOR4)重复第2步，直到M(x)全部取出5)CRCRegister即为CRC校验值

在DirectTable算法中，当RefIn、RefOut为True，每次都需要对数据做颠倒操作，很麻烦。为此产生了ReflectedDirectTable算法，该算法改变了CRCRegister的移动方向，而不需要对M(x)做任何处理，按字节顺序读取即可，算法模型如下图所示

算法流程如下：1)建立一个长度为r的CRCRegister，按照Init值对其初始化2)将CRCRegister右移一个byte，从M(x)左移一个byte，两者进行XOR3)第2步中XOR后的值作为index，从表中取出对应的n位宽的值，将该值与CRCRegister进行XOR4)重复第2步，直到M(x)全部取出5)CRCRegister即为CRC校验值

Name:CRC标准

Width:生成的CRC的位宽

Poly:生成多项式，一般采用十六进制简记，长度为width+1，由于其最高位恒为1，故记法中不体现出来（例如：x16+x12+x5+1记为0x1021）

Init:初始值，如果数据前添加了若干个前导零，在前述算法中，一般是检测不到的，故通过改变CRCRegister中的预设值，以实现对该类型错误的检测。在DirectTable算法中用Init初始化CRCRegister即可，在TableDriven算法中，不可以直接用Init初始化CRCRegister，因为其等同于在原始数据前插入了Init，必须要先把CRCRegister设为0，等M(x)·xn移动n/8次后，即CRCRegister的预设值0全部移出时，再将Init值异或进CRCRegister。完成Init操作

Xorout:结果异或值，所有计算完成后将CRCRegister与Xorout进行异或作，作为最后的校验值

RefIn:输入反转，这是一个布尔值，如果为False，则每个字节内的位顺序保持不变，即Bit7为MSB，Bit0为LSB。如果为True，则将需要每个字节内的位顺序颠倒，即Bit7为LSB，Bit0为MSB。这个约定在硬件CRC中是合理的，因为在串口通讯中硬件一般默认先发送字节的Bit0，最后发送Bit7

RefOut:输出反转，这是一个布尔值，如果为False，则在计算结束后，直接进入Xorout环节，如果为True，则在计算结束后，将CRCRegister进行颠倒后，再进入Xorout环节。注意和RefIn颠倒字节内的位顺序不同的是，这个是将CRCRegister的值作为一个整体颠倒，即Bitn到Bit0进行颠倒

针对常见常用的下述CRC给出了实现方法，以供参考