基于100G以太網的一種并行CRC算法

胡坤焌 黃元峰

摘要：為解決大規模數據傳輸中CRC校驗的實時處理問題，文章提出了一種可同時處理256位數據的并行算法。文章首先通過遞推法推導出4位數據并行運算CRC（Cyclical Redundancy Check）關系式，并將表達式系數提出轉化為矩陣，在此基礎上對矩陣反復迭代，求得256位數據并行計算矩陣。該并行算法推導過程直觀易懂，算法實現簡單。文章最后采用硬件描述語言對算法進行描述，并搭建了驗證環境。仿真驗證結果表明了該方案的可行性，達到了設計指標要求，在時鐘頻率為400MHz的條件下可滿足100G以太網中CRC校驗需求。

關鍵詞：高速以太網;256位并行數據;CRC編碼; 矩陣并行算法;CRC校驗

中圖分類號：TP319.56 ? ? ? ?文獻標識碼：A

文章編號：1009-3044（2022）13-0037-03

1 引言

隨著科學技術的發展，數據的存儲和傳輸速度大大提高[1]。由于信息傳輸過程中的干擾，信號的失真依然難以避免，而通過增加冗余碼的方式來對傳輸數據進行檢錯和糾錯，可大大提高數字通信的可靠性。在多種檢錯碼中，由于CRC編碼和解碼方法簡單、檢錯能力強等特點，在數字通信中得到廣泛應用[2]。如今，網絡安全已經是熱門的探討話題[3]，CRC校驗也同樣在網絡安全領域中廣泛應用。在IEEE 2010年發布的802.3ba標準中，MAC（Media Access Control）層仍沿用之前的規定，而100Gb/s的數據傳輸速率使得以往CRC計算方法不再適用，需要采用更高位寬的并行數據來滿足現代數字通信對于高吞吐量需求。

CRC編碼實現方式多種多樣[4]。傳統串行編碼利用LFSR（Linear Feedback Shift Register）進行級聯，其結構簡單且容易實現，但缺點是處理效率低下且無法應用到對速度要求較高的場合，因此在高速通信領域中越來越多地使用并行計算的方法。文獻[5]中提到的查表法運算較快，但需要存儲模塊來預先存儲表中項目。當并行計算位數每增加一位，所需存儲的表項就會呈現指數級增長，由于占用資源多，所以難以應用在高位寬數據場合。文獻[6]提出了一種用級聯結構實現對64位數據的并行運算，但當進一步提高并行數據位寬時，級聯結構就會增多，256位并行計算時需要32個模塊，延時大大增加。文獻[7]提出了一種128位并行數據的CRC算法，但由于時鐘頻率的限制，滿足不了100Gb/s的吞吐量的需求。

本文提出了一種可實現256位并行數據的CRC編碼方案，并對此方案進行了硬件實現。通過對仿真結果進行分析，驗證了其準確性并具有一定的實用價值，在時鐘頻率為400MHz的情況下，其能夠滿足吞吐量為100Gb/s的需求。

2 CRC校驗原理

設通信中待檢測的信息碼為n位，將此信息碼用多項式M表示：

[M=mn-1Xn-1+mn-2Xn-2+…+m1X+m0 ] ? ? ?（1）

為了計算該數據的CRC，還需要一個稱為生成多項式的多項式g（x），其最高次冪為k。待編碼的信息序列與多項式g（x）進行模二運算，則會對應生成一個k-1位的冗余碼。CRC檢驗的一般計算流程如下：

1）將式（1）中的多項式M乘以[Xk]，即信息序列左移k位得到式（2）：

[XkM=mn-1Xk+n-1+mn-2Xk+n-2+L+m1Xk+1+m0Xk] ? ? （2）

2）將得出來的結果式（2）除以生成多項式g（x），得到式（3）及相應的余數多項式r（x）：

[XkMg（x）=q（x）+rxgx ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）]

其中r（x）為：

[rx=rk-1xk-1+rk-2xk-2+…+r1x+r0 ? ? ? ? ? ? （4）]

3）將式（2）（4）帶入式（3）中，則得到附有CRC碼的數據序列式（5）：

[qxgx=XkM+rx=mn-1Xk+n-1+…+m1Xk+1+…+r1x+r0 ]

