摘要：設(shè)計(jì)了一種用于16位定點(diǎn)DSP中的片內(nèi)乘法器。該乘法器采用了改進(jìn)型Booth算法，
使用CSA構(gòu)成的乘法器陣列，并采用跳躍進(jìn)位加法器實(shí)現(xiàn)進(jìn)位傳遞，該設(shè)計(jì)具有可擴(kuò)展性，并提出了更高位擴(kuò)展時(shí)應(yīng)改進(jìn)型方向。設(shè)計(jì)時(shí)綜合考慮了高性能定點(diǎn)DSP對(duì)乘法器在面積和速度上的要求，具有極其規(guī)整的布局布線。
　　關(guān)鍵詞： 改進(jìn)型Booth編碼；部分積產(chǎn)生器；陣列乘法器

1 引言
　　大多數(shù)先進(jìn)的數(shù)字系統(tǒng)為實(shí)現(xiàn)高速算術(shù)運(yùn)算都包含有硬件乘法器，例如許多高速單片機(jī)微控制器中的算邏運(yùn)算都使用了硬件并行乘法器。目前廣泛應(yīng)用的DSP芯片內(nèi)核中，通常都有可單周期完成的片內(nèi)硬件乘法器，以實(shí)現(xiàn)某些復(fù)雜算法如濾波以及實(shí)時(shí)處理等。通常乘法器處于關(guān)鍵延時(shí)路徑上，因此乘法器的速度對(duì)整個(gè)芯片以及系統(tǒng)性能有重要影響。按結(jié)構(gòu)可分為串行乘法器和并行乘法器，串行乘法器面積和功耗，但是運(yùn)算速度也慢，因此高速數(shù)字應(yīng)用系統(tǒng)通常會(huì)采用并行乘法器。并行乘法器有三個(gè)主要部分[1]：部分積產(chǎn)生器、加法陣列塊和進(jìn)位加法器。部分積產(chǎn)生器的功能是根據(jù)輸入的操作數(shù)產(chǎn)生部分積；加法陣列塊完成對(duì)部分積的歸約，是將所有的部分積相加產(chǎn)生2n位的結(jié)果；進(jìn)位加法器是為了生成終結(jié)果。
　　本文將討論一種用于16位定點(diǎn)DSP芯片的并行乘法器的設(shè)計(jì)?？偟膩碚f，對(duì)快速乘法器性能的改進(jìn)，設(shè)計(jì)時(shí)不外從三個(gè)方面來考慮：減少部分積的數(shù)目，比如采用改進(jìn)的Booth算法；對(duì)部分積歸約，比如采用Wallace樹形結(jié)構(gòu)；減少進(jìn)位傳遞時(shí)間。文中從芯片制造的角度綜合衡量芯片成本、可靠性及性能后，對(duì)于部分積產(chǎn)生器采用改進(jìn)型BoothII算法設(shè)計(jì)；加法陣列塊直接用CSA陣列乘法將部分積相加生成進(jìn)位項(xiàng)和偽和項(xiàng)；采用跳躍進(jìn)位加法器將進(jìn)位與偽和相加，產(chǎn)生終結(jié)果。版圖實(shí)現(xiàn)采用靜態(tài)CMOS 工藝，加法單元主要采用CMOS傳輸門實(shí)現(xiàn)。
2 計(jì)算公式
　　Booth算法適用于補(bǔ)碼表示的乘法運(yùn)算。16×16位整數(shù)AS 、BS乘積PS的計(jì)算公式[2]如下
(基2的表示)
, （b-1=0）， (基4的表示) (1)
式中，A表示被乘數(shù)；B表示乘數(shù)；P表示乘積；下標(biāo)S代表補(bǔ)碼整數(shù)；下標(biāo)O代表無符號(hào)數(shù)。
　　部分積 ， n = 0,1,…7。
對(duì)于16位無符號(hào)數(shù)AO、BO的乘積，PO的計(jì)算公式為
(基2的表示)
, （b16=b17=0） (基4的表示) (2)
部分積 ， n = 0,1,…,8 ，其中b16= b17= 0，b-1= 0。
　　顯然，采用基4算法比采用基2算法的部分積項(xiàng)簡化了近一半；對(duì)于16位有符號(hào)整數(shù)的乘法，有8個(gè)部分積項(xiàng)，而16位無符號(hào)數(shù)的乘法，則有9個(gè)部分積項(xiàng)。將式(1)和式(2)統(tǒng)一起來，可以認(rèn)為16位乘法有9個(gè)部分積，一個(gè)部分積PP8的取值為
PP8 = 0 整數(shù)乘法
A×b15×216 無符號(hào)數(shù)乘法
　　對(duì)于基更高的Booth編碼，例如基8也是可以實(shí)現(xiàn)的，不過需要額外的加法器進(jìn)行被乘數(shù)的3倍和5倍的計(jì)算，控制電路更復(fù)雜，簡化部分積項(xiàng)的優(yōu)點(diǎn)反而不明顯。本設(shè)計(jì)中不采用。
3 邏輯設(shè)計(jì)及其設(shè)計(jì)實(shí)現(xiàn)
　　圖1描述了該16位并行乘法器的整體結(jié)構(gòu)有三個(gè)主要部分：部分積產(chǎn)生器、加法陣列塊和進(jìn)位加法器。下面詳細(xì)討論各部分的邏輯設(shè)計(jì)及實(shí)現(xiàn)。

