摘 要:为了解决10G" title="10G">10G以太网接入" title="以太网接入">以太网接入系统中大规模并行CRC编码器的设计问题,提出了矩阵法、代入" title="代入">代入法、流水线法等三种" title="三种">三种设计方法。以此为基础,给出了10G以太网接入系统中CRC编码器的实现方案。具体计算表明,在10G以太网接入系统中采用直接并行的CRC编码器是可行的。直接并行设计的CRC编码器已经通过了EDA模拟,并成功地应用于10G以太网接入系统中。
关键词:10G 以太网 CRC 并行

通信系统不可避免地要受到各种干扰的影响,使接收端收到的信息与发送端发出的信息不一致,即接收端收到的信息产生了误码?为了降低数据通信线路传输的误码率,通常有改善数据通信线路传输质量和差错检测控制两种方法?差错检测控制的方法很多,本文讨论在10G以太网接入系统中并行实现CRC-32编解码的方法?并行CRC算法的Unfolding算法^[1]可以实现并行CRC的计算,但是并行电路所用的资源增加到了原来的J倍?8位并行CRC算法^[2]?并行CRC-16的编码逻辑^[3]?USB技术中并行CRC算法^[4]给出的并行算法都建立在公式递推的基础上?当并行深度较小时,递推算法比较适用?而当并行深度很大的情况下(10G以太网接入系统使用64比特并行数据通路),递推过程就显得过于烦琐而缺乏实用性?为此,本文提出了矩阵法?代入法和流水线法等三种算法,解决了深度并行情况下CRC算法的实现问题?利用本文提出的算法,可以得出64比特并行CRC计算的逻辑表达式,并用于10G以太网接入系统的设计?设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,转换成16进制码为g=0x104C01DB7H?用m除以g(模2除法),所得余数0x3738F30BH就是0x9595H的CRC-32码?实现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码,只需将数组a的上界和for循环中i的初始值改为32+L,并用该序列代替数组a开始的序列“1001010110010101”即可?用数字电路实现的串行CRC编码器如图1所示^[5]?图1中每个矩形表示D触发器?g_i的取值范围是1或者0?取1时表示通路,取0时表示断路?进行基本CRC-32编码时,每个D触发器初始状态为0,从数据端串行输入二进制的信息码?信息码输入结束后,D触发器中锁存的数值就是信息码的基本CRC-32编码?此电路适用于信息码长为任意值的情况?在某些信息系统中以基本CRC产生算法为基础附加了新的规定?例如IEEE802.3协议规定^[6],以太网的FCS(帧校验序列)域以CRC-32为基础,并且在编码时首先将信息码的最初4个字节取反码,对目的地址?源地址?长度/类型域?数据域?PAD域求出基本CRC-32码之后再将结果取反,最后的结果才是FCS?同上述过程等价的另一种实现方法" title="实现方法">实现方法是将图1中所有D触发器的初值置1,这样结果不必取反?为使电路设计者验证其FCS编码正确,IEEE802.3还给出了一个样本,即:将序列0xBED723476B8FB3145EFB3559H重复126次,最后得到的FCS值应该为0x94D254ACH?10G以太网是IEEE802.3ae工作组提出的建议^[7]?它保持了以前以太网的帧结构,但是线速度达到了10Gbps的量级?为了降低10G以太网接入系统的功耗并达到芯片加工工艺的要求,必须采用并行数据通路?为计算FCS需要研究并行CRC算法?所设计的10G以太网接入系统采用64比特并行数据通路,因此本文主要讨论64比特并行CRC-32的实现方法?本文共介绍三种实现方法,其中矩阵法和代入法是基于组合逻辑的直接实现方法,第三种方法是基于流水线的实现方法?

1 矩阵法

记图1中的32个D触发器的输出从右至左依次为d₃₁,d₃₀,...,d₀?信息码元的输入端为i?令D=[d₀d₁...d₃₁]^T表示编码器当前所处的状态,I=[i₆₃i₆₂...i₀]表示第1至第64个时钟的信息码元输入,向量D′=[d₀′d₁′...d₃₁′]T表示编码器的下一个状态,D⁽⁶⁴⁾表示64个时钟之后CRC编码器所处的状态?则设计64位并行CRC逻辑编码器,就是找出函数关系D⁽⁶⁴⁾=f(D,I)?

则从图1可以看出:

这里所有矩阵运算和代数运算中的加号的语义都是模2加法?为了设计64位并行CRC电路,必须计算(2)式中的大规模矩阵乘法T⁶⁴?T⁶³S等?

2 代入法