（5）

4）在接收端接收到帶CRC碼的數據序列后，使用相同的多項式進行模二運算。若余數為0，則表明數據在傳輸中沒有錯誤。反之，則說明傳輸發生錯誤。

通過線性反饋寄存器級聯實現的CRC串行計算電路[8]主要由移位寄存器和異或門組成，具體硬件結構如圖1所示[9]。每個時鐘周期僅能輸入1比特數據，并進行相應移位和異或運算后得到計算結果。對于n位的數據來說，則需要n個周期完成CRC值計算。由于串行計算效率低下，一般只被用于低速通信的場合中[10]。

設[cj+1i+1]為第j+1次輸入數據的情況下第i+1位CRC的值，[cji]為第j次輸入數據的情況下第i位CRC的值，[dj+1]為第j+1位的數據輸入，[cj31]為第j位數據輸入后的第31位CRC值。由此則可以得到當前此位數據的CRC值與前一位數據及其CRC碼之間的關系，即式（6）：

[cj+1i+1=cji⊕gi+1dj+1⊕cj31 ? ? ? ? ? ? ? ? ? ? ? ? ?（6）]

3矩陣并行算法

依據以太網的國際標準IEEE 802.3[11]，數據幀中使用的CRC校驗模型為CRC-32[12]，其對應的生成多項式g（x）為[13]：

[gx=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1]

對式（6）進行4次遞歸運算，可得到處理4位數據后的CRC碼與初始CRC碼和數據之間的關系式，推導出的CRC-32關系式如下：

[c431=c270c430=c260L ? ? ? ? ?L c45=c310⊕c290⊕c280⊕c280⊕c00⊕d3⊕d1⊕d0L ? ? ? ? ?Lc41=c290⊕c280⊕d1⊕d0c40=c280⊕d0]

當前CRC值中的每一位的值都可表達為式（7）：

[c1i=xi31c031⊕L⊕xi0c00⊕yi3d13⊕L⊕yi0d10 ? ? ? ? ? ? ? ? ? （7）]

其中i為自然數，i=0，1，...，31。x和y分別為初始CRC碼及輸入的4位數據的系數。

將式（7）表達式中的系數x、y提出，可得到一個36*32的矩陣，如矩陣（1）。

將矩陣（1）進行轉置，拆分成兩塊。其中前32行為系數x組成的32*32 CRC系數矩陣[14]，如矩陣（2）。

后四行為系數y組成的4*32輸入數據參數矩陣：

[00100110000010001110110110111000000100110000010001110110110111000000100110000010001110110110111000000100110000010001110110110111]

設：

[C1=C131，C130…C1i…C10]

[C0=C131，C130…C1i…C10]

根據式（2）并將式中的加號替換為異或，可以得到第一次4位數據輸入結果，計算公式如式（8）：

[C1=C0*C32*32+D1*D4*32] ? ? ? ? ? ? ? ? ? ? ? [8]

將式（8）進行一次迭代，可以得到第二次4位數據輸入計算結果式（9）：

[C2=C1*C32*32+D2*D4*32=C0*C32*32+D1*D4*32*C32*32+D2*D4*32] ? ? ? ? ? ? [9]

同理，將式（9）再進行迭代，經過6次迭代后可得到256位數據并行的矩陣表達式，即式（10）：

[C256=C0*C25632*32+D256*D256256*32 ? ? ? ? ? ? ? ? ? ? ? 10]

式（10）中[C256]為256位并行數據輸入后的CRC值，[D256]為256位并行輸入數據，[D256256*32]和[C25632*32]為256位數據并行時的參數矩陣。注意：當用MATLAB計算矩陣時要將矩陣進行奇數變1，偶數變0的處理[15-16]。

256位并行數據的計算流程如圖2所示。

4邏輯設計

本文以100G以太網中采用的CRC-32計算為例，該以太網每周期可處理數據位寬為256bit，時鐘頻率可達400MHz，其邏輯設計結構如圖3所示。

在一個時鐘周期內，輸入256bit待處理數據。根據信號szin、sop對數據進行前補零、字節高低位翻轉等預處理操作。將處理結束的數據送入計算模塊，得到第一步計算數據crc_s1，并將crc_s1作為下一輸入的參數值進行迭代。當eop信號有效時表示輸入計算結束，對此時得到的crc_s1進行翻轉，取反操作即得到輸入CRC碼。

