基于StratixⅡ的加法樹(shù)設(shè)計(jì)及其應(yīng)用

數(shù)字信號(hào)處理(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)算，無(wú)論是減法、乘法、除法或FFT運(yùn)算，最終都要分解為加法運(yùn)算。隨著在FPGA設(shè)計(jì)中加法功能需求的日益增長(zhǎng)，加法樹(shù)規(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)可以說(shuō)是FPGA構(gòu)架方面的革命。StratixⅡALM模塊可以靈活配置為3～7輸入的查找表(LUT)，他包含內(nèi)置的加法器塊，能夠一次完成最多3比特的加法而不需要耗費(fèi)額外的LUT資源。對(duì)于通用算術(shù)和加法樹(shù)功能，StratixⅡ器件比其他FPGA架構(gòu)提供了更好的性能和更少的邏輯占用。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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