圖1 并行乘法器的體系結(jié)構(gòu)

3．1 改進(jìn)型基4 Booth編碼器
　　Booth編碼邏輯設(shè)計(jì)的實(shí)質(zhì)，就是將部分積表達(dá)式中的系數(shù)值，編碼后用邏輯表達(dá)式來描述，然后進(jìn)行邏輯實(shí)現(xiàn)。根據(jù)基4表示的乘法計(jì)算公式可以看出，基4 的Booth編碼的優(yōu)點(diǎn)就是只有5種系數(shù)的部分積項(xiàng)，即0，1，2，-1，-2，也就意味著編碼邏輯只需要3位，即1個(gè)符號(hào)位和2個(gè)數(shù)值編碼位。本設(shè)計(jì)中采用改進(jìn)型Booth編碼如表1所示。根據(jù)編碼表可以得出編碼信號(hào)的邏輯表達(dá)式如下
NEG2n=b2n+1；B12n =b2n ^ b2n-1；

為產(chǎn)生所有部分積的系數(shù)，設(shè)計(jì)中采用9個(gè)Booth編碼器，即Booth0，Booth1，…，Booth8。編碼信號(hào)產(chǎn)生邏輯如圖2所示，以b2n+1 、 b2n 、b2n-1為輸入，3個(gè)編碼信號(hào)為輸出。對(duì)PP0來說，因?yàn)閎-1=0，所以輸入信號(hào)變?yōu)?個(gè)，因此Booth0編碼結(jié)構(gòu)可以簡化。Boothi（i= 1，2，…，7）編碼原理相同，考慮負(fù)載能力的不同，實(shí)現(xiàn)時(shí)用了不同結(jié)構(gòu)。因?yàn)椴糠址ePP8的作用是為了考慮有符號(hào)數(shù)和無符號(hào)數(shù)的乘法，Booth8的編碼實(shí)現(xiàn)邏輯采用B116=b15 & SXM，B216=0，NEG=0；SXM=0時(shí)完成符號(hào)數(shù)乘法運(yùn)算，SXM=1時(shí)為無符號(hào)數(shù)乘法運(yùn)算。Booth編碼的輸出全為互補(bǔ)的信號(hào)，這是產(chǎn)生部分積邏輯的需要。

(a) Booth0 的邏輯結(jié)構(gòu)

(b) Booth1和Booth i (i=2,…,7)的兩種邏輯結(jié)構(gòu)
圖2 Booth編碼邏輯實(shí)現(xiàn)
3．2 部分積產(chǎn)生器
　　首先考慮各編碼數(shù)字對(duì)應(yīng)的產(chǎn)生部分積的操作：0，作為部分積；+1，被乘數(shù)作為部分積；+2，被乘數(shù)左移一位作為部分積；-1，被乘數(shù)的補(bǔ)碼作為部分積； -2，被乘數(shù)左移一位后的補(bǔ)碼作為部分積。9個(gè)Booth編碼器可以產(chǎn)生PPn（n = 0,1,…,8）等9個(gè)部分積，關(guān)于部分積的產(chǎn)生有不同的邏輯，本設(shè)計(jì)采用
邏輯實(shí)現(xiàn)如圖3所示，PPi ( i = 0,1 )和PPi（i=2,…8）采用了不同結(jié)構(gòu)。所產(chǎn)生的部分積是有
符號(hào)數(shù)，在部分積進(jìn)入陣列乘法器進(jìn)行歸約加法之前，需要進(jìn)行符號(hào)擴(kuò)展，使上面邏輯式中的輸入

(a) PPi 的邏輯結(jié)構(gòu) （i=0,1） (b)PPi的邏輯結(jié)構(gòu)( i≠ 0或1)
圖3部分積產(chǎn)生邏輯實(shí)現(xiàn)
　　信號(hào)為被乘數(shù)符號(hào)擴(kuò)展位，就能很容易地實(shí)現(xiàn)符號(hào)擴(kuò)展，大大減少了符號(hào)擴(kuò)展的耗費(fèi)。而對(duì)有符號(hào)數(shù)來說，在NEG2n=1時(shí)，還要與NEG2n相加，才能完成對(duì)結(jié)果的求補(bǔ)操作，這一操作在乘法陣列中實(shí)現(xiàn)。
3．3 陣列乘法器
　　當(dāng)部分積PPn產(chǎn)生之后，將它們相加就得到乘法操作的結(jié)果[3]。布線版圖規(guī)則的相加就是簡單的陣列乘法器的結(jié)構(gòu)，即P=（…(（（PP0+PP1）+ PP2）+ PP3) +…）+PP8 ，n個(gè)部分積需要n-1行全加器。采用3．2節(jié)的保留進(jìn)位加法器CSA，即進(jìn)位信號(hào)不傳遞給本次加法的高位，而在下次加法時(shí)傳遞到高位的輸入端，可避免本級(jí)加法器內(nèi)的進(jìn)位延時(shí)。而只有到高16位字結(jié)果計(jì)算時(shí)，才將前面乘法陣列產(chǎn)生的偽和與進(jìn)位信號(hào)相加，得到真正結(jié)果。乘法陣列采用Booth算法，原理框圖如圖4。每次加法可以得出低2位結(jié)果，即部分積的相加與低16位結(jié)果的產(chǎn)生是并行的，高位結(jié)果由一個(gè)16位的快速進(jìn)位傳遞加法器CPA完成。

