一個(gè)進(jìn)位保留加法陣列的HDL代碼生成器

在現(xiàn)代數(shù)字通信系統(tǒng)中，FPGA的應(yīng)用相當(dāng)廣泛。尤其在對(duì)基帶信號(hào)的處理和整個(gè)系統(tǒng)的控制中，FPGA不但能大大縮減電路的體積，提高電路的穩(wěn)定性，而且先進(jìn)的開(kāi)發(fā)工具使整個(gè)系統(tǒng)的設(shè)計(jì)調(diào)試周期大大縮短。其中對(duì)于一些基帶信號(hào)處理任務(wù)，既可以用硬件實(shí)現(xiàn)，也可以用軟件實(shí)現(xiàn)。用硬件實(shí)現(xiàn)的突出特點(diǎn)是可處理的數(shù)據(jù)速率大大提高，但相應(yīng)的硬件實(shí)現(xiàn)也有一些弊端。對(duì)于目前流行的一些CPU包括DSP和單片機(jī)，都擁有豐富的指令集，可以很方便地處理各種數(shù)學(xué)運(yùn)算。而用FPGA或ASIC這樣的純硬件來(lái)實(shí)現(xiàn)數(shù)學(xué)運(yùn)算則有一定的困難，且不同的實(shí)現(xiàn)結(jié)構(gòu)所能達(dá)到的性能也大不相同。加法器是在FPGA中實(shí)現(xiàn)各種數(shù)學(xué)運(yùn)算的基礎(chǔ)。一個(gè)單純的兩個(gè)加數(shù)的加法器可以用簡(jiǎn)單的組合邏輯來(lái)實(shí)現(xiàn)。但對(duì)于求多個(gè)加數(shù)和的運(yùn)算，則可以有多種實(shí)現(xiàn)方案。下面首先比較幾種實(shí)現(xiàn)方案的性能和所消耗資源，然后針對(duì)最優(yōu)方案給出一種HDL(Hardware Description Language)代碼生成器。

1 多加數(shù)加法器不同實(shí)現(xiàn)方案的分析和比較

　　本文所討論的加法器的加數(shù)都是無(wú)符號(hào)的正數(shù)，對(duì)于帶符號(hào)的加法運(yùn)算可以通過(guò)一些附加處理后送入無(wú)符號(hào)加法器。以計(jì)算8個(gè)1位二進(jìn)制加數(shù)的和為例進(jìn)行分析，它可以有以下幾種方案來(lái)實(shí)現(xiàn):方案一最普通，是直接用加法器的級(jí)聯(lián)將所有8個(gè)位逐次相加，這種實(shí)現(xiàn)方案最簡(jiǎn)單。因?yàn)?個(gè)1Bit數(shù)據(jù)的和最大可以是8，為4Bit數(shù)據(jù)，為了處理方便，所有的加數(shù)都事先擴(kuò)展到4Bit再進(jìn)行相加。設(shè)累加器的總延時(shí)為T(mén)add，一個(gè)全加器的延時(shí)為T(mén)a，則用普通加法器進(jìn)行一個(gè)4Bit加法。由于進(jìn)位的逐級(jí)傳遞，所以在最壞情況下，需要大約4Ta的時(shí)間，8個(gè)加數(shù)全部加完需要7×4Ta=28Ta的時(shí)間。方案二是對(duì)方案一的改進(jìn)，即將4Bit全加器全部換成超前進(jìn)位加法器。設(shè)超前進(jìn)位加法器的延時(shí)為T(mén)c(Ta≤Tc4Ta)，這樣全部加法需要7Tc的時(shí)間。雖然方案二的時(shí)延已經(jīng)縮短很多，可以處理的數(shù)據(jù)速率得到提高，但這種級(jí)聯(lián)式的加法器的延時(shí)會(huì)隨著加數(shù)的增多而呈線(xiàn)性增長(zhǎng)，在要求速度較高的場(chǎng)合無(wú)法達(dá)到要求。于是本文提出方案三，即采用適合硬件實(shí)現(xiàn)高速并行的進(jìn)位保留加法陣列。典型的8個(gè)1Bit數(shù)據(jù)進(jìn)位保留加法陣列如圖1所示。

