基于StratixⅡ的加法樹(shù)設計及其應用

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

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

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

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

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

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

2 針對ALM的加法樹(shù)設計

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

這里N是指輸入數據的數目。

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

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

3 加法樹(shù)的應用

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

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

(1) 對應值進(jìn)行異或運算，得到N個(gè)l位相關(guān)運算結果；

(2) 統計N位相關(guān)結果中0或1的數目，得到N位數字中相同位和不同位的數目。

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

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

4 結語(yǔ)

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