董高云，孙军峰

（卡斯柯信号有限公司，上海 200071）

CRC查表法的推广及其在iLOCK联锁系统中的应用

董高云，孙军峰

（卡斯柯信号有限公司，上海 200071）

通过整数字节的CRC查表算法，改进了CRC编码校验算法的效率；同时经过推导证明，可以将传统的16 bit或32 bit的整数字节CRC查表法，推广至小于16 bit或32 bit的任意位数信息位的非整数字节。随后将这两种CRC查表法，应用到iLOCK计算机联锁系统中的冗余编码运算中，提高了冗余编码计算的运算效率及iLOCK系统的整体性能。

CRC；查表法；计算机联锁；冗余编码

循 环 冗 余 编 码 检 验 技 术（CRC，Cyclic Redundancy Check）被广泛应用于通信传输领域。由于其实现简单，检错能力强，被广泛使用在各种数据校验应用中。它占用系统资源少，用软硬件均能实现，是进行数据传输差错检测的一种很好的手段[1～5]。卡斯柯信号有限公司 iLOCK 联锁系统[3～4]下位机的冗余编码就采用了多种不同的CRC循环冗余编码校验算法。

由于采用硬件实现 CRC循环冗余编码需要专用的移位寄存器电路，且硬件电路的调整不够灵活，因此在 iLOCK 联锁系统中采用软件来实现 CRC 冗余编码。由软件完成 CRC 计算，即 CRC 的算法问题[5]，许多相关的文献中对此均有描述，软件CRC算法普遍存在相对于硬件 CRC 算法耗时长的缺陷。

联锁下位机系统作为高实时的嵌入式系统，为了适应大站场时的大规模联锁逻辑运算的需求，对于计算效率的要求比较高。为了提高效率，需要尽量减少CRC计算的耗时，以改进软件CRC算法耗时长的缺陷，为此，编程人员提出了众多的解决方法，CRC 查表法是最常用的一种缩短计算耗时的方法。

本文阐述单字节的CRC算法原理，通过建立单字节CRC表格，实现双字节迭代CRC查表法，并将其应用于 iLOCK 联锁系统中。通过证明和推导，将整数字节的数据位的CRC查表法推广至任意位数据位的非整数字节。随后也将其应用于 iLOCK 联锁系统中，大幅度提高了冗余编码计算效率，从而提高了 iLOCK 系统的整体性能。

1 单字节CRC算法及CRC查表法简介

CRC 的计算原理说明如下 :

下面为一个二进制除法计算过程，假设待计算CRC 的原始数据为一个字节 0xd8（11011000），CRC生 成 多 项 式 取 为 0x17d3b（10111110100111011），则以 0xd8 为被除数，以生成多项式为除数，进行二进制除法运算。计算原理见文献 [1]。由于生成多项式为2个字节，进行除法运算时，被除数需要在其后 补 齐 2 个 字 节 的 0， 变 为 :0xd80000（11011000 00000000 00000000）。

上面计算 的余数为 0xdaab（1101101010101011），即为原始数据 0xd8 的 CRC 校验码值。这就是单字节 CRC 计算原理。

对于所有的单字节原始数据（信息码）（取值范围为 :0x00～0xff）采用上述的多项式除法，都唯一对应一个双字节的余数（CRC 校验码），全部的单字节数据及其对应的双字节余数（CRC校验码）即可组成一张表，于是可编写程序代码按上式的计算方法生成一张信息码—校验码对照表，求取单字节的信息码所对应的校验码的过程就简化为了查表过程，缩短了多项式除法的计算时间，这就是通用的单字节查表法。

构造上述 16 bitCRC 表的 C 语言程序如下 :

说明如下 :aPoly 为除数（生成多项式）但注意要去掉最高位，只保留低 16 bit双字节。nData 即为0～255 的单字节原始信息位数据，Table_CRC[i]即为生成的校验码表，共有 256 个值，对应 0～255 的信息位 nData。nAccum 为中间余数，初值为 nData。当中间余数最高位为1时，下一次的除法运算的中间余数就是本次中间余数移位后和 aPoly 异或的结果，否则只需将本次中间余数移位即可[3]。

2 多字节CRC迭代查表算法及其在iLOCK联锁系统中的应用

上述单字节查表法仅解决了单字节信息位数据的校验码求取问题，对于2个字节的数据，作如下分析:

为与单字节的情况作比较，将两字节拆开计算，先看高字节数据D1的计算:

上述运算中将每移位一个字节的单字节除法运算作为一个阶段，称为1次，则2个字节共有2次余数。

比较双字节运算和高字节运算的第1次余数A’和 HA’。先看低字节余数 A0’和 HA0’:注意到两种运算被除数的第 2 个字节均为 0x00，而第 1 次的余数的低字节数据只与被除数的第2个字节和除数的移位有关，根据前述的单字节查表法原理知，除数的移位操作只与被除数的最高字节D1有关，由于两种运算的D1值相同，因此除数的移位也完全相同，故有 :A0’=HA0’。

