史興強，劉夢影

（中科芯集成電路股份有限公司，江蘇無錫214072）

基于AHB總線的快速并行CRC算法設計與實現(xiàn)

史興強，劉夢影

（中科芯集成電路股份有限公司，江蘇無錫214072）

循環(huán)冗余校驗(CRC,Cyclic Redundancy Check)以其簡單的算法、強大的檢錯能力和抗干擾能力，廣泛應用于通信領域，以提高數(shù)據(jù)傳輸?shù)目煽啃?。為滿足高頻率的數(shù)據(jù)傳輸要求，基于CRC基本原理，介紹了一種快速并行CRC算法，然后采用該算法基于高級高性能(AHB,Advanced High Performance Bus)總線，運用硬件描述語言Verilog HDL設計并實現(xiàn)了CRC計算模塊。仿真結(jié)果表明，該算法能夠在確保數(shù)據(jù)可靠性的同時提高CRC的計算速度。

CRC；快速；并行；AHB總線

1 引言

在數(shù)據(jù)通信過程中，由于通信傳輸特性不理想，且存在噪聲和信道之間串擾等其他因素的干擾，因此接收端的信息可能發(fā)生錯誤決斷[1]。為降低通信誤碼率，提高數(shù)據(jù)通信有效性，采用信道編碼進行檢錯和糾錯是必要的。

目前，常用的差錯校驗方法包括奇偶校驗法、bcc異或校驗法、md5校驗法以及CRC法等[2]。奇偶校驗法根據(jù)數(shù)據(jù)中“1”的個數(shù)為奇數(shù)或為偶數(shù)進行校驗，該方法能夠檢測出信息傳輸過程中的部分誤碼，雖不能夠糾錯，但由于其實現(xiàn)簡單，因而得到廣泛使用；bcc異或校驗法則通過將數(shù)據(jù)與指定初始值進行異或運算進而生成校驗結(jié)果，該方法適用于大多數(shù)要求不高的數(shù)據(jù)通訊；md5校驗法則對接收數(shù)據(jù)執(zhí)行散列運算以檢查數(shù)據(jù)的正確性，該方法是一種不可逆算法，通常用于檢驗文件的完整性和正確性；CRC是由分組線性碼的分支而來[3]，其編碼簡單易實現(xiàn)，具有強大的檢錯能力和優(yōu)異的抗干擾性能，是一種高效可靠的差錯校驗法。因此，CRC在數(shù)字通信中應用最為廣泛。

隨著通信和存儲技術(shù)的快速發(fā)展，信息傳輸速率急劇提升[4]，高頻率的數(shù)據(jù)傳輸要求通信總線和設備能夠高速處理多種數(shù)據(jù)流。因此，新一代AMBA總線——AHB總線應運而生，該總線可滿足高性能可綜合設計要求，并用于高性能和高時鐘工作頻率模塊。此外，為同時保證通信數(shù)據(jù)系統(tǒng)的快速性和可靠性，同樣需要改進數(shù)據(jù)差錯校驗方法[5～6]。傳統(tǒng)的串行CRC方法每個時鐘周期僅能處理1 bit數(shù)據(jù)[7]，校驗時間長且速度慢，已不能滿足高速通信領域的要求。不僅如此，由于需要高速串行移位時鐘及相應的高速設備，極大地增加了實現(xiàn)的難度[8]。

本文首先詳細介紹了CRC基本原理及串行算法，隨后針對如何提高CRC碼計算速度推導出并行算法，接著采用該算法基于AHB總線設計了CRC計算模塊，并運用硬件描述語言Verilog HDL完成建模與實現(xiàn)，最后通過時序和功能仿真驗證了該算法能夠保證數(shù)據(jù)的有效性，并大幅度提高CRC碼的計算速度。

2 并行CRC基本原理和算法

