EEPW论坛

CRC校验算法之数学原理

CRC，做为一名电子工程师肯定或多或少会在工作中听说过，因为有数据通讯的地方必定有CRC的存在。那么什么是CRC呢？CRC的全称是Cyclic Redundancy Check，中文多译为“循环冗余校验码”。

“循环冗余校验（英语：Cyclic redundancy check，通称“CRC”）是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者存储之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。一般来说，循环冗余校验的值都是32位的整数。由于本函数易于用二进制的计算机硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误，因此获得广泛应用。此方法是由W. Wesley Peterson于1961年发表。”——引自网络

上一篇文章中我们介绍了LRC校验算法(《竟然还有不到10行的校验算法？》https://forum.eepw.com.cn/thread/379500/1，LRC算法并不能校验出来大小端错误，如果错误较多，也存在校验不出来的情况，但今天要介绍的CRC则可识别的错误方面比LRC算法要强，也多用于检测在通讯中数据位的突变，数据传输错误等情况的发生。由于CRC校验算法应用太广，分支较多，因此我们今天也讲解一下其数学原理，其应用场景篇我们另文阐述。

GF(2)多项式

GF(2)多项式中只有一个变量x，其系数也只有0和1。比如x8+x2+x+1，使用GF(2)来表示：1*x8+0*x7+0*x6+0*x5+0*x4+0*x3+1*x2+1*x1+1*x0

模2除法

我们平时使用的除法是算法除法，而在CRC算法里面是模2除法。模2除法在形式上与算数除法相同，但模2除法没有借位操作。其实，模2除法就是异或命令操作。

生成多项式

生成多项式，Generator Polynomial，是指在校验过程与验证过程两侧使用的相同的除数。其也为一种GF(2)多项式。我们在上面提到的x8+x2+x+1，可以表示为100000111，记做0x07（忽略最高位）。

CRC校验原理

这里先表一个前提：CRC校验是按bit位来进行操作的，也就是说，其最小的单位是bit，而不是字节。

下面我们来说明CRC校验原理。我们先假设如下：

1. n = 待校验数据的位的个数；

2. k = 生成多项式的位的个数；

校验过程也只是三步：

1. 在待校验数据的末位添加k-1个0；

2. 对待样验数据使用生成多项式进行模2除法

3. 得到余数就是CRC校验数据

举例说明

我们对数据 0x10, 0x20, 0x30, 0x40进行数据传输，我们使用生成多项式0x07计算CRC8的值。

计算过程如下：

通过计算我们就得出来了CRC8的结果0x1A。

总结

通过与在线CRC校验工具的的对比，我们计算结果正确，原理正确。

下一篇，将继续分享CRC算法之具体应用场景。敬请期待……