◆張 穎 郭志君

?

10G以太網(wǎng)高速CRC的FPGA實(shí)現(xiàn)與優(yōu)化

◆張 穎 郭志君

（1.陸軍參謀部第一通訊站 北京 101100；2.中國(guó)電子科技集團(tuán)第三十研究所 四川 610212）

在現(xiàn)今的以太網(wǎng)中，CRC校驗(yàn)已經(jīng)得到了廣泛的應(yīng)用。為了解決大流量的CRC校驗(yàn)的實(shí)時(shí)處理問題，本文提出了一種基于FPGA的流水線式的并行處理結(jié)構(gòu)。并拓展出了通用的校驗(yàn)?zāi)K。最后采用工業(yè)級(jí)的FPGA，并用Verilog硬件描述語言實(shí)現(xiàn)。并搭建環(huán)境進(jìn)行試驗(yàn)與驗(yàn)證。

可編程邏輯陣列（FPGA）；循環(huán)沉余校驗(yàn)（CRC）；10G以太網(wǎng)；并行結(jié)構(gòu)；流水線結(jié)構(gòu)

0 前言

0.1 研究背景

在現(xiàn)今的高速網(wǎng)絡(luò)中，為了保證傳輸質(zhì)量和差錯(cuò)控制[1]，循環(huán)沉余校驗(yàn)（CRC）因其具有很強(qiáng)的誤碼檢驗(yàn)?zāi)芰涂垢蓴_能力，被廣泛的應(yīng)用。

在IEEE802.3以太網(wǎng)的標(biāo)準(zhǔn)協(xié)議中，CRC校驗(yàn)碼是以太網(wǎng)傳輸幀的重要造成部分。但是常用的傳統(tǒng)的CRC校驗(yàn)碼的實(shí)現(xiàn)方式都是采用串行方式實(shí)現(xiàn)，其通過串行移位的方式編碼實(shí)現(xiàn)，這種方式通過較高的頻率得以用簡(jiǎn)單的電路。但其也存在著很多缺陷，最致命的就是處理數(shù)據(jù)吞吐量較低，已經(jīng)難以適應(yīng)現(xiàn)今網(wǎng)絡(luò)對(duì)于吞吐量日益增長(zhǎng)的要求[2]。

隨著以FPGA為代表的可編程邏輯器件在網(wǎng)絡(luò)設(shè)備中大規(guī)模的應(yīng)用，給CRC的高速實(shí)現(xiàn)提供了一個(gè)新的實(shí)現(xiàn)途徑。CRC校驗(yàn)易于在FPGA中實(shí)現(xiàn)，其占用資源少，且很容易實(shí)現(xiàn)較高的吞吐量，因此其可以成為高速以太網(wǎng)中差錯(cuò)檢驗(yàn)的一種重要實(shí)現(xiàn)方式[3]。

0.2 研究現(xiàn)狀

在以太網(wǎng)的發(fā)展過程中，研究人員對(duì)CRC校驗(yàn)進(jìn)行了很多的研究。Ahmad等人提出過基于流水線的CRC校驗(yàn)算法，該方式的優(yōu)點(diǎn)是資源占用少，但是處理仍然需要較多個(gè)時(shí)鐘周期[4]。Stavinov等人對(duì)CRC的邏輯電路進(jìn)行了優(yōu)化，但由于其邏輯表并沒有改變，所以其資源占用依然較多[5]。畢占坤等人針對(duì)不同位寬的數(shù)據(jù)設(shè)計(jì)CRC校驗(yàn)方式，該方法能大大的提升性能，但因?yàn)槠鋸?fù)雜性以及資源占用高，而無法大規(guī)模使用[6]。徐展琦等人提出了一種多通道的CRC實(shí)現(xiàn)方式，該方式在性能上有很大的提升，但其設(shè)計(jì)難度較高，并且對(duì)處理器自身的性能要求很高，因而也不適宜大規(guī)模使用[7]。

基于上文中等人的研究，在這里提出一種并行方式和流水線方式相結(jié)合的CRC實(shí)現(xiàn)方法。該方法可以很容易的計(jì)算出任意比特長(zhǎng)度的CRC校驗(yàn)的值。該方法充分利用的FPGA硬件本身所具有的并行特性、流水線特性、以及高性能的特性；并且設(shè)計(jì)了任意比特（小于64bit）位寬的CRC效驗(yàn)處理單元，極大的節(jié)省了資源。最后通過Verilog進(jìn)行編碼，并進(jìn)行試驗(yàn)驗(yàn)證。