再 看 高 字节余 数 A1’和 HA1’。 双 字 节运算的 A1’=D0^p1^p2^…^p8，p1～p8 为逐 位 移 位运过程中与高字节被除数的第 3 个字节 0x00 相对齐的除数（生成多项式）的一个字节的部分码位。而高字节运算 HA1’=0x00^p1^p2^…^p8，同样根据前述的单字节查表法原理知，由于两种运算的被除数最高位 D1 值相同，故除数移位也完全相同，即 p1～p8与 高 字 节 运 算 的 p1～p8 也 相 同， 再 根 据 逻 辑 代 数的相关运算定律，逻辑代数运算满足结合律，且有 data=0x00^data, 故 A1’=D0^(p1^p2^..p8)= D0^(0x00^p1^p2^…p8)=D0^HA1’。

由上面的分析可知，可直接根据高字节运算的第 1 次余数值 HA0’，HA1’和低字节数值 D0 来计算出 A0’，A1’，而高字节的第1次余数实际上就是单字节CRC运算，可直接由前述的单字节查表法程序查表算得。

设查表法计算的函数为 PA=f(D)，D 为单字节数据，PA 为余数值，则 A1’=HA1’^D0=(HA’＞＞8)^D0=f(D1)＞＞8^D0。A0’=f(D1) && 0x00FF。

接下来的第2次余数值计算与第1次结构完全相同，仅将 D1，D0换成了A1’，A0’，对于 N 个字节的数据，则有n次结构相同的迭代运算，设单字节第 n 次的查表法计算所得余数为 PA(n)，则第n次的余数为:

式（1）解释如下:d 为第 n-1 次的余数的高 8 bit值，d=(PA(n-1)＞＞8)^D(n)

第 n-1 次余数的高 8 bit在由单字节查表算出后，还需与双字节原始数据的低字节 D(n)异或。

第 n 次余数值先由第 n-1 次余数的高 8 bit值 d查表算出 f(d)，然后需将 f（d）的高 8 bit与第 n-1次 余 数 的 低 8 bit PA（n-1） 异 或（ 类 比 前 述 A1’=D0^HA1’），异或前先将 PA（n-1）左移 8 bit以便与 f（d）高 8 bit对齐。

于是总的迭代公式可表示为:

式（2） 中 的 函 数 f(d) 的 实 现 由 前 述 的 16 bit CRC 查表程序完成。

据此编写的计算多字节数据的 16 bit CRC 值的C语言程序如下:

上面的 程 序 中，0x7d3b 为 16 bit生成多项式，首先调用 BuildTable16 函数建立信息码 -校验码的对照表 CRCTable1，然后在 CRC_16 函数中可迭代查表。*aData 为指向一个单字节数据的指针，aSize 则为总共的字节个数。

利用上述的多字节迭代查表算法，可以求出整数个字节的数据的CRC校验码，当除数（生成多项式）为 16 bit时，相应的余数（CRC 校验码）也为双字节 16 bit数。这样，对于 0x0000～0xFFFF 范围内的每一个数据，都有唯一对应的CRC校验码，组合起来可以构成冗余编码值用于冗余编码运算。

在 iLOCK 联锁系统中采用了双字节的数据及其CRC 校验码共同组成冗余码字，进行 NISAL 码字运算。为了提高运算效率，将上述的多字节迭代CRC查表算法引入到 iLOCK 联锁系统的冗余码字校验中。方法说明如下:

假 设 一 个 4 字 节 的 冗 余 码 字 为 D（DH，DL），其中 DL为原始数据位，DH 为其 CRC校验码，则可采用上述的多字节迭代CRC查表算法检验DH是否为DL所对应的正确的CRC值，以下程序中aData[0],aData[1] 分别为 DL 双字节数据位的高、低字节，通过双字节的迭代CRC查表法，算出CRC值 DH，左移 16 bit后，再与 DL 组合为最终的结果值 result，判断 result如果与 D 相同，则通过校验，否则不通过。

3 CRC查表法的推广——非整数字节的任意信息位编码的查表及其在iLOCK联锁系统中的应用

以上叙述了通用的CRC算法及查表法，以及基于该表格的多字节的迭代 CRC查表运算。更多字节（如 32 bit）的 CRC 查表法可依此类推。该算法已成功被应用到 iLOCK 联锁系统的冗余编码运算中，极大地改善了采用传统移位算法进行CRC运算的计算效率。

除了上述CRC应用外，在编码领域，大量的场合还需要用到非整数个字节的数据的CRC冗余编码，例如 :7 bit原始数据位，15 bit数据位等。本文将要证明在非规则的多项式除法运算的情况下，非整数个字节的数据位编码也可采用类似上面的规则多项式除法和整数个字节的方法实现查表法求取校验码字，并给出相关的实现程序。随后，同样将这类非整数个字节的 CRC 编码运算应用到 iLOCK 系统的冗余编码运算中。

图1 为非规则的 7 bit移位 CRC 算法，一个 4 字节的 32 bit原始数据左移 7 bit（在其后添加 7 个 0）后再与 32 bit生成多项式 aPoly 进行多项式除法运算，最终的 7 步除法后的余数（32 bit）即为此非规则的CRC校验码值。

