应用于片上网络的BCH码的设计与实现

孙觉非，胡庆生，黄圆圆

(东南大学1仪器科学与工程学院，2信息科学与工程学院，3集成电路学院，江苏 南京 210096)

0 引言

片上网络(NoC)是将计算机网络互联的设计理念引入到芯片设计中来，在芯片上实现基于网络通信的多核系统[1]。图1所示为一个3×3的Hermes NoC平台，Hermes NoC采用的是2D-Mesh的拓扑结构，通过虫孔交换机制和XY路由算法，实现基于包的交换功能[2]。图中有9个交换器，每个交换器都有一组双向端口分别和相邻交换器和一个IP核相连。根据位置的不同，各交换器有不同的端口数目，中心交换器包含所有的五个端口，四个角上的交换器只有三个端口。每个交换器均有一个独一无二的地址，用XY来表示，如图中标出的00，10等。其中X代表水平位置，Y代表垂直位置。

图1 一个3×3的Hermes NoC结构

在NoC的研究过程中，功耗问题是关注的重点之一。采用低摆幅信号是目前NoC中降低功耗较为常用手段，根据估算，在0.18μm工艺下，将互连信号的摆幅减小数百个毫伏，可以减少功耗10倍[3]。但随着小振幅信号的引入，噪声对于信号质量的干扰趋于明显。网络通信系统中常用的差错控制方法是在信号的传输过程中引入纠错编码。由于芯片内部通信信道的传输条件较为可靠，只需使用编码解码方法较为简单，功耗和延时都较低的第一代纠错编码即可。

1 NoC中的差错控制编码

1)汉明码

汉明码是一种在数字通信系统中应用广泛的线性分组码，它延伸了奇偶校验位的概念，在需要传送的数据后面添加数位冗余数据，每发送2m-m-1位数据时，就添加n位的冗余比特，从而达到差错控制的目的。普通汉明码的汉明距离为3，因此可以对一组数据中的一位错误进行检错和纠错。

2)BCH码

BCH码是数据通信领域中常用的一种差错校验码，其特征是可以纠正多位错误。给定任一有限域GF(q)及其扩域GF(qm)，其中q是素数或素数的幂，m为某一正整数。若码元取自GF(q)上的一循环码，它的生成多项式g(x)的根集合R中含有以下 δ-1 个连续根:{αm0，αm0+1，……，αm0+δ-2}时，则由g(x)生成的循环码称为q进制BCH码。

设 mi(x)和 ei分别是 αi(i=0，1，…，δ-2)相应的最小多项式和级，则BCH码的生成多项式和码长分别是

其中，LCM表示取最小公倍式。

2 适用片上网络的差错控制编码

目前的片上网络通信错误主要集中在一位错误或者两位错误上[3-4]。这样，纠一位错的汉明码和可纠多位错的BCH码的纠错能力均可满足NoC的纠错要求。下面本文首先对两种码在编码效率、硬件复杂度和功耗等方面进行比较，之后，给出纠两位错的BCH码的设计与实现。

2.1 编码的码率比较

表1给出了汉明码和BCH码的码率比较，其中BCH码的码间距离为5，能够纠两位错码。从表可见，汉明码的编码效率高于BCH码。但是，当信息长度超过120位后，两种编码效率都超过90%。随着信息长度增加，其编码效率差距更小。

表1 编码的码率

2.2 编码的硬件复杂度比较

将两种编码方案的编码模块和解码模块分别用Synopsis公司的综合工具进行综合，并基于TSMC公司0.13μm CMOS工艺，得到了表2所示的综合结果。其中时钟频率为200MHz。BCH码的面积和功耗要比汉明码大，但BCH码的纠错能力也大于汉明码。

表2 编解码的硬件复杂度比较

由表1，2结合前面的分析讨论，我们可以得到表3所示的汉明 (15，11)和BCH(15，7)编解码方案的比较结果。

表3 两种编解码方案的比较

由表3可见，发生一位错误的时候，两种码都可以检测并纠正这一位随机错误。发生两位随机错误的时候，只有BCH码可以纠错。但BCH码的编解码电路略微复杂，电路面积较之汉明码的面积大86.6%，电路功耗增大44.10%。可见，BCH码纠错能力的提高是以复杂度和功耗为代价的。为了满足纠两位随机错误的需求，本文将讨论BCH码。

2.3 BCH 的编解码

BCH码编码的实质就是以生成多项式g(x)为模的除法问题，通常用线性反馈移位寄存器来实现。BCH码的译码方法有时域译码和频域译码两种，常用的是基于BM(Berlekamp-Massey)算法的时域译码方法。BM迭代算法主要由以下三步实现[5]。