1 CRC原理

1.1. CRC校驗(yàn)原理

CRC校驗(yàn)[8]的基本原理是線性編碼理論。當(dāng)發(fā)送方要發(fā)送K位信息序列時(shí)，以一定規(guī)則產(chǎn)生長(zhǎng)度為l位的校驗(yàn)序列，并跟隨信息位一起傳送給對(duì)端。接收方接到序列后，根據(jù)校驗(yàn)序列來判斷傳輸是否出現(xiàn)錯(cuò)誤。

CRC校驗(yàn)碼的實(shí)現(xiàn)方法就是采用多項(xiàng)式方式循環(huán)編碼。其先將信息多項(xiàng)式左移l位，然后進(jìn)行模2除的運(yùn)算?？梢员硎緸椋?/p>

如圖1所示。

其中R(x)即為CRC序列，M(x)為數(shù)據(jù)序列，G(x)為生成多項(xiàng)式。

在接收端，接收到比特串后，用模二整除G(x)，如果得到的結(jié)果等于R(x)，那么說明該CRC校驗(yàn)正確，反之則錯(cuò)誤。

在IEEE802.3的規(guī)定中，生成多項(xiàng)式G(x)的標(biāo)準(zhǔn)格式為：

例如CRC32的表達(dá)式即為：

1.2. CRC算法實(shí)現(xiàn)

傳統(tǒng)的CRC效驗(yàn)實(shí)現(xiàn)方法，是通過移位異或的迭代運(yùn)算來實(shí)現(xiàn)的。在實(shí)際電路中，是通過線性移位寄存器的級(jí)聯(lián)來實(shí)現(xiàn)。其具體實(shí)現(xiàn)過程如圖2所示。

圖2 CRC原理

圖2中寄存器狀態(tài)表示余數(shù)，異或表示模2除。l0,、l1、...、lk-1為寄存器的狀態(tài)，g0,、g1、...、gk-1為生成多項(xiàng)式。其值為0表示斷開，為1表示連通。這種電路只需要最基本的寄存器與異或門電路來實(shí)現(xiàn)。

但是在實(shí)際的應(yīng)用中，這種實(shí)現(xiàn)方式雖然簡(jiǎn)單，但是其處理速度非常慢，其每個(gè)周期只處理一位數(shù)據(jù)，這樣對(duì)于較長(zhǎng)的數(shù)據(jù)流來說其時(shí)延會(huì)非常高。并且這種方式，當(dāng)有n比特的數(shù)據(jù)流需要進(jìn)行處理時(shí)，就需要n個(gè)寄存器和2n個(gè)異或門，這對(duì)資源的占用也是一種很大的挑戰(zhàn)。

為了適應(yīng)于硬件加速與高速處理，遞推算法和矩陣算法相繼被提出[9]。

（1）遞推法

由于CRC算法的串行特性，其CRC當(dāng)前值只與前一CRC值與輸入的前一值相關(guān)。若假如數(shù)據(jù)以8位并行輸入，其計(jì)算方式應(yīng)該和8位串行輸入計(jì)算方式一樣。其計(jì)算方法為下式。

以此類推就可得到更多的CRC計(jì)算式。并且此方法有較好的通用性，并且其可拓展性也較強(qiáng)。

（2）矩陣法

矩陣法適用于并行程度較高的數(shù)據(jù)。以CRC32為例。

由圖2可推倒得出：

其中：

第一，企業(yè)應(yīng)強(qiáng)化相關(guān)管理意識(shí)，承擔(dān)共享單車回收管理的主要責(zé)任。第二，企業(yè)應(yīng)加強(qiáng)與政府之間的合作，合理有效利用政府的資金、技術(shù)、人員等支持，同時(shí)發(fā)揮企業(yè)與政府雙重作用，更好地建立健全共享單車回收維修管理制度，實(shí)現(xiàn)資源更優(yōu)配置。第三，企業(yè)可與相關(guān)同行企業(yè)合作，降低人力成本，更好的回收損壞報(bào)廢共享單車，減輕城市交通壓力以便方便政府對(duì)于城市慢行交通系統(tǒng)管理。第四，企業(yè)應(yīng)建立健全單車回收維修管理體制，為相關(guān)維修人員提供學(xué)習(xí)培訓(xùn)的機(jī)會(huì)。