CRC碼屬于分組碼中一類重要的線性碼，其主要應用是二元碼字。CRC的原理是利用線性編碼理論，在發(fā)送端根據(jù)待發(fā)送的位二進制信息碼序列，以一定的規(guī)則生成一個位用于校驗的監(jiān)督碼，通常將該監(jiān)督碼稱為CRC碼[9]，且附于信息碼后(如圖1所示)，從而構(gòu)成一個共位的新二進制碼序列，最終發(fā)送該新序列。隨后接受端根據(jù)信息碼和監(jiān)督碼之間所遵循的規(guī)則進行檢驗，以確定數(shù)據(jù)通信過程中是否出錯[2～10]。

圖1 CRC碼結(jié)構(gòu)

2.1 CRC基本原理

CRC的本質(zhì)是模-2除法求余數(shù)。假設待發(fā)送的k位二進制信息碼M=(mk-1，…，mk-2，m1，m0)，信息碼的比特序列作為多項式M（x）的系數(shù)，則：

然后根據(jù)CRC碼的長度，發(fā)送端和接收端規(guī)定一個(n-k)階生成多項式G(x):

目前，具有通用標準的生成多項式包括CRC-4、CRC-12、CRC-16、CRC-ITU、CRC-32和CRC-32c(如表1所示)。本文規(guī)定的生成多項式為CRC-32。

表1 通用標準的生成多項式

接著，將信息碼M=(mk-1，mk-2，…，m1，m0)左移(n-k)位，得到相應多項式xn-kM(x)，以此作為被除數(shù)，G(x)作為除數(shù)，進行模-2多項式除法，那么：

其中Q(x)表示商多項式，r(x)為余數(shù)多項式。假設r(x)可表示為：

將式(1)和式(4)帶入式(3)，得：

通常定義發(fā)送碼多項式C(x)=Q(x)G(x)，因此發(fā)送碼序列則為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多項式除法，每一位進行除法或減法運算的結(jié)果均不影響其他位，即不向上借位或進位，故邏輯上與異或運算等效。因此CRC串行算法可通過一系列移位寄存器和異或門組合實現(xiàn)，其典型電路結(jié)構(gòu)如圖2所示。

圖2 CRC串行實現(xiàn)的典型電路結(jié)構(gòu)[11]

圖2中rj(i)表示第j個觸發(fā)器在i時刻的狀態(tài)，根據(jù)該實現(xiàn)電路的結(jié)構(gòu)可推導得出CRC碼的關(guān)系式為：

式中，“·”表示位于運算，“⊕”表示異或運算。

根據(jù)圖2可知，k位信息碼序列M從高位至低位依次從串行輸入端輸入，當M全部輸入后，寄存器的輸出值即為所求CRC碼。因此經(jīng)過k個時鐘周期即可算出CRC碼。該串行算法編碼簡單易實現(xiàn)，具有修改靈活和可移植性好等特點，然而逐位計算導致處理過程復雜冗余，尤其在高頻率數(shù)據(jù)傳輸過程中，大量計算導致過長時間的占用處理器，甚至會因超時而導致通信部分失敗[12]。

2.3 CRC并行算法

由于串行CRC算法存在一定的局限性，因此為加快數(shù)據(jù)校驗速度需要采用多位并行計算的方法[13]，在并行計算的過程中，每次計算的位數(shù)可以選擇固定的8位[14]或16位[15]等，也可以是變化的值[16]。

當進行串行運算時，當前CRC碼僅與當前信息碼輸入值和前一時刻CRC碼有關(guān)。如果并行計算CRC碼（如8位并行運算），8位信息碼同時輸入并行運算電路所得的CRC碼與8位信息碼連續(xù)相繼輸入串行運算電路所產(chǎn)生的CRC碼相同，那么該兩種電路等效。由此可以推導出CRC并行算法。

本文設計的并行CRC算法，規(guī)定生成多項式為CRC-32，如式(8)所示：

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

