基于新型部分積生成器和提前壓縮器的乘法器設(shè)計(jì)

蔡永祺，李振濤，萬江華,

（1.湘潭大學(xué)物理與光電工程學(xué)院，湖南湘潭411100；2.湖南轂梁微電子有限公司，長沙410000）

1 引言

2 Booth 編碼器

在通用微處理器中，乘法是通過時(shí)鐘控制一連串的“移位-加法”操作實(shí)現(xiàn)，將乘數(shù)的每一位分別與被乘數(shù)相乘得到部分積，再將所有部分積進(jìn)行壓縮求和[1]。對于需要做大量卷積運(yùn)算的數(shù)字信號(hào)處理器，多次“移位-加法”操作會(huì)造成芯片資源浪費(fèi)，所以需要設(shè)計(jì)專用乘法器提高乘法運(yùn)算性能[2]。專用乘法器需要在1 個(gè)時(shí)鐘周期內(nèi)對2 個(gè)bit 位的輸入作快速并行乘法，同時(shí)由輸入輸出寄存器鎖存數(shù)據(jù)，配合流水線操作[3]。

由Booth 夫婦提出的Booth 算法[4]是目前最流行的優(yōu)化乘法器的算法，其編碼思想開啟了乘法器部分積陣列產(chǎn)生模塊研究史的新紀(jì)元。華萊士提出的用多個(gè)保留進(jìn)位加法器組成的華萊士樹[5]也是目前流行的部分積壓縮求和結(jié)構(gòu)。文獻(xiàn)[6]中提出一種部分積符號(hào)位擴(kuò)展方法，能夠有效解決部分積壓縮求和時(shí)位數(shù)擴(kuò)展帶來的面積浪費(fèi)，減少了壓縮求和過程中大量的符號(hào)位運(yùn)算，但部分積的符號(hào)位仍有冗余。文獻(xiàn)[7]提出用2 個(gè)3-2 壓縮器組成1 個(gè)4-2 壓縮器來緩解傳統(tǒng)壓縮器處理位數(shù)不夠的問題，但在部分積壓縮求和時(shí)會(huì)造成資源浪費(fèi)。文獻(xiàn)[8]提出了一種Booth 選擇器，其輸入信號(hào)的產(chǎn)生過程復(fù)雜，正邏輯門數(shù)多，延時(shí)較大。

為了能讓Booth 編碼乘法器具有更快的速度和更小的面積，本文在上述已有的一些算法及結(jié)構(gòu)的基礎(chǔ)上，提出了一種新的Booth 編碼器及部分積生成器，并通過簡化邏輯，將部分積結(jié)果在進(jìn)入壓縮結(jié)構(gòu)前進(jìn)行處理，設(shè)計(jì)得到部分積提前壓縮結(jié)構(gòu)，最終搭建了一個(gè)16 bit 有符號(hào)數(shù)乘法器。

Booth 編碼是一種常用的優(yōu)化乘法器的方法，其基本原理是通過減少部分積的數(shù)量來簡化運(yùn)算，典型的Booth 編碼算法有基2 Booth 編碼、基4 Booth 編碼和基8 Booth 編碼算法?；? Booth 編碼算法編碼表簡單，算法容易實(shí)現(xiàn)，但不能簡化運(yùn)算；基8 Booth 編碼算法可以減少3/4 的部分積，但編碼中有乘-3 的操作，電路難以實(shí)現(xiàn)；基4 Booth 編碼算法[7]可以減少一半的部分積，并且電路容易實(shí)現(xiàn)。本文基于基4 Booth編碼算法設(shè)計(jì)Booth 編碼器，以優(yōu)化乘法器性能。

在乘法運(yùn)算中，乘數(shù)為B，被乘數(shù)為A，B 在處理器中以補(bǔ)碼的形式存在，基4 Booth 編碼算法是通過在乘數(shù)B 末尾添一位0 充當(dāng)B-1，n bit 數(shù)B 和A×B為