由上式可以得出：

矩陣運(yùn)算適合大規(guī)模并行數(shù)據(jù)的運(yùn)算，但由于其運(yùn)算復(fù)雜，資源消耗多，應(yīng)用并不是十分廣泛。

2 以太網(wǎng)中的CRC設(shè)計(jì)

現(xiàn)今高速的10G以太網(wǎng)已經(jīng)廣發(fā)的普及。FPGA+PHY芯片的以太網(wǎng)處理方案也變得越來越多。所以基于FPGA的CRC設(shè)計(jì)就顯得尤為重要。

2.1. 以太網(wǎng)中的CRC校驗(yàn)控制

根據(jù)IEEE802.3協(xié)議，以太網(wǎng)幀（包含CRC校驗(yàn)字段）的結(jié)構(gòu)如圖3所示。

圖3 以太網(wǎng)幀結(jié)構(gòu)

在實(shí)際的網(wǎng)絡(luò)應(yīng)用中，發(fā)送和接收雙方約定生成多項(xiàng)式和位寬，以實(shí)現(xiàn)數(shù)據(jù)通信的差錯(cuò)控制。其具體步驟如圖4所示。

圖4 以太網(wǎng)幀的CRC校驗(yàn)

在網(wǎng)絡(luò)設(shè)備接收到以太網(wǎng)數(shù)據(jù)幀后，先送到MAC層進(jìn)行編碼處理。在MAC層中進(jìn)行CRC校驗(yàn)。當(dāng)校驗(yàn)結(jié)果正確，則傳輸?shù)缴蠈舆M(jìn)行更多的處理；當(dāng)校驗(yàn)錯(cuò)誤時(shí)就進(jìn)行重傳操作。這樣便保證了數(shù)據(jù)傳輸?shù)耐暾院涂煽啃浴?/p>

具體的CRC校驗(yàn)過程為：（1）FCS效驗(yàn)區(qū)域字段高低比特翻轉(zhuǎn)。（2）寄存器初值置為1。（3）計(jì)算CRC（采用CRC算法邏輯）。（4）CRC取反。（5）取反后的CRC字段高低比特翻轉(zhuǎn)。這樣就得到了以太網(wǎng)的CRC字段的值。

2.2.流水線CRC校驗(yàn)設(shè)計(jì)

在10G以太網(wǎng)中，通常采用64位并行數(shù)據(jù)來進(jìn)行處理。而以太網(wǎng)的數(shù)據(jù)不都是64的整數(shù)倍，那么肯定就會(huì)出現(xiàn)不夠64位的邊界問題。在傳統(tǒng)的設(shè)計(jì)中，對(duì)于滿64位的則采用CRC32進(jìn)行校驗(yàn)計(jì)算，對(duì)于不夠64位的部分，采用CRC8、CRC16等來進(jìn)行計(jì)算。這就導(dǎo)致設(shè)計(jì)中必須有以上對(duì)應(yīng)的CRC計(jì)算模塊，這樣就占用了資源。

本文現(xiàn)設(shè)計(jì)一個(gè)流水線結(jié)構(gòu)的CRC編碼器。

設(shè)X的CRC32為X’[31:0]，Y的CRC32為Y’[31:0]，X’的CRC32為Z[31:0]，則可以得出X的拓展序列{X,Y}的CRC32為：

那么對(duì)于8-64位的任意位寬的輸入，的計(jì)算中間節(jié)點(diǎn)可以表示為：

圖5表示一個(gè)流水線的CRC編碼器。

圖5 流水線CRC編碼器

模塊CRC8為8位輸入的CRC模塊，CRC_EXPEND模塊為N位CRC模塊（N=8*k，k=1,2，...）

以上的流水線模塊可以輸出任意N位的CRC校驗(yàn)值。通過SIZE選擇器來控制不同位寬的輸出。這樣就降低了存儲(chǔ)空間。

CRC校驗(yàn)計(jì)算包含大量的異或運(yùn)算。采用適當(dāng)?shù)姆绞綄?duì)異或運(yùn)算并行，也可以大大的降低總的時(shí)延。

圖6 傳統(tǒng)異或運(yùn)算

