基于AHB总线的快速并行CRC算法设计与实现

史兴强，刘梦影

（中科芯集成电路股份有限公司，江苏无锡214072）

基于AHB总线的快速并行CRC算法设计与实现

史兴强，刘梦影

（中科芯集成电路股份有限公司，江苏无锡214072）

循环冗余校验(CRC,Cyclic Redundancy Check)以其简单的算法、强大的检错能力和抗干扰能力，广泛应用于通信领域，以提高数据传输的可靠性。为满足高频率的数据传输要求，基于CRC基本原理，介绍了一种快速并行CRC算法，然后采用该算法基于高级高性能(AHB,Advanced High Performance Bus)总线，运用硬件描述语言Verilog HDL设计并实现了CRC计算模块。仿真结果表明，该算法能够在确保数据可靠性的同时提高CRC的计算速度。

CRC；快速；并行；AHB总线

1 引言

在数据通信过程中，由于通信传输特性不理想，且存在噪声和信道之间串扰等其他因素的干扰，因此接收端的信息可能发生错误决断[1]。为降低通信误码率，提高数据通信有效性，采用信道编码进行检错和纠错是必要的。

目前，常用的差错校验方法包括奇偶校验法、bcc异或校验法、md5校验法以及CRC法等[2]。奇偶校验法根据数据中“1”的个数为奇数或为偶数进行校验，该方法能够检测出信息传输过程中的部分误码，虽不能够纠错，但由于其实现简单，因而得到广泛使用；bcc异或校验法则通过将数据与指定初始值进行异或运算进而生成校验结果，该方法适用于大多数要求不高的数据通讯；md5校验法则对接收数据执行散列运算以检查数据的正确性，该方法是一种不可逆算法，通常用于检验文件的完整性和正确性；CRC是由分组线性码的分支而来[3]，其编码简单易实现，具有强大的检错能力和优异的抗干扰性能，是一种高效可靠的差错校验法。因此，CRC在数字通信中应用最为广泛。

随着通信和存储技术的快速发展，信息传输速率急剧提升[4]，高频率的数据传输要求通信总线和设备能够高速处理多种数据流。因此，新一代AMBA总线——AHB总线应运而生，该总线可满足高性能可综合设计要求，并用于高性能和高时钟工作频率模块。此外，为同时保证通信数据系统的快速性和可靠性，同样需要改进数据差错校验方法[5～6]。传统的串行CRC方法每个时钟周期仅能处理1 bit数据[7]，校验时间长且速度慢，已不能满足高速通信领域的要求。不仅如此，由于需要高速串行移位时钟及相应的高速设备，极大地增加了实现的难度[8]。

本文首先详细介绍了CRC基本原理及串行算法，随后针对如何提高CRC码计算速度推导出并行算法，接着采用该算法基于AHB总线设计了CRC计算模块，并运用硬件描述语言Verilog HDL完成建模与实现，最后通过时序和功能仿真验证了该算法能够保证数据的有效性，并大幅度提高CRC码的计算速度。

2 并行CRC基本原理和算法

CRC码属于分组码中一类重要的线性码，其主要应用是二元码字。CRC的原理是利用线性编码理论，在发送端根据待发送的位二进制信息码序列，以一定的规则生成一个位用于校验的监督码，通常将该监督码称为CRC码[9]，且附于信息码后(如图1所示)，从而构成一个共位的新二进制码序列，最终发送该新序列。随后接受端根据信息码和监督码之间所遵循的规则进行检验，以确定数据通信过程中是否出错[2～10]。

图1 CRC码结构

2.1 CRC基本原理

CRC的本质是模-2除法求余数。假设待发送的k位二进制信息码M=(mk-1，…，mk-2，m1，m0)，信息码的比特序列作为多项式M（x）的系数，则：

然后根据CRC码的长度，发送端和接收端规定一个(n-k)阶生成多项式G(x):

目前，具有通用标准的生成多项式包括CRC-4、CRC-12、CRC-16、CRC-ITU、CRC-32和CRC-32c(如表1所示)。本文规定的生成多项式为CRC-32。

表1 通用标准的生成多项式

接着，将信息码M=(mk-1，mk-2，…，m1，m0)左移(n-k)位，得到相应多项式xn-kM(x)，以此作为被除数，G(x)作为除数，进行模-2多项式除法，那么：

其中Q(x)表示商多项式，r(x)为余数多项式。假设r(x)可表示为：

将式(1)和式(4)带入式(3)，得：

