袁 征，冶曉?。?，郭 超

（1.國家數字交換系統(tǒng)工程技術研究中心，河南 鄭州450002；2.69019部隊）

0 引 言

循環(huán)冗余校驗 （CRC）易于實現，且具有較優(yōu)的誤碼檢錯能力和抗干擾性能被廣泛應用于高速網絡的差錯控制中［1］。隨著FPGA等可編程器件在骨干網絡傳輸設備中的大量使用，基于異或邏輯的CRC校驗在FPGA中易于實現、占用資源較少、且能實現線速網絡數據的差錯檢測而成為骨干網絡鏈路差錯控制的主要方式［2］。

在IEEE802.3以太網協議中，CRC校驗碼是以太網幀結構中重要的組成部分。傳統(tǒng)的CRC編譯碼器的實現都是基于串行方式，這種方式具有較高的工作頻率和簡單的電路結構，但是其采用串行移位，導致處理效率較低。隨著網絡速度的增長，尤其針對10G網絡已經難以實現實時處理［3］。為此研究人員針對CRC校驗的并行計算展開了研究［4－6］，文獻 ［7］提出了基于流水線的并行CRC校驗算法，該方法占用邏輯資源較少，但是處理單個周期需要8個周期的時延，無法滿足實時處理要求。Stavinov［8］針對CRC校驗的邏輯電路進行了改進，但是采用傳統(tǒng)并行邏輯表，占用資源較多。文獻 ［9］設計了一種多通道并行CRC，可以滿足10G以太網的實時CRC校驗，但算法設計復雜，對處理器性能要求較高。畢占坤［10］針對不同處理位寬分別設計了CRC校驗模塊，該方法處理性能較高，但推導復雜，難以實際部署應用。

基于此，本文提出了一種基于級聯結構的CRC校驗方法，通過此結構可以輸出任意比特位的CRC校驗值，解決了10G以太網非64比特結尾時需設計多種CRC邏輯而占用大量邏輯資源的問題，并改進了異或電路，降低了大量異或邏輯計算的處理時延。最后借助FPGA對本文方法進行了實現和驗證。

1 CRC校驗

1.1 CRC校驗原理

CRC校驗［11］利用線性編碼理論，其基本思想是：發(fā)送方在發(fā)送k位信息序列時，以一定規(guī)則產生監(jiān)督序列 （r位）并附在信息序列后面進行傳送。接收方收到序列后，根據規(guī)則進行檢驗是否傳輸錯誤。

CRC校驗碼是一種采用多項式編碼方式的循環(huán)碼字。如圖1所示，如果被檢驗序列有n位，則信息碼為 ｛mn－1，mn－2，...，m1，m0｝，多項表達式 M（x）可表示為

一般的CRC編碼方式是：先將信息多項式左移r位，然后做模2除法。即

所得到的R（x）就是CRC校驗碼，其中G（x）為生成多項式。

圖1 帶CRC的數據序列

對于接收端，在收到信息序列M（x）后，如果其模二整除G（x）所得的余數等于接收的R（x），則沒有誤碼。

G（x）的通用表達式為：G（x）＝xk＋gk－1xk－1＋gk－2xk－2＋...＋g2x2＋g1x＋1。以太網802.3協議對CRC校驗的生成多項式進行了規(guī)定。

802.3 規(guī)定的CRC32表達式為：G（x）＝x32＋x26＋x23＋x22＋x16＋x12＋x11＋x10＋x8＋x7＋x5＋x4＋x2＋x＋1。

1.2 CRC編碼過程

傳統(tǒng)的CRC校驗碼可以通過線性移位寄存器 （多次迭代的移位異或運算）來實現。如圖2所示，為通用的串行移位電路。其中：CRC校驗碼的余數用寄存器的狀態(tài) （存數）表示，模2除運算用異或表示。

圖2 串行CRC編碼實現原理

在圖2中，r0、r1、…、rk－1為k個移位寄存器的存數，移位過程由外部時鐘進行驅動，gi（i＝0、1、2、…、k－1）為生成多項式g（x）的系數，當gi為 “0”時表示斷路，gi為 “1”時表示通路。串行電路作為基本的CRC運算電路，只需要移位寄存器和異或門來實現。

1.3 CRC并行算法

