通用并行CRC計(jì)算方法及FPGA實(shí)現(xiàn)

仇曉濤

摘要：循環(huán)冗余校驗(yàn)（CRC）碼是諸多信道編碼方式中最常用的一種編碼，也是一種檢錯(cuò)概率高且容易硬件實(shí)現(xiàn)的檢錯(cuò)碼，因檢錯(cuò)能力強(qiáng)、容易實(shí)現(xiàn)而得到廣泛應(yīng)用。首先，本文介紹了循環(huán)冗余校驗(yàn)的算法原理，分析了CRC校驗(yàn)碼的具體運(yùn)算過(guò)程；其次，本文在原算法的基礎(chǔ)上提出一種高速并行CRC算法，并以CRC-CCITT為例，推導(dǎo)出8位并行運(yùn)算的CRC- CCITT邏輯關(guān)系式；最后，本文根據(jù)推導(dǎo)的8位并行運(yùn)算的邏輯關(guān)系式，描述了8位并行的CRC- CCITT硬件實(shí)現(xiàn)電路。將該算法與現(xiàn)有的查找表法的性能進(jìn)行分析比較發(fā)現(xiàn)，該算法具有節(jié)省邏輯資源、運(yùn)行速度快等特點(diǎn)。

關(guān)鍵詞：循環(huán)冗余校驗(yàn)；生成多項(xiàng)式；并行計(jì)算；FPGA

中圖分類號(hào)：TN911.22? 文獻(xiàn)標(biāo)志碼：A

0 引言

當(dāng)數(shù)字信號(hào)在實(shí)際的無(wú)線信道通信系統(tǒng)中進(jìn)行傳輸時(shí)，由于噪聲的干擾以及不良信道傳輸特性的影響，該數(shù)字信號(hào)不可避免地在接收端產(chǎn)生誤碼?？垢蓴_是無(wú)線通信信道數(shù)據(jù)傳輸中的關(guān)鍵問(wèn)題之一，可以通過(guò)信道編碼來(lái)解決。在諸多信道編碼方法中，循環(huán)冗余校驗(yàn)（Cyclic Redundancy Check，CRC）碼是一種在數(shù)據(jù)通信領(lǐng)域中廣泛使用的檢錯(cuò)碼，因檢錯(cuò)能力強(qiáng)、容易實(shí)現(xiàn)而得到廣泛應(yīng)用［1-3］。CRC碼不但可以有效地抗隨機(jī)干擾，還可以有效地抗突發(fā)干擾，因此，在各種通信系統(tǒng)、計(jì)算機(jī)系統(tǒng)、磁記錄以及存儲(chǔ)中得到廣泛的應(yīng)用。

1 CRC校驗(yàn)碼原理

CRC校驗(yàn)碼由一個(gè)二進(jìn)制的多項(xiàng)式產(chǎn)生，若該多項(xiàng)式的最高次冪為k，則可以產(chǎn)生k-1位的冗余碼。選取合適的二進(jìn)制多項(xiàng)式，不但可以使CRC校驗(yàn)碼檢測(cè)出所有奇數(shù)位隨機(jī)誤碼，還可以檢測(cè)出突發(fā)長(zhǎng)度小于等于k-1位的突發(fā)誤碼。

CRC校驗(yàn)碼的編碼步驟：

設(shè)D=（dn-1，dn-2，…，d1，d0）為n位的待校驗(yàn)的二進(jìn)制數(shù)據(jù)流，用多項(xiàng)式D（x）表示：

D（x）=dn-1Xn-1+dn-2Xn-2+…+d1X+d0（1）

如果所用生成多項(xiàng)式G（x）的最高次冪為k，在式（1）等號(hào)的兩側(cè)同時(shí)乘以Xk，化簡(jiǎn)可得出：

XkD（x）=dn-1Xk+n-1+dn-2Xk+n-2+…+d1Xk+1+d0Xk（2）

