仇曉濤

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

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

中圖分類號：TN911.22? 文獻標志碼：A

0 引言

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

1 CRC校驗碼原理

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

CRC校驗碼的編碼步驟：

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

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

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

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

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

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

余數(shù)多項式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）對應(yīng)的碼組為n+k位，即：

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

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

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

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

2 并行計算與實現(xiàn)

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

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

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

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

3 性能分析

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

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

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

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

4 結(jié)語

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

參考文獻

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

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

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

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

［5］俞訊.32位CRC校驗碼的并行算法及硬件實現(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