??? 摘 要: 為了解決10G" title="10G">10G以太網(wǎng)接入" title="以太網(wǎng)接入">以太網(wǎng)接入系統(tǒng)中大規(guī)模并行CRC編碼器的設計問題,提出了矩陣法、代入" title="代入">代入法、流水線法等三種" title="三種">三種設計方法。以此為基礎,給出了10G以太網(wǎng)接入系統(tǒng)中CRC編碼器的實現(xiàn)方案。具體計算表明,在10G以太網(wǎng)接入系統(tǒng)中采用直接并行的CRC編碼器是可行的。直接并行設計的CRC編碼器已經(jīng)通過了EDA模擬,并成功地應用于10G以太網(wǎng)接入系統(tǒng)中。
??? 關鍵詞: 10G 以太網(wǎng) CRC 并行

?

??? 通信系統(tǒng)不可避免地要受到各種干擾的影響,使接收端收到的信息與發(fā)送端發(fā)出的信息不一致,即接收端收到的信息產(chǎn)生了誤碼?為了降低數(shù)據(jù)通信線路傳輸?shù)恼`碼率,通常有改善數(shù)據(jù)通信線路傳輸質(zhì)量和差錯檢測控制兩種方法?差錯檢測控制的方法很多,本文討論在10G以太網(wǎng)接入系統(tǒng)中并行實現(xiàn)CRC-32編解碼的方法?并行CRC算法的Unfolding算法^[1]可以實現(xiàn)并行CRC的計算,但是并行電路所用的資源增加到了原來的J倍?8位并行CRC算法^[2]?并行CRC-16的編碼邏輯^[3]?USB技術中并行CRC算法^[4]給出的并行算法都建立在公式遞推的基礎上?當并行深度較小時,遞推算法比較適用?而當并行深度很大的情況下(10G以太網(wǎng)接入系統(tǒng)使用64比特并行數(shù)據(jù)通路),遞推過程就顯得過于煩瑣而缺乏實用性?為此,本文提出了矩陣法?代入法和流水線法等三種算法,解決了深度并行情況下CRC算法的實現(xiàn)問題?利用本文提出的算法,可以得出64比特并行CRC計算的邏輯表達式,并用于10G以太網(wǎng)接入系統(tǒng)的設計?設M(x)為信息多項式,G(x)為生成多項式?一般的CRC編碼方法是:先將信息碼多項式左移r位,即M(x)·x^r,然后作模2除法^[5]?

?????

??? 所得到的R(x)就是CRC校驗碼?以二進制碼0x9595H的CRC-32編碼為例:?

??? ·將信息碼左移32比特變成0x959500000000H,記為m??

??? ·CRC-32的生成多項式G(x)=x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1,轉(zhuǎn)換成16進制碼為g=0x104C01DB7H?用m除以g(模2除法),所得余數(shù)0x3738F30BH就是0x9595H的CRC-32碼?實現(xiàn)0x9595H的基本CRC-32編碼的Matlab程序如下:?

??? g(33:-1:1)=[1, 0 0 0 0 0 1 0 0, 1 1 0 0 0 0 0 1,0 0 0 1 1 1 0 1, 1 0 1 1 0 1 1 1]:?

??? a(48:-1:1)=[1 0 0 1 0 1 0 1, 1 0 0 1 0 1 0 1,?

??????? 0 0 0 0 0 0 0 0 ,0 0 0 0 0 0 0 0 ,0 0 0 0 0 0 0 0,0 0 0 0 0 0 0 0]:?

??? for i=48:-1:33,?

??? ??? if a(i)==1?

????? ??????? a(i:-1:i-32)=xor(a(i:-1:i-32),g(33:-1:1)):?

??? ??? end?

??? end?

??? crc=a(32:-1:1)?

??? 如果想用以上CRC-32程序計算其他長為L的序列的基本CRC-32碼,只需將數(shù)組a的上界和for循環(huán)中i的初始值改為32+L,并用該序列代替數(shù)組a開始的序列“1001010110010101”即可?用數(shù)字電路實現(xiàn)的串行CRC編碼器如圖1所示^[5]?圖1中每個矩形表示D觸發(fā)器?g_i的取值范圍是1或者0?取1時表示通路,取0時表示斷路?進行基本CRC-32編碼時,每個D觸發(fā)器初始狀態(tài)為0,從數(shù)據(jù)端串行輸入二進制的信息碼?信息碼輸入結束后,D觸發(fā)器中鎖存的數(shù)值就是信息碼的基本CRC-32編碼?此電路適用于信息碼長為任意值的情況?在某些信息系統(tǒng)中以基本CRC產(chǎn)生算法為基礎附加了新的規(guī)定?例如IEEE802.3協(xié)議規(guī)定^[6],以太網(wǎng)的FCS(幀校驗序列)域以CRC-32為基礎,并且在編碼時首先將信息碼的最初4個字節(jié)取反碼,對目的地址?源地址?長度/類型域?數(shù)據(jù)域?PAD域求出基本CRC-32碼之后再將結果取反,最后的結果才是FCS?同上述過程等價的另一種實現(xiàn)方法" title="實現(xiàn)方法">實現(xiàn)方法是將圖1中所有D觸發(fā)器的初值置1,這樣結果不必取反?為使電路設計者驗證其FCS編碼正確,IEEE802.3還給出了一個樣本,即:將序列0xBED723476B8FB3145EFB3559H重復126次,最后得到的FCS值應該為0x94D254ACH?10G以太網(wǎng)是IEEE802.3ae工作組提出的建議^[7]?它保持了以前以太網(wǎng)的幀結構,但是線速度達到了10Gbps的量級?為了降低10G以太網(wǎng)接入系統(tǒng)的功耗并達到芯片加工工藝的要求,必須采用并行數(shù)據(jù)通路?為計算FCS需要研究并行CRC算法?所設計的10G以太網(wǎng)接入系統(tǒng)采用64比特并行數(shù)據(jù)通路,因此本文主要討論64比特并行CRC-32的實現(xiàn)方法?本文共介紹三種實現(xiàn)方法,其中矩陣法和代入法是基于組合邏輯的直接實現(xiàn)方法,第三種方法是基于流水線的實現(xiàn)方法??

?

?

1 矩陣法?

??? 記圖1中的32個D觸發(fā)器的輸出從右至左依次為d₃₁,d₃₀,...,d₀?信息碼元的輸入端為i?令D=[d₀d₁...d₃₁]^T表示編碼器當前所處的狀態(tài),I=[i₆₃i₆₂...i₀]表示第1至第64個時鐘的信息碼元輸入,向量D′=[d₀′d₁′...d₃₁′]T表示編碼器的下一個狀態(tài),D⁽⁶⁴⁾表示64個時鐘之后CRC編碼器所處的狀態(tài)?則設計64位并行CRC邏輯編碼器,就是找出函數(shù)關系D⁽⁶⁴⁾=f(D,I)??

??? 則從圖1可以看出:?

???

??? 這里所有矩陣運算和代數(shù)運算中的加號的語義都是模2加法?為了設計64位并行CRC電路,必須計算(2)式中的大規(guī)模矩陣乘法T⁶⁴?T⁶³S等??

2 代入法?

??? 矩陣法的優(yōu)點在于其直觀性?但是需要做大規(guī)模乘法運算?下面討論的代入法能夠得到與矩陣法相同的結果?同時可以避免大規(guī)模矩陣乘法運算?設8比特并行CRC-32電路的初始狀態(tài)是d₃₁,d₃₀,...,d₀,輸入是i₇,i₆,...,i₀,輸出是z₃₁,z₃₀,...,z₀?利用前面所述的矩陣法,可以得出8比特并行CRC-32編碼器的組合邏輯表達式?如表1所示??

??? 即:?

??? z₃₁=d₂₃+d₂₉+i₅:?

??? z₃₀=d₂₂+d₃₁+i₇+d₂₈+i₄?

??? ...?

??? z₀=d₂₄+d₃₀+i₆+i₀?

?

?

??? 下文用“+”表示按位模2和運算,“{,}”表示鏈接運算?從CRC的(1)式很容易得出以下算法:?

??? 算法1:已知序列N的CRC-32為A[31:0],序列B(=[b7,b6,...,b0])的CRC-32碼為Y[31:0]?序列A[31:24]的CRC-32為X[31:0],則延拓序列{N,B}的CRC-32碼為{Y[31:24]+X[31:24]+A[23:16],Y[23:16]+X[23:16]+A[15:8],Y[15:8]+X[15:8]+A[7:0],Y[7:0]+X[7:0]}??

??? 推論:已知序列N的CRC-32為A[31:0],序列A[31:24]的CRC-32為X[31:0],則補0延拓序列{N,O}的CRC-32碼為{X[31:24]+A[23:16],X[23:16]+A[15:8],X[15:8]+A[7:0],X[7:0]}??

??? 利用上述算法構造APPEND模塊,其端口A和B分別表示前導序列的CRC和延拓的8比特序列,則其輸出端口Z為拓展之后序列的CRC?圖2利用APPEND模塊構造了級聯(lián)結構的64比特并行CRC編碼器?這種級聯(lián)構造的編碼器設計比較簡單?其中間節(jié)點:?

??? Z₁(n)=f(r,d[0:7])???????? n∈[31,0]?

??? Z₂(n)=f(Z₁,d[8:15])=f(f(r,d[0:7]),d[8:15])?

??? ...????????????????????????????????????? (3)?

?

?

?

??? 顯然(3)還可以進一步化簡?冗余的邏輯使得這種級聯(lián)結構占用芯片面積大,且只能用于低速場合?對(3)進一步化簡,可以得到Z₂的最簡異或表達式?同理可以得到Z₃...Z₈的表達式?Z₁,Z₂,...,Z₈分別對應8比特?16比特?……?64比特的并行CRC運算表達式?具體表達式限于篇幅不在這里給出?Z₈中最長的異或運算表達式有52項參加運算,如果使用4-異或門則只需要用三級,即能在一般CMOS工藝的一級傳輸延遲時間之內(nèi)完成?當用于以太網(wǎng)接入系統(tǒng)時,因為以太網(wǎng)幀不一定結束在64比特邊界,因此編碼器應該有同時計算8?16?24?……?64比特并行編碼的能力?具體電路如圖3?因為一般情況下大量用到64比特并行編碼,因此平時使能信號mux使其他7個編碼模塊不工作以降低功耗?在幀尾部根據(jù)具體情況使用這7個模塊進行剩余字節(jié)的編碼??

?

?

3 流水線法?

??? 矩陣法和代入法本質(zhì)上都是設計直接并行編碼電路的方法,二者的最終效果是一樣的?直接并行實現(xiàn)的CRC編碼電路控制邏輯比較簡單,但是需要進行復雜的組合邏輯運算?為了在更高頻率下進行并行CRC編碼,可以進一步用流水線的方法簡化編碼邏輯,所付出的代價是整個幀的處理延遲了8個時鐘周期?圖4給出了CRC編碼的流水線實現(xiàn)?將并行輸入的64比特分成7個字節(jié),分別用D₀?D₁?……?D₇表示?P模塊(P0～P7)計算形如“D_i′,O,O,O,O,O,O,O,D_i”的序列的CRC,其中D_i′是Di位置上的上一次輸入?D_i′的CRC碼由端口R[31:0]輸入,Di由端口D[7:0]輸入,結果由Z[31:0]端口輸出??

?

?

??? C模塊(C₁～C₇)的輸入是“D₀′,O,O,O,O,O,O,O,D₀”和“D₁′,O,O,O,O,O,O,O,D₁”的CRC(分別由端口R1和R2輸入),輸出是“D₀′,D₁′,O,O,O,O,O,O,D₀,D₁” CRC?求P的邏輯表達式時,重復應用算法1的推論,可以求出“D_i′,O,O,O,O,O,O,O”的CRC碼,再應用算法1,就可以求出“D_i′,O,O,O,O,O,O,O,D_i”的CRC碼?直接應用算法1可以求出C模塊的邏輯表達式?P模塊和C模塊進行異或運算的長度遠小于直接并行CRC電路中的ENC8模塊,因此更有利于在高速電路中應用??

4 10G以太網(wǎng)接入系統(tǒng)中的CRC編解碼器設計?

??? 10G以太網(wǎng)接入系統(tǒng)所需接口速率高達10Gbps以上?從降低系統(tǒng)功耗和芯片制造成本的角度考慮希望接口能工作在200MHz以下?采用并行化設計雖然可以降低系統(tǒng)時鐘頻率,但也從以下兩方面增加了設計難度?首先,數(shù)據(jù)通路的并行程度越高,對它的控制就越復雜?系統(tǒng)采用8字節(jié)并行數(shù)據(jù)通路,則發(fā)送的以太網(wǎng)幀可能在8個并行字節(jié)中的任意一個位置上結束,控制邏輯的設計就必須考慮所有這些可能性并逐一做出相應的處理?其次,系統(tǒng)中的CRC編碼器?擾碼器等的設計須采用并行算法?為了滿足IEEE802.3協(xié)議對以太網(wǎng)幀CRC編碼的要求,實際的編解碼器模塊還需要能對輸入輸出信號進行任意字節(jié)數(shù)的求反運算?考慮到10G接入系統(tǒng)的復雜性,該模塊功能應該高度集成化,以便用宏信號端口對其進行操作?在對收到的以太網(wǎng)幀進行校驗時,沒必要先計算不包括FCS域的序列的CRC編碼(結果取反)再與FCS域做對比?在編碼正確且沒有誤碼的情況下,對整個以太網(wǎng)幀(包括FCS域)進行結果不取反的CRC編碼的結果應該為序列0xC704DD7BH?采用這種判別方法,無需在幀的結束前停止計算CRC編碼,因而可以大大簡化電路設計??

5 CRC編碼器的實現(xiàn)?

??? 本文提出的各種算法的硬件實現(xiàn)已經(jīng)通過了FPGA驗證,并被應用到具體芯片?使用Xilinx公司的Virtex2系列FPGA中的XC2V1000分別仿真了采用上述代入法和流水線法設計的CRC編碼器和解碼器,驗證了設計方法的正確性?在綜合考慮邏輯復雜度?所占用的芯片面積和工藝要求后,最終在所設計的10G以太網(wǎng)接入芯片中,采用了代入法設計的CRC編碼器和解碼器??

??? 10G以太網(wǎng)接入系統(tǒng)中需要采用并行CRC編碼器?本文提出了基于組合邏輯的直接實現(xiàn)和基于流水線的實現(xiàn)方法?其中直接實現(xiàn)的方法又分為矩陣法和代入法兩種?經(jīng)過具體推導發(fā)現(xiàn)直接實現(xiàn)的編碼器可以滿足延時要求,因而被本系統(tǒng)所采用?而基于流水線的設計因為其延時較小,可以用于更高速的場合?本文提出的三種并行化設計方法已經(jīng)通過了硬件驗證?這些設計思想同樣適用于其他線性移位寄存器,如擾碼器的設計??

參考文獻?

1 程 超,程善美.Unfolding算法實現(xiàn)的高速并行CRC電路的VLSI設計.微電子學與計算機[J],2002:(12):68～69?

2 劉新寧,王超,胡晨,蔡洪亮.一種快速CRC算法的硬件實?現(xiàn)方法.電子器件[J]:2003:26(1):88~91?

3 王 耿,姜智忠.用HDL語言實現(xiàn)循環(huán)冗余校驗.微電子學與計算機[J],2002:(5):4～6?

4 程 軍,陳貴燦,姜 飛.USB數(shù)據(jù)傳輸中CRC校驗碼的并行算法實現(xiàn).微電子學與計算機[J],2003:(3):77～80?

5 曹志剛,錢亞生.現(xiàn)代通信原理[B].北京:清華大學出版社,1992:344～346?

6 IEEE Std,802.3.2000.?

7 IEEE Std,802.3ae.2002.