傳統(tǒng)的串行CRC計算雖然實現簡單，但是其每個周期只處理一位數據，對于具有n位的數據流來說，需要n個周期完成CRC值的計算，其對于高速網絡通信數據的實時處理已經難以滿足要求。并且基于硬件來實現多維數據（n維）的串行CRC計算時，需要使用n個存儲器級的移位寄存器和2 n個異或門，占用了大量的運算資源，因此需要引入并行計算方法來提高處理效率。傳統(tǒng)基于軟件實現的并行CRC方法主要是查表法［12］，這種方法對于不同維數生成多項式序列和并行輸入序列需要建立不同的余數表，占用了大量存儲資源，并且查表深度和并行處理位寬呈2的冪次關系，不適用于硬件運算。因此提出了遞推法和矩陣法［13］。

1.3.1 遞推法

CRC并行算法是根據串行移位電路推導而來，如圖2所示。對于串行移位計算，當前CRC的值只與輸入信息序列的前一位和前一狀態(tài)的CRC值有關。當進行并行計算時，以8位并行輸入為例，8位信息序列同時輸入與8位信息序列串行移位輸入產生的CRC值相同，此時兩種電路等效。由此可得出并行CRC計算的方法，即

以此類推，可以得到r81、…、r815。遞推法計算并行CRC運算具有通用性，該方法消除了余數表，降低了對存儲資源的需求，提高了計算速度，具有較好的擴展性。

1.3.2 矩陣法

遞推法適用于并行輸入維數較低的情況，當并行度較高時，遞推運算較為復雜，因此提出了矩陣法計算。

以63位信息序列輸入的CRC－32為例。如圖2所示，記R＝ ［r0r1…r22r23］T為移位寄存器的當前狀態(tài)，D ＝［d64d63…d1d0］T為第1至64個時鐘的信息序列輸入，R′＝［r′0r′1…r′22r′23］T為移位寄存器的下一個狀態(tài)，R（64）為第64個時鐘之后移位寄存器的狀態(tài)。CRC－32并行設計就是找出函數關系R（64）＝f（R，D）。

由圖2進行遞推可得矩陣表達式

由式 （4）可得：R′＝T·R′＋S·d30＝T2·R＋TS·d31＋d·i30，以此類推，可得

其中所有代數運算和矩陣運算中的加法運算都為模2加。矩陣法將公式中的遞推關系轉化為矩陣運算，其更加直觀，并且適用于大位寬數據的并行運算。但矩陣法涉及大規(guī)模的矩陣乘法運算，在硬件實現時需占用大量的存儲資源和計算單元。因此，如何提高大位寬數據的并行CRC算法的計算效率和降低資源使用率成為一個重要的研究方面。

2 10G以太網中CRC設計

隨著10G以太網技術大量應用于骨干網絡鏈路和支持10G鏈路速率的MAC、PHY芯片的大量應用，使得基于高性能可編程器件FPGA結合以太網處理芯片 （MAC、PHY等）成為10G以太網處理設備的主流解決方案。

CRC校驗作為網絡數據處理流程的重要組成部分，隨著網絡速率的不斷增長，為了滿足線速CRC校驗，基于FPGA等硬件實現的CRC計算成為主要方式。傳統(tǒng)的并行CRC計算需要占用大量的存儲資源和邏輯資源，降低了系統(tǒng)的處理性能。因此，研究新型CRC計算方法以降低系統(tǒng)功耗和芯片工藝的要求成為必要。

2.1 以太網中CRC校驗

以太網通信中CRC校驗具有重要作用，通信雙方以約定的校驗生成多項式和校驗位寬實現數據傳輸的錯誤校驗。包括對接收的數據幀進行CRC計算、當CRC錯誤時進行數據重傳、發(fā)送數據幀時添加CRC校驗序列和為下一跳節(jié)點提供數據檢錯依據等。通過CRC校驗確保了以太網數據在整個鏈路中數據傳輸的可靠性。以太網數據傳輸中每個節(jié)點的CRC處理流程如圖3所示，具體包括：

（1）數據收到物理層之后送到介質訪問控制層（MAC）進行編解碼處理，MAC層中首先進行CRC校驗，通過比較計算的接收數據CRC值和接收的CRC值，當校驗不一致時產生重傳。

