基于查表法CRC检错码改进算法的研究与实现

周凯, 田枫, 李爱国

(1. 东北石油大学 计算机与信息技术学院,大庆 163318； 2.大庆油田工程有限公司,大庆 163712)

基于查表法CRC检错码改进算法的研究与实现

周凯1, 田枫1, 李爱国2

(1. 东北石油大学 计算机与信息技术学院,大庆 163318； 2.大庆油田工程有限公司,大庆 163712)

在工业现场通信过程中为保证数据传输的正确性，采用了CRC校验码，并且选择了基于查表法来提高生成CRC码的效率。通用查表法中每次计算出1个字节的CRC码，处理效率不高，所以提出了一种基于通用查表法的一种改进算法。改进后的算法每次处理2个字节，即计算出2个字节的CRC校验码，并且需要分别保留这2个字节的CRC码。下一组的2个字节信息输入后，借助前面两个字节的CRC校验码计算出后面两个字节的CRC校验码。以此类推，每一组的2个字节的CRC码都是在上一组2个字节的CRC码的基础上计算获得，直到所有信息输入完毕。在进行实验验证后，结果表明该算法运行时间相对有所减少。

基金会现场总线； CRC； 查表法； 校验码

0 引言

工业现场中，仪器仪表及各种自动化装置间的联网通讯已非常普遍，由于信道本身的原因及环境干扰因素，数据传输过程中出现差错几乎不可避免，误码的产生影响系统正常工作甚至引发灾难性后果，因此，数据接收方必须对数据的正确性进行判断以决定是否可用[1]。鉴于上述原因，在实际的通信过程中，多种校验算法不断发展，循环冗余校验(Cyclic Redundancy Check, CRC)作为一种特殊的线性分组编码被广泛应用于相关领域，最主要的原因就是查表法的计算速度快，纠错能力强[2][3]。

1 CRC校验码的原理及算法

CRC码的原理为将要发送的数据作为多项式F(x)的系数，这里系数的取值只能为0或1；多项式G(x)作为双方预先约定好的多项式，发送方用多项式F(x)除以G(x)，得到余数多项式CRC(x)；将CRC(x)附加到多项式F(x)后，发送到接收方；接收方将接收到的多项式除以G(x)，判断运算结果：如果最后的余数为0，则表示传输正确，如果余数不为0，则表示传输错误，请求重新发送。算法实现过程如下：

步骤1：设要发送的m位信息作为多项式F(x)的系数，则多项式为m阶多项式，最高阶为m-1，可表示为：

步骤2：设G(x)为发送方和接收方约定好的生成多项式，设G(x)为k阶，表示为：

步骤3：将要发送的数据向左移动K位，则变为M+K位的多项式，则为：

步骤4：用G(x)除多项式F’(x)运算，则求出余数CRC(x)，如式(1)。

(1)

步骤5：将余数CRC(x)直接附加到多项式F’(x)最后，则要发送的数据就变为F′(x)+CRC(x)，然后进行发送。

步骤6：接收端受到信息后，用G(x)对接收到的信息再进行模2除[4]运算，如式(2)。

(2)

步骤7：将式(1)代入式(2)中，得到式(3)。

(3)

步骤8：根据相同的序列按位异或的结果为0，所以式(3)可化为式(4)。

(4)

步骤9：根据式(4)可以看出，判断接收端是否正确，只需要看最后的运算结果是否有余数，如果无余数，则表示无差错，如果有余数，则说明有差错，重新发送。

