基于系數運算的并行CRC算法

張笑銘，梁利平，王志君

（1.中國科學院大學北京100029；2.中國科學院微電子研究所，北京100029）

CRC（循環冗余校驗）是通信領域廣泛使用的一種校驗算法，它將計算出的校驗碼添加在數據位之后，為通信過程提供校驗能力。CRC分為串行CRC和并行CRC[1]，串行CRC每個周期只能輸入一位數據進行計算，通常使用LFSR[2-3]（線性反饋移位寄存器）進行實現。并行CRC每個周期可以同時輸入多位數據，用并行度這一參數來表示它每個周期計算的數據位數。相比串行CRC，并行CRC效率更高，但相應的算法復雜度也較大。一種普遍的做法是查表法[4]，事先將數據的CRC校驗碼存儲在一張表中，使用時直接查表就可以得到要計算的CRC校驗碼，但缺點是表不能太大，一般按字節進行計算，即并行度為8，此時表的大小為2的8次方。如果需要同時輸入4字節進行計算，那么表的大小為2的32次方，這時表所占用的存儲空間太大，難以實現。由于查表法適用于較小并行度下使用，因此限制了數據傳輸的速度。文獻[5-7]提出同時計算多次串行CRC完成并行CRC的計算，該方法雖然不需要額外的存儲資源，但在并行度較大時推導復雜，并且并行度改變時又需要重新計算。矩陣法[8-10]可以滿足并行度較大的情況，但由于涉及大量的矩陣乘法運算，復雜度較高。文獻[11-12]提前將矩陣乘法的結果計算出來，但由于不同并行度的矩陣乘法結果不同，需要在計算之前固定好并行度，在需要多種并行度計算的情況下就要為每種并行度計算矩陣乘法的結果，并且只適合于并行度小于生成多項式位數的情況。文獻[13-16]提出針對多并行度CRC計算的解決方法，但其資源占用過多且延時較大。本文中的算法利用并行CRC中特殊矩陣的性質，將矩陣乘法的計算簡化成矩陣列向量之間的線性組合，只需要計算出該線性組合的系數，可以同時完成多種并行度的CRC計算。在軟件層面，該算法在并行度較小時，運行時間大于矩陣法，隨著并行度增大，運行時間逐漸小于矩陣法并趨于固定值。在硬件層面，該算法與矩陣法相比在占用更少資源的情況下可以獲得更高的工作頻率。

1 并行CRC算法

CRC算法的原理是假設發送一個k位的序列，將其表示為{d0，d1，…，dk-1}，為了驗證其發送和傳輸過程中是否發生錯誤，需要在數據位之后添加校驗位，校驗位的生成需要一個（m+1）位的生成多項式，省略掉最高位系數（最高位系數恒為1），表示為{pm-1，pm-2，…po}。生成方法是將原本的信息位左移m位后除以生成多項式，這里的除法是二進制除，最終得到的余數就是所要添加的CRC校驗碼。檢測過程將接收到的結果除以生成多項式，如果能被整除，說明數據正確，否則發生了錯誤。

并行CRC算法每次可以同時輸入多位數據進行計算，當所有的數據位輸入完成后產生最終的校驗位，而串行CRC算法每次只能輸入一位數據，所以速度上要比并行CRC算法慢。但串行CRC算法的優點是實現簡單并且耗費資源少，適用于對速度要求不高的場合，而對數據處理速度有較高要求時，就需要使用在串行CRC算法基礎上推導出的并行CRC算法。

圖1 串行CRC實現

由于串行CRC算法一般采用LFSR實現（如圖1），而LFSR可以看作是一個離散的線性時不變系統[1]，由線性系統的理論，一個離線的線性時不變系統可以使用方程組來表示。

其中，X表示系統的狀態，Y表示系統的輸出，U表示系統的輸入。X，Y，U為列向量，F，G，H，J為矩陣。通過對此系統進行分析并結合LFSR的性質，可以得出在這個系統中系統的狀態同時是系統的輸出，即Y=X。因此由第二個方程可以推出H為單位矩陣，J為零矩陣。而第一個方程可以推出

依次類推可以得到一個公式，這個公式就是并行CRC算法的基本公式。

對上面式子使用Galois Field理論，將式中的加法用按位異或運算代替，乘法使用按位與來代替，式子仍然成立。式子變為

式（5）就是矩陣法所用的公式，w為并行度參數。為了求出w位輸入后的系統狀態（也就是CRC校驗的輸出），需要求解F矩陣的1到w次方，因此涉及到大量的矩陣乘法運算。

