基于改進(jìn)的布斯算法FPGA嵌入式18×18乘法器

摘要：設計了一款嵌入FPGA的乘法器，該乘法器能夠滿(mǎn)足兩個(gè)18 b有符號或17 b無(wú)符號數的乘法運算。該設計基于改進(jìn)的布斯算法，提出了一種新的布斯譯碼和部分積結構，并對9-2壓縮樹(shù)和超前進(jìn)位加法器進(jìn)行了優(yōu)化。該乘法器采用TSMC 0．18μn CMOS工藝，其關(guān)鍵路徑延遲為3．46 ns。

關(guān)鍵詞：布斯算法；部分積；9-2壓縮；兩級超前進(jìn)位加法器

目前，FPGA作為可編程邏輯器件(PLD)的主要產(chǎn)品，在通信、消贊電子、汽車(chē)電子、工業(yè)控制、國防安全等領(lǐng)域得到廣泛的應用。由于在性能和靈活性方面的完美組合，FPGA的使用范圍越來(lái)越廣，客觀(guān)上要求加強FPGA數字處理功能(如嵌入乘法器，數字信號處理器(DSP)等)?，F住幾乎每一款商用FPGA內部幾乎都嵌入了乘法器或數字信號處理器，如Xilinx公司的VirtexⅡ系列、Spartan-3／3A系列等。相對來(lái)說(shuō)我國的FPGA僅僅處于起步階段，FPGA的發(fā)展特別是高性能FPGA的發(fā)展刻不容緩。本文緊跟國家重大項目，對嵌入到FPGA的乘法器進(jìn)行了深入的研究提出了一個(gè)低功耗、高速度的乘法器。該乘法器采用了高速布斯譯碼、基于全加器的9-2壓縮樹(shù)和35 b兩級超前進(jìn)位加法器。高速布斯譯碼器采用了改進(jìn)的布斯算法，使得部分積經(jīng)過(guò)3個(gè)門(mén)的延遲得到，提高速度約為50％；9-2壓縮樹(shù)由3個(gè)3-2壓縮和一個(gè)4-2壓縮組成，使得部分積陣列僅經(jīng)過(guò)7個(gè)異或門(mén)延遲；35 b兩級超前進(jìn)位加法器采用的是基于4 b超前進(jìn)位加法器，使得加法器僅僅經(jīng)過(guò)10個(gè)門(mén)的延遲。

1 整體結構

圖1為18×18位乘法器的整體結構，它包含了布斯譯碼模塊、壓縮樹(shù)模塊和超前進(jìn)位加法模塊。部分積是通過(guò)本文采取的布斯譯碼器快速產(chǎn)生，然后其通過(guò)9-2壓縮樹(shù)被壓縮成兩個(gè)35 b的二進(jìn)制數，最后通過(guò)超前進(jìn)位加法器生成無(wú)符號位的35 b的結果。通過(guò)乘數和被乘數的符號位異或產(chǎn)生最終積的符號位，這樣就得到了36 b的最終結果。從圖1可以看出該乘法器整體結構和傳統的結構是一樣的。

2 布斯譯碼和部分積

通常進(jìn)行兩個(gè)數相乘，是通過(guò)所有的部分積相加得到。這樣，不僅乘法器的速度都得不到保證，而且會(huì )浪費芯片的面積。因此采取現在比較流行的布斯算法，因為它可以使部分積的數目減半，這樣對面積和速度都比較有利。在原算法的基礎上進(jìn)行了改進(jìn)并得到一種新的布斯譯碼和部分積結構。我們將布斯算法分解為“sig”，“sht”，“add”三個(gè)個(gè)因子，分別用來(lái)代表對被乘數的不同操作。其中“sig”用來(lái)決定被乘數是取反還是保持不變；“sht”代表是否對被乘數進(jìn)行左移一位；而“add”則表示決定最終得到部分積。改進(jìn)的算法用表達式表示則為：

從圖2可以看出，改進(jìn)的布斯譯碼器由1個(gè)異或門(mén)、2個(gè)與門(mén)和1個(gè)或門(mén)構成而部分積則是有3個(gè)二選一多路選擇器構成，其關(guān)鍵路徑為3個(gè)門(mén)的延遲。因此結構要比傳統的更為簡(jiǎn)單、延遲更小。

3 9-2壓縮樹(shù)

華萊士樹(shù)(Wallace Tree)算法通過(guò)并行相加來(lái)提高速度。在華萊士樹(shù)中所有部分積列在同一時(shí)間各自獨立的進(jìn)行相加。采用的是一種基于保留進(jìn)位全加器的9-2壓縮樹(shù)用來(lái)壓縮部分積陣列的，在每一個(gè)9-2壓縮樹(shù)的最頂層有9 b的部分積。9-2壓縮樹(shù)中用到了3個(gè)3-2壓縮和1個(gè)4-2壓縮。對于那些少于9 b的部分積列，為了進(jìn)一步減小芯片面積，根據部分積的數目采用相應的壓縮樹(shù)，并且可以用半加器用來(lái)代替3-2壓縮(全加器)。