數(shù)字信號處理(DSP)技術(shù)在許多領(lǐng)域內(nèi)具有廣泛的用途，如雷達(dá)、圖像處理、數(shù)據(jù)壓縮、數(shù)字電視和數(shù)據(jù)通信等。加法器和乘法器是構(gòu)成所有DSP系統(tǒng)的基本結(jié)構(gòu)，而加法運(yùn)算是最基本的算術(shù)運(yùn)算，無論是減法、乘法、除法或FFT運(yùn)算，最終都要分解為加法運(yùn)算。隨著在FPGA設(shè)計(jì)中加法功能需求的日益增長，加法樹規(guī)模的日益增大，人們提出了很多實(shí)現(xiàn)加法功能的設(shè)計(jì)方法，以期在高的運(yùn)算速度與低的邏輯占用之間求得最佳的實(shí)現(xiàn)效果。StratixⅡ是Altera公司推出的新一代高端FPGA，他采用了不同于以往系列FPGA的邏輯結(jié)構(gòu)——自適應(yīng)邏輯模塊(ALM)，這種ALM結(jié)構(gòu)可以說是FPGA構(gòu)架方面的革命。StratixⅡALM模塊可以靈活配置為3～7輸入的查找表(LUT)，他包含內(nèi)置的加法器塊，能夠一次完成最多3比特的加法而不需要耗費(fèi)額外的LUT資源。對于通用算術(shù)和加法樹功能，StratixⅡ器件比其他FPGA架構(gòu)提供了更好的性能和更少的邏輯占用。

本文提出了一種針對StratixⅡ中ALM特點(diǎn)的加法樹設(shè)計(jì)方案，給出了一個在高速數(shù)字相關(guān)器中的實(shí)際應(yīng)用，并進(jìn)行計(jì)算機(jī)綜合測試驗(yàn)證。

1 StratixⅡ的自適應(yīng)邏輯模塊(ALM)

FPGA的邏輯單元(LE)的經(jīng)典結(jié)構(gòu)是由一個4輸入的LUT和一個觸發(fā)器組成的。為什么是4輸入而不是其他的邏輯結(jié)構(gòu)呢，這是由于采用較“窄”的邏輯結(jié)構(gòu)，比較節(jié)省硅片面積，但是總體性能比較差，而采用較“寬”的邏輯結(jié)構(gòu)，總體性能比較好，但是浪費(fèi)硅片面積，成本較高。所以采用4輸入的LUT只是在成本和性能之間做的一個折衷。

圖1給出的StratixⅡ的ALM正是兼有了“窄”的邏輯結(jié)構(gòu)的高利用率和“寬”邏輯結(jié)構(gòu)的高性能。ALM中的組合邏輯模塊可以根據(jù)用戶的需求由設(shè)計(jì)工具自動配置成需要的模式?？梢耘涑?輸入和3輸入的LUT，或兩個4輸入的LUT等。另外，ALM內(nèi)部獨(dú)立于LUT之外還有兩個3輸入加法器，每個ALM中允許對3個不同的2 b數(shù)據(jù)進(jìn)行加法操作。這種能力通過壓縮加法樹中總的步驟數(shù)，大大提高了加法樹的性能，并且邏輯資源耗用也大大減少了，因?yàn)閷?個1 b數(shù)據(jù)相加在StratixⅡ器件中只占用半個ALM，而對于傳統(tǒng)的4輸入LUT架構(gòu)則需要2個LE。

圖2列出了和傳統(tǒng)的4輸入LUT結(jié)構(gòu)的FPGA相比較，采用ALM的StratixⅡFPGA器件例化3輸入加法器的優(yōu)勢。從圖2中可以清楚地看出，對于同樣3個2 b數(shù)據(jù)相加的邏輯結(jié)構(gòu)，傳統(tǒng)4輸入LUT結(jié)構(gòu)的FPGA例化需2級完成，占用4個LE，而對于采用ALM的StratixⅡFPGA器件來例化，只需一個ALM即可。

2 針對ALM的加法樹設(shè)計(jì)

目前大多數(shù)FPGA都是基于傳統(tǒng)的4輸入LUT加上一個觸發(fā)器的LE結(jié)構(gòu)，如Altera的Stratix，APEX，Cy-clone和FLEX10K等器件族。他們在實(shí)現(xiàn)加法樹時只能采用2輸入加法樹，而采用ALM結(jié)構(gòu)的StratixⅡ器件實(shí)現(xiàn)加法樹時，可根據(jù)需要采用3輸入加法樹或2輸入加法樹。這樣，就能壓縮加法樹總的步驟數(shù)，提高加法樹的性能。減少的加法樹步驟n可由以下公式計(jì)算出：

這里N是指輸入數(shù)據(jù)的數(shù)目。