XkD（x）模2除以G（x），用Q（x）表示商多項(xiàng)式，R（x）表示余數(shù)多項(xiàng)式，可得：

XkD（x）+R（x）=Q（x）G（x）（3）

余數(shù)多項(xiàng)式R（x）可表示為：

R（x）=rk-1Xk-1+rk-2Xk-2+…+r1X+r0（4）

將式（2）和式（4）代入式（3），得：

Q（x）G（x）=XkD（x）+R（x）=dn-1Xk+n-1+dn-2Xk+n-2+…+d1Xk+1+d0Xk+rk-1Xk-1+rk-2Xk-2+…+r1X+r0（5）

式（5）對(duì)應(yīng)的碼組為n+k位，即：

D′=（dn-1，dn-2，…，d1，d0，rk-1，rk-2，…，r1，r0）（6）

由D到D′的計(jì)算過(guò)程就是CRC的編碼步驟，rk-1，rk-2，…，r1，r0為校驗(yàn)位。式（1）～式（6）的計(jì)算步驟表明，CRC校驗(yàn)碼的編碼步驟中的運(yùn)算需要模2除運(yùn)算，產(chǎn)生的余數(shù)就是CRC碼的校驗(yàn)位。同理，接收端將接收到的n+k位信息碼除以相同的生成多項(xiàng)式G（x），根據(jù)式（3），如果產(chǎn)生的余數(shù)為0，則認(rèn)為接收端接收到的二進(jìn)制數(shù)據(jù)流正確無(wú)誤碼；否則就認(rèn)為接收端接收到的二進(jìn)制數(shù)據(jù)流在傳輸過(guò)程中產(chǎn)生了誤碼。

CRC校驗(yàn)碼的通用串行電路如圖1所示，其中，符號(hào)代表表示模2加運(yùn)算，表示加權(quán)乘法運(yùn)算。用r0，r1，…，rk-2，rk-1表示k個(gè)二進(jìn)制移位寄存器的狀態(tài)值，該寄存器的移位由外部同步時(shí)鐘控制。生成多項(xiàng)式G（x）的系數(shù)用gi（i=1，2，…k-1）表示，其取值只有0或者1兩個(gè)狀態(tài)，物理意義上0表示無(wú)反饋，是斷開(kāi)；1表示有反饋，是閉合。當(dāng)生成多項(xiàng)式G（x）確定時(shí)，可進(jìn)一步簡(jiǎn)化圖1的電路。本文以CRC-CCITT的生成多項(xiàng)式G（x）=X16+X12+X5+1為例，此時(shí)g0=g5=g12=1，相應(yīng)地簡(jiǎn)化串行電路，如圖2所示。

該CRC-CCITT串行電路只用到了基本的異或門(mén)和移位寄存器邏輯單元。如果在高速數(shù)字通信系統(tǒng)中采用CRC串行運(yùn)算，就需要高速串行同步時(shí)鐘及相應(yīng)的高速器件，極大地增加了電路的硬件成本以及實(shí)現(xiàn)復(fù)雜度。該問(wèn)題通?？梢圆捎貌⑿羞\(yùn)算的處理方法解決，因此需要研究一種并行CRC處理電路。

2 并行計(jì)算與實(shí)現(xiàn)

CRC余數(shù)值即各個(gè)二進(jìn)制移位寄存器中的狀態(tài)值，進(jìn)行串行運(yùn)算時(shí)，當(dāng)前的CRC余數(shù)值取決于輸入的二進(jìn)制數(shù)據(jù)流的當(dāng)前值和前一個(gè)狀態(tài)的二進(jìn)制移位寄存器中的余數(shù)值。如果進(jìn)行并行運(yùn)算，以8位二進(jìn)制數(shù)據(jù)流并行運(yùn)算為例，即同時(shí)輸入8位二進(jìn)制數(shù)據(jù)流到并行運(yùn)算電路所產(chǎn)生的CRC余數(shù)與相繼輸入連續(xù)8位二進(jìn)制數(shù)據(jù)流到串行運(yùn)算電路所產(chǎn)生的CRC余數(shù)相同，則稱這兩種電路是等效的。因此，可以推導(dǎo)出CRC的并行運(yùn)算方法［4］。

