??? 摘 要: 為了解決10G" title="10G">10G以太網(wǎng)接入" title="以太網(wǎng)接入">以太網(wǎng)接入系統(tǒng)中大規(guī)模并行CRC編碼器的設(shè)計問題,提出了矩陣法、代入" title="代入">代入法、流水線法等三種" title="三種">三種設(shè)計方法。以此為基礎(chǔ),給出了10G以太網(wǎng)接入系統(tǒng)中CRC編碼器的實現(xiàn)方案。具體計算表明,在10G以太網(wǎng)接入系統(tǒng)中采用直接并行的CRC編碼器是可行的。直接并行設(shè)計的CRC編碼器已經(jīng)通過了EDA模擬,并成功地應(yīng)用于10G以太網(wǎng)接入系統(tǒng)中。
??? 關(guān)鍵詞: 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技術(shù)中并行CRC算法^[4]給出的并行算法都建立在公式遞推的基礎(chǔ)上?當(dāng)并行深度較小時,遞推算法比較適用?而當(dāng)并行深度很大的情況下(10G以太網(wǎng)接入系統(tǒng)使用64比特并行數(shù)據(jù)通路),遞推過程就顯得過于煩瑣而缺乏實用性?為此,本文提出了矩陣法?代入法和流水線法等三種算法,解決了深度并行情況下CRC算法的實現(xiàn)問題?利用本文提出的算法,可以得出64比特并行CRC計算的邏輯表達式,并用于10G以太網(wǎng)接入系統(tǒng)的設(shè)計?設(shè)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ù)端串行輸入二進制的信息碼?信息碼輸入結(jié)束后,D觸發(fā)器中鎖存的數(shù)值就是信息碼的基本CRC-32編碼?此電路適用于信息碼長為任意值的情況?在某些信息系統(tǒng)中以基本CRC產(chǎn)生算法為基礎(chǔ)附加了新的規(guī)定?例如IEEE802.3協(xié)議規(guī)定^[6],以太網(wǎng)的FCS(幀校驗序列)域以CRC-32為基礎(chǔ),并且在編碼時首先將信息碼的最初4個字節(jié)取反碼,對目的地址?源地址?長度/類型域?數(shù)據(jù)域?PAD域求出基本CRC-32碼之后再將結(jié)果取反,最后的結(jié)果才是FCS?同上述過程等價的另一種實現(xiàn)方法" title="實現(xiàn)方法">實現(xiàn)方法是將圖1中所有D觸發(fā)器的初值置1,這樣結(jié)果不必取反?為使電路設(shè)計者驗證其FCS編碼正確,IEEE802.3還給出了一個樣本,即:將序列0xBED723476B8FB3145EFB3559H重復(fù)126次,最后得到的FCS值應(yīng)該為0x94D254ACH?10G以太網(wǎng)是IEEE802.3ae工作組提出的建議^[7]?它保持了以前以太網(wǎng)的幀結(jié)構(gòu),但是線速度達到了10Gbps的量級?為了降低10G以太網(wǎng)接入系統(tǒng)的功耗并達到芯片加工工藝的要求,必須采用并行數(shù)據(jù)通路?為計算FCS需要研究并行CRC算法?所設(shè)計的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表示編碼器當(dāng)前所處的狀態(tài),I=[i₆₃i₆₂...i₀]表示第1至第64個時鐘的信息碼元輸入,向量D′=[d₀′d₁′...d₃₁′]T表示編碼器的下一個狀態(tài),D⁽⁶⁴⁾表示64個時鐘之后CRC編碼器所處的狀態(tài)?則設(shè)計64位并行CRC邏輯編碼器,就是找出函數(shù)關(guān)系D⁽⁶⁴⁾=f(D,I)??

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

???

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

2 代入法?

??? 矩陣法的優(yōu)點在于其直觀性?但是需要做大規(guī)模乘法運算?下面討論的代入法能夠得到與矩陣法相同的結(jié)果?同時可以避免大規(guī)模矩陣乘法運算?設(shè)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]}??

??? 利用上述算法構(gòu)造APPEND模塊,其端口A和B分別表示前導(dǎo)序列的CRC和延拓的8比特序列,則其輸出端口Z為拓展之后序列的CRC?圖2利用APPEND模塊構(gòu)造了級聯(lián)結(jié)構(gòu)的64比特并行CRC編碼器?這種級聯(lián)構(gòu)造的編碼器設(shè)計比較簡單?其中間節(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)結(jié)構(gòu)占用芯片面積大,且只能用于低速場合?對(3)進一步化簡,可以得到Z₂的最簡異或表達式?同理可以得到Z₃...Z₈的表達式?Z₁,Z₂,...,Z₈分別對應(yīng)8比特?16比特?……?64比特的并行CRC運算表達式?具體表達式限于篇幅不在這里給出?Z₈中最長的異或運算表達式有52項參加運算,如果使用4-異或門則只需要用三級,即能在一般CMOS工藝的一級傳輸延遲時間之內(nèi)完成?當(dāng)用于以太網(wǎng)接入系統(tǒng)時,因為以太網(wǎng)幀不一定結(jié)束在64比特邊界,因此編碼器應(yīng)該有同時計算8?16?24?……?64比特并行編碼的能力?具體電路如圖3?因為一般情況下大量用到64比特并行編碼,因此平時使能信號mux使其他7個編碼模塊不工作以降低功耗?在幀尾部根據(jù)具體情況使用這7個模塊進行剩余字節(jié)的編碼??

?

?

3 流水線法?

??? 矩陣法和代入法本質(zhì)上都是設(shè)計直接并行編碼電路的方法,二者的最終效果是一樣的?直接并行實現(xiàn)的CRC編碼電路控制邏輯比較簡單,但是需要進行復(fù)雜的組合邏輯運算?為了在更高頻率下進行并行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]輸入,結(jié)果由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的邏輯表達式時,重復(fù)應(yīng)用算法1的推論,可以求出“D_i′,O,O,O,O,O,O,O”的CRC碼,再應(yīng)用算法1,就可以求出“D_i′,O,O,O,O,O,O,O,D_i”的CRC碼?直接應(yīng)用算法1可以求出C模塊的邏輯表達式?P模塊和C模塊進行異或運算的長度遠小于直接并行CRC電路中的ENC8模塊,因此更有利于在高速電路中應(yīng)用??

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

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

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

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

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

參考文獻?

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

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

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

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

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

6 IEEE Std,802.3.2000.?

7 IEEE Std,802.3ae.2002.