（2）對于CRC校驗正確的數據幀，上傳到上層進行處理，包括路由查表、TTL更新等。

（3）對于需要發(fā)送到下一跳 （next hop）時，首先計算待發(fā)送數據的CRC值，添加到數據序列組幀，為下一節(jié)點數據校驗提供依據，最后送到物理層進行傳輸。

圖3 以太網CRC校驗和計算流程

以太網CRC校驗遵循以太網IEEE802.3協議，IEEE802.3協議規(guī)定的以太網MAC子層的幀格式如圖4所示，包括：源＼目的地址、長度、數據域和幀校驗序列（frame check sequence，FCS），FCS校驗的區(qū)域包括幀的協議字段和數據字段區(qū)域。

圖4 以太網幀格式

在以太網通信中，以太網的字節(jié)序是大端模式 （高位在先），在計算FCS時首先需對幀內數據進行處理。IEEE802.3規(guī)定的以太網CRC校驗計算步驟如下：

步驟1 對收到的幀進行字節(jié)內部高低比特翻轉；

步驟2 寄存器初始值置為全1；

步驟3 利用并行CRC算法邏輯表計算CRC；

步驟4 對求得的CRC取反；

步驟5 取反后的CRC按照字節(jié)內高低比特翻轉，得到以太網FCS。

2.2 基于級聯結構的并行CRC設計

10G以太網接入系統(tǒng)中常采用64位并行數據通路，而FCS校驗數據長度為60－1514字節(jié) （如圖4所示），使得以太網幀不一定結束在64比特邊界，因此常轉化為如圖5所示的數據格式待處理。

圖5 10G以太網64位并行數據接口

如圖5所示，為10G以太網64位并行數據處理接口，其中Valid為數據有效指示，Sop為幀頭部指示，Eop為幀結束指示，Data為以太網數據，每個周期為64比特，Size代表當前周期數據的有效比特數。

在傳統(tǒng)并行CRC設計中，通常把數據處理分為兩部分，對于Eop之前使用64位并行CRC32校驗算法，對于Eop處則根據Size的指示位表示的數據有效位數選擇8，16，24，32，40，48，56和64位CRC32校驗模塊中的一種來計算最后的CRC校驗值，導致設計中必須設計以上所有位數的CRC校驗模塊，占用了大量的計算資源。

由式 （2）可得如下推論：

推論：已知序列X的CRC32為X’［31：0］，序列Y的CRC32為Y’［31：0］，設序列X’［31：24］的CRC32為Z［31：0］，則序列X的延拓序列 ｛X，Y｝的CRC32為

在已知8位的并行CRC32校驗情況下，可以根據式（6）得到任意N位序列并行CRC32校驗的表達式，并設計8－64位任意輸入時并行CRC32表達式，如圖6所示。其中間節(jié)點為

圖6 基于級聯結構的CRC編碼器

如圖6所示，為本文設計的基于級聯結構的CRC編碼器，其中CRC8模塊為8位輸入的CRC32校驗模塊，其根據式 （3）推導可得，CRC＿EXPAND模塊為根據式 （6）設計的N位CRC－32校驗模塊，其中N＝8＊k，k＝1，2...8。采用以上級聯模塊可以輸出任意N位的CRC校驗值，通過SIZE和選擇器MUX對Eop時任意字節(jié)的CRC32輸出，從而避免了分別對需要對8，16，24，32，40，48，56和64位數據輸入時的CRC校驗模塊設計，降低了存儲空間。

CRC校驗基于FPGA設計時的運算是對輸入數據按比特的異或運算，如式 （3）所示，基于64位輸入的CRC32運算需要多次異或運算，如d23甚至需要進行40多次運算，大量的組合邏輯產生的門延遲超出了系統(tǒng)的時延限度，尤其對于單個時鐘周期的64位輸入無法滿足實時CRC處理要求。

異或運算取決于組合電路的具體結構。如組合邏輯A＝A1⊕A2⊕A3⊕A4⊕A5⊕A6的綜合電路如圖7所示，大量的異或次數導致了較大的時延。

圖7 傳統(tǒng)異或電路結構及時延