根據(jù)式(8)可知，當j=0，1，2，4，5，7，8，10，11，12，16，22，23，26時，gj=1，則式(7)可化簡為：

若將計算結(jié)果表示為r7=[r731，r730，…，r70]，根據(jù)式(9)迭代推導r7表達式為：

由式(10)可知，運用本文介紹的并行算法計算8位信息碼序列的32位CRC碼，僅需1個時鐘周期即可計算得到CRC碼。該算法邏輯簡單易實現(xiàn)，快速的處理過程極大縮短了CPU占用時間，其與CRC串行算法計算周期對比如表2所示。

表2 CRC碼計算周期對比

3 基于AHB總線的CRC算法實現(xiàn)

AHB總線是為滿足高性能且可綜合設計要求而提出的新一代AMBA總線，該總線用于高性能和快時鐘工作頻率模塊，可連接CPU、高帶寬片上RAM、高帶寬外部存儲器接口、DMA和其他擁有AHB接口的控制器等，以構(gòu)成一個獨立并完整的系統(tǒng)級芯片(SoC, System on Chip)系統(tǒng)。不僅如此，其還可通過AHB-APB橋以連接APB總線系統(tǒng)。目前，AHB總線系統(tǒng)已被廣泛使用于SoC設計中。

基于AHB總線所設計的CRC計算模塊，不僅需要具備高工作頻率的特點，而且能夠計算多種數(shù)據(jù)流的CRC碼，傳統(tǒng)的串行算法并不能夠滿足該要求，因而運用并行算法是必要的。

3.1 AHB總線協(xié)議概述

作為高性能SoC系統(tǒng)總線，AHB總線支持多總線主機和高帶寬的操作，具有包括單個時鐘邊沿觸發(fā)、非三態(tài)實現(xiàn)方法、允許突發(fā)傳輸且支持傳輸字節(jié)、半字和全字等特征。一個典型的AHB系統(tǒng)包括主設備(Master)、從設備(Slave)以及基礎結(jié)構(gòu)。其中，基礎結(jié)構(gòu)包含一個決定總線控制權(quán)的仲裁器以及一個根據(jù)地址片選Slave的譯碼器。

通常情況下，Master發(fā)出傳輸請求，Slave負責響應。當AHB總線系統(tǒng)工作時，Master向仲裁器發(fā)起一個請求，然后仲裁器指示Master何時能夠使用總線，接著被授權(quán)的Master向Slave提供地址信號和控制信號等信息以發(fā)送讀操作請求或?qū)懖僮髡埱?，其中控制信號包含了傳輸方向、傳輸?shù)據(jù)大小和傳輸類型等信息，譯碼器根據(jù)地址信息選中需響應Master的Slave。

AHB總線操作主要包括寫操作和讀操作。如圖3所示，將AHB總線細分為寫數(shù)據(jù)總線(hwdata)，讀數(shù)據(jù)總線(hrdata)和地址控制信號(address&control)。當Master發(fā)送寫操作請求時，hwdata將數(shù)據(jù)從Master傳輸至Slave，反之，hrdata將數(shù)據(jù)從Slave傳輸至Master以完成讀操作。圖3中，hclk和hresetn為全局信號，表示總線時鐘和復位，hsel則為譯碼器傳輸至Slave的片選信號。

圖3 AHB總線基本結(jié)構(gòu)圖

完成一次讀操作或?qū)懖僮靼▋蓚€階段：僅一個有效周期的地址階段以及一個或者多個有效周期的數(shù)據(jù)階段。因此，Slave須在地址階段采樣有效地址，在數(shù)據(jù)階段可通過控制hreadyout信號插入等待狀態(tài)，以確保其有足夠的時間提供或采樣有效數(shù)據(jù)。

圖4和圖5簡單地描述了未插入等待狀態(tài)的讀操作和插入等待狀態(tài)的寫操作，haddr為地址總線，hwrite表示傳輸方向。由此可見，拉低hreadyout可在數(shù)據(jù)階段插入相應的等待周期。

