基于改進(jìn)的布斯算法FPGA嵌入式18×18乘法器
摘要:設(shè)計(jì)了一款嵌入FPGA的乘法器,該乘法器能夠滿足兩個(gè)18 b有符號(hào)或17 b無符號(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。
本文引用地址:http://www.ex-cimer.com/article/190351.htm關(guān)鍵詞:布斯算法;部分積;9-2壓縮;兩級(jí)超前進(jìn)位加法器
目前,FPGA作為可編程邏輯器件(PLD)的主要產(chǎn)品,在通信、消贊電子、汽車電子、工業(yè)控制、國防安全等領(lǐng)域得到廣泛的應(yīng)用。由于在性能和靈活性方面的完美組合,FPGA的使用范圍越來越廣,客觀上要求加強(qiáng)FPGA數(shù)字處理功能(如嵌入乘法器,數(shù)字信號(hào)處理器(DSP)等)?,F(xiàn)住幾乎每一款商用FPGA內(nèi)部幾乎都嵌入了乘法器或數(shù)字信號(hào)處理器,如Xilinx公司的VirtexⅡ系列、Spartan-3/3A系列等。相對(duì)來說我國的FPGA僅僅處于起步階段,F(xiàn)PGA的發(fā)展特別是高性能FPGA的發(fā)展刻不容緩。本文緊跟國家重大項(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)位加法器生成無符號(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è)因子,分別用來代表對(duì)被乘數(shù)的不同操作。其中“sig”用來決定被乘數(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)的更為簡單、延遲更小。
3 9-2壓縮樹
華萊士樹(Wallace Tree)算法通過并行相加來提高速度。在華萊士樹中所有部分積列在同一時(shí)間各自獨(dú)立的進(jìn)行相加。采用的是一種基于保留進(jìn)位全加器的9-2壓縮樹用來壓縮部分積陣列的,在每一個(gè)9-2壓縮樹的最頂層有9 b的部分積。9-2壓縮樹中用到了3個(gè)3-2壓縮和1個(gè)4-2壓縮。對(duì)于那些少于9 b的部分積列,為了進(jìn)一步減小芯片面積,根據(jù)部分積的數(shù)目采用相應(yīng)的壓縮樹,并且可以用半加器用來代替3-2壓縮(全加器)。
linux操作系統(tǒng)文章專題:linux操作系統(tǒng)詳解(linux不再難懂)
評(píng)論