李冠楠 李强

（顺德职业技术学院 电子与信息工程系，广东 顺德 528300）

1.CRC算法介绍

CRC校验采用多项式编码方法。利用生成多项式为k个数据位产生r个校验位进行编码，其编码长度为n=k+r，所以又称为（n，k）码。其编码格式如下：

1.1 编码规则[1]

设有k个数据位，需要添加r个校验位，n=k+r，其编码规则如下：

用W(x)=W W…W表示k个数据位，把W(x)左移r位，即相当于W(x)×2，给校验位空出r位来；

给定一个r阶的多项式E(x)，可以求出一个校验位表达式F(x)。E(x)称为该循环码的生成多项式。即如下表达式：

根据上面公式可知，用W(x)去除生成多项式G(x)，商为H(x)，余数则为R(x)。据此可得：

在CRC编码过程中，四则运算采用模2运算，即不考虑借位和进位。所以有：

M(x)+R(x)即为所求n位CRC码，它应是生成多项式G(x)的倍式，即可以被G(x)整除。

校验数据时用数据的n位CRC编码去除G(x)，若余数为0则说明数据正确，否则根据余数的值即可查出差错位。

1.2 生成多项式特点

生成多项式应满足以下条件：

（1）任何一位发生错误，W(x)×2+R(x)即CRC码除以G(x)的余数不能为0；

（2）余数继续作模2除，应使余数循环；

（3）若要能纠正一位错，则不同的码位错不能有相同的余数，且当给定生成多项式后，余数与出错位之间的对应关系应保持不变，与编码无关。

1.3 原算法实现[2]

/*以CRC-CCITT为例，按位计算CRC算法实现，不使用额外空间*/

从上述代码可知，直接基于问题的描述和所涉及的概念出发，利用按位计算CRC，虽然代码简单（也可采用模拟硬件电路按位操作加以实现），所占用的内存比较少，但其最大的缺点就是一位一位地计算会占用很多的处理器处理时间，尤其在高速通讯的场合，这个缺点更是不可容忍，因而实现对它的改进具有理论和实际的意义。……