基于StratixⅡ的加法樹設計及其應用

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

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

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

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

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

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

2 針對ALM的加法樹設計

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

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

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

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

3 加法樹的應用

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

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

(1) 對應值進行異或運算，得到N個l位相關運算結果；

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

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

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

4 結語

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