一种新的CRC16算法及其在通信系统中的应用

何秉姣，汪 红

(中南民族大学计算机科学学院，武汉430074)

通信系统遵循公认的通信协议以数据包等形式进行数据交换，实现资源共享.例如通信系统中有主机A和主机B，主机A将数据传送给主机B前，两者必须建立数据通信线路，保证高效准确的数据通信.正常情况数据包P与数据包P'一致，当通信受到干扰时，数据包P与数据包P'不一致，即数据包P'出现差错，必须予以及时处理.循环冗余校验码CRC(Cyclic Redundancy Check)在数据通信线路中能很好地校验所传输信息的正误［1，2］.

1 CRC串行算法

1.1 数据包格式

主机A将数据传送给主机B时，主机A先将较长报文划分成一个个小的等长的数据段，在每个数据段前加上首部，末尾加上校验码，就构成一个数据包，传输到通信线路上.数据包到达主机B后，主机B能从数据包中得到所需要的各种控制信息和传输的有效信息.数据包的格式如下.

SOH 序号 长度 数据 CRC校验码

其中，SOH是包头，序号是报文组序，长度是本数据包中数据的字节数，数据是传输的有效信息，CRC校验码是通过CRC算法计算出来的本数据包中数据的CRC码.

在报文的数据包传输协议中，主机A算出CRC校验码，并拼装在数据包尾部.主机B校验器接收到数据包后，用同样的CRC算法算得新的CRC码，并与接收到的CRC码进行比较.若两组CRC码值相等，则接着传输下一个数据包，否则说明传输中有差错，给予有效处理.

1.2 CRC16串行算法及其实现

主机A的CRC编码器将传送的32bit数据序列D={d31，d30，…，d1，d0}看成是系数为 0 或 1 的多项式D(x)=d31x31+d30x30+…+d1x+d0，用预定的生成多项式G(x)=x16+x12+x5+1，将D按照模运算法则产生一个长度为16bit的两字节序列R={r15，r14，…，r1，r0}，R 即为 D 的 CRC 码，计算 R(x)的步骤如下.

(i)形成被除数方程:

(ii)构造余数R(x)方程为:

其中Q(x)为多项式运算的商，R(x)即为数据序列D的余式多项式.

(iii)M多项式方程为:

主机B的校验码将收到的M'(x)采用以上同样的方式计算出余数R'，与R比较，根据结果是否为零来判断传输过程是否无误.

其实现方法包括软硬两类方法.一般采用硬件方法实现.以往CRC硬件实现一般采用串行移位异或算法，其电路结构如图1所示.

图1 CRC16串行移位结构Fig.1 Serial shift structure of CRC16

图1中包括16个保存中间结果的D触发器和15个异或门，在48个时钟里Din端输入数据序列x16·D(x)48位，前32位是原始数据，后16位是0.D 触发器输出 R15，R14，…，R1，R0就是要求的 CRC值［3-5］.数位越长，求CRC码时间越长，这种通过时间换空间循环逐位实现的算法难以满足日益高速的数据通信需要.为了适应现代通信高速传输数据，本文设计了一种新的并行输入CRC16校验算法.

2 通信系统中CRC16并行算法及其实现

基于 R(x)算法，用数据为 D(x)=11010111011，G'(x)=10011列竖式模2除如图2所示.

图2 模2除Fig.2 Division of mode 2

据图2，余数最高位为1，则余数与G'异或再移位，否则与零异或再移位，由于与零异或等于不做异或运算，另外，由于余数最高位为零的情况至少占一半，那么设计新算法可省去至少一半的异或运算，当余数最高位为零时，直接移位，这加快CRC码的形成.

先设计第i位处理方法.令余数最高位R高，对应除数Gi，时钟到来前第i－1位余数的现态Ri－1，时钟到来后第i位次态Rn+1i，可列出其逻辑关系如表1所示.

表1 第i位次态逻辑关系Tab.1 Logical relationship of next state the i bit