圖4 16位陣列乘法器原理框圖

　　本設(shè)計(jì)的乘法運(yùn)算是針對(duì)無符號(hào)數(shù)和有符號(hào)整數(shù)兩類操作數(shù)。設(shè)計(jì)實(shí)現(xiàn)中，為了防止在相乘時(shí)被乘數(shù)左移可能產(chǎn)生的溢出，在整數(shù)運(yùn)算時(shí)對(duì)其高位補(bǔ)兩個(gè)符號(hào)位，無符號(hào)數(shù)運(yùn)算時(shí)高位補(bǔ)兩個(gè)0，形成了18位的補(bǔ)碼表示的數(shù)據(jù)（a17a16a15,…, a0），設(shè)計(jì)實(shí)現(xiàn)邏輯采用a17 = a16 = & a15。
　　根據(jù)基4的Booth算法，共有9個(gè)部分積，每個(gè)為18位，所以可用8個(gè)18位全加器來完成乘法運(yùn)算。圖5顯示了用CSA實(shí)現(xiàn)的乘法陣列。從圖中可以看出，延遲主要由部分積(PP0, PP1)產(chǎn)生電路、FA以及FA0單元、進(jìn)位傳遞加法器的延遲構(gòu)成，若要求更高的運(yùn)算速度，要從減少這些電路的延遲來考慮。前面已經(jīng)提到的同樣功能電路實(shí)現(xiàn)結(jié)構(gòu)不同，也是基于延時(shí)及功耗考慮的結(jié)果。
3．4 進(jìn)位傳遞加法器
　　快速進(jìn)位傳遞加法器（CPA）是為了實(shí)現(xiàn)偽和與進(jìn)位相加以得到終結(jié)果，除了優(yōu)化設(shè)計(jì)其中全加器單元的電路結(jié)構(gòu)，為進(jìn)一步減少進(jìn)位延遲，采用分段進(jìn)位鏈的結(jié)構(gòu)，對(duì)16位的CPA采用等

　　長分段的跳躍進(jìn)位加法器來實(shí)現(xiàn)，分為4段，每段4位，段內(nèi)以行波進(jìn)位實(shí)現(xiàn)，如圖6(a)。假設(shè)分段數(shù)為n，每段中k位，則第i段中位的進(jìn)位邏輯表達(dá)式為 ，具體實(shí)現(xiàn)如圖6（b）。

圖6 跳躍進(jìn)位鏈的邏輯實(shí)現(xiàn)
4 結(jié)論
　　本文設(shè)計(jì)的16位定點(diǎn)乘法器，版圖采用上華的0.6μm CMOS工藝實(shí)現(xiàn)，主要模塊采用靜態(tài)CMOS完成，加法單元主要采用CMOS傳輸門實(shí)現(xiàn)。作為性能為20MIPS的數(shù)字電機(jī)控制DSP芯片產(chǎn)品的片內(nèi)集成乘法器，可實(shí)現(xiàn)單周期乘法運(yùn)算。該設(shè)計(jì)實(shí)現(xiàn)結(jié)構(gòu)簡單，設(shè)計(jì)時(shí)綜合考慮了速度、面積和功耗指標(biāo)，易于擴(kuò)展。為擴(kuò)展到更高位數(shù)的乘法器并保證其運(yùn)算性能，設(shè)計(jì)實(shí)現(xiàn)時(shí)可考慮對(duì)處于關(guān)鍵路徑上的單元進(jìn)行改進(jìn)，如對(duì)全加器單元進(jìn)行優(yōu)化設(shè)計(jì)；采用Wallace樹形乘法陣列對(duì)部分積歸約；減少高位字的進(jìn)位傳遞時(shí)間，如 CPA實(shí)現(xiàn)時(shí)選取優(yōu)化分組的跳躍進(jìn)位加法器或者改用先行進(jìn)位加法器等。

  

參考文獻(xiàn):

[1]. b15 datasheet http://www.hbjingang.com/datasheet/b15_1826251.html.
[2]. a15 datasheet http://www.hbjingang.com/datasheet/a15_1244519.html.