基于StratixⅡ的加法树设计及其应用

数字信号处理(DSP)技术在许多领域内具有广泛的用途，如雷达、图像处理、数据压缩、数字电视和数据通信等。加法器和乘法器是构成所有DSP系统的基本结构，而加法运算是最基本的算术运算，无论是减法、乘法、除法或FFT运算，最终都要分解为加法运算。随着在FPGA设计中加法功能需求的日益增长，加法树规模的日益增大，人们提出了很多实现加法功能的设计方法，以期在高的运算速度与低的逻辑占用之间求得最佳的实现效果。StratixⅡ是Altera公司推出的新一代高端FPGA，他采用了不同于以往系列FPGA的逻辑结构——自适应逻辑模块(ALM)，这种ALM结构可以说是FPGA构架方面的革命。StratixⅡALM模块可以灵活配置为3～7输入的查找表(LUT)，他包含内置的加法器块，能够一次完成最多3比特的加法而不需要耗费额外的LUT资源。对于通用算术和加法树功能，StratixⅡ器件比其他FPGA架构提供了更好的性能和更少的逻辑占用。

本文提出了一种针对StratixⅡ中ALM特点的加法树设计方案，给出了一个在高速数字相关器中的实际应用，并进行计算机综合测试验证。

1 StratixⅡ的自适应逻辑模块(ALM)

FPGA的逻辑单元(LE)的经典结构是由一个4输入的LUT和一个触发器组成的。为什么是4输入而不是其他的逻辑结构呢，这是由于采用较“窄”的逻辑结构，比较节省硅片面积，但是总体性能比较差，而采用较“宽”的逻辑结构，总体性能比较好，但是浪费硅片面积，成本较高。所以采用4输入的LUT只是在成本和性能之间做的一个折衷。

图1给出的StratixⅡ的ALM正是兼有了“窄”的逻辑结构的高利用率和“宽”逻辑结构的高性能。ALM中的组合逻辑模块可以根据用户的需求由设计工具自动配置成需要的模式。可以配成5输入和3输入的LUT，或两个4输入的LUT等。另外，ALM内部独立于LUT之外还有两个3输入加法器，每个ALM中允许对3个不同的2 b数据进行加法操作。这种能力通过压缩加法树中总的步骤数，大大提高了加法树的性能，并且逻辑资源耗用也大大减少了，因为将3个1 b数据相加在StratixⅡ器件中只占用半个ALM，而对于传统的4输入LUT架构则需要2个LE。

图2列出了和传统的4输入LUT结构的FPGA相比较，采用ALM的StratixⅡFPGA器件例化3输入加法器的优势。从图2中可以清楚地看出，对于同样3个2 b数据相加的逻辑结构，传统4输入LUT结构的FPGA例化需2级完成，占用4个LE，而对于采用ALM的StratixⅡFPGA器件来例化，只需一个ALM即可。

2 针对ALM的加法树设计

目前大多数FPGA都是基于传统的4输入LUT加上一个触发器的LE结构，如Altera的Stratix，APEX，Cy-clone和FLEX10K等器件族。他们在实现加法树时只能采用2输入加法树，而采用ALM结构的StratixⅡ器件实现加法树时，可根据需要采用3输入加法树或2输入加法树。这样，就能压缩加法树总的步骤数，提高加法树的性能。减少的加法树步骤n可由以下公式计算出：

这里N是指输入数据的数目。

对于传统的FPGA，如果实现A+B+C三个数的加法器，最高频率的方法是先实现2个数的加法，如A+B，将和用寄存器打一拍，然后将寄存器的和与第三个被加数(C)相加。这种方法实现1比特加法器时，A+B相加将使用1个加法器和1个寄存器，即一个LE，需1级逻辑完成。这种思路通常被称为2输入加法树结构，将加法树逐级拓展，可以实现更长的加法树结构。如果实现A+B+C+D+E五个数(16位)的加法树，使用这种2输入加法树方法共需3级寄存器缓存。其Verilog程序主要算法如下给出，选用器件StratixⅡEP2S15FC484-5，图3(a)给出了经过Synplify Pro 7.7综合后的RTL视图。综合结果为：默认约束条件下，共需64个ALM，实现估算的时钟频率为400.00 MHz。

由于ALM对输入可以在3到7之间自由配置，那么对于上述16比特的5个数的加数求和的加法器，可以让ALM配置成6输入的LUT，使用6-LUT可以同时完成3比特加法，用2个3输入的加法器取代上述的4个2输人加法器来实现。其算法如下给出，在其他同样条件下，综合后的RTL视图如图3(b)所示，综合结果为共需32个ALM，实现估算的时钟频率为427.30 MHz。可见节约了50％的ALM资源。

3 加法树的应用

加法树在很多应用中出现，比如用在滤波器、乘法器、累加器、第三代(3G)无线基站的信道卡相关器等。下面以在数字通信系统中广泛应用的高速数字相关器为例来说明加法树的应用。

在数字通信系统中，常用一个特定的序列作为数据开始的标志，称为帧同步字，发送端在发送数据前插入帧同步字，接收端如果收到帧同步字就可以确定帧的起始位置，从而实现发送和接收数据的帧同步。数字相关器的作用是实现两个数字信号之间的相关运算，即比较等长度的两个序列间相等的位数。最基本的相关器是异或门。例如y=a○+b，当a=b时，y=0，表示数据位相同；当a≠b时，y=1，表示数据位不同。多位数字相关器可以由l位相关器级连构成。N位数字相关器的运算通常可以分解为以下两个步骤：

(1) 对应值进行异或运算，得到N个l位相关运算结果；

(2) 统计N位相关结果中0或1的数目，得到N位数字中相同位和不同位的数目。

对于一个32位的高速数字相关器，由于实现起来需要的乘积项、或门过多，因此为降低耗用资源，可以分解为8个4位相关器，然后用3级加法器相加得到全部32位的相关结果，这是传统的实现方法，如图4(a)所示。针对采用灵活的ALM结构的StratixII器件，可以采用3输入加法器来改进加法树，只用2级加法树就可完成，如图4(b)所示。

采用器件StratixⅡEP2S15FC484-5分别用2输入加法器树和3输入加法器树来实现上述相关器，SynplifyPro 7.7对图4(a)综合结果为占用80个ALUTs(自适应查找表)和56个FF(触发器)，估算时钟频率为509.9 MHz。而对图4(b)综合结果为占用65个ALUTs和41个FF，估算时钟频率为465.0MHz。可见虽然稍微降低了时钟频率，但节省了大约20％的资源占用。

4 结语

本文给出了使用StratixⅡFPGA实现加法树的方案及其在高速数字相关器中的应用。计算机综合仿真结果表明，该方案与传统实现加法树的方案比较，能通过压缩加法树中总的步骤数，大大减少了对FPGA逻辑资源的占用，并且随着加法树输入数据的数目增加，逻辑级和逻辑资源减少的百分比会更大。