根据上述步骤，计算出00-FFH所有的CRC校验码，计算过程中采用的生成多项式为国际标准CRC-16(即G(x)=x16+x15+x2+1，形成CRC-16校验码表[5]。

2 CRC查表法的基本理论

CRC查表法中是以单字节为单位，每个字节有28=256种情况，所以对应的CRC校验码也有256种。将这些校验码(256*2=512字节)存储于一个表中，根据输入的信息可直接在表中查找到相对应的CRC校验码。

2.1 通用查表法的实现

通用查表法的算法为设要输入的信息为F(1)，F(2)，F(3)，……，如图1所示。

图1 输入信息图

对F(1)进行查表，得到F(1)的CRC校验码CF(1)，取校验码CF(1)的高8位和F(2)进行异或运算得到F’(2)，取CF(1)的低8位和F(3)进行异或运算得到F’(3)，则输入信息变为F’(2)，F’(3)，……，以此类推，直到所有的信息全部执行完。具体过程如图1所示。在通用查表法中，每次仅处理一个字节的信息，直到所有的信息处理完毕，最后得到的就是此信息的CRC校验码。

2.2 CRC查表法的改进算法

通用查表法中，每次仅处理一个字节，改进后的算法与通用查表法最大的不同是一次处理2个字节。根据要发送的信息，首先处理第1个和第2个字节，即通过异或运算分别求出他们的CRC校验码，并且对这两个校验码分别进行保存，不进行合并处理；接下来读入下一组的2个字节信息，这2个字节的CRC码的计算需要借助于第一组中2个字节的CRC校验码才能计算出来，所以要求整个计算过程中不能对每组中的2个字节的CRC码进行合并；以此类推，每一组的2个字节的CRC码都是在上一组2个字节的CRC码的基础上计算获得，直到所有信息输入完毕；最后根据最后一个字节的CRC校验码计算出整个信息的CRC校验码。

改进的查表法的算法：设要输入的信息为F(1)，F(2)，F(3)，F(4)……，根据F(1)的数据查出所对应的16位校验码，命名为CRC(1)，那么它就是F(1)的校验码；F(2)的校验码CRC(2)的值是将F(2)与CRC(1)的高8位异或运算，得到的值进行查表得出；F(3)的CRC校验码CRC(3)的计算是用F(3)、CRC(1)的低8位和CRC(2)的高8位进行异或运算后，查表得出；同理F(4)的CRC校验码CRC(4)是用F(4)、CRC(2)的低8位和CRC(3)的高8位进行异或运算后，查表得出；以此类推，CRC(n)的值应为F(n)和CRC(n-2)的低8位和CRC(n-1)的高8位进行异或运算后查表所得。具体实现过程,如图2所示。

图2中，先计算出F(1)、F(2)的CRC码CRC(1)、CRC(2)，且没有进行合并处理。当F(3)、F(4)在同时读入时，根据改进的查表算法，分别算出F(3)、F(4)的CRC码，代替原来的CRC(1)、CRC(2)，保留至下次输入信息。整个发送信息的CRC码用最后一个字节的CRC码的高8位和上一个字节CRC码的低8位异或运算，得到的结果左移8位后加上最后字节的低8位。

3 实验设计与分析

实验系统中采用主/从结构的通信方式，即网络中制定一个站作为主站，负责控制所有的通信，主站采用轮询的方式进行通信，从站要在主站的启动下才能进行通信，负责接收信息。在保证数据传输正确性的同时，更重要的是进行传输后对比两种算法的时间效率。将要传送的数据存储在一个文件名为b.TXT文件中，然后根据两种不同的算法对该TXT文件进行读入，最终计算出该文档中数据的CRC码所花费的时间。

实验步骤如下：

步骤1：创建传送数据文本文件b.TXT，文件中包含若干字节的待传输数据。

步骤2：分别编写通用查表算法和改进的查表算法的程序，两种算法的流程图(假设传输数据的字节数大于2)如图3，图4所示。

步骤3：将要传送的数据文件导入两种算法中，分别计算出CRC码所花费的时间。为了解决其他软件可能占用时间，时间不稳定的问题，实验中将两种算法的程序运行不同的次数进行比较。

图2 改进的查表法的计算过程

图3 通用查法算法流程图

图4 改进查表法算法流程图

步骤4：对比运行结果，得出结论。

实验结果,如表1所示。

表1 计算同一文件两种算法的时间对比

从表1中的统计结果可以看出，运用改进的查表法计算CRC校验码所花费的时间较短，所以改进的查表法的算法是优于通用查表法的算法的。

4 总结

由于CRC校验码便于实现、纠错能力强，已经得到广泛的应用。工业现场通信系统中采用CRC校验能够提高数据传输的质量以及差错控制能力。本文提出的CRC校验码的改进算法，经过实验证明，改进的查表法不但能够保证传输的正确性，而且相对于通用查表法来说，缩短了生成CRC码的时间。

[1] 阳宪惠.现场总线技术及其应用[M].北京:清华大学出版社,2005:41-43.

[2] 王月琴,杨恒新. CRC码串并结合算法的研究与实现[J].计算机技术与发展 2014(6):103-106.

[3] 周赵斌,许力,李世唐.基于CRC的防污染网络编码方案[J].计算机系统应用.2016(25):101-106.

[4] 蔺冰.关于同余式2n≡4(modn)[J].安徽师范大学学报:自然科学版,2010,33(5)：425-427.

[5] 鹿玲杰.CRC检错码在基金会现场总线通信中的应用[J].南方冶金学院学报,2005,(8):22-26.

Research and Implementation of the CRC Improved Algorithm Based on Check Look-Up Table Algorithm

Zhou Kai1, Tian Feng1, Li Aiguo2

(1. School of Computer and Information Technology, Northeast Petroleum University, Daqing, 163318, China;2. Daqing Oilfield Engineer CO., Daqing, 163712, China)

In order to judge the correctness of data transmission in Industrial field, the Cyclic Redundancy Check look-up table algorithm is adopted in the CRC code. An improved algorithm is proposed based on general look-up table algorithm. It could read 2 bytes once, and calculate the CRC code of 2 bytes, but the two CRC codes does not been merged in the improved algorithm. After reading a group of 2 bytes information, according to the previous two bytes CRC code to calculate the following 2 bytes CRC code, until all the information input is completed. After the experimental verification, the results show that the running time of the algorithm is relatively reduced.

FF; CRC; look-up table; check code

国家自然科学基金项目(61502094)，黑龙江省自然科学基金项目(F2016002)

周凯(1979-)，女，黑龙江肇源，讲师，硕士研究生，研究方向：工业控制。 田枫(1980-)，男，黑龙江安达，副教授，博士研究生，研究方向：数据挖掘、图像处理。 李爱国(1979-)，男，山东菏泽，高级工程师，硕士研究生，研究方向：供配电。

1007-757X(2017)08-0012-03

TP311

A

2000.00.00)