先聊聊奇偶校验

所谓通讯过程的校验是指在通讯数据后加上一些附加信息，通过这些附加信息来判断接收到的数据是否和发送出的数据相同。校验得通信双方都有才行，接收方收到数据后进行计算得到一个校验值，与发送方发的校验值比较，如果校验值相等，则说明数据传输无误，否则可丢弃数据。

比如说串口通信中可以设置奇偶校验位。奇偶校验(Parity Check)是一种校验代码传输正确性的方法。根据被传输的一组二进制代码的数位中“1”的个数是奇数或偶数来进行校验。采用奇数的称为奇校验，反之，称为偶校验。采用何种校验是事先规定好的。通常专门设置一个奇偶校验位，用它使这组代码中“1”的个数为奇数或偶数。若用奇校验，则当接收端收到这组代码时，校验“1”的个数是否为奇数，从而确定传输代码的正确性。

这里有个问题需要确认：传输数据时，分为数据位和校验位，奇偶校验里的奇或偶是针对数据位还是数据位加校验位一起呢？答案是加一起校验。

采用奇校验，发送方通过添加校验位使得发送的数据中1的个数为奇数，然后接收方就会进行奇校验（数据位+校验位），如果数据位加上校验位里1的个数为奇数个，则验证成功，表明数据有效。

采用偶校验，发送方通过添加校验位使得发送的数据中1的个数为偶数，然后接收方就会进行偶校验（数据位+校验位），如果数据位加上校验位里1的个数为偶数个，则验证成功，表明数据有效。

来梳理一下：

如果我们要发送的字节用二进制表示为0001 1010。

采用奇校验，则在数据后补上个0，数据变为0001 1010 0，使得数据中1的个数为奇数个（3个），接收方校验1的个数为奇数；

采用偶校验，则在数据后补上个1，数据变为0001 1010 1，使得数据中1的个数为偶数个（4个），接收方校验1的个数为偶数。

接收方通过计算数据中1个数是否满足奇偶性来确定数据是否有错。

如果我们要发送的字节用二进制表示为1001 1010。

采用奇校验，则在数据后补上个1，数据变为1001 1010 1，使得数据中1的个数为奇数个（5个），接收方校验1的个数为奇数；

采用偶校验，则在数据后补上个0，数据变为1001 1010 0，使得数据中1的个数为偶数个（4个），接收方校验1的个数为偶数。

接收方通过计算数据中1个数是否满足奇偶性来确定数据是否有错。

奇偶校验的缺点也很明显，首先，它对错误的检测概率大约只有50%。也就是只有一半的错误它能够检测出来。另外，每传输一个字节都要附加一位校验位，对传输效率的影响很大。因此，在高速数据通讯中很少采用奇偶校验。不过奇偶校验优点也很明显，它很简单，因此可以用硬件来实现，这样可以减少软件的负担。因此，奇偶校验也被广泛的应用着。

奇偶校验就先介绍到这来，之所以从奇偶校验说起，是因为这种校验方式最简单，而且后面将会知道奇偶校验其实就是CRC 校验的一种(CRC-1)。

累加和校验

另一种常见的校验方式是累加和校验。所谓累加和校验实现方式有很多种，最常用的一种是在一次通讯数据包的最后加入一个字节的校验数据。这个字节内容为前面数据包中全部数据的忽略进位的按字节累加和。比如下面的例子：

我们要传输的信息为： 6、23、4

加上校验和后的数据包：6、23、4、33

这里 33 为前三个字节的校验和。接收方收到全部数据后对前三个数据进行同样的累加计算，如果累加和与最后一个字节相同的话就认为传输的数据没有错误。

累加和校验由于实现起来非常简单，也被广泛的采用。但是这种校验方式的检错能力也比较一般，对于单字节的校验和大概有1/256 的概率将原本是错误的通讯数据误判为正确数据。之所以这里介绍这种校验，是因为CRC校验在传输数据的形式上与累加和校验是相同的，都可以表示为：通讯数据校验字节（也可能是多个字节）

CRC校验

CRC在线计算：CRC（循环冗余校验）在线计算_ip33.com

首先了解下两个概念：

概念1：模二运算

模2运算是一种二进制算法，CRC校验技术中的核心部分。与四则运算相同，模2运算也包括模2加法、模2减法、模2乘法、模2除法四种二进制运算。与四则运算不同的是模2运算不考虑进位和借位，模2算术是编码理论中多项式运算的基础。

模二加法：

所谓“模2加法”就是0和1之间的加法，其中0+0=0，1+0=0+1=1，1+1=0，不带进位，比如：

模2加的定义可以得出一个重要结论：奇数个1相加得1，偶数个1相加得0。这个结论在奇偶校验中是很有用的。

模2减法：

是一种不考虑借位的减法,其定义如下：0-0=0，1-1=0，1-0=1，0-1=1，如下：

其实，模2减法和模2加法得到的结果也是一模一样的，所以模2加法和模2减法实际上是一回事，所有用模2减法的地方都可用模2加法来代替，故不用给模2减法定义专用的符号。