對于傳統(tǒng)的FPGA，如果實(shí)現(xiàn)A+B+C三個數(shù)的加法器，最高頻率的方法是先實(shí)現(xiàn)2個數(shù)的加法，如A+B，將和用寄存器打一拍，然后將寄存器的和與第三個被加數(shù)(C)相加。這種方法實(shí)現(xiàn)1比特加法器時，A+B相加將使用1個加法器和1個寄存器，即一個LE，需1級邏輯完成。這種思路通常被稱為2輸入加法樹結(jié)構(gòu)，將加法樹逐級拓展，可以實(shí)現(xiàn)更長的加法樹結(jié)構(gòu)。如果實(shí)現(xiàn)A+B+C+D+E五個數(shù)(16位)的加法樹，使用這種2輸入加法樹方法共需3級寄存器緩存。其Verilog程序主要算法如下給出，選用器件StratixⅡEP2S15FC484-5，圖3(a)給出了經(jīng)過Synplify Pro 7.7綜合后的RTL視圖。綜合結(jié)果為：默認(rèn)約束條件下，共需64個ALM，實(shí)現(xiàn)估算的時鐘頻率為400.00 MHz。

由于ALM對輸入可以在3到7之間自由配置，那么對于上述16比特的5個數(shù)的加數(shù)求和的加法器，可以讓ALM配置成6輸入的LUT，使用6-LUT可以同時完成3比特加法，用2個3輸入的加法器取代上述的4個2輸人加法器來實(shí)現(xiàn)。其算法如下給出，在其他同樣條件下，綜合后的RTL視圖如圖3(b)所示，綜合結(jié)果為共需32個ALM，實(shí)現(xiàn)估算的時鐘頻率為427.30 MHz?？梢姽?jié)約了50％的ALM資源。

3 加法樹的應(yīng)用

加法樹在很多應(yīng)用中出現(xiàn)，比如用在濾波器、乘法器、累加器、第三代(3G)無線基站的信道卡相關(guān)器等。下面以在數(shù)字通信系統(tǒng)中廣泛應(yīng)用的高速數(shù)字相關(guān)器為例來說明加法樹的應(yīng)用。

在數(shù)字通信系統(tǒng)中，常用一個特定的序列作為數(shù)據(jù)開始的標(biāo)志，稱為幀同步字，發(fā)送端在發(fā)送數(shù)據(jù)前插入幀同步字，接收端如果收到幀同步字就可以確定幀的起始位置，從而實(shí)現(xiàn)發(fā)送和接收數(shù)據(jù)的幀同步。數(shù)字相關(guān)器的作用是實(shí)現(xiàn)兩個數(shù)字信號之間的相關(guān)運(yùn)算，即比較等長度的兩個序列間相等的位數(shù)。最基本的相關(guān)器是異或門。例如y=a○+b，當(dāng)a=b時，y=0，表示數(shù)據(jù)位相同；當(dāng)a≠b時，y=1，表示數(shù)據(jù)位不同。多位數(shù)字相關(guān)器可以由l位相關(guān)器級連構(gòu)成。N位數(shù)字相關(guān)器的運(yùn)算通?？梢苑纸鉃橐韵聝蓚€步驟：

(1) 對應(yīng)值進(jìn)行異或運(yùn)算，得到N個l位相關(guān)運(yùn)算結(jié)果；

(2) 統(tǒng)計(jì)N位相關(guān)結(jié)果中0或1的數(shù)目，得到N位數(shù)字中相同位和不同位的數(shù)目。

對于一個32位的高速數(shù)字相關(guān)器，由于實(shí)現(xiàn)起來需要的乘積項(xiàng)、或門過多，因此為降低耗用資源，可以分解為8個4位相關(guān)器，然后用3級加法器相加得到全部32位的相關(guān)結(jié)果，這是傳統(tǒng)的實(shí)現(xiàn)方法，如圖4(a)所示。針對采用靈活的ALM結(jié)構(gòu)的StratixII器件，可以采用3輸入加法器來改進(jìn)加法樹，只用2級加法樹就可完成，如圖4(b)所示。

采用器件StratixⅡEP2S15FC484-5分別用2輸入加法器樹和3輸入加法器樹來實(shí)現(xiàn)上述相關(guān)器，SynplifyPro 7.7對圖4(a)綜合結(jié)果為占用80個ALUTs(自適應(yīng)查找表)和56個FF(觸發(fā)器)，估算時鐘頻率為509.9 MHz。而對圖4(b)綜合結(jié)果為占用65個ALUTs和41個FF，估算時鐘頻率為465.0MHz。可見雖然稍微降低了時鐘頻率，但節(jié)省了大約20％的資源占用。

4 結(jié)語

本文給出了使用StratixⅡFPGA實(shí)現(xiàn)加法樹的方案及其在高速數(shù)字相關(guān)器中的應(yīng)用。計(jì)算機(jī)綜合仿真結(jié)果表明，該方案與傳統(tǒng)實(shí)現(xiàn)加法樹的方案比較，能通過壓縮加法樹中總的步驟數(shù)，大大減少了對FPGA邏輯資源的占用，并且隨著加法樹輸入數(shù)據(jù)的數(shù)目增加，邏輯級和邏輯資源減少的百分比會更大。