5仿真驗證

為了驗證矩陣計算的正確性，使用傳統串行計算和矩陣計算的方法對相同的輸入值進行編碼，在Modalism SE-64搭建的平臺上進行仿真驗證，再將兩者的仿真結果進行對比。由仿真波形可以看出，當輸入值為63時，利用矩陣計算的CRC值為32xec7dd02d，而使用傳統串行計算最后的結果值也為32xec7dd02d。另外選取不同輸入值進行校驗，皆可得到相同的結果，說明矩陣計算的方法是正確的。

說明：圖4中clk為時鐘信號，din為當前的輸入值，crc為計算結果。由于使用矩陣法可一次處理256位數據，所以可單周期完成運算。圖5中data為總輸入值，din為當前輸入值，一個時鐘周期輸入1比特的0或1。

注意：在本次使用矩陣法和串行方式對輸入值進行計算時均沒有加入數據預處理和結果處理部分，僅為驗證相同輸入情況下矩陣計算的正確性。

6結論

本文介紹了CRC并行和串行兩種實現方式，并分析了如今主流高位寬并行算法的特點，然后基于4位并行數據的矩陣算法，通過反復迭代得到可應用于高位寬輸入的計算矩陣。利用本文的思想和方法可以方便地得出不同的并行度下的CRC計算矩陣，并應用到不同場合的數據校驗中。本文以256位數據并行為例，用硬件描述語言對算法進行硬件實現并搭建驗證環境。仿真驗證結果表明，在時鐘頻率為400MHz情況下，數據吞吐量可達到100Gb/s，本文的思想和方法能夠滿足100G以太網中高速網絡通信中進行CRC計算校驗的要求。

參考文獻：

[1] 夏忠海，任勇峰，賈興中，等.基于FPGA的CRC查表法設計及優化[J].電測與儀表，2017，54（3）：54-59，88.

[2] 楊衛平.CRC計算實現方法[J].電子技術與軟件工程，2018（9）：158-159.

[3] 黃麗麗.大數據背景下的計算機網絡安全探討[J].電腦知識與技術，2021，17（23）：38-39.

[4] 姚威.循環冗余校驗碼并行算法的研究與實現[J].計算機與數字工程，2006，34（9）：112-114.

[5] 周凱，田楓，李愛國.基于查表法CRC檢錯碼改進算法的研究與實現[J].微型電腦應用，2017，33（8）：12-14.

[6] 王濤，屈代明，江濤.降低SCL譯碼錯誤的級聯極化碼[J].中興通訊技術，2019，25（1）：5-11.

[7] 趙坤鵬，吳龍勝，馬徐瀚，等.一種基于矩陣的并行CRC校驗算法[J].電子設計工程，2017，25（3）：85-88.

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

[9] Sprachmann M.Automatic generation of parallel CRC circuits[J].IEEE Design & Test ofComputers，2001，18（3）：108-114.

[10] 朱正鵬，朱旭鋒，李賓，等.一種位寬可變的CRC校驗算法及硬件實現[J].航天控制，2019，37（2）：42-48.

[11] Cheng C，Parhi K K.High-speed parallel CRC implementation based on unfolding，pipelining，and retiming[J].IEEE Transactionson Circuits and Systems II：Express Briefs，2006，53（10）：1017-1021.

[12] 張穎，郭志君.10G以太網高速CRC的FPGA實現與優化[J].網絡安全技術與應用，2018（12）：58-60.

[13] Ahmad A，Hayat L.Selection of polynomials for cyclic redundancy check for the use of high speed embedded： an algorithmic procedure[J].WSEAS Transactions on Computers，2011，10（1）：16-20.

[14] 陳基昕，王忠，趙錦宇.基于CAN總線的改進CRC校驗算法設計[J].工業控制計算機，2018，31（5）：37-38.

[15] 時亞麗.基于FPGA的CRC32校驗查找表算法的設計[J].山東工業技術，2016（10）：215.

[16] 王爽.CAN總線控制器CRC校驗碼的設計原理及實現[J].微處理機，2019，40（3）：25-28.

【通聯編輯：代影】