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

通信系統(tǒng)不可避免地要受到各種干擾的影響，使接收端收到的信息與發(fā)送端發(fā)出的信息不一致，即接收端收到的信息產(chǎn)生了誤碼。為了降低數(shù)據(jù)通信線路傳輸?shù)恼`碼率，通常有改善數(shù)據(jù)通信線路傳輸質(zhì)量和差錯檢測控制兩種方法。差錯檢測控制的方法很多，本文討論在10G以太網(wǎng)接人系統(tǒng)中并行實現(xiàn)CRC-32編解碼的方法、并行CRC算法的Unfolding算法可以實現(xiàn)并行CRC的計算，但是并行電路所用的資源增加到了原來的J倍。8位并行CRC算法、并行CRC-16的編碼邏輯、USB技術(shù)中并行CRC算法給出的并行算法都建立在公式遞推的基礎(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）·xr，然后作模2除法

(M(x)· x r)/G(x)=Q(x)+R(x)/G(x) (1)

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

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

·CRC-32G的生成多項G(x)=x32+x26+x23+x22+x16+x12+xll+x10+x8+x7+x5+x4+x2+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),i(33:-1:1));

end

end

crc=a(32:-1:1)

如果想用以上CRC-32程序計算其他長為L的序列的基本CRC-32碼，只需將數(shù)組α的上界和for循環(huán)中i的初始值改為32+L，并用該序列代替數(shù)組。開始的序列1001010110010101即可。用數(shù)字電路實現(xiàn)的串行CRC編碼器如圖1所示。圖1中每個矩形表示D觸發(fā)器。gi的取值范圍是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ī)定，以太網(wǎng)的FES(幀校驗序列)域以CRC-32為基礎(chǔ)，并且在編碼時首先將信息碼的最初4個字節(jié)取反碼，對目的地址、源地址、長度／類型域、數(shù)據(jù)域、PAD域求出基本CRC-32碼之后再將結(jié)果取反，最后的結(jié)果才是FCS。同上述過程等價的另一種實現(xiàn)方法是將圖1中所有D觸發(fā)器的初值置1，這樣結(jié)果不必取反。為使電路設(shè)計者驗證其FCS編碼正確，IEEE802．3還給出了一個樣本，即：將序列0xBED723476B8FB3145EFB3559H重復(fù)126次，最后得到的FCS值應(yīng)該為0x94D254ACH。10G以太網(wǎng)是IEEE802．3ae工作組提出的建議。它保持了以前以太網(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ā)器的輸出從右至左依次為d31，d30，…，d0。信息碼元的輸入端為i。令D=[d0d1…d31]T表示編碼器當(dāng)前所處的狀態(tài)，I=[i63i62…i0]表示第1至第64個時鐘的信息碼元輸入，向量Dˊ=[d0ˊd1ˊ，…d31ˊ] T表示編碼器的下一個狀態(tài)，D(64)表示64個時鐘之后CRC編碼器所處的狀態(tài)。則設(shè)計64位并行CRC邏輯編碼器，就是找出函數(shù)關(guān)系D（64）=f（D，I）。

do=d31+i63

d1=d0+d31+i63

d2=d1+d31+i63

d3=d2

…

d31=d30

寫成行列式，有D=TD+Si63

其中：

2個時鐘之后編碼器的狀態(tài)為：

D=TD+Si62=T)TD+Si63)+Si62=T2D+TSi63+Si62

依此類推，有：

D(64)=T64D+T63Si63+T62Si62+…+TSi1+Si0 （2）

這里所有矩陣運算和代數(shù)運算中的加號的語義都是模2加法。為了。設(shè)計64位并行CRC電路，必須計算(2)式中的大規(guī)模矩陣乘法T64、T63S等。

2 代入法

矩陣法的優(yōu)點在于其直觀性。但是需要做大規(guī)模乘法運算。下面討論的代入法能夠得到與矩陣法相同的結(jié)果。同時可以避免大規(guī)模矩陣乘法運算。設(shè)8比特并行CRC-32電路的初始狀態(tài)是d31，d30，…，d0，輸入是i7，i6，…，j0，輸出是z31，Z30，…，z0。利用前面所述的矩陣法，可以得出8比特并行CRC-32編碼器的組合邏輯表達式。如表1所示。

即：

z31=d23+d29+i5;

z30=d22+d31+i7+d28+i4

…

z0=d24+d30+i6+i0

表1 8位行CRC邏輯表

下文用+表示按位模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]+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]+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é)點：

Z1(n)=f(r,d[0:7] n[31,0]

Z2(n)=f(Z1,d[8:15])=f(f(r,d[0:7]),d{8:15])

… （3）

顯然(3)還可以進一步化簡。冗余的邏輯使得這種級聯(lián)結(jié)構(gòu)占用芯片面積大，且只能用于低速場合。對(3)進一步化簡，可以得到Z2的最簡異或表達式。同理可以得到Z3…Z8的表達式。Zl，Z2，…，Z8分別對應(yīng)8比特、16比特、……、64比特的并行CRC運算表達式。具體表達式限于篇幅不在這里給出。Z8中最長的異或運算表達式有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é)，分別用D0、D1、……、D7表示。P模塊(P0~P7)計算形如Di，O，O，O，O，O，O，O，Di的序列的CRC，其中Diˊ，是Di位置上的上一次輸入。Diˊ的CRC碼由端口R[31：0]輸入，Di由端口D[7：0]輸入，結(jié)果由Z[31：0]端口輸出。

C模塊(C1~C7)的輸入是D0，O，O，O，O，O，O，O，D0和D1ˊ，O，O，O，O，O，O，O，D1的CRC(分別由端口R1和R2輸入)，輸出是D0ˊ，D1ˊ，O，O，O，O，O，O，D0，D1 CRC。求P的邏輯表達式時，重復(fù)應(yīng)用算法1的推論，可以求出Diˊ，O，O，O，O，O，O，Di的CRC碼，再應(yīng)用算法1，就可以求出Diˊ，O，O，O，O，O，O，O，Di的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è)計。