通用并行CRC計算方法及FPGA實現

仇曉濤

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

關鍵詞：循環冗余校驗；生成多項式；并行計算；FPGA

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

0 引言

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

1 CRC校驗碼原理

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

CRC校驗碼的編碼步驟：

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

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

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

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

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

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

余數多項式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）對應的碼組為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除運算，產生的余數就是CRC碼的校驗位。同理，接收端將接收到的n+k位信息碼除以相同的生成多項式G（x），根據式（3），如果產生的余數為0，則認為接收端接收到的二進制數據流正確無誤碼；否則就認為接收端接收到的二進制數據流在傳輸過程中產生了誤碼。

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

該CRC-CCITT串行電路只用到了基本的異或門和移位寄存器邏輯單元。如果在高速數字通信系統中采用CRC串行運算，就需要高速串行同步時鐘及相應的高速器件，極大地增加了電路的硬件成本以及實現復雜度。該問題通常可以采用并行運算的處理方法解決，因此需要研究一種并行CRC處理電路。

2 并行計算與實現

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

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

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

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

3 性能分析

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

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

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

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

4 結語

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

參考文獻

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

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

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

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

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