通過將傳統(tǒng)的組合邏輯改為A＝（A1⊕A2）⊕（A3⊕A4）⊕（A5⊕A6），此邏輯的電路功能并未改變，其綜合電路結構如圖8所示。

圖8 優(yōu)化后的異或電路結構及時延

優(yōu)化后的電路利用并行設計，將串行電路中累加的延時分散到了多個并行分支中，將門時延從5級降低到了3級。對于N位數據的異或操作，傳統(tǒng)的按位異或將產生N－1級門延時，而圖8的結構只產生 log2N （ 表示向上取整）級門延時，從而降低了異或操作的延時。對于多維數據的異或操作，此結構具有更大的優(yōu)勢，將使得延時以指數級減少，提高了處理效率。

3 實驗驗證及分析

3.1 實驗環(huán)境及工具

為了驗證本文方法的有效性和可靠性，搭建了實驗平臺進行驗證。實驗平臺如圖9所示。其中網絡測試儀為Spirent公司的SMB600B網絡測試儀，其具有1個10G網絡端口。10G以太網處理板卡包括10G光模塊和FPGA，FPGA型號為Xilinx公司的XC5VLX30，其中MAC幀處理通過FPGA中例化MAC核來實現。對網絡測試儀發(fā)送的10G以太網數據在FPGA中計算CRC校驗值并重新添加FCS域，打環(huán)返回到測試儀，利用測試儀集成的FCS校驗功能判斷所設計模塊的正確性。

圖9 并行CRC32驗證平臺

實驗工具為普通PC機，該主機配備操作系統(tǒng)為Windows XP Professional SP3， 具 體 配 置 為：CPU 為 Intel Core2 1.86GHz，內存為2GB。實驗仿真軟件工具采用Xi－linx公司FPGA開發(fā)環(huán)境ISE13.3和以太網分析工具Wireshark。

3.2 CRC校驗驗證

為了驗證基于FPGA的并行CRC校驗算法的正確性，從網絡獲取實際以太網數據包，通過Wireshark可以看到該數據是完整的以太網幀，在每幀的結束位置包括一個幀校驗序列FCS。本文獲取了10G以太網中常用的校驗方式CRC32以太網幀數據進行驗證，結果如圖10和圖11所示。

圖10 CRC32以太網數據包

圖11 并行CRC32運算的VHDL仿真結果

如圖10所示，為CRC32以太網數據幀，數據域的最后4個字節(jié)為FCS，其值為A6FF4847。將此以太網幀輸入到本文所設計方法的仿真結果如圖11所示，其中仿真時鐘為200MHz，計算所得的CRC值為A6FF4847，與實際抓包值一致，說明了本方法的有效性。同時，基于64比特輸入時，時鐘采用200MHz，理論的速率為200x64＝12.8Gbps＞10Gbps，在幀結束的下一時鐘周期即可計算出CRC值，說明本文所述方法滿足10G速率的CRC實時計算。

3.3 資源利用情況及性能分析

對本文設計的并行CRC－32編碼器進行綜合布局布線，為了比較本文所述方法，并和傳統(tǒng)的矩陣法和代入法所得的CRC32編碼器進行比較，分別對以上兩種方法的CRC32編碼器同時進行布局布線，綜合結果見表1。

表1 CRC32編碼器綜合布線結果

從表1可以看出，相比較代入法和矩陣法，本文所述方法在資源占用方面和傳統(tǒng)方法近似，但輸入輸出延遲為3.7ns，處理效率提高了10%。允許的最高時鐘頻率超過250MHz，，完全可以滿足10G以太網CRC校驗的實時處理要求。

為了進一步驗證所設計模塊的有效性，通過打環(huán)測試（測試儀輸出流量到FPGA進行FCS重計算，并將FCS添加到數據幀返回測試儀）進行分析。測試儀顯示的相關結果見表2。

表2 10G網絡測試儀的CRC32測試結果

從表2可以看出，在10G測試儀100%輸出速率時，在78－1518字節(jié)的各種測試條件下，經過本模塊計算的以太網數據幀FCS校驗錯誤為0，丟包率為0，滿足系統(tǒng)要求。

4 結束語

