基于系數(shù)運(yùn)算的并行CRC算法

張笑銘，梁利平，王志君

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

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

1 并行CRC算法

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

并行CRC算法每次可以同時(shí)輸入多位數(shù)據(jù)進(jìn)行計(jì)算，當(dāng)所有的數(shù)據(jù)位輸入完成后產(chǎn)生最終的校驗(yàn)位，而串行CRC算法每次只能輸入一位數(shù)據(jù)，所以速度上要比并行CRC算法慢。但串行CRC算法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單并且耗費(fèi)資源少，適用于對速度要求不高的場合，而對數(shù)據(jù)處理速度有較高要求時(shí)，就需要使用在串行CRC算法基礎(chǔ)上推導(dǎo)出的并行CRC算法。

圖1 串行CRC實(shí)現(xiàn)

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

其中，X表示系統(tǒng)的狀態(tài)，Y表示系統(tǒng)的輸出，U表示系統(tǒng)的輸入。X，Y，U為列向量，F(xiàn)，G，H，J為矩陣。通過對此系統(tǒng)進(jìn)行分析并結(jié)合LFSR的性質(zhì)，可以得出在這個(gè)系統(tǒng)中系統(tǒng)的狀態(tài)同時(shí)是系統(tǒng)的輸出，即Y=X。因此由第二個(gè)方程可以推出H為單位矩陣，J為零矩陣。而第一個(gè)方程可以推出

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

對上面式子使用Galois Field理論，將式中的加法用按位異或運(yùn)算代替，乘法使用按位與來代替，式子仍然成立。式子變?yōu)?/p>

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

2 基于系數(shù)運(yùn)算的并行CRC算法

基于系數(shù)運(yùn)算的并行CRC算法在并行CRC公式的基礎(chǔ)上推導(dǎo)而來，由文獻(xiàn)[1]中并行CRC的生成特性可知X=[xm-1…x1xo]T，G=[0 0 … 0 1]，F(xiàn)=

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

F矩陣n次方的列向量也是F列向量線性組合的形式，區(qū)別只是每個(gè)列向量的系數(shù)不同。當(dāng)其與某個(gè)列向量相乘時(shí)，結(jié)果是一個(gè)列向量，這個(gè)列向量也是F列向量的線性組合。

F的（w-1）次方到1次方與列向量G相乘都可以表示為F列向量的一個(gè)線性組合，僅僅是列向量的系數(shù)不同，所以關(guān)鍵問題就是求出F每一列向量的系數(shù)。因?yàn)榱邢蛄縂也可以看作是F的列向量的線性組合。

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

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

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

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

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

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

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

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

基于系數(shù)運(yùn)算的并行CRC算法可以同時(shí)實(shí)現(xiàn)多種并行度的CRC計(jì)算，當(dāng)并行度變?yōu)閣1時(shí)（w1小于w），根據(jù)矩陣法的公式，需要求出Fw1和[Fw1-1G…FG…G]，因?yàn)槠湎禂?shù)矩陣和并行度為w時(shí)的系數(shù)矩陣最后（w1+m）行相同，所以可以將系統(tǒng)當(dāng)前狀態(tài)與輸入的w1位數(shù)據(jù)組成列向量，然后在此列向量的起始補(bǔ) 0到（w+m）維，列向量變?yōu)閇0…0xm-1…x1x0d0d1…dw1-1]T，此時(shí)按照并行度為w的方法計(jì)算就可以得到并行度為w1時(shí)的CRC校驗(yàn)碼。

圖2 基于系數(shù)運(yùn)算的并行CRC實(shí)現(xiàn)

算法的多數(shù)操作都是位運(yùn)算，消除了矩陣法當(dāng)中大量的乘法運(yùn)算，因此易于硬件電路的實(shí)現(xiàn)，其電路結(jié)構(gòu)如圖2所示，可以看出硬件電路的結(jié)構(gòu)和算法實(shí)現(xiàn)步驟一致。

3 實(shí)驗(yàn)結(jié)果

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

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

圖3 矩陣法和系數(shù)運(yùn)算法運(yùn)行時(shí)間變化曲線

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

表1 并行度32綜合布線結(jié)果對比

表2 并行度64綜合布線結(jié)果對比

表3 并行度128綜合布線結(jié)果對比

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

4 結(jié)論

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

參考文獻(xiàn)：

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

[2]李永基，魏文軍.基于LFSR的CRC校驗(yàn)碼在FPGA上的實(shí)現(xiàn)[J].蘭州交通大學(xué)學(xué)報(bào)，2015，34（6）:91-94.

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

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

[5]朱榮華.一種CRC并行計(jì)算原理及實(shí)現(xiàn)方法[J].電子學(xué)報(bào)，1999，27（4）:143-145.

[6]闞佳沖，潘文明，鄭堅(jiān)澤，等.基于FPGA全參數(shù)化CRC的推導(dǎo)及實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù)，2015，38（8）:154-158.

[7]劉偉，王俊芳，王立瑩，等.千兆以太網(wǎng)MAC中CRC算法的設(shè)計(jì)與實(shí)現(xiàn)[J].通信技術(shù)，2012，45（7）:36-38.

[8]劉昭，蘇厲，金德鵬，等.10G以太網(wǎng)系統(tǒng)中的并行CRC編解碼器的設(shè)計(jì)[J].電子技術(shù)應(yīng)用，2004，30（4）:47-50.

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

[10]梁海華，盤麗娜.快速CRC逆序校驗(yàn)方法[J].計(jì)算機(jī)應(yīng)用，2013，33（7）:1833-1835.

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

[12]薛俊，段發(fā)階，蔣佳佳，等.基于Matlab的并行循環(huán)冗余校驗(yàn)Verilog代碼自動(dòng)生成方法[J].計(jì)算機(jī)應(yīng)用，2016，36（9）:2503-2507.

[13]袁征，冶曉隆，郭超.基于FPGA的10G以太網(wǎng)并行CRC設(shè)計(jì)[J].計(jì)算機(jī)工程與設(shè)計(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以太網(wǎng)并行循環(huán)冗余校驗(yàn)設(shè)計(jì)[J].計(jì)算機(jī)工程，2016，42（5）:292-296.

[16]張友亮，劉志軍，馬成海，等.萬兆以太網(wǎng)MAC層控制器的FPGA設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（6）:77-79.