　　一個(gè)1位全加器有三個(gè)輸入 A、B、Ci和兩個(gè)輸出Sum、Co，其中A和B是加數(shù)與被加數(shù)，Ci是輸入進(jìn)位，Sum是和，Co是輸出進(jìn)位。三個(gè)輸入對(duì)兩個(gè)輸出而言是對(duì)稱(chēng)的，即使它們互相交換位置結(jié)果也不會(huì)受到影響。如果把一串全加器簡(jiǎn)單排成一行，它們之間的進(jìn)位線(xiàn)不連接，則這一串全加器稱(chēng)為進(jìn)位保留全加器。它具有如下特性:三個(gè)輸入數(shù)之和等于兩個(gè)輸出數(shù)之和，即三個(gè)相加數(shù)每通過(guò)一次進(jìn)位保留加法器，其個(gè)數(shù)就變?yōu)樵瓉?lái)的2/3。利用該特點(diǎn)，對(duì)于所有相加數(shù)，在第一級(jí)將這些相加數(shù)分成三個(gè)一組，每組進(jìn)入一個(gè)進(jìn)位保留加法器，產(chǎn)生的和與進(jìn)位數(shù)為原來(lái)的2/3，但是產(chǎn)生的和數(shù)位數(shù)有所擴(kuò)展。在第二級(jí)再將上一級(jí)的輸出分為3個(gè)一組，分別相加。依此類(lèi)推，直到最后形成兩個(gè)操作數(shù)，即累加和與累加進(jìn)位。再用超前進(jìn)位加法器將它們相加就得到最終的結(jié)果。由圖1可知這種進(jìn)位保留加法陣列的延時(shí)為:4Ta+Tc。

　　以Altera公司的FPGA芯片EPF10K30為實(shí)現(xiàn)芯片，對(duì)采用上面三種方案的8個(gè)1Bit加數(shù)的加法器進(jìn)行了仿真，仿真波形如圖2所示。

　　由圖2可以看出，對(duì)于8Bit的Codeword中的“1”進(jìn)行統(tǒng)計(jì)，三種加法器方案中進(jìn)位保留加法陣列方案(AdderArray)的延時(shí)最短;方案二，超前進(jìn)位加法器級(jí)聯(lián)方案(FastAdder)的延時(shí)次之;方案一，采用普通全加器級(jí)聯(lián)方案(FullAdder)的延時(shí)最長(zhǎng)。上面的仿真由于位數(shù)較少，并不能很明顯地體現(xiàn)出幾種方案的差別。圖3是對(duì)32Bit漢明距離發(fā)生器所用的累加器的仿真波形圖。

　　由圖3可以很明顯地看出，方案三，進(jìn)位保留加法陣列的延時(shí)大大低于另兩種方案;而方案二的延時(shí)小于方案一，但相差不是很大，這主要因?yàn)殡m然超前進(jìn)位加法器本身的計(jì)算時(shí)間小于普通全加器。但累加結(jié)果在級(jí)間是逐級(jí)串行傳遞的，所以隨著級(jí)數(shù)的增多，其延時(shí)也會(huì)迅速增大。而每一級(jí)的超前進(jìn)位的加法優(yōu)勢(shì)受輸入數(shù)據(jù)影響較大，對(duì)于比較小的數(shù)據(jù)，不涉及到向高位的進(jìn)位傳遞問(wèn)題，超前進(jìn)位邏輯的作用就不能被完全發(fā)揮出來(lái)。

　　一般說(shuō)來(lái)，系統(tǒng)可實(shí)現(xiàn)的性能與它所消耗的資源或處理復(fù)雜度之間總是矛盾的，性能的提高總是要以多消耗資源為代價(jià)的，而資源節(jié)省也總要相應(yīng)降低一些性能。但是對(duì)于三種加法器方案所消耗資源進(jìn)行統(tǒng)計(jì)表明，進(jìn)位保留加法陣列消耗的資源大大小于其他兩種方案。對(duì)于32個(gè)1Bit加法器方案，若采用Altera公司的EPF10K30芯片分別實(shí)現(xiàn)，級(jí)聯(lián)型全加器方案和級(jí)聯(lián)型超前進(jìn)位加法器方案均需要消耗182個(gè)LC(Logical Cells)，而進(jìn)位保留加法陣列方案僅需65個(gè)LC。由此可知，進(jìn)位保留加法陣列方案無(wú)論從性能表現(xiàn)還是資源消耗上都比前兩種方案優(yōu)異。這是因?yàn)樗且环N并行處理的資源利用率更高的方案，是一種本質(zhì)上不同于前兩者的更好的實(shí)現(xiàn)方案。

