基于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邏輯資源的占用，并且隨著加法樹輸入數據的數目增加，邏輯級和邏輯資源減少的百分比會更大。