對-2B2i+1+B2i+B2i-1進(jìn)行基4 Booth 編碼，即可將A×B的部分積數(shù)量降低到B 位數(shù)的一半，節(jié)省邏輯單元的使用。由式(2)可知，-2B2i+1+B2i+B2i-1有0、1、2、-1、-2 這5 種可能的結(jié)果，A×B 的部分積有0、A、2A、-A、-2A這5 種結(jié)果。設(shè)計(jì)Booth 編碼器，對每組-2B2i+1+B2i+B2i-1進(jìn)行基4 Booth 編碼，編碼結(jié)果如表1 所示，編碼結(jié)果分別為S、Sbar、Sel1、Sel2、E0。S 為補(bǔ)償位[6]，在進(jìn)行乘負(fù)數(shù)運(yùn)算時(shí)，需要對被乘數(shù)進(jìn)行求補(bǔ)碼操作，S 用來實(shí)現(xiàn)求補(bǔ)碼的加1 操作以及控制被乘數(shù)是否需要取反；Sbar為S 的取反，Sel1、Sel2代表被乘數(shù)是進(jìn)行乘1 還是乘2 的操作，都為0 時(shí)被乘數(shù)進(jìn)行乘0 操作；E0在被乘數(shù)進(jìn)行乘0 操作時(shí)起作用，同時(shí)作用于符號(hào)位擴(kuò)展。

表1 基4 Booth 編碼結(jié)果

基4 Booth 編碼電路如圖1 所示，該電路實(shí)現(xiàn)了對乘數(shù)B 的編碼，電路輸入信號(hào)Ba、Bb、Bc為乘數(shù)的連續(xù)3 bit，輸出5 個(gè)編碼信號(hào)S、Sbar、Sel1、Sel2、E0。目前芯片設(shè)計(jì)多用CMOS 電路，CMOS 為反邏輯輸出，所以該電路全用反邏輯門來實(shí)現(xiàn)，以減少編碼電路延時(shí)。

圖1 基4 Booth 編碼電路

3 新型部分積生成器

文獻(xiàn)[8]提出的Booth 選擇器結(jié)構(gòu)如圖2 所示，該電路有8 個(gè)輸入，pp0[t]～pp3[t]為4 個(gè)部分積第t 位的可能值，需要對被乘數(shù)進(jìn)行額外的計(jì)算方可得到該值；Sel0～Sel3是對乘數(shù)進(jìn)行Booth 編碼的結(jié)果，分別為A、2A、-A、-2A、0 的選擇信號(hào)，用來選擇正確的部分積可能值。該電路的被乘數(shù)需進(jìn)行額外的計(jì)算，耗費(fèi)大量面積，且使用大量正邏輯單元，增加了路徑延時(shí)。

圖2 文獻(xiàn)[8]的Booth 選擇器

針對上述Booth 選擇器所帶來的問題，本文提供了一種新的部分積生成方案，一次性完成部分積可能值的生成和部分積的選擇。新型部分積生成器的電路如圖3 所示，它共有7 個(gè)輸入和2 個(gè)輸出，S、Sbar、Sel1、Sel2是由Booth 編碼電路產(chǎn)生的，Ai為被乘數(shù)的某一位，Aibar為Ai的反信號(hào)，M 為上一個(gè)部分積生成器所輸出的Mout。輸出Pi+1為部分積P 第i+1 位的結(jié)果，因?yàn)椴糠址e最低位P0為補(bǔ)償位，所以部分積生成器針對第i 位被乘數(shù)所生成的是第i+1 位部分積。Mout則將Ai生成的部分積可能值提供給下一個(gè)部分積生成器進(jìn)行選擇。

圖3 新型部分積生成器的電路

該部分積生成器由2 個(gè)與或非門組成，AOI1 中的與或邏輯利用S 和Sbar來選擇Ai或Aibar，實(shí)現(xiàn)乘數(shù)為負(fù)數(shù)時(shí)的取反操作，然后利用非邏輯取反，產(chǎn)生部分積可能值Mout，提供給AOI2 進(jìn)行選擇的同時(shí)還輸出給下一個(gè)部分積生成器；AOI2 實(shí)現(xiàn)基4 Booth 編碼算法的乘2 操作，該門的與或邏輯通過Sel1和Sel2對2 個(gè)部分積可能值進(jìn)行選擇，Sel1為高電平時(shí)選擇AOI1 產(chǎn)生的部分積可能值，Sel2為高電平時(shí)選擇上一個(gè)部分積生成器輸出的Mout，最后非邏輯進(jìn)行取反，輸出部分積Pi+1。

其中X 和Y 為

被乘數(shù)進(jìn)行取反操作后輸入到該電路結(jié)構(gòu)。該結(jié)構(gòu)使用2 個(gè)與或非門實(shí)現(xiàn)對部分積可能值的生成以及選擇，利用CMOS 反邏輯通過2 次取反得到正確的值；相較于文獻(xiàn)[8]中的Booth 選擇器，該結(jié)構(gòu)使用更少的邏輯單元實(shí)現(xiàn)更多的功能，優(yōu)化了電路的延時(shí)和面積。

4 部分積提前壓縮器