2 基于系數運算的并行CRC算法

基于系數運算的并行CRC算法在并行CRC公式的基礎上推導而來，由文獻[1]中并行CRC的生成特性可知X=[xm-1…x1xo]T，G=[0 0 … 0 1]，F=

將一個矩陣表示為列向量的形式T=[t0t1…tm-1]，根據矩陣乘法的性質，其與F矩陣相乘的結果是T·F=[pm-1·t0+…+p0·tm-1t0t1…tm-2]，可以看出是此矩陣每列向右移動一位，第一列變成F第一列每個元素與此矩陣每一列做與運算然后求和的結果。將F矩陣也表示為列向量的形式F=[f0f1…fm-1]，這樣F矩陣平方的列向量可以表示為F列向量線性組合的形式。

F矩陣n次方的列向量也是F列向量線性組合的形式，區別只是每個列向量的系數不同。當其與某個列向量相乘時，結果是一個列向量，這個列向量也是F列向量的線性組合。

F的（w-1）次方到1次方與列向量G相乘都可以表示為F列向量的一個線性組合，僅僅是列向量的系數不同，所以關鍵問題就是求出F每一列向量的系數。因為列向量G也可以看作是F的列向量的線性組合。

所以列向量G的系數為[1pm-1pm-2…p1]，為了求得FG的系數，對其進行化簡。

將F展開為列向量[f0f1…fm-1]，原本相乘的列向量按元素展開并進行整理合并。

因此FG系數為[((1·pm-1)+pm-1)+((1·pm-2)+pm-2)…(1·p0)]，把系數用新的符號表示。

同樣為求得F的2次方與G乘積的系數，也需要對其進行整理化簡。

F的2次方與G乘積的系數為，依次類推就可以得到F各次方與列向量G相乘的系數表示。

F的w次方每列的系數表示也適用上述類推規則，這是因為G=[0 0 … 0 1]T，Fw·G的結果就是Fw的最后一列，Fw+1·G的結果是Fw的倒數第二列（Fw與F相乘是Fw每列向右移動一位），依次進行下去直到最后Fw+m+1是Fw的第一列，因此可以從系數開始（初值為 [1pm-1pm-2…p1]），按照來生成下一系數表示，直到生成（w+m）次，這樣就得到了Fw列向量和[Fw-1G…FG…G]的系數表示。

由于每個系數表示都可以看作是行向量，因此可以把這些行向量組合成一個系數矩陣

根據矩陣法的公式（式（5）），將系統當前狀態與輸入數據組成列向量[xm-1…x1x0d0d1…dw-1]T，此列向量分別與系數矩陣的每一列按位與，得到的結果向量中元素之和（用異或代替）就是一個系數的最終計算結果。因此將每個結果向量進行縮減異或運算，得到最終的系數向量[a0a1a2…am-1]，把系數代入線性組合表達式中，就可以獲得w位數據輸入后系統的狀態，同時也是系統的輸出。

基于系數運算的并行CRC算法可以同時實現多種并行度的CRC計算，當并行度變為w1時（w1小于w），根據矩陣法的公式，需要求出Fw1和[Fw1-1G…FG…G]，因為其系數矩陣和并行度為w時的系數矩陣最后（w1+m）行相同，所以可以將系統當前狀態與輸入的w1位數據組成列向量，然后在此列向量的起始補 0到（w+m）維，列向量變為[0…0xm-1…x1x0d0d1…dw1-1]T，此時按照并行度為w的方法計算就可以得到并行度為w1時的CRC校驗碼。

圖2 基于系數運算的并行CRC實現

算法的多數操作都是位運算，消除了矩陣法當中大量的乘法運算，因此易于硬件電路的實現，其電路結構如圖2所示，可以看出硬件電路的結構和算法實現步驟一致。

3 實驗結果

在MATLAB上比較矩陣法和基于系數運算的并行CRC算法的運行時間，設定生成多項式為CRC-32的生成多項式，并行度分別為1，2，4，8，16，32，64和128，測試數據共1 000組，每組大小128字節。實驗主機配置：CPU型號Intel Core i5，主頻2.7 GHz，內存8 GB。統計在不同并行度下一組數據的平均運行時間，繪制矩陣法和系數運算法的平均運行時間隨并行度變化曲線（如圖3）。