矩阵法的优点在于其直观性?但是需要做大规模乘法运算?下面讨论的代入法能够得到与矩阵法相同的结果?同时可以避免大规模矩阵乘法运算?设8比特并行CRC-32电路的初始状态是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模块构造了级联结构的64比特并行CRC编码器?这种级联构造的编码器设计比较简单?其中间节点:

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)还可以进一步化简?冗余的逻辑使得这种级联结构占用芯片面积大,且只能用于低速场合?对(3)进一步化简,可以得到Z₂的最简异或表达式?同理可以得到Z₃...Z₈的表达式?Z₁,Z₂,...,Z₈分别对应8比特?16比特?……?64比特的并行CRC运算表达式?具体表达式限于篇幅不在这里给出?Z₈中最长的异或运算表达式有52项参加运算,如果使用4-异或门则只需要用三级,即能在一般CMOS工艺的一级传输延迟时间之内完成?当用于以太网接入系统时,因为以太网帧不一定结束在64比特边界,因此编码器应该有同时计算8?16?24?……?64比特并行编码的能力?具体电路如图3?因为一般情况下大量用到64比特并行编码,因此平时使能信号mux使其他7个编码模块不工作以降低功耗?在帧尾部根据具体情况使用这7个模块进行剩余字节的编码?

3 流水线法

矩阵法和代入法本质上都是设计直接并行编码电路的方法,二者的最终效果是一样的?直接并行实现的CRC编码电路控制逻辑比较简单,但是需要进行复杂的组合逻辑运算?为了在更高频率下进行并行CRC编码,可以进一步用流水线的方法简化编码逻辑,所付出的代价是整个帧的处理延迟了8个时钟周期?图4给出了CRC编码的流水线实现?将并行输入的64比特分成7个字节,分别用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以太网接入系统中的CRC编解码器设计

10G以太网接入系统所需接口速率高达10Gbps以上?从降低系统功耗和芯片制造成本的角度考虑希望接口能工作在200MHz以下?采用并行化设计虽然可以降低系统时钟频率,但也从以下两方面增加了设计难度?首先,数据通路的并行程度越高,对它的控制就越复杂?系统采用8字节并行数据通路,则发送的以太网帧可能在8个并行字节中的任意一个位置上结束,控制逻辑的设计就必须考虑所有这些可能性并逐一做出相应的处理?其次,系统中的CRC编码器?扰码器等的设计须采用并行算法?为了满足IEEE802.3协议对以太网帧CRC编码的要求,实际的编解码器模块还需要能对输入输出信号进行任意字节数的求反运算?考虑到10G接入系统的复杂性,该模块功能应该高度集成化,以便用宏信号端口对其进行操作?在对收到的以太网帧进行校验时,没必要先计算不包括FCS域的序列的CRC编码(结果取反)再与FCS域做对比?在编码正确且没有误码的情况下,对整个以太网帧(包括FCS域)进行结果不取反的CRC编码的结果应该为序列0xC704DD7BH?采用这种判别方法,无需在帧的结束前停止计算CRC编码,因而可以大大简化电路设计?

5 CRC编码器的实现

本文提出的各种算法的硬件实现已经通过了FPGA验证,并被应用到具体芯片?使用Xilinx公司的Virtex2系列FPGA中的XC2V1000分别仿真了采用上述代入法和流水线法设计的CRC编码器和解码器,验证了设计方法的正确性?在综合考虑逻辑复杂度?所占用的芯片面积和工艺要求后,最终在所设计的10G以太网接入芯片中,采用了代入法设计的CRC编码器和解码器?

10G以太网接入系统中需要采用并行CRC编码器?本文提出了基于组合逻辑的直接实现和基于流水线的实现方法?其中直接实现的方法又分为矩阵法和代入法两种?经过具体推导发现直接实现的编码器可以满足延时要求,因而被本系统所采用?而基于流水线的设计因为其延时较小,可以用于更高速的场合?本文提出的三种并行化设计方法已经通过了硬件验证?这些设计思想同样适用于其他线性移位寄存器,如扰码器的设计?

参考文献

1 程 超,程善美.Unfolding算法实现的高速并行CRC电路的VLSI设计.微电子学与计算机[J],2002:(12):68～69

2 刘新宁,王超,胡晨,蔡洪亮.一种快速CRC算法的硬件实 现方法.电子器件[J]:2003:26(1):88~91

3 王 耿,姜智忠.用HDL语言实现循环冗余校验.微电子学与计算机[J],2002:(5):4～6

4 程 军,陈贵灿,姜 飞.USB数据传输中CRC校验码的并行算法实现.微电子学与计算机[J],2003:(3):77～80

5 曹志刚,钱亚生.现代通信原理[B].北京:清华大学出版社,1992:344～346

6 IEEE Std,802.3.2000.

7 IEEE Std,802.3ae.2002.