部分積低4 位P[3:0]如圖4 所示，P0為補(bǔ)償位S，需要與P1進(jìn)行壓縮求和。最常用的壓縮結(jié)構(gòu)是華萊士樹[6]結(jié)構(gòu)，壓縮單元使用半加器、3-2 壓縮器以及由2個(gè)3-2 壓縮器所構(gòu)成的4-2 壓縮器。由圖4 可知，后續(xù)壓縮過程需用半加器壓縮P1與P0，產(chǎn)生保留位S0與進(jìn)位C1，后續(xù)將C1與P2進(jìn)行壓縮。

圖4 部分積低4 位

S0和C1的表達(dá)式為

本文對式(6)(7)進(jìn)行簡化，設(shè)計(jì)了一種低位提前壓縮器，在部分積生成時(shí)就將P1和P0進(jìn)行壓縮，通過低位提前壓縮器生成的新P[1:0]為

為了消除被乘數(shù)進(jìn)行乘0 操作時(shí)部分積生成器所產(chǎn)生的錯(cuò)誤的1，式(9)中對E0進(jìn)行了或操作，可以在后續(xù)壓縮進(jìn)位中依次消除部分積生成器產(chǎn)生的1。部分積的低位部分在生成時(shí)已經(jīng)被壓縮，生成和壓縮同時(shí)進(jìn)行，減少了邏輯門的使用，從而使乘法器面積和運(yùn)算延時(shí)減小。低位提前壓縮器電路如圖5 所示，圖中3 個(gè)邏輯門就能實(shí)現(xiàn)部分積低位的生成、壓縮。部分積低位示例如圖6 所示，圖中C1即P0，在后續(xù)過程中將與P2進(jìn)行壓縮、求和。

圖5 低位提前壓縮器電路

圖6 本設(shè)計(jì)部分積低位示例

在所有部分積生成后進(jìn)行壓縮求和操作，每個(gè)部分積的位數(shù)對應(yīng)的壓縮權(quán)重不同，需要將所有部分積擴(kuò)展至相同位數(shù)，文獻(xiàn)[6]中的高位符號(hào)位擴(kuò)展方法可以有效減少擴(kuò)展操作以及壓縮單元的使用。E 信號(hào)在部分積為正數(shù)時(shí)為高電平，擴(kuò)展后的第1 個(gè)部分積的高3 位符號(hào)位P[19:17]即{E,E,E}，其他部分積的高2 位為{1,E}。第1 個(gè)部分積高3 位有很強(qiáng)的關(guān)聯(lián)性，所以本文又提出了一種高位提前壓縮器，利用其關(guān)聯(lián)性，簡化壓縮步驟。

本文所設(shè)計(jì)的16 bit 有符號(hào)數(shù)乘法器經(jīng)過Booth編碼后共產(chǎn)生8 個(gè)部分積。將通過低位提前壓縮器產(chǎn)生的第8 個(gè)部分積的C1與第8 個(gè)部分積的P2用半加器進(jìn)行壓縮，產(chǎn)生的進(jìn)位為C2，正好與第1 個(gè)部分積的P17權(quán)重相同，可以在進(jìn)入壓縮樹之前先將它們合并，由于第1 個(gè)部分積P[19:17]值只有{1,0,0}和{0,1,1}2 種，經(jīng)過合并后不會(huì)產(chǎn)生進(jìn)位，只會(huì)產(chǎn)生3 個(gè)保留位。高位提前壓縮器將第1 個(gè)部分積低位所產(chǎn)生的C2與第8 個(gè)部分積的高3 位提前進(jìn)行合并生成Pnew[19:17]，其邏輯表達(dá)式為

經(jīng)過化簡后只需要3 個(gè)邏輯門即可將4 個(gè)值進(jìn)行合并，在提高效率的同時(shí)減少了壓縮單元的使用，高位提前壓縮器的電路結(jié)構(gòu)如圖7 所示。

圖7 高位提前壓縮器的電路結(jié)構(gòu)

5 乘法器結(jié)構(gòu)

將基4 Booth 編碼器、新型部分積生成器、部分積提前壓縮器運(yùn)用至16 bit 有符號(hào)數(shù)乘法器，該乘法器經(jīng)過基4 Booth 編碼共生成8 個(gè)部分積，單個(gè)部分積生成流程如圖8 所示。圖中的Ba、Bb、Bc進(jìn)入Booth 編碼單元進(jìn)行編碼，A 的最低位A0與編碼結(jié)果通過低位部分積提前壓縮單元生成部分積P 的低2 位P[1:0]，被乘數(shù)高15 位A[15:1]與編碼結(jié)果通過新型部分積生成單元生成部分積P[16:2]，并產(chǎn)生進(jìn)位信號(hào)，進(jìn)位信號(hào)與編碼結(jié)果通過高位符號(hào)位擴(kuò)展單元完成對部分積的符號(hào)位擴(kuò)展，從而生成整個(gè)部分積結(jié)果。