圖2中二進(jìn)制移位寄存器的狀態(tài)值用rij表示，輸入的二進(jìn)制數(shù)據(jù)流用di（表示第i個(gè)輸入的二進(jìn)制數(shù)據(jù)）表示，其中，i=1，2，…，n，為輸入的數(shù)據(jù)流序號(hào)（表示r的第i次變化，其中，n=4，8，16，32，表示數(shù)據(jù)流的并行度），j=0，1，…，k-1，為移位寄存器的編號(hào)（此處k=16），由此可得：

根據(jù)表1中的邏輯關(guān)系式，可以很容易地實(shí)現(xiàn)8位并行的CRC- CCITT硬件運(yùn)算電路，其硬件實(shí)現(xiàn)過(guò)程如圖3所示。

上述CRC并行運(yùn)算方法的推導(dǎo)步驟雖然是以8位并行CRC-CCITT運(yùn)算為例進(jìn)行的，但該方法具有普遍適用性，即使用該方法可以推導(dǎo)出各種CRC生成多項(xiàng)式的不同并行度（包括16位、32位，甚至是64位）的并行運(yùn)算邏輯關(guān)系式。

3 性能分析

查找表方法既可以用軟件實(shí)現(xiàn)，也可以用硬件實(shí)現(xiàn)。在余數(shù)表中存儲(chǔ)相應(yīng)的余數(shù)，再通過(guò)查找該余數(shù)表的方法就可以進(jìn)行該CRC生成多項(xiàng)式的運(yùn)算。

分析比較查找表和并行運(yùn)算兩種方法，可以得出如下結(jié)論。

本研究提出的CRC并行運(yùn)算方法無(wú)需存儲(chǔ)查找表方法中所必需的CRC余數(shù)表。該并行運(yùn)算方法不但可節(jié)約硬件電路的成本，還提高了電路的運(yùn)算速度。在查找表方法中，電路的硬件實(shí)現(xiàn)不僅需要FPGA內(nèi)部資源，還必須使用存儲(chǔ)龐大CRC余數(shù)表的外部高速存儲(chǔ)器件以及FPGA的輸入、輸出引腳。硬件電路所產(chǎn)生的總時(shí)延包括兩級(jí)異或門(mén)時(shí)延、寄存器鎖存時(shí)延、輸入輸出引腳時(shí)延以及讀取外部高速存儲(chǔ)器件存放數(shù)據(jù)的時(shí)延。由于使用了存儲(chǔ)CRC余數(shù)表的外部存儲(chǔ)器件，硬件電路處理時(shí)會(huì)產(chǎn)生較大的時(shí)延，電路需要使用更高的處理時(shí)鐘。如果依據(jù)本研究提出的直接硬件實(shí)現(xiàn)法，以Xilinx FPGA XC7K480T實(shí)現(xiàn)CRC-CCITT為例［2］，完全可以使用FPGA的內(nèi)部邏輯資源來(lái)實(shí)現(xiàn)，硬件電路所產(chǎn)生的總時(shí)延包括兩級(jí)異或門(mén)時(shí)延和寄存器鎖存時(shí)延，產(chǎn)生的時(shí)延較小。