圖4 簡單AHB讀操作

3.2 基于AHB總線的CRC算法實現(xiàn)

本文運用并行算法設計一個CRC計算模塊，作為AHB總線系統(tǒng)的Slave，模塊結(jié)構(gòu)如圖6所示，主要由CRC控制單元(AHB_CRC)和CRC計算單元(CRC_ calculation)兩部分組成。AHB系統(tǒng)Master通過AHB總線配置CRC相關(guān)控制寄存器并寫入所需計算數(shù)據(jù)流至寄存器crc_wdr，CRC控制單元每個時鐘向CRC計算單元輸入8位信息碼序列，該計算單位采用如式(10)所示的公式立即計算32位CRC碼，每個時鐘計算得到的結(jié)果均為下個時鐘計算的初始值。

圖5 等待狀態(tài)的AHB寫操作

圖6 CRC模塊結(jié)構(gòu)

為改進CRC碼計算速度，同時提高總線利用率，當Master向hwdata寫入數(shù)據(jù)時或前一數(shù)據(jù)CRC碼計算完成時，CRC控制單元立刻取相應的8位數(shù)據(jù)(crc_cal_byte)輸入至CRC計算單元。由于AHB總線允許傳輸8位、16位和32位數(shù)據(jù)，因此CRC計算單元分別需要1、2和4個時鐘周期計算得到32位CRC碼，并將計算結(jié)果(crc_result)輸出至寄存器crc_rdr以供Master讀取。

假設Master先向CRC模塊寫入第1個32位數(shù)據(jù)Data1，間隔一個hclk后寫入第2個8位數(shù)據(jù)Data2，實現(xiàn)過程時序如圖7所示。

該實現(xiàn)步驟大致如下：

(1)T0～T1：Master發(fā)送寫操作請求；

(2)T1～T2：Master向hwdata寫入32位數(shù)據(jù)Data1，同時CRC控制單元向CRC計算單元輸入Byte0_1(其值為Data1[7:0])進行CRC碼計算，得到結(jié)果result0_1；

(3)T2～T3：CRC控制單元采樣hwdata數(shù)據(jù)寫入crc_wdr，并向CRC計算單元輸入Byte1_1(即Data1 [15：8])，CRC計算單元以result0_1為初值與Byte1_1計算得到result1_1，同時Master發(fā)送第2個數(shù)據(jù)的寫操作請求；

圖7 CRC計算時序圖

(4)T3～T4：CRC控制單元向CRC計算單元輸入Byte2_1(即Data1[23：16])，得到CRC碼result2_1，同時Master寫入總線8位數(shù)據(jù)Data2，因為Data1的計算未結(jié)束，Data2還不能寫入crc_wdr，因此置hready=0以插入一個hclk的等待狀態(tài)；

(5)T4～T5：CRC控制單元向CRC計算單元輸入Byte3_1(即Data1[31:24])，得到result1為Data1的CRC碼，此時拉高hready使Slave能夠在下個時鐘采樣hwdata；

(6)T5～T6：采樣數(shù)據(jù)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以獲取該數(shù)據(jù)流（Data1和Data2）的CRC碼。

4 仿真與結(jié)果

本文采用HDL verilog硬件描述語言設計電路，并對程序進行時序和功能仿真。由于Master向CRC模塊寫入數(shù)據(jù)的隨機性，給出如圖8和圖9所示兩種情況下的仿真結(jié)果。

定義總線時鐘頻率為36 MHz，如果Master連續(xù)發(fā)出向crc_wdr寫入待計算數(shù)據(jù)的請求，則該情況下CRC碼的計算過程時序如圖8所示。Master依次連續(xù)地向hwdata寫32’h1122_5566、16’h7788和8’h99，從圖中清晰地看到，當hwdata出現(xiàn)新數(shù)據(jù)時而CRC模塊對crc_wdr中數(shù)據(jù)的計算還未結(jié)束，hready變?yōu)?，為CRC模塊提供足夠的計算時間。