圖8 單個(gè)部分積生成流程

8 個(gè)部分積PP1～PP8 全部生成后，使用華萊士壓縮樹結(jié)構(gòu)對其進(jìn)行壓縮求和，乘法器壓縮求和流程如圖9 所示。將8 個(gè)部分積分為2 組，PP1～PP4 為第1組，PP5～PP8 為第2 組，使用4-2 壓縮器進(jìn)行壓縮[7]，PP1 的高位符號(hào)位和PP8 的C2進(jìn)位通過部分積高位提前壓縮單元壓縮后再參與到第1 組4-2 壓縮器。2組4-2 壓縮器出來的結(jié)果進(jìn)入到第2 級4-2 壓縮器，最后用加法器進(jìn)行求和，加法器的輸出即為乘法最終結(jié)果。

圖9 乘法器壓縮求和流程

6 驗(yàn)證與綜合

本文使用電路設(shè)計(jì)工具進(jìn)行16 bit 有符號(hào)數(shù)乘法器的電路搭建，導(dǎo)出CDL 網(wǎng)表，通過腳本語言將CDL網(wǎng)表轉(zhuǎn)換成門電路級別的Verilog 代碼。用Verilog 描寫測試文件，輸入隨機(jī)的16 bit 有符號(hào)數(shù)x、w 作為乘數(shù)和被乘數(shù)，輸出定義為y_latch。然后給定一個(gè)乘法結(jié)果原型y_real=x×w，y_latch 和y_real 結(jié)果相同時(shí)賦予check 為高電平，其他情況為低電平。使用Verilog仿真工具進(jìn)行仿真，波形如圖10 所示，圖中的check 信號(hào)為高電平，說明計(jì)算出來的結(jié)果與原型相同，證明本文設(shè)計(jì)的16 bit 有符號(hào)數(shù)乘法器計(jì)算功能正確。

圖10 乘法器仿真波形

使用邏輯綜合工具在28 nm 工藝下對其進(jìn)行綜合，本文中Verilog 代碼是使用門電路搭建的，所以使用邏輯綜合工具對設(shè)計(jì)進(jìn)行唯一化處理，確保了乘法器數(shù)據(jù)的真實(shí)性。由綜合報(bào)告可知，乘法器的關(guān)鍵路徑延時(shí)為0.77 ns，時(shí)鐘頻率可達(dá)到1.3 GHz，總邏輯單元數(shù)為894 個(gè)，總面積為937.3 μm2，功耗為935.71 μW。本設(shè)計(jì)與文獻(xiàn)[8]提出的Booth 選擇器的參數(shù)對比如表2 所示，本設(shè)計(jì)與相似類型乘法器參數(shù)對比如表3所示。從對比結(jié)果可知，本設(shè)計(jì)在延時(shí)、總面積方面都有較大的優(yōu)勢。

表2 本設(shè)計(jì)與文獻(xiàn)[8]提出的Booth 選擇器的參數(shù)對比

表3 本設(shè)計(jì)與相似類型乘法器參數(shù)對比

7 結(jié)論

本文設(shè)計(jì)了一種新型16 bit 有符號(hào)數(shù)乘法器，使用基4 Booth 編碼，減少了一半的部分積；設(shè)計(jì)的新型部分積生成器結(jié)構(gòu)簡單，在節(jié)省邏輯單元的同時(shí)擁有更低的延時(shí)；設(shè)計(jì)了新型低位部分積提前壓縮器，將8個(gè)部分積的低2 位在生成時(shí)就進(jìn)行壓縮；設(shè)計(jì)了高位部分積提前壓縮器，將第8 個(gè)部分積的高位符號(hào)位先進(jìn)行合并處理，再進(jìn)入壓縮結(jié)構(gòu)，低位與高位的提前壓縮器設(shè)計(jì)優(yōu)化了壓縮邏輯，減少了壓縮單元的使用。與文獻(xiàn)[8]相比，本文設(shè)計(jì)的乘法器關(guān)鍵路徑延時(shí)降低了21.4%，總面積減少了49.6%，計(jì)算性能大大提高，該乘法器的實(shí)現(xiàn)思路可以很好地適用于現(xiàn)代乘法器。