摘? 要: 多加數的加法器是FPGA的一個比較常見的應用。仿真對比了其三種實現方案的性能和所消耗資源，得出進位保留加法陣列是首選方案。針對進位保留加法陣列實現的復雜性給出了一個加法陣列的HDL代碼生成器，極大地簡化了加法陣列的設計工作。?
關鍵詞: 進位保留加法陣列? FPGA HDL代碼生成器?
?
在現代數字通信系統中，FPGA的應用相當廣泛。尤其在對基帶信號的處理和整個系統的控制中，FPGA不但能大大縮減電路的體積，提高電路的穩定性，而且先進的開發工具使整個系統的設計調試周期大大縮短。其中對于一些基帶信號處理任務，既可以用硬件實現，也可以用軟件實現。用硬件實現的突出特點是可處理的數據速率大大提高，但相應的硬件實現也有一些弊端。對于目前流行的一些CPU包括DSP和單片機，都擁有豐富的指令集，可以很方便地處理各種數學運算。而用FPGA或ASIC這樣的純硬件來實現數學運算則有一定的困難，且不同的實現結構所能達到的性能也大不相同。加法器是在FPGA中實現各種數學運算的基礎。一個單純的兩個加數的加法器可以用簡單的組合邏輯來實現。但對于求多個加數和的運算，則可以有多種實現方案。下面首先比較幾種實現方案的性能和所消耗資源，然后針對最優方案給出一種HDL(Hardware Description Language)代碼生成器。?
1 多加數加法器不同實現方案的分析和比較?
本文所討論的加法器的加數都是無符號的正數，對于帶符號的加法運算可以通過一些附加處理后送入無符號加法器。以計算8個1位二進制加數的和為例進行分析，它可以有以下幾種方案來實現:方案一最普通，是直接用加法器的級聯將所有8個位逐次相加，這種實現方案最簡單。因為8個1Bit數據的和最大可以是8，為4Bit數據，為了處理方便，所有的加數都事先擴展到4Bit再進行相加。設累加器的總延時為Tadd，一個全加器的延時為Ta，則用普通加法器進行一個4Bit加法。由于進位的逐級傳遞，所以在最壞情況下，需要大約4Ta的時間，8個加數全部加完需要7×4Ta=28Ta的時間。方案二是對方案一的改進，即將4Bit全加器全部換成超前進位加法器。設超前進位加法器的延時為Tc(Ta≤Tc<<4Ta)，這樣全部加法需要7Tc的時間。雖然方案二的時延已經縮短很多，可以處理的數據速率得到提高，但這種級聯式的加法器的延時會隨著加數的增多而呈線性增長，在要求速度較高的場合無法達到要求。于是本文提出方案三，即采用適合硬件實現高速并行的進位保留加法陣列。典型的8個1Bit數據進位保留加法陣列如圖1所示。?
?
?
一個1位全加器有三個輸入 A、B、Ci和兩個輸出Sum、Co，其中A和B是加數與被加數，Ci是輸入進位，Sum是和，Co是輸出進位。三個輸入對兩個輸出而言是對稱的，即使它們互相交換位置結果也不會受到影響。如果把一串全加器簡單排成一行，它們之間的進位線不連接，則這一串全加器稱為進位保留全加器。它具有如下特性:三個輸入數之和等于兩個輸出數之和，即三個相加數每通過一次進位保留加法器，其個數就變為原來的2/3。利用該特點，對于所有相加數，在第一級將這些相加數分成三個一組，每組進入一個進位保留加法器，產生的和與進位數為原來的2/3，但是產生的和數位數有所擴展。在第二級再將上一級的輸出分為3個一組，分別相加。依此類推，直到最后形成兩個操作數，即累加和與累加進位。再用超前進位加法器將它們相加就得到最終的結果。由圖1可知這種進位保留加法陣列的延時為:4Ta+Tc。?
以Altera公司的FPGA芯片EPF10K30為實現芯片，對采用上面三種方案的8個1Bit加數的加法器進行了仿真，仿真波形如圖2所示。?
?
?
由圖2可以看出，對于8Bit的Codeword中的“1”進行統計，三種加法器方案中進位保留加法陣列方案(AdderArray)的延時最短;方案二，超前進位加法器級聯方案(FastAdder)的延時次之;方案一，采用普通全加器級聯方案(FullAdder)的延時最長。上面的仿真由于位數較少，并不能很明顯地體現出幾種方案的差別。圖3是對32Bit漢明距離發生器所用的累加器的仿真波形圖。?
?
?
由圖3可以很明顯地看出，方案三，進位保留加法陣列的延時大大低于另兩種方案;而方案二的延時小于方案一，但相差不是很大，這主要因為雖然超前進位加法器本身的計算時間小于普通全加器。但累加結果在級間是逐級串行傳遞的，所以隨著級數的增多，其延時也會迅速增大。而每一級的超前進位的加法優勢受輸入數據影響較大，對于比較小的數據，不涉及到向高位的進位傳遞問題，超前進位邏輯的作用就不能被完全發揮出來。?
一般說來，系統可實現的性能與它所消耗的資源或處理復雜度之間總是矛盾的，性能的提高總是要以多消耗資源為代價的，而資源節省也總要相應降低一些性能。但是對于三種加法器方案所消耗資源進行統計表明，進位保留加法陣列消耗的資源大大小于其他兩種方案。對于32個1Bit加法器方案，若采用Altera公司的EPF10K30芯片分別實現，級聯型全加器方案和級聯型超前進位加法器方案均需要消耗182個LC(Logical Cells)，而進位保留加法陣列方案僅需65個LC。由此可知，進位保留加法陣列方案無論從性能表現還是資源消耗上都比前兩種方案優異。這是因為它是一種并行處理的資源利用率更高的方案，是一種本質上不同于前兩者的更好的實現方案。?
2 進位保留加法陣列的HDL代碼生成器?
雖然進位保留加法器具有如此明顯的優勢，但它的實現是比較復雜的，不如級聯型加法器直觀、易實現。首先需要計算加法陣列的結構參數，參見圖1，包括加法陣列的層數，每層所需要的全加器的個數和每層操作數的位數，然后按照陣列的規則畫出陣列的結構圖，最后對照結構圖寫HDL代碼。其中每層操作數的位數都不同，而且全加器的輸出Sum和Co有不同的權值，在加到下一層運算中時處理方式是不同的，Co需要移位相加。對于一個稍微大一點的陣列，編寫HDL代碼是一件既耗時又容易出錯的工作。針對這種情況，本文給出了一個進位保留加法陣列的HDL代碼生成器。它可以根據設計的需要自動計算加法陣列的結構參數，然后生成對應的HDL代碼，大大方便了加法陣列的設計工作。?
如圖4所示，程序所需要的輸入參數是加法陣列輸入加數的個數和位數，單擊“計算”按鈕后程序將生成整個進位保留加法陣列的結構參數和消耗資源統計。由圖4可知，32個1Bit加數的加法陣列共有8層，第一層需要10組全加器，每組1Bit;第二層需要7組全加器，每組2Bit(即兩個1Bit全加器)，以此類推。窗口左下角的資源統計欄里計算了整個加法陣列所需的全加器個數。而所需的LC數目是一個大概的統計值，它是在Maxplus II Version 10里編譯本HDL代碼生成器所生成的AHDL(Altera HDL)代碼，然后讓編譯器自選FLEX 10K器件進行適配的結果。需要特別指出的是，加法陣列各層之間的連接結構將極大地影響FPGA的適配結果。所以本生成器根據Altera公司FPGA的結構特點，對陣列的連接結構進行了優化設計，使加法陣列適配后消耗的資源接近最小。?
?
?
點擊“生成代碼”按鈕后將出現圖5所示的HDL代碼窗口。圖5中顯示的是32個1Bit加法陣列的AHDL代碼。單擊“拷貝”按鈕，然后在Maxplus II軟件中粘貼到一個tdf文件中就可以直接進行編譯和適配了。本程序還可以提供加法陣列的VHDL和Verilog代碼，使進位保留加法陣列可以很方便地嵌入任何一種形式的系統設計中。?
?
?
一些很典型的FPGA應用如FIR濾波器、高速乘法器和漢明距離發生器等都需要計算多個加數的和。針對此需求，本文首先比較了多加數加法器的三種實現方案，得出進位保留加法陣列是一種性能優異的實現方案。然后給出了一個能夠自動生成加法陣列HDL代碼的程序，它方便易用，并且能夠提供AHDL、VHDL和Verilog三種HDL語言的代碼，可以極大地提高開發效率。?
參考文獻?
1 Singh S， Rose J. The Effect of Logic Block Architecture on FPGA Performance， IEEE Journal of Solid-State Circuits， 1992;27(3)?
2 羅 莉，胡受仁.一個并行高速乘法器芯片的設計與實現.計算機工程與科學，1997;11?
3 馬群生，李健航編譯. MAX plus II 入門.北京:清華大學Altera培訓中心，1996.4?
4 Leonardo HDL Synthesis Guide，Exemplar Logic?
5 Altera Corporation， Device Data Book， May 1999