第1個數(shù)據(jù)32’h1122_5566經(jīng)過4個hclk計算得到CRC碼32’ha516_f9f3，然后以該數(shù)值為初值與第2個數(shù)據(jù)16’h7788經(jīng)過2個hclk計算得到CRC碼32’hb252_7259，接著與第3個數(shù)據(jù)僅需1個hclk則得到結(jié)果為32’he118_3481。

圖8連續(xù)寫入數(shù)據(jù)以計算CRC碼

圖9 的仿真波形則描述了當Master不連續(xù)地寫入數(shù)據(jù)時，CRC模塊生成校驗結(jié)果的時序過程。AHB控制信號的波形說明Master每次間隔1個hclk發(fā)出向crc_wdr寫入數(shù)據(jù)的請求。當?shù)?個數(shù)據(jù)8’h99寫入總線時，16’h7788的計算已完成，CRC模塊不需要插入等待狀態(tài)，因此hready一直維持為1。

圖9 非連續(xù)寫入數(shù)據(jù)以計算CRC碼

仿真結(jié)果表明，本文基于AHB總線所設計的CRC計算模塊，運用的并行算法加快了CRC碼的計算速度。此外，該模塊不受輸入數(shù)據(jù)流結(jié)構(gòu)的限制，能夠計算連續(xù)或非連續(xù)輸入的任意長度數(shù)據(jù)的32位CRC碼。

5 結(jié)論

本文基于CRC原理，詳細介紹了一種CRC并行算法。運用該算法基于AHB總線，采用硬件描述語言Verilog HDL設計并實現(xiàn)CRC計算模塊。通過仿真，驗證了該算法能夠在高頻率的數(shù)據(jù)傳輸過程中計算任意數(shù)據(jù)流的CRC碼，且編碼簡單易實現(xiàn)。此外，相較于傳統(tǒng)CRC串行算法每個時鐘周期僅能處理1位數(shù)據(jù)，該CRC并行算法每個時鐘周期能夠處理8位數(shù)據(jù)，極大地提高了計算效率，彌補了傳統(tǒng)CRC串行算法的不足。

[1]黃維超,劉橋,黃初華.基于Verilog的CRC并行實現(xiàn)[J].微計算機信息,2009,25(30):112-113.

[2]任宇,陳欣,呂迅竣.適用于串行通信數(shù)據(jù)流的循環(huán)冗余校驗方法[J].工業(yè)控制計算機,2006,19(12):5-6.

[3]王蕾,平靜,馬世霞.數(shù)據(jù)通信中CRC方法的原理與實現(xiàn)[J].河南機電高等專科學校學報,2006,14(3):28-29.

[4]常天海,胡鑒.基于FPGA的CRC并行算法研究與實現(xiàn)[J].微處理機,2010,2:45-48.

[5]建輝.10G以太網(wǎng)接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]金巍,肖立權(quán).一種并行CRC計算原理及FPGA實現(xiàn)[C].計算機工程與工藝全國學術(shù)年會,2003:125-129.

[9]廖海紅.通信系統(tǒng)中的CRC算法的研究和工程實現(xiàn)[D].北京:北京郵電大學,2006.

[10]趙鴻,彭碧玉,王宏卓.基于VHDL的CRC校驗及其在測控通信中的應用[J].通信技術(shù),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碼串并行結(jié)合算法的研究與實現(xiàn)[J].計算機技術(shù)與發(fā)展,2014,24(6):103-106.

[13]蔣安平.循環(huán)冗余校驗(CRC)的硬件并行實現(xiàn)[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數(shù)據(jù)傳輸中CRC校驗碼的并行算法實現(xiàn)[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年畢業(yè)于南京理工大學電子工程專業(yè)，現(xiàn)從事SoC數(shù)字設計及低功耗技術(shù)研究。

2017-4-21