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

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

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

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

1 整體結(jié)構(gòu)

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

2 布斯譯碼和部分積

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

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

3 9-2壓縮樹

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

[!--empirenews.page--]

典型的4-2壓縮是由2個(gè)3-2壓縮構(gòu)成的，其延遲為4個(gè)異或。圖3為一個(gè)優(yōu)化了的4-2壓縮，其延遲為3個(gè)異或的延遲。因此9-2壓縮樹從頂層到最終輸出僅過了7個(gè)異或門的延遲。

4 35 b兩級(jí)超前進(jìn)位加法器

超前進(jìn)位加法器對(duì)乘法器的整體性能的影響至關(guān)重要，要想提高乘法器的速度，超前進(jìn)位加法器也必須進(jìn)行必要的優(yōu)化。在此采取基于4 b超前進(jìn)位加法器的兩級(jí)加法器。

由于進(jìn)位鏈延遲時(shí)間隨著輸入的增加而增加，必須考慮到輸入信號(hào)的個(gè)數(shù)，在面積和速度中進(jìn)行折中發(fā)現(xiàn)4 b超前進(jìn)位加法器是最適合作為基本的模塊。

從圖4(b)中可以看到在4 b超前進(jìn)位加法器中，除了P和G由與門實(shí)現(xiàn)的，其他的都是有與非門實(shí)現(xiàn)的。

圖4(a)為1位全加器的變形，有3個(gè)輸入Ai，Bi，Ci和三個(gè)輸出Pi，Si和Gi，其中Ai和Bi為兩個(gè)加數(shù)，Cin為進(jìn)位輸入，Pi和Gi分別為進(jìn)位傳輸和進(jìn)位產(chǎn)生，而Si為第i位的和。

采用基于4 b的超前進(jìn)位加法器來(lái)組成16 b超前進(jìn)位加法器，進(jìn)位鏈采取與4 b超前進(jìn)位鏈相同的結(jié)構(gòu)。同樣的分析方法，發(fā)現(xiàn)16 b的P和G延時(shí)為5個(gè)門的延遲。用2個(gè)16 b的超前進(jìn)位加法器和一個(gè)3 b超前進(jìn)位加法器組成35 b超前進(jìn)位加法器，其進(jìn)位鏈采取與上面相同的方法。研究不難發(fā)現(xiàn)，經(jīng)過7個(gè)門延遲進(jìn)位到達(dá)3 b超前進(jìn)位加法器，再經(jīng)過3個(gè)門的延遲得到第35位的結(jié)果。也就是說整個(gè)加法器僅僅經(jīng)過10個(gè)門的延遲。

[!--empirenews.page--]

5 設(shè)計(jì)總結(jié)

5．1 綜合條件說明

采用TSMC0．18μm CMOS工藝和Synopsis DC進(jìn)行的綜合并進(jìn)行延遲分析。并在DC命令窗口輸入了命令“set_dont_use”和“set_dont_ touch”。

5．2 布斯譯碼和部分積

把傳統(tǒng)的布斯譯碼和部分積與本文采取的布斯譯碼和部分積進(jìn)行了比較，并把結(jié)果列在了表2中。從表中發(fā)現(xiàn)本設(shè)計(jì)關(guān)鍵路徑與OhkuBo相比減少了50％，生成部分積的速度相應(yīng)的提高了50％。

5．3 與其他的乘法器進(jìn)行比較

本文的乘法器與表3中乘法器相比速度有明顯提高，與Xilinx公司的Spartan-3A系列嵌入到FPGA的乘法器相比本文乘法器的速度更提高40％。更為關(guān)鍵的是在沒有增加芯片面積的情況下把速度提高40％。

6 結(jié)語(yǔ)

本文基于改進(jìn)的布斯算法的18×18乘法器是特意為嵌入到FPGA而設(shè)計(jì)的，它解決了乘法器占用FPGA較多資源的問題，并為以后DSP嵌入到FPGA做了必要的準(zhǔn)備工作。采用了一種新的布斯譯碼和部分積、9-2壓縮和兩級(jí)超前進(jìn)位加法器以使乘法器達(dá)到較好的性能。經(jīng)過仿真驗(yàn)證，這里提出的基于改進(jìn)的布斯乘法器各項(xiàng)指標(biāo)均能很好的滿足嵌入到FPGA的要求。