根据表1，用卡诺图化简法得第i位的次态方程为:

据此推导出通信系统中CRC16的次态方程组为:

上述逻辑关系表明当R最高位为1时，Rn+1i是异或求得，否则直接移位;CRC的值只与当时输入的16位生成表达式G和电路现态Ri有关.因此采用层次结构模式可实现通信系统中CRC16并行算法.

基于公式(4)设计的CRC16模块被重用17次，由公式(4)推导式设计的CRC165被重用3次，再组合成图4实现通信系统中CRC16校验编码电路，系统层次设计模式能实现模块化和元件重用.根据实际需要用CRC165可以组装成任意生成多项式，也能并行处理任意长度的数据序列.

3 CRC16并行算法仿真结果分析

在硬件系统设计中，主要进行3次仿真:行为仿真、RTL仿真和门级仿真.一般前两种为功能仿真，后一种为时序仿真.功能仿真验证设计模块的逻辑功能，时序仿真验证设计模块的时序关系.对于CRC模块的仿真采用的是功能仿真，主要是验证该模块是否可以正常工作.

整个设计是在 Quartus 9.0 平台下进行［6，7］，设计输入编译后仿真.仿真目录包含以下文件:输入输出、并行文件、配置文件等.主机A向主机B发送数据包前，用CRC1616编码器模块形成CRC码.其仿真结果如图3所示.

图3 CRC16仿真波形图Fig.3 Simulation waveform of CRC16

其中 D(x)=8D6F646Eh，G(x)=11021h，首先初始化8D6Fh，第一个时钟上跳沿到来后R中的值依次为1ADEh，15FFh，2BFF，…，1962h 等直到 CRC 码32C4h的形成，最后M(x)=8D6F646E32C4h发往通信网络.主机B的校验器也采用同样的过程计算CRC码，如果等于32C4h，则数据包正确，否则反馈重发.在Alterra的EP1S25F672C6芯片下通过综合与仿真验证，CRC模块的最大时钟频率Fmax达到425.56MHz，能够满足高速通信系统的需要.

4 结语

本文通过分析CRC串行算法，得出了CRC并行实现的推理公式，与已有的方法［8］相比具有以下3个优点:(1)理论推导与现有的方法不同，本文推导过程清楚明了;(2)CRC码编码器模块采用层次结构，在硬件结构上很容易实现任意长度CRC码的形成，可适用于任意长度的生成多项式和并行处理位宽，即并行处理位宽可以小于、等于或大于CRC16的阶数16，而目前公开发表的文献多集中在并行处理小于、等于生成多项式的阶数的情况下进行讨论;(3)充分利用了数据0信息，减少至少一半的异或运算，加快了CRC的形成，电路综合结果具有很好的性能.该系统自成一体，用户只需对接口进行操作.因此，它既可独立使用，亦可配合其他系统作为其校验模块使用.

［1］王新梅，马文平，武传坤.纠错密码理论［M］.北京:人民邮电出版社，2001:48-73.

［2］Campobello G，Patane G.Parallel CRC realization［J］.IEEE Trans-Action on Computers，2003，52(10):1312-1319.

［3］Pei Tongbi，Zukowski C .High-speed parallel CRC circuits in VLSI［J］.IEEE Transations on Communications 1992，40(4):653-657.

［4］Lrvin D R.Cyclic redundancy checks with factorable generator［J］.IEEE.Proc-Commun，2003，150(1):179-191.

［5］何秉姣，刘 科.SEC-DED海明校验码算法研究及其FPGA实现［J］.中南民族大学学报:自然科学版，2012(3):89-92.

［6］俞建新，王 建，宋健建.嵌入式系统基础教程［M］.北京:机械工业出版社，2009:23-30.

［7］潘 松，黄继业.EDA技术与 VHDL［M］.3版.北京:清华大学出版社，2010:182-210.

［8］Robert H M.纠错编码的艺术［M］.2版.张立军，译.北京:北京交通大学出版社，2007:8-32.