图1 非规则的7位移位CRC算法

这种非整数字节的移位CRC算法参照前述的CRC算法，可用以下的代码实现 :

以下将证明，上述的按位移位的CRC算法仍然可以采用查表法来实现，说明如下:

将原始数据D分拆为高低两部分数据，高位数据 DH 为 7 bit(hhhhhhh)，低位数据 DL 为 25 bit(lllll llllllllllllllllllll)，则仅仅高位数据的多项式除法运算可表示为:

根据函数中定义的逻辑运算规则知，每一步运算中P是直接移位还是要进行异或运算，取决于每步移位操作中的最高位，实际上就是高位数据DH的各位状态，故上面的实际数据D的运算和高位数据H 的运算过程中，由于高 7 bit均为 H，故总共 7 步除法的移位/异或操作过程相同。将上两个运算的余数 A，A’分别拆为 A1、A0 和 A1’、A0’，A1,A1’为余数的高 25 bit，A0、A0’为余数的低 7 bit，则由于 A0，A0’所对应的原始数据都为补齐的 7 个 0，故 A0=A0’，而 A1 和 A1’所对应的原始数据分别为 DL（25 bit低位数据）和 0，且有 :

A1=DL^p1^p2…^p7，A1’=0^p1^p2…^p7。由于两种运算中高 7 bit数据 DH 相同，故 7 步除法中的移位 /异或操作过程相同，从而 7步运算的异或值p1～p7 在两种运算中相同，又 data=data^0。故有 :

A1=DL^0^p1^p2 … ^p7=D L^(0^p1^p2 …^p7)=DL^A1’。

即 :原始数据的余数的高 25 bit值等于原始数据的高 7 bit数据的余数与其低 25 bit数据相异或，而原始数据的余数的低 7 bit值就是原始数据高 7 bit数据的余数值的低 7 bit值。

DH的余数A’在生成多项式确定的情况下，只随着DH的改变而改变，于是可以遵循上面的运算规则生成一张 DH 与其余数 A1’相对应表格。采用查表法计算上述冗余编码的程序可表示为:

计算最终的原始数据的余数时，再将上述查表结果 A’^（DL＜＜7）, 即可求出 A。其低 7 bit就是A’的低 7 bit，高 25 bitA’需要与原始信息位的低25 bit异或（需左移 7 bit以对齐），最终高低位拼起来就组成了A。利用生成的表格进行查表运算和后续处理的函数为:

以上非规则的移位 CRC 算法同样被用于 iLOCK联锁系统中的冗余编码运算中，从而大幅度提高了运算效率，使得整体的冗余编码运算速度大幅度加快，从而提高了 iLOCK 系统的整体性能。

4 结束语

循环冗余编码CRC校验算法被广泛应用于各种数据校验中。用软件实现的CRC算法效率较低，在实际应用中需要通过查表法来提高运算效率。本文基于单字节信息位的 16 bit CRC 冗余码，建立了 16 bit的CRC表，并且推导了基于该CRC表进行多字节查表的算法，将其应用于 iLOCK 联锁系统的下位机冗余编码运算中，经过理论推导，进一步将整数字节的查表法推广至任意位数信息位的查表算法，相关的算法也应用到了 iLOCK 联锁系统的冗余编码运算中。经测试，查表算法的应用能大幅度提高冗余编码计算效率，提高 iLOCK 系统的整体性能。

[1] 沙 依（美）.数据通信与网络教程 [M].高传善 ,译 .北京：机械工业出版社，2000.

[2] 杨萃南 .数字电子技术与逻辑设计教程 [M].北京 ：电子工业出版社，2003（4）.

[3] 姜坚华 .iLOCK 的安全模型和安全性分析 [J]. 铁道通信信号，2010（7）.

[4] 吕永昌，林瑜筠 . 计算机联锁 [M]. 北京 ：中国铁道出版社，2007（4）.

[5] 冯翔宇 .循环冗余校验码 CRC 算法分析与实现 [J].中国 科技信息，2010（21）.

责任编辑 方 圆

CRC table look-up method’s extension and its application in iLOCK Interlocking System

DONG Gaoyun, SUN Junfeng
( Casco Signal LTD., Shanghai 200071, China )

The ef ciency of CRC Code Veri cation Algorithm was improved by CRC Table Lookup Algorithm of integer byte. The derivation showed that the traditional CRC Table Lookup Algorithm for 16 bit or 32 bit of integer byte could be extended to less than 16 bit or 32 bit of non integer byte of arbitrary. Two kinds of CRC Table Lookup Algorithm were successfully applied to the redundant coding calculation in iLOCK Interlocking System, greatly improved the ef ciency of the redundant coding calculation. So the total performance of iLOCK System was improved.

CRC; Table Lookup Algorithm; computer interlocking; redundant coding

U284.3∶TP39

：A

1005-8451（2015）01-0040-06

2014-01-23

董高云，高级工程师；孙军峰，高级工程师。