(1)由接收到的R(x)计算伴随式S=(s1，s2，…，s2t);

(2)根据伴随式求错误位置多项式σ(x)=σtxt+σt-1xt-1+...+σ1x1+1;

(3)求解σ(x)的根(钱氏搜索法)确定错误位置，并纠正错误。

3 基于BCH码的NoC差错控制系统

本文将BCH码应用在一个Hermes NoC平台中，并在Xilinx Virtex-5开发板上实现了基于BCH码的NoC差错控制系统。具体实现的是一个2×2 Mesh结构的 NoC网络，它包括 N00，N10，N01和N11四个节点模块，每个模块已经将本地IP核和交换器集成在一起，其地址分别为“00”，“10”，“01”，“11”(图1)。

1)未纠错的板级FPGA验证

对未加入纠错码的Hermes NoC平台进行板级的FPGA验证，图2即为2×2 Mesh结构的Hermes NoC的板级测试波形。其中txN00＜0＞，txN10，＜3＞为节点“00”和“10”发送的控制信号，ack_rxN10＜1＞，ack_rxN11＜2＞为节点“10”和“11”接收的应答信号，＜0＞、＜1＞、＜2＞和＜3＞分别代表交换器的东、西、北和南四个方向。data_outN00，data_outN10和data_inN10，data_outN11分别为相应节点的数据输出和数据输入，数据位宽为8比特。图2中的波形表示一个数据包从节点N00传送到节点N11的过程，该包的第一个数据分片包含着目的地址信息“11”，从节点N00的东向端口出发，到达节点N10的西向端口，然后经由节点N10转发，从其南向端口发出，最终到达节点N11。

图2 Hermes NoC平台的测试波形

2)差错控制系统FPGA验证

然后将BCH码加入到该Hermes平台中，实现NoC的差错控制系统。由于该系统的数据位宽为8比特，因此采用纠错能力t=2的BCH(31，21)的缩短码BCH(18，8)。参看图3，信息宽度为8比特的数据包从节点N00出发，经由节点N10最终到达节点N11，中间经过的两个信道都要进行BCH的编解码，其中编码后的数据宽度为18比特。为了验证该系统的差错控制效果，在信道中加入了误码，以观察系统的工作情况，其中错误限制在2个以内。

图3 Hermes NoC平台的差错控制系统验证框图

Hermes NoC差错控制系统的板级FPGA验证波形如图4所示，其中信号encode0010是数据data_outN00经编码后得到的，表示从节点N00到节点N10的编码器的输出信号;decode0010为在endode0010信号中加入误码后的信号，是从N00节点到N10节点的解码器的输入，而data_inN10就是解码器的输出。信号encode1011和decode1011的含义与此类似，分别表示节点N10和节点N11间的编码器输出和解码器输入信号。

图4 Hermes NoC差错控制系统的验证波形

从上图可以看出，从节点N00发出的数据data_outN00中的数据信息为“11”和“07”;编码后得到的数据encode0010分别为“04713”和“01E37”等;信道产生误码后的数据decode0010分别变为“14712”和“29E37”;decode0010信号经过解码后的输出信号data_inN10为“11”和“07”，与节点N00发送的数据相同。从而证明了数据在信道中产生的误码能够被BCH码有效地纠正。继而在节点N11，可以得到了同样的译码数据“11”和“07”，说明BCH码完成了前向纠错功能。

该系统已用Xilinx FPGA XC5VSX50T实现，ISE的布线结果显示系统的最高频率可达125MHz。

4 结语

本文研究了适用于NoC的差错控制系统，对能纠1到2位错的两种编码方案在性能上进行了比较。在此基础上设计实现了一种能纠两位错码的BCH码，并将其应用于基于Hermes的NoC平台实现的一个NoC的差错控制系统。

[1]Benini L，de Micheli G.Networks on Chips:A New SoC Paradigm[J].Computer，2002，35(1):70-78

[2]Fernando Moraes，Ney Calazans，Aline Mello，Leandro Moeller，Luciano Ost.HERMES:an infrastructure for low area overhead packet-switching networks on chip，Integration，2004 ，vol.38，no.1，pp.69-93，

[3]D.Bertozzi，L.Benini，and G.D.Micheli.Error control schemes for on-chip communication links:The energy-reliability tradeoff.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.24(6):818-831，June 2005.

[4]S.Murali et al.Analysis of error recovery schemes for networks on chips.IEEE Design ＆ Test of Computers.22(5):434-442，Sep.-Oct.2005

[5]Zhang Jun，Wang-Zhigong，Hu-Qingsheng，Xiao Jie.High-speed architecture and implementation for Berlekamp-Messay algorithm.Journal of Circuits and System，vol.11，no.4，pp85-89，August，2006