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

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

1 引言

2 Booth 編碼器

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

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

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

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

在乘法運算中，乘數(shù)為B，被乘數(shù)為A，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è)計Booth 編碼器，對每組-2B2i+1+B2i+B2i-1進(jìn)行基4 Booth 編碼，編碼結(jié)果如表1 所示，編碼結(jié)果分別為S、Sbar、Sel1、Sel2、E0。S 為補償位[6]，在進(jìn)行乘負(fù)數(shù)運算時，需要對被乘數(shù)進(jìn)行求補碼操作，S 用來實現(xiàn)求補碼的加1 操作以及控制被乘數(shù)是否需要取反；Sbar為S 的取反，Sel1、Sel2代表被乘數(shù)是進(jìn)行乘1 還是乘2 的操作，都為0 時被乘數(shù)進(jìn)行乘0 操作；E0在被乘數(shù)進(jìn)行乘0 操作時起作用，同時作用于符號位擴展。

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

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

圖1 基4 Booth 編碼電路

3 新型部分積生成器

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

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

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

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

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

其中X 和Y 為

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

4 部分積提前壓縮器

部分積低4 位P[3:0]如圖4 所示，P0為補償位S，需要與P1進(jìn)行壓縮求和。最常用的壓縮結(jié)構(gòu)是華萊士樹[6]結(jié)構(gòu)，壓縮單元使用半加器、3-2 壓縮器以及由2個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è)計了一種低位提前壓縮器，在部分積生成時就將P1和P0進(jìn)行壓縮，通過低位提前壓縮器生成的新P[1:0]為

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

圖5 低位提前壓縮器電路

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

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

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

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

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

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

將基4 Booth 編碼器、新型部分積生成器、部分積提前壓縮器運用至16 bit 有符號數(shù)乘法器，該乘法器經(jīng)過基4 Booth 編碼共生成8 個部分積，單個部分積生成流程如圖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)位信號，進(jìn)位信號與編碼結(jié)果通過高位符號位擴展單元完成對部分積的符號位擴展，從而生成整個部分積結(jié)果。

圖8 單個部分積生成流程

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

圖9 乘法器壓縮求和流程

6 驗證與綜合

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

圖10 乘法器仿真波形

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

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

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

7 結(jié)論

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