CRC原理详解(附crc16校验代码)

算法原理

Cyclic Redundancy Check循环冗余检验，是基于数据计算一组效验码，用于核对数据传输过程中是否被更改或传输错误。

假设数据传输过程中需要发送15位的二进制信息g= 101 0011 1010 0001，这串二进制码可表示为代数多项式g(x) = x¹⁴ + x¹² + x⁹ + x⁸ + x⁷ + x⁵ + 1，其中g中第k位的值，对应g(x)中x^k 的系数。将g(x)乘以x^m，既将g后加m个0，然后除以m阶多项式h(x)，得到的(m-1)阶余项r(x)对应的二进制码r就是CRC编码。

h(x)可以自由选择或者使用国际通行标准，一般按照h(x)的阶数m，将CRC算法称为CRC-m，比如CRC-32、CRC-64等。

g(x)和h(x)的除运算，可以通过g(x)和h(x)做xor（异或）运算。比如将1 1001与1 0101做xor运算：

明白了xor运算法则后，举一个例子使用CRC-8算法求 101 0011 1010 0001的效验码。CRC-8标准的h(x) = x⁸+ x⁷ + x⁶ + x⁴ + x² + 1，既h是9位的二进制串 1 1101 0101。

经过迭代运算后，最终得到的r是1000 1100，这就是CRC效验码。

通过示例，可以发现一些规律，依据这些规律调整算法：

1. 每次迭代，根据$g_k$的首位决定b，b是与$g_k$进行运算的二进制码。若$g_k$的首位是1，则b=h；若$g_k$的首位是0，则b=0，或者跳过此次迭代，上面的例子中就是碰到0后直接跳到后面的非零位。
   

2. 每次迭代，$g_k$的首位将会被移出，所以只需考虑第2位后计算即可。这样就可以舍弃h的首位，将b取h的后m位。比如CRC-8的h是1 1101 0101，b只需是1101 0101。 个人理解扩展：根据item1，$g_k$是1，而常用的h首位也是1，所以首位的nor运算结果必定是0，为了提高运算速度，运算时忽略$g_k$与h的首位
   

3. 每次迭代，只取$g_k$的前m位作运算，所以构建一个m位的寄存器S，此寄存器储存$g_k$的前m位。每次迭代计算前先将S的首位抛弃，将寄存器左移一位，同时将g的后一位加入寄存器。若使用此种方法，计算步骤如下：
   

※蓝色表示寄存器S的首位，是需要移出的，b根据S的首位选择0或者h。黄色是需要移入寄存器的位。S’是经过位移后的S。

查表法

同样是上面的那个例子，将数据按每4位组成1个block，这样g就被分成6个block。

下面的表展示了4次迭代计算步骤，灰色背景的位是保存在寄存器中的。

经4次迭代，$B_1$被移出寄存器。被移出的部分，不我们关心的，我们关心的是这4次迭代对$B_2$和$B_3$产生了什么影响。注意表中红色的部分，记 $B_2$ B 3 B_3 B