通常定义发送码多项式C(x)=Q(x)G(x)，因此发送码序列则为C=(mk-1，mk-2，…，m1，m0，rn-k-1，rn-k-2，…，r0)，其中(rn-k-1，rn-k-2，…，r0)为CRC码。

如果接收端接收到的信息不存在误码，那么接收码多项式能够被生成多项式模-2整除。反之亦然。

2.2 CRC串行算法

由于CRC编码采用模-2多项式除法，每一位进行除法或减法运算的结果均不影响其他位，即不向上借位或进位，故逻辑上与异或运算等效。因此CRC串行算法可通过一系列移位寄存器和异或门组合实现，其典型电路结构如图2所示。

图2 CRC串行实现的典型电路结构[11]

图2中rj(i)表示第j个触发器在i时刻的状态，根据该实现电路的结构可推导得出CRC码的关系式为：

式中，“·”表示位于运算，“⊕”表示异或运算。

根据图2可知，k位信息码序列M从高位至低位依次从串行输入端输入，当M全部输入后，寄存器的输出值即为所求CRC码。因此经过k个时钟周期即可算出CRC码。该串行算法编码简单易实现，具有修改灵活和可移植性好等特点，然而逐位计算导致处理过程复杂冗余，尤其在高频率数据传输过程中，大量计算导致过长时间的占用处理器，甚至会因超时而导致通信部分失败[12]。

2.3 CRC并行算法

由于串行CRC算法存在一定的局限性，因此为加快数据校验速度需要采用多位并行计算的方法[13]，在并行计算的过程中，每次计算的位数可以选择固定的8位[14]或16位[15]等，也可以是变化的值[16]。

当进行串行运算时，当前CRC码仅与当前信息码输入值和前一时刻CRC码有关。如果并行计算CRC码（如8位并行运算），8位信息码同时输入并行运算电路所得的CRC码与8位信息码连续相继输入串行运算电路所产生的CRC码相同，那么该两种电路等效。由此可以推导出CRC并行算法。

本文设计的并行CRC算法，规定生成多项式为CRC-32，如式(8)所示：

且每次并行计算8位信息码，生成32位CRC码，因此，取p=8，n-k=31。

根据式(8)可知，当j=0，1，2，4，5，7，8，10，11，12，16，22，23，26时，gj=1，则式(7)可化简为：

若将计算结果表示为r7=[r731，r730，…，r70]，根据式(9)迭代推导r7表达式为：

由式(10)可知，运用本文介绍的并行算法计算8位信息码序列的32位CRC码，仅需1个时钟周期即可计算得到CRC码。该算法逻辑简单易实现，快速的处理过程极大缩短了CPU占用时间，其与CRC串行算法计算周期对比如表2所示。

表2 CRC码计算周期对比

3 基于AHB总线的CRC算法实现

AHB总线是为满足高性能且可综合设计要求而提出的新一代AMBA总线，该总线用于高性能和快时钟工作频率模块，可连接CPU、高带宽片上RAM、高带宽外部存储器接口、DMA和其他拥有AHB接口的控制器等，以构成一个独立并完整的系统级芯片(SoC, System on Chip)系统。不仅如此，其还可通过AHB-APB桥以连接APB总线系统。目前，AHB总线系统已被广泛使用于SoC设计中。

基于AHB总线所设计的CRC计算模块，不仅需要具备高工作频率的特点，而且能够计算多种数据流的CRC码，传统的串行算法并不能够满足该要求，因而运用并行算法是必要的。

3.1 AHB总线协议概述

作为高性能SoC系统总线，AHB总线支持多总线主机和高带宽的操作，具有包括单个时钟边沿触发、非三态实现方法、允许突发传输且支持传输字节、半字和全字等特征。一个典型的AHB系统包括主设备(Master)、从设备(Slave)以及基础结构。其中，基础结构包含一个决定总线控制权的仲裁器以及一个根据地址片选Slave的译码器。

通常情况下，Master发出传输请求，Slave负责响应。当AHB总线系统工作时，Master向仲裁器发起一个请求，然后仲裁器指示Master何时能够使用总线，接着被授权的Master向Slave提供地址信号和控制信号等信息以发送读操作请求或写操作请求，其中控制信号包含了传输方向、传输数据大小和传输类型等信息，译码器根据地址信息选中需响应Master的Slave。

AHB总线操作主要包括写操作和读操作。如图3所示，将AHB总线细分为写数据总线(hwdata)，读数据总线(hrdata)和地址控制信号(address&control)。当Master发送写操作请求时，hwdata将数据从Master传输至Slave，反之，hrdata将数据从Slave传输至Master以完成读操作。图3中，hclk和hresetn为全局信号，表示总线时钟和复位，hsel则为译码器传输至Slave的片选信号。