基于系數運算的并行CRC算法隨著并行度的增加運行時間首先遞減然后逐漸趨于固定值。因為隨著并行度逐漸增大，計算的次數變少，相應的運行時間也在變少，雖然生成系數矩陣的時間隨著并行度的增大而增加，但增加的時間小于減少的時間，運行時間出現下降的趨勢。當并行度增加到一定程度后，增加的時間和減少的時間基本一致，因而逐漸平穩。矩陣法的運行時間先遞減然后線性遞增。因為當并行度較小時，計算矩陣的w次方與計算次數相比對運行時間影響較小，因此隨著并行度增大運行時間逐漸減少。當并行度w繼續增大時，計算矩陣的w次方所用的時間迅速增加，由于較大并行度下的計算次數變化不明顯，因而運行時間又開始逐漸遞增。根據實驗結果，當并行度大于14時，基于系數運算的并行CRC算法運行時間開始小于矩陣法。

圖3 矩陣法和系數運算法運行時間變化曲線

在Xilinx型號為XC6VSX475T的FPGA上進行算法的硬件實現，將其并行度分別設為32，64和128，綜合以及布局布線后查看其資源使用率和最高工作頻率，與矩陣法的對比如表1，表2和表3所示。

表1 并行度32綜合布線結果對比

表2 并行度64綜合布線結果對比

表3 并行度128綜合布線結果對比

在并行度為32時，`系數運算法比矩陣法占用的資源少18%，工作頻率比矩陣法高6%。在并行度為64時，系數運算法比矩陣法占用的資源少19%，工作頻率比矩陣法高12%。在并行度為128時，系數運算法比矩陣法占用的資源少49%，工作頻率比矩陣法高21%。并行度越大系數運算法優勢越明顯，因此更適合于對并行度有較高要求的情況下使用。

4 結論

在并行CRC公式基礎之上利用特殊矩陣性質推導出基于系數運算的并行CRC算法。此算法相比矩陣法減少了計算量，并且和矩陣法一樣具有通用性，適合于任意并行度的CRC計算。未來的工作是探索其在以太網等對速度要求很高且需要多種并行度情況下的具體應用。

參考文獻：

[1]Campobello G，Patane G，Russo M.Parallel CRC realization [J].IEEETransactions on Computers，2003，52（10）:1312-1319.

[2]李永基，魏文軍.基于LFSR的CRC校驗碼在FPGA上的實現[J].蘭州交通大學學報，2015，34（6）:91-94.

[3]鄭誠瑋，戴紫彬，李偉.面向可重構并行化處理的線性反饋移位寄存器統一架構研究[J].微電子學與計算機，2015，32（11）:111-115.

[4]季鵬輝，孟丁，任勇峰.基于FPGA的16bit CRC校驗查表法設計[J].電子器件，2013，36（4）:580-584.

[5]朱榮華.一種CRC并行計算原理及實現方法[J].電子學報，1999，27（4）:143-145.

[6]闞佳沖，潘文明，鄭堅澤，等.基于FPGA全參數化CRC的推導及實現[J].現代電子技術，2015，38（8）:154-158.

[7]劉偉，王俊芳，王立瑩，等.千兆以太網MAC中CRC算法的設計與實現[J].通信技術，2012，45（7）:36-38.

[8]劉昭，蘇厲，金德鵬，等.10G以太網系統中的并行CRC編解碼器的設計[J].電子技術應用，2004，30（4）:47-50.

[9]梁海華，盤麗娜，趙秀蘭，等.CRC查詢表及其并行矩陣生成方法[J].計算機科學，2012，39（6）:154-158.

[10]梁海華，盤麗娜.快速CRC逆序校驗方法[J].計算機應用，2013，33（7）:1833-1835.

[11]陳玉泉.一種并行CRC算法的實現方法[J].現代電子技術，2005，28（22）:21-23.

[12]薛俊，段發階，蔣佳佳，等.基于Matlab的并行循環冗余校驗Verilog代碼自動生成方法[J].計算機應用，2016，36（9）:2503-2507.

[13]袁征，冶曉隆，郭超.基于FPGA的10G以太網并行CRC設計[J].計算機工程與設計，2014，35（5）:1510-1515.

[14]B Li，ZP Huang，SJ Su，et al.Implementation of CRC in 10-Gigabit Ethernet Based on FPGA[J].Applied Mechanics&Materials，2014，599-601:1548-1552.

[15]鐘桂森，易清明，石敏.一種新型的10G以太網并行循環冗余校驗設計[J].計算機工程，2016，42（5）:292-296.

[16]張友亮，劉志軍，馬成海，等.萬兆以太網MAC層控制器的FPGA設計與實現[J].計算機工程與應用，2012，48（6）:77-79.