CRC校验码

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

算法原理

1. CRC原理
   一般来说，CRC 的计算对应于 GF (2)上多项式的带余除法
   即 $ M(x) \cdot x^{n} = Q(x)G(x) + R(x) $
   通常我们并不关心 \(Q(x)\)，因为他没有特殊的性质；但是\(R(x)\)在特定的生成函数\(G(x)\)下，会表现出循环特性，我们也是依靠这一点来对信息进行校验的。对于\(R(x)\)我们就可以表示为：\(R(x) = M(x)\cdot x^n \ mod\ G(x)\).
   其中，\(x\)在电子信息系统中取2，\(M(x)\)为原信息串，\(n\)为其位数，\(G(x)\)为生成函数，设位数为\(g\)；应该有$ n+g \le 2^g - 1 $，也就是最后生成的校验码的最小位数应为 $ (g-1) $。

2. 多项式取余
   以上问题转变成了求二项式除法余数的问题。
   模2运算的规则：
   1)加减运算：异或运算，加不进位，减不借位
   2)除法：按模2减法，求部分余数，不借位（因为高位对求商没有帮助，余数则可通过一次减法得到）
   ??根据模2运算规则，可以将原信息码乘以\(2^n\)的结果\(M(2) \cdot 2^n\)的系数除以\(G(x)\)的系数，得到的余数则是\(R(x)\)。而\(M(2) \cdot 2^n\)的系数从数字特征上看，就是在\(M(x)\)的系数后面增加\((g-1)\)个\(0\)。

求校验和步骤

1. 根据多项式写出对应数串
2. 在\(M(x)\)后添加\((g-1)\)个\(0\).
3. 以上述串为被除数，\(G(x)\)为除数做除法，从左往右按位异或.
4. 当位数不够时，取最后\((g-1)\)位为余数.

e.g.
M=1101 0110 11
G=1001 1 //g=5

  1101 0110 11 0000 //增加四位
^ 1001 1
= 0100 1
   100 11  //补齐至g=5位即可
^  100 11
=  000 00
         10 11 0 //补齐至5位
^        10 01 1
=        00 10 1
            10 100
^           10 011
=           00 111
               1110 //位数不够5位了，则最后g-1=4为余数

最后求得校验和为1110

纠错步骤

当\(G(x)=1011,M(x)=1100\)时，当且仅当总串为\(1100010\)时，其校验和余数为0，否则余数应如下表所示

由于每一种错误的余数不同，因此可以定位到错误的位置，从而纠错。
??又由于计算系统时常使用硬件系统进行纠错，不希望有庞大的编码系统，总是想要以最小的硬件带价完成工作，因此我们利用了下面这条性质：对于有出错的数据串，其余数末尾加0并求对\(G(x)\)的余数，可以得到下一行的余数。（补0后若最高位为1，则用除数做模2减取余；若最高位为0，则其最低3位就是余数）
例如：

e.g.1
  0010 //补0
^   1011 //位数不够，直接取后3位为余数
   010 //余数,为下一行

e.g.2
  1000 //补0
^ 1011
= 0011 //余数011

??利用这个循环性质我们可以在进行余数循环的同时，将数串向左循环移动一次，并且对其中某一种错误进行译码，当余数被译码时，修改对应位置，这样能将移动过去的错误代码修改，再继续上述操作直至余数循环回原本的余数，此时修改过的数串也会回到原位。这里的余数循环起到了一种计数的效果。

假设译码状态为101，则当余数变为101时对第一位进行修改。下面以1100010为例，完成一次纠错

参考资料

计算过程：
数学：
https://en.wikipedia.org/wiki/Cyclic_redundancy_check#Mathematics
https://en.wikipedia.org/wiki/Mathematics_of_cyclic_redundancy_checks
计算过程可视化：https://www.bilibili.com/video/BV1V4411Z7VA
纠错原理和余数循环：https://blog.csdn.net/neufeifatonju/article/details/89353958