图3 AHB总线基本结构图

完成一次读操作或写操作包括两个阶段：仅一个有效周期的地址阶段以及一个或者多个有效周期的数据阶段。因此，Slave须在地址阶段采样有效地址，在数据阶段可通过控制hreadyout信号插入等待状态，以确保其有足够的时间提供或采样有效数据。

图4和图5简单地描述了未插入等待状态的读操作和插入等待状态的写操作，haddr为地址总线，hwrite表示传输方向。由此可见，拉低hreadyout可在数据阶段插入相应的等待周期。

图4 简单AHB读操作

3.2 基于AHB总线的CRC算法实现

本文运用并行算法设计一个CRC计算模块，作为AHB总线系统的Slave，模块结构如图6所示，主要由CRC控制单元(AHB_CRC)和CRC计算单元(CRC_ calculation)两部分组成。AHB系统Master通过AHB总线配置CRC相关控制寄存器并写入所需计算数据流至寄存器crc_wdr，CRC控制单元每个时钟向CRC计算单元输入8位信息码序列，该计算单位采用如式(10)所示的公式立即计算32位CRC码，每个时钟计算得到的结果均为下个时钟计算的初始值。

图5 等待状态的AHB写操作

图6 CRC模块结构

为改进CRC码计算速度，同时提高总线利用率，当Master向hwdata写入数据时或前一数据CRC码计算完成时，CRC控制单元立刻取相应的8位数据(crc_cal_byte)输入至CRC计算单元。由于AHB总线允许传输8位、16位和32位数据，因此CRC计算单元分别需要1、2和4个时钟周期计算得到32位CRC码，并将计算结果(crc_result)输出至寄存器crc_rdr以供Master读取。

假设Master先向CRC模块写入第1个32位数据Data1，间隔一个hclk后写入第2个8位数据Data2，实现过程时序如图7所示。

该实现步骤大致如下：

(1)T0～T1：Master发送写操作请求；

(2)T1～T2：Master向hwdata写入32位数据Data1，同时CRC控制单元向CRC计算单元输入Byte0_1(其值为Data1[7:0])进行CRC码计算，得到结果result0_1；

(3)T2～T3：CRC控制单元采样hwdata数据写入crc_wdr，并向CRC计算单元输入Byte1_1(即Data1 [15：8])，CRC计算单元以result0_1为初值与Byte1_1计算得到result1_1，同时Master发送第2个数据的写操作请求；

图7 CRC计算时序图

(4)T3～T4：CRC控制单元向CRC计算单元输入Byte2_1(即Data1[23：16])，得到CRC码result2_1，同时Master写入总线8位数据Data2，因为Data1的计算未结束，Data2还不能写入crc_wdr，因此置hready=0以插入一个hclk的等待状态；

(5)T4～T5：CRC控制单元向CRC计算单元输入Byte3_1(即Data1[31:24])，得到result1为Data1的CRC码，此时拉高hready使Slave能够在下个时钟采样hwdata；

(6)T5～T6：采样数据Data2写入crc_wdr，同时以result1为初值计算Byte0_2(即Data2)的CRC码，得到Data1和Data2的CRC码(result2)，CRC计算单元向控制单元输出result1存入crc_rdr；

(7)T6～T7：将result2存入crc_rdr，Master可通过读取crc_rdr以获取该数据流（Data1和Data2）的CRC码。

4 仿真与结果

本文采用HDL verilog硬件描述语言设计电路，并对程序进行时序和功能仿真。由于Master向CRC模块写入数据的随机性，给出如图8和图9所示两种情况下的仿真结果。

定义总线时钟频率为36 MHz，如果Master连续发出向crc_wdr写入待计算数据的请求，则该情况下CRC码的计算过程时序如图8所示。Master依次连续地向hwdata写32’h1122_5566、16’h7788和8’h99，从图中清晰地看到，当hwdata出现新数据时而CRC模块对crc_wdr中数据的计算还未结束，hready变为0，为CRC模块提供足够的计算时间。

第1个数据32’h1122_5566经过4个hclk计算得到CRC码32’ha516_f9f3，然后以该数值为初值与第2个数据16’h7788经过2个hclk计算得到CRC码32’hb252_7259，接着与第3个数据仅需1个hclk则得到结果为32’he118_3481。

图8连续写入数据以计算CRC码