圖7 優(yōu)化后的異或運(yùn)算

這樣雖然所進(jìn)行的異或次數(shù)一樣，但是前三次可以并行運(yùn)算，這樣跟傳統(tǒng)的方式相比就大大的降低了時(shí)延。對(duì)于多維的數(shù)據(jù)，這種方式的優(yōu)化效果更明顯。

3 試驗(yàn)與驗(yàn)證

3.1 仿真驗(yàn)證

驗(yàn)證CRC算法的正確性，通過Wireshark和ISE仿真軟件來抓包來進(jìn)行驗(yàn)證。驗(yàn)證結(jié)果如圖8，圖9所示。

圖8 一個(gè)以太網(wǎng)數(shù)據(jù)包

圖9 ISE仿真結(jié)果

從上圖可以看出，仿真結(jié)果的CRC運(yùn)算結(jié)果的值為A6FF4878，與Wireshark抓包的結(jié)果一致，這樣就驗(yàn)證了其正確性。

3.2 試驗(yàn)驗(yàn)證

采用Verilog語言，在賽靈思的Spartan-6,FPGA進(jìn)行編碼驗(yàn)證。采用10G的Testcenter網(wǎng)絡(luò)測(cè)試儀進(jìn)行吞吐量的測(cè)試。10G網(wǎng)絡(luò)測(cè)試儀試驗(yàn)環(huán)境如圖10所示。

圖10 測(cè)試環(huán)境

本試驗(yàn)采用200M時(shí)鐘，64位，即12.8GB的吞吐量，完全滿足10G的要求，經(jīng)測(cè)試，也完全能達(dá)到10G吞吐量。

本文所設(shè)計(jì)的CRC編碼器的資源占用情況對(duì)比，如表1所示?？梢钥闯鲈谫Y源節(jié)省方面也有很大的提升。

表1 本文所設(shè)計(jì)的CRC編碼器的資源占用情況對(duì)比

4 結(jié)束與總結(jié)

本文CRC運(yùn)算的效率問題。提出了一種流水線的CRC效驗(yàn)短發(fā)，并對(duì)其中的組合邏輯部分進(jìn)行了并行化的改進(jìn)。通過這兩種方式，節(jié)省了芯片的邏輯資源，并且降低了時(shí)延，提高了系統(tǒng)的性能。并且通過軟件仿真，以及實(shí)際網(wǎng)絡(luò)測(cè)試儀測(cè)試兩種方式進(jìn)行了驗(yàn)證，證實(shí)了上述的性能的提升。

[1]王新梅，肖國(guó)振.糾錯(cuò)碼：原理與方法[M]，西安：西安電子科技大學(xué)出版社，1991.

[2]張友亮，劉志軍，馬成海.萬兆以太網(wǎng)ＭＡＣ層控制器的ＦＰＧＡ設(shè)計(jì)與實(shí)現(xiàn)[J]．計(jì)算機(jī)工程與應(yīng)用，2018.

[3]劉璐，武明亮，何俊強(qiáng)．基于循環(huán)冗余校驗(yàn)碼的差錯(cuò)控制分析與實(shí)現(xiàn)［J］.成都大學(xué)學(xué)報(bào)（自然科學(xué)版），2011.

[4]AhmadA, Hayatl. Selection of polynomials forcyclic redundancy check for the use of high speed embedded: An algorithmic procedure [J]. WSEAS Transactions on Computers, 2011.

[5]Stavinov E. A practical parallel CRC generation method [J]. Circuit Cellar the Magazine for Computer Applications, 2010.

[6]畢占坤，張羿猛，黃芝平，等?；谶壿嬙O(shè)計(jì)的高速 ＣＲＣ并行算法研究及其FPGA實(shí)現(xiàn)[J]。儀器儀表學(xué)報(bào)，2007.

[7]徐展琦，裴昌幸，董淮南。一種通用多通道并行CRC計(jì)算及其實(shí)[J]。南京郵電大學(xué)學(xué)報(bào)，2008.

[8]Ramabadran T V, Gaitonde S S, A tutorial on CRC computations [J]. IEEE Micro, 1988.

[9]張樹剛，張遂南．CRC校驗(yàn)碼并行計(jì)算的FPGA實(shí) 現(xiàn)[J]。計(jì)算機(jī)技術(shù)與發(fā)展，2007.