本研究提出的CRC實(shí)現(xiàn)法可提高并行運(yùn)算的并行度。在查找表方法中，隨著并行度的增加，CRC余數(shù)表所需的存儲(chǔ)空間會(huì)急劇增大，為節(jié)省空間，查找表法中的并行度一般被限制在8位以內(nèi)。例如：當(dāng)運(yùn)算并行度為16位數(shù)據(jù)的CRC校驗(yàn)碼時(shí)，其余數(shù)表長(zhǎng)度達(dá)到65 536（216）項(xiàng)；當(dāng)運(yùn)算并行度為32位數(shù)據(jù)的CRC校驗(yàn)碼時(shí)，其余數(shù)表長(zhǎng)度高達(dá)4 294 967 296（232）項(xiàng)，這對(duì)FPGA有限的資源來(lái)說(shuō)是不太現(xiàn)實(shí)的。假如要進(jìn)行數(shù)據(jù)傳輸率為3.3 Gbps的數(shù)據(jù)傳輸，就必須要求電路處理時(shí)鐘的頻率達(dá)到1/0.3 ns=3 333 MHz，不僅大多數(shù)FPGA無(wú)法滿足如此高的時(shí)鐘頻率，規(guī)模的專用集成電路也很難滿足這個(gè)要求。對(duì)于本研究提出的CRC并行運(yùn)算方法，當(dāng)數(shù)據(jù)的并行度為8位或者更大（如32位，甚至是64位）時(shí)，可以有效地降低處理時(shí)鐘的頻率，即使使用普通的CMOS器件也可以實(shí)現(xiàn)速率很高的CRC運(yùn)算，如用Xilinx FPGAXC7K325T可以實(shí)現(xiàn)超過(guò)3.3 Gbps甚至5.0 Gbps的CRC運(yùn)算［5］。

4 結(jié)語(yǔ)

本研究對(duì)CRC運(yùn)算原理進(jìn)行了分析，在此基礎(chǔ)之上推導(dǎo)和實(shí)現(xiàn)了一種通用的并行CRC運(yùn)算的方法。此種方法可以方便快捷地實(shí)現(xiàn)不同數(shù)據(jù)并行度的各種生成多項(xiàng)式的CRC運(yùn)算，運(yùn)用硬件來(lái)實(shí)現(xiàn)該算法也相對(duì)容易，尤其是對(duì)于需要提高并行度（大于8）的高速通信系統(tǒng)的CRC運(yùn)算。與查找表法相比較，該方法具有優(yōu)越性和現(xiàn)實(shí)性。

參考文獻(xiàn)

［1］王新梅，肖國(guó)鎮(zhèn).糾錯(cuò)碼原理與方法［M］，西安：西安電子科技大學(xué)出版社，2001.

［2］李云松，宋銳，雷杰，等.Xilinx FPGA設(shè)計(jì)基礎(chǔ)［M］.西安：西安電子科技大學(xué)版社，2008.

［3］樊昌信.通信原理［M］.北京：國(guó)防工業(yè)出版社，2001.

［4］張樹(shù)剛，張遂南，黃士坦.CRC校驗(yàn)碼并行計(jì)算的FPGA實(shí)現(xiàn)［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2007（2）：56-58，62.

［5］俞訊.32位CRC校驗(yàn)碼的并行算法及硬件實(shí)現(xiàn)［J］.信息技術(shù)，2007（4）：71-74.

（編輯 王永超）

General parallel CRC computing method and implementation based on FPGA

Qiu? Xiaotao

（CEC Defense Technology Company Limited， Nanjing 210000， China）

Abstract：? Cyclic redundancy check （CRC） code is one of the most commonly used code in channel codes. It is an error detection code with high detection probability and easy hardware implementation. It is widely used for its simple implementation and strong error detection ability. Firstly， this paper introduces the algorithm principle of cyclic redundancy check， and analyzes the specific calculation process of CRC. Secondly， this paper proposes a high-speed parallel CRC algorithm， and takes CRC-CCITT as an example to derive the CRC-CCITT logic relation of 8-bit parallel computing. Finally， according to the deduced logic relation of 8-bit parallel computing， the hardware implementation circuit of 8-bit parallel CRC-CCITT is given. Compared with the existing lookup table methods， the algorithm has the characteristics of saving logical resources and high speed.

Key words： cyclic redundancy check; generator polynomial; parallel computing; FPGA