10G以太網CRC校驗需要CRC算法滿足實時性要求，本文提出了一種基于級聯結構的并行CRC校驗算法，并對算法中的組合邏輯電路進行改進。根據實際10G以太網中非64字節(jié)臨界處理，通過傳統(tǒng)8位CRC32校驗電路產生級聯的任意輸入的CRC32校驗電路，無需產生8－64位輸入的所有校驗電路，提高了處理的靈活性和降低了芯片使用面積。通過實際以太網數據包和網絡測試儀進行實驗驗證，實驗結果表明該方法具有較低的處理時延，可滿足10G以太網CRC校驗的實時處理要求。

［1］WANG Xinmei，XIAO Guozhen.Error correcting code：Principle and method ［M］.Xi’an：Xidian University Publisher，1991（in Chinese）.［王新梅，肖國鎮(zhèn).糾錯碼：原理與方法［M］.西安：西安電子科技大學出版社，1991.］

［2］LIU Lu，WU Mingliang，HE Junqiang.Implementation of error control based on cyclic redundancy check ［J］.Journal of Chengdu University （Natural Science Edition），2011，30 （1）：82－85（in Chinese）.［劉璐，武明亮，何俊強.基于循環(huán)冗余校驗碼的差錯控制分析與實現 ［J］.成都大學學報 （自然科學版），2011，30 （1）：82－85.］

［3］ZHANG Youliang，LIU Zhijun，MA Chenghai，et al.Design and implementation of 10－Gigabit Ethernet MAC controller based on FPGA ［J］.Computer Engineering and Applications，2012，48 （6）：77－79 （in Chinese）. ［張友亮，劉志軍，馬成海，等.萬兆以太網MAC層控制器的FPGA設計與實現［J］.計算機工程與應用，2012，48 （6）：77－79.］

［4］Patane G Campobello，Russo M.Parallel CRC realization ［J］.IEEE Transactions on Computers，2003，52 （10）：1312－13l9.

［5］PENG Wei.Research on embedded system CRC algorithm design［J］.Journal of Nanjing University of Information Science ＆ Technology （Natural Science Edition），2012，4 （3）：258－265 （in Chinese）.［彭偉.嵌入式系統(tǒng)CRC循環(huán)冗余校驗算法設計研究［J］.南京信息工程大學學報，2012，4 （3）：258－265.］

［6］Wong Y，Zhang H.Techniques for segmented CRC design in high speed networks：U.S.Patent 8，037，399 ［P］.2011－10－11.

［7］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.

［8］Stavinov E.A practical parallel CRC generation method ［J］.Circuit Cellar－the Magazine for Computer Applications，2010，31 （234）：38.

［9］XU Zhanqi，PEI Changxing，DONG Huainan.Generalized CRC computation algorithm with multiple channels and its implementation［J］.Journal of Nanjing University of Posts and Telecommunications（Natural Science），2008 （2）：53－57 （in Chinese）.［徐展琦，裴昌幸，董淮南.一種通用多通道并行CRC計算及其實 ［J］.南京郵電大學學報，2008 （2）：53－57.］

［10］BI Zhankun，ZHANG Yimeng，HUANG Zhiping，et al.Study on CRC parallel algorithm and its implementation in FPGA ［J］.Chinese Journal of Scientific Instrument，2007，28（12）：2244－2249 （in Chinese）. ［畢占坤，張羿猛，黃芝平，等.基于邏輯設計的高速CRC并行算法研究及其FPGA實現［J］.儀器儀表學報，2007，28 （12）：2244－2249.］

［11］Ramabadran T V，Gaitonde S S.A tutorial on CRC computations ［J］.IEEE Micro，1988，8 （4）：62－75.

［12］LI Youmou，FANG Dingyi.Research and implementation of a new CRC coding algorithm ［J］.Journal of Northwest University（Natural Science Edition），2006，36 （6）：895－898 （in Chinese）.［李宥謀，房鼎益.CRC編碼算法研究與實現 ［J］.西北大學學報 （自然科學版），2006，36 （6）：895－898.］

［13］ZHANG Shugang，ZHANG Suinan.CRC parallel computation implementation on FPGA ［J］.Computer Technology and Development，2007，17 （2）：56－58 （in Chinese）.［張樹剛，張遂南.CRC校驗碼并行計算的FPGA實現 ［J］.計算機技術與發(fā)展，2007，17 （2）：56－58.］