CRC校验算法详解

        数据在传输过程（比如通过网线在两台计算机间传文件）中，由于传输信道的原因，可能会有误码现象（比如说发送数字5但接收方收到的却是6），方法发送额外的数据让接收方校验是否正确，这就是数据校验。常用的校验方法是和校验，就是将传送的数据(按字节方式)加起来计算出数据的总和，并将总和传给接收方，接收方收到数据后也计算总和，并与收到的总和比较看是否相同。如果传输中出现误码，那么总和一般不会相同，从而知道有误码产生，可以让发送方再发送一遍数据。

        CRC即循环冗余校验码（Cyclic Redundancy Check）：数据通信领域中最常用的一种差错校验码，其信息字段和校验字段长度可以任意指定，但要求通信双方定义的CRC标准一致。

        在K位信息码（目标发送数据）后再拼接R位校验码，使整个编码长度为N位，因此这种编码也叫（N,K）码。通俗的说，就是在需要发送的信息后面附加一个数（即校验码），生成一个新的发送数据发送给接收端。这个数据要求能够使生成的新数据被一个特定的数整除。这里的整除需要引入模 2除法的概念，CRC校验的过程

（1）选定一个标准除数（K位二进制数据串）

（2）在要发送的数据（m位）后面加上K-1位0，然后将这个新数（M+K-1位）以模2除法的方式除以上面这个标准除数，所得到的余数也就是该数据的CRC校验码（注：余数必须比除数少且只少一位，不够就补0）

（3）将这个校验码附在原m位数据后面，构成新的M+K-1位数据，发送给接收端。

（4）接收端将接收到的数据除以标准除数，如果余数为0则认为数据正确。

        注意：CRC校验中有两个关键点：一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串（或多项式）；二是把原始帧与上面选定的除进行二进制除法运算，计算出FCS。前者可以随机选择，也可按国际上通行的标准选择，但最高位和最低位必须均为“1”

实例：对于数据10110011（16#B3），以指定除数110011求它的CRC校验码，其过程如下：

        这里需要知道几个组成部分或者说计算概念：多项式公式、多项式简记式、数据宽度、初始值、结果异或值、输入值反转、输出值反转、参数模型。

（1）多项式公式

        对于CRC标准除数，一般使用多项式（或二项式）公式表示，如上例中除数11011的二项式为G(X)=X4+X3+X+1，X的指数就代表了该bit位上的数据为1,（最低位为0）。这里特别注意一下位数问题，除数的位数为二项式最高次幂+1（4+1=5），这个很重要。

（2）多项式简记式

        通过对CRC的基本了解我们知道，多项式的首尾必定为1，而这个1的位置在下一步计算一定为0，所以就把前面这个1给省略掉了，出现了一个叫简记式的东西，如上例中除数11011的简记式为1011，很多看过CRC高级语言源码的人会知道，对于CRC_16标准下G(X)=X16+X15+X2+1（16#18005）的poly值实际上是8005，这里使用的就是简记式。后面会对这个用法做一个说明。

（3）数据宽度

        数据宽度指的就是CRC校验码的长度（二进制位数），知道了CRC的运算概念和多项式，就可以理解这个概念了，CRC长度始终要比除数位数少1，与简记式长度是一致的。

        以上三个数据就是我们经常能够用到的基本数据

（4）初始值与结果异或值

        在一些标准中，规定了初始值，则数据在进行上述二项式运算之前，需要先将要计算的数据与初始值的最低字节进行异或，然后再与多项式进行计算。

        而在结果异或值不为零的情况下，则需要将计算得到的CRC结果值再与结果异或值进行一次异或计算，得到的最终值才是我们需要的CRC校验码。

这里可以看出，初始值与结果值的位数要求与数据宽度一致。

（5）输入值反转与输出值反转

        输入值反转的意思是在计算之前先将二项式反转，然后再用得到的新值和数据进行计算。如对于G(X)=X16+X15+X2+1（16#18005），其正向值为1 1000 0000 0000 0101，反转值则为1010 0000 0000 0001 1

        输出值反转则是将最终得到的CRC结果反转。

        通常，输入值反转后的结果值也会是反转的，所以这两个选项一般是同向的，我们只有在在线CRC计算器中会看到自由选择正反转的情况存在。