2 進(jìn)位保留加法陣列的HDL代碼生成器

　　雖然進(jìn)位保留加法器具有如此明顯的優(yōu)勢(shì)，但它的實(shí)現(xiàn)是比較復(fù)雜的，不如級(jí)聯(lián)型加法器直觀(guān)、易實(shí)現(xiàn)。首先需要計(jì)算加法陣列的結(jié)構(gòu)參數(shù)，參見(jiàn)圖1，包括加法陣列的層數(shù)，每層所需要的全加器的個(gè)數(shù)和每層操作數(shù)的位數(shù)，然后按照陣列的規(guī)則畫(huà)出陣列的結(jié)構(gòu)圖，最后對(duì)照結(jié)構(gòu)圖寫(xiě)HDL代碼。其中每層操作數(shù)的位數(shù)都不同，而且全加器的輸出Sum和Co有不同的權(quán)值，在加到下一層運(yùn)算中時(shí)處理方式是不同的，Co需要移位相加。對(duì)于一個(gè)稍微大一點(diǎn)的陣列，編寫(xiě)HDL代碼是一件既耗時(shí)又容易出錯(cuò)的工作。針對(duì)這種情況，本文給出了一個(gè)進(jìn)位保留加法陣列的HDL代碼生成器。它可以根據(jù)設(shè)計(jì)的需要自動(dòng)計(jì)算加法陣列的結(jié)構(gòu)參數(shù)，然后生成對(duì)應(yīng)的HDL代碼，大大方便了加法陣列的設(shè)計(jì)工作。

　　如圖4所示，程序所需要的輸入?yún)?shù)是加法陣列輸入加數(shù)的個(gè)數(shù)和位數(shù)，單擊“計(jì)算”按鈕后程序?qū)⑸烧麄€(gè)進(jìn)位保留加法陣列的結(jié)構(gòu)參數(shù)和消耗資源統(tǒng)計(jì)。由圖4可知，32個(gè)1Bit加數(shù)的加法陣列共有8層，第一層需要10組全加器，每組1Bit;第二層需要7組全加器，每組2Bit(即兩個(gè)1Bit全加器)，以此類(lèi)推。窗口左下角的資源統(tǒng)計(jì)欄里計(jì)算了整個(gè)加法陣列所需的全加器個(gè)數(shù)。而所需的LC數(shù)目是一個(gè)大概的統(tǒng)計(jì)值，它是在Maxplus II Version 10里編譯本HDL代碼生成器所生成的AHDL(Altera HDL)代碼，然后讓編譯器自選FLEX 10K器件進(jìn)行適配的結(jié)果。需要特別指出的是，加法陣列各層之間的連接結(jié)構(gòu)將極大地影響FPGA的適配結(jié)果。所以本生成器根據(jù)Altera公司FPGA的結(jié)構(gòu)特點(diǎn)，對(duì)陣列的連接結(jié)構(gòu)進(jìn)行了優(yōu)化設(shè)計(jì)，使加法陣列適配后消耗的資源接近最小。

　　點(diǎn)擊“生成代碼”按鈕后將出現(xiàn)圖5所示的HDL代碼窗口。圖5中顯示的是32個(gè)1Bit加法陣列的AHDL代碼。單擊“拷貝”按鈕，然后在Maxplus II軟件中粘貼到一個(gè)tdf文件中就可以直接進(jìn)行編譯和適配了。本程序還可以提供加法陣列的VHDL和Verilog代碼，使進(jìn)位保留加法陣列可以很方便地嵌入任何一種形式的系統(tǒng)設(shè)計(jì)中。

　　一些很典型的FPGA應(yīng)用如FIR濾波器、高速乘法器和漢明距離發(fā)生器等都需要計(jì)算多個(gè)加數(shù)的和。針對(duì)此需求，本文首先比較了多加數(shù)加法器的三種實(shí)現(xiàn)方案，得出進(jìn)位保留加法陣列是一種性能優(yōu)異的實(shí)現(xiàn)方案。然后給出了一個(gè)能夠自動(dòng)生成加法陣列HDL代碼的程序，它方便易用，并且能夠提供AHDL、VHDL和Verilog三種HDL語(yǔ)言的代碼，可以極大地提高開(kāi)發(fā)效率。