另外，模2减法的结果和位异或是一样的。

模二乘法：

一位数的模2乘法定义如下：0×0=0，0×1=0，1×0=0，1×1=1，多位数的模2乘法与普通乘法一样演算，如：

唯一的区别是，部分积相加时按模2加。

模2除法：

和普通除法类似，区别就是在步骤中相减时使用的是模2减法，即不带借位。

模2除法具有下列三个性质：

1、当最后余数的位数小于除数位数时，除法停止。

2、当被除数的位数小于除数位数时，则商数为0，被除数就是余数。

3、只要被除数或部分余数的位数与除数一样多，且最高位为1，不管其他位是什么数，皆可商1。

模2算术是编码理论中多项式运算的基础。模2算术在其他数字领域中的应用也是很广泛的。

概念2：多项式除法（注，以下xn表示x的n次幂）：

比如多项式x4+x3+x2+x1+x0除以另一个多项式x+1

得到商为x3+x，且余数为1

了解了以上两个概念，接下来就开始讲CRC校验了。

循环冗余校验（Cyclic Redundancy Check， CRC）

CRC校验计算速度快，检错能力强，易于用编码器等硬件电路实现。从检错的正确率与速度、成本等方面，都比奇偶校验等校验方式具有优势。因而，CRC 成为计算机信息通信领域最为普遍的校验方式。

CRC校验就是借鉴多项式除法的思想，将多项式化成对应的二进制，并将其作为除数，待校验的数据作为被除数，通过模2除法得到最后的余数，该余数即为CRC校验值。

多项式如何对应二进制呢？

多项式的次幂从高到低，有该次幂的就对应二进制的1，没有该次幂的就对应二进制的0，可以理解成多项式各次幂的系数。

比如：

x4 +x3+x2+x1+x0就对应二进制11111，因为从高到低的次幂都有；

x4 +x2+1就对应二进制10101，只有次幂存在的才对应二进制的1。

CRC校验有很多种，比如CRC-4/CRC-8/CRC-16/CRC-32等，分别对应的是多项式的最高次幂，比如多项式x4 +x3+x2+x1+x0对应的就是CRC-4校验。

其实，不管是哪种校验，都要先指定一个多项式或者对应的二进制形式。

以下举例说明CRC的校验步骤：

要发送的数据为1101011011，采用CRC校验，生成多项式为10011，则最终发送数据为多少？

步骤如下：

1、待校验数据末尾补0，多项式最高次幂是几次幂就补几个0，也就是说，比多项式位数少一位，这里多项式为5位，说明最高次幂是4次幂，也就是CRC-4，则补4个0。那么，被除数构造成了11010110110000

2、被除数通过模2除法来除以多项式10011

3、得到余数1110，放到待发送数据后，则最终发送数据为：11010110111110

接收方在接收到数据后，进行CRC校验，如果余数为0，则为有效数据，否则数据无效。

这里因为将余数加到了待发送数据后面，所以如果数据没出错，则余数会为0。

注意：除数10011也可以以多项式形式x4+x+1给出

CRC参数模型

由以上内容可知，CRC校验有很多种，同一种也可能有不同的生成多项式。

同样的CRC多项式，调用不同的CRC计算函数，得到的结果却不一样，而且和手算的结果也不一样，这就涉及到CRC的参数模型了。计算一个正确的CRC值，需要知道CRC的参数模型。

常用的21个标准CRC参数模型：

CRC算法参数模型解释：
NAME：参数模型名称。
WIDTH：宽度，即生成的CRC数据位宽，如CRC-8，生成的CRC为8位。
POLY：生成项的简写，以16进制表示。例如：CRC-8多项式对应的二进制为100000111，最高位肯定是1，所以省略了，直接写000001111，即0x07。
INIT：这是算法开始时寄存器（crc）的初始化预置值，十六进制表示。计算后寄存器（crc）放的就是CRC校验值了。

XOROUT：计算结果与此参数异或后得到最终的CRC值。
REFIN：待测数据的每个字节是否按位反转，True或False。注意这里是按字节来反转的，而且，这里的反转不是按位取反，也不是正负反转，而是顺序颠倒，比如0101，顺序颠倒后变成了1010，MSB和LSB颠倒的意思。
REFOUT：在计算之后，异或输出之前，整个数据是否按位反转，True或False。注意这里是整个数据都颠倒顺序。

是否是每个字节还是整个数据反转，在大于8位时才有明显区别。比如二进制数据01110111 00111110，共16位：

按字节反转1110111001111100

整个数据反转0111110011101110

数据反转的理解可能有三种：按位取反、正负反转，另外还有一种是前后颠倒，看到类似说法时要十分注意。

以下以CRC-4/ITU为例来说明：

对二进制数据11010110进行CRC-4/ITU校验。

生成的校验值将会是4位；

对应的多项式为10011；

CRC初始值为0000；

输入会反转，即待校验的数据变成了01101011

经计算，最后的余数为11，即0011

输出反转，变成1100

跟0000异或，保持不变，所以最终CRC校验值为1100

用CRC计算器验证下看看：