图9 的仿真波形则描述了当Master不连续地写入数据时，CRC模块生成校验结果的时序过程。AHB控制信号的波形说明Master每次间隔1个hclk发出向crc_wdr写入数据的请求。当第3个数据8’h99写入总线时，16’h7788的计算已完成，CRC模块不需要插入等待状态，因此hready一直维持为1。

图9 非连续写入数据以计算CRC码

仿真结果表明，本文基于AHB总线所设计的CRC计算模块，运用的并行算法加快了CRC码的计算速度。此外，该模块不受输入数据流结构的限制，能够计算连续或非连续输入的任意长度数据的32位CRC码。

5 结论

本文基于CRC原理，详细介绍了一种CRC并行算法。运用该算法基于AHB总线，采用硬件描述语言Verilog HDL设计并实现CRC计算模块。通过仿真，验证了该算法能够在高频率的数据传输过程中计算任意数据流的CRC码，且编码简单易实现。此外，相较于传统CRC串行算法每个时钟周期仅能处理1位数据，该CRC并行算法每个时钟周期能够处理8位数据，极大地提高了计算效率，弥补了传统CRC串行算法的不足。

[1]黄维超,刘桥,黄初华.基于Verilog的CRC并行实现[J].微计算机信息,2009,25(30):112-113.

[2]任宇,陈欣,吕迅竣.适用于串行通信数据流的循环冗余校验方法[J].工业控制计算机,2006,19(12):5-6.

[3]王蕾,平静,马世霞.数据通信中CRC方法的原理与实现[J].河南机电高等专科学校学报,2006,14(3):28-29.

[4]常天海,胡鉴.基于FPGA的CRC并行算法研究与实现[J].微处理机,2010,2:45-48.

[5]建辉.10G以太网接I：I并行CRC校验的一种简化算法[J].微计算机信息,2006,20:213-215.

[6]Renuka H K,Jayashree C N.Design and Computation of CyclicRedundancy Code for Ethernet Application:an implementationUsing FPGA[J].World Journal of Science and Technology,2011,1(8):68-73.

[7]Kounavis M E,Berry F L.Novel Table Lookup Based Algorithms for High Performance CRC Generation[J].IEEE Transon Computer Society,2008,57(11):1550-1560.

[8]金巍,肖立权.一种并行CRC计算原理及FPGA实现[C].计算机工程与工艺全国学术年会,2003:125-129.

[9]廖海红.通信系统中的CRC算法的研究和工程实现[D].北京:北京邮电大学,2006.

[10]赵鸿,彭碧玉,王宏卓.基于VHDL的CRC校验及其在测控通信中的应用[J].通信技术,2010,2(43):29-34.

[11]Giuseppe Campobello,Giuseppe Patane,Marco Russo. Parallel CRC realization[C].IEEE Transactions on Computers,2003,52(10):1312-1319.

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

[13]蒋安平.循环冗余校验(CRC)的硬件并行实现[J].微电子学与计算机,2007,24(2):107-112.

[14]Sadiq M Sait,Wasif Hasan.Hardware design and VLSI implementation of a byte-wise CRC generation chip[J]. IEEE Transactions on Consumer Electronics,1995,41(1): 195-200.

[15]程军,陈贵灿,姜飞.USB数据传输中CRC校验码的并行算法实现[J].微电子学与计算机,2003,20(3):77-80.

[16]Ji H M,Killian E.Fast parallel CRC algorithm and implementation on a configurable processor[C].IEEE International Conference on Communications,2002,3: 1813-1817.

Design and Implementation of AHB-Based Fast Parallel CRC Algorithm

SHI Xingqiang,LIU Mengying
（China Key System Co.,Ltd.,Wuxi 214072,China）

On account of simple algorithm and extraordinary error-detecting and anti-jamming capabilities, Cyclic Redundancy Check(CRC)is widely used in data communications in purpose of enhancing data reliability.On the basisofCRCfundamental,a fastparallelCRCalgorithm isintroduced in the paper to meet the requirements of high-speed data transmission.The algorithm is then used to design a CRC calculation module based on AHB bus system using Verilog HDL.The simulation results indicate that the fast parallel CRC algorithm dramatically improvescalculation speed while ensuring the data reliability.

CRC;fast;parallel;AHBbus

TN402

A

1681-1070（2017）07-0011-06

史兴强（1976—），男，江苏宜兴人，1999年毕业于南京理工大学电子工程专业，现从事SoC数字设计及低功耗技术研究。

2017-4-21