乘法是數(shù)字信號(hào)處理中的基本運(yùn)算。在圖像、語音、加密等數(shù)字信號(hào)處理領(lǐng)域中，乘法器扮演著重要的角色，并在很大程度上左右著系統(tǒng)的性能。如何以最少的資源實(shí)現(xiàn)乘法器的最高速度將成為乘法器的主要研究方向。由于樹型結(jié)構(gòu)模塊是陣列乘法器設(shè)計(jì)中的瓶頸，本文在深入研究了乘法器的體系結(jié)構(gòu)，并比較了各種樹型結(jié)構(gòu)的基礎(chǔ)之上，提出了一種適合于16×16有/無符號(hào)數(shù)乘法器的混合壓縮比結(jié)構(gòu)。并且基于該結(jié)構(gòu)同時(shí)采用改進(jìn)布斯算法、符號(hào)擴(kuò)展技術(shù)設(shè)計(jì)出了一個(gè)16×16有/無符號(hào)數(shù)乘法器，其架構(gòu)如圖1所示。

1 改進(jìn)布斯算法與布斯編碼設(shè)計(jì)
　　在高速乘法器的設(shè)計(jì)中廣泛應(yīng)用的是改進(jìn)布斯算法(Modified Booth Algorithm, MBA)，也稱為基4(Radix-4)布斯算法。該算法通過對(duì)乘數(shù)重新編碼和壓縮部分乘積項(xiàng)" title="乘積項(xiàng)">乘積項(xiàng)(PP)的數(shù)目來提高運(yùn)算速度。而壓縮率則取決于編碼方法，如果采用三位MBA編碼，則可以壓縮一半的PP^[1]，大大提高了運(yùn)算速度。
　　MBA編碼原理如下：對(duì)于有符號(hào)數(shù)乘法運(yùn)算A×B，若乘數(shù)B的長度為奇數(shù)，則需要高位擴(kuò)展一位符號(hào)位使乘數(shù)的位數(shù)是偶數(shù)；若乘數(shù)B的長度為偶數(shù)則不用高位擴(kuò)展。設(shè)擴(kuò)展后乘數(shù)B的長度為N位，這時(shí)N是偶數(shù)，乘數(shù)B可寫為：

　　這樣，N位的乘數(shù)B將會(huì)產(chǎn)生N/2個(gè)部分乘積項(xiàng)。
　　改進(jìn)布斯編碼規(guī)則是：首先對(duì)乘數(shù)的最低位額外增加一位(B_[-1]=0)，然后每次取乘數(shù)的偶數(shù)位(B[0]，B^[2]，B^[4]，… )以及相鄰的奇數(shù)位(共三位)進(jìn)行編碼。這樣E＜i＞的取值為0，±1,±2，然后再與被乘數(shù)A相乘，得到對(duì)應(yīng)的部分乘積項(xiàng)是(0，＋A，－A，＋2A，－2A)，這五種操作需要3位的布斯?fàn)顟B(tài)碼進(jìn)行識(shí)別。
　　在本設(shè)計(jì)中，布斯?fàn)顟B(tài)碼所采用的邏輯關(guān)系如下：
　　PN=BH
　　ONE=(~BR)&BL∣ BR&(~BL)=BR⊕BL????????????????????????????? (3)
　　TWO=(~BH)&BR&BL∣ BH&(~BR)&(~BL)
　　= (~BH)&(BR&BL)∣BH&(~(BR∣BL))
　　式中，BH表示相鄰高位，BR表示本位，BL表示相鄰低位。PN為0時(shí)為加操作，為1時(shí)為減操作；ONE為0時(shí)操作數(shù)為0，為1時(shí)操作數(shù)為A；TWO為0時(shí)操作數(shù)為0，為1時(shí)操作數(shù)為2A。
　　如圖1所示，本乘法器的輸入量為1位符號(hào)標(biāo)志位sign，用于標(biāo)識(shí)有/無符號(hào)數(shù)以及16位被乘數(shù)A與乘數(shù)B。首先根據(jù)符號(hào)標(biāo)志位sign將被乘數(shù)A與乘數(shù)B都轉(zhuǎn)換為17位的有符號(hào)數(shù)。由于布斯編碼需要乘數(shù)寬度N為偶數(shù)，故對(duì)乘數(shù)B再進(jìn)行1位高位擴(kuò)展，因此該乘法器實(shí)際操作數(shù)變成了17位×18位。由式(1)可知，對(duì)18位的乘數(shù)進(jìn)行改進(jìn)布斯編碼會(huì)產(chǎn)生9(18/2)個(gè)部分乘積項(xiàng)。
2 符號(hào)補(bǔ)償技術(shù)
　　在乘法器樹型求和過程中，為了使各個(gè)部分乘積項(xiàng)對(duì)齊，將需要大量的符號(hào)位擴(kuò)展操作。因?yàn)椴糠殖朔e項(xiàng)的符號(hào)位可能是1或者0，所以擴(kuò)展存在不確定性，直接擴(kuò)展會(huì)造成資源的浪費(fèi)。解決的方法是采用符號(hào)補(bǔ)償技術(shù)^[2]，消除符號(hào)位擴(kuò)展中的不確定性，節(jié)省占用的邏輯資源，提高運(yùn)算速度。
　　符號(hào)補(bǔ)償算法描述如下：例如，把8bit有符號(hào)數(shù)SXXXXXXX擴(kuò)展為12bit，其中S表示符號(hào)位，X表示數(shù)據(jù)位。采用符號(hào)位直接擴(kuò)展時(shí)，可以得到SSSSSXXXXXXX。對(duì)其進(jìn)行等價(jià)邏輯變換：
　　
　　于是，符號(hào)位擴(kuò)展轉(zhuǎn)化成為：對(duì)原操作數(shù)的符號(hào)位取反，并在高位直接補(bǔ)0，再對(duì)式(4)中第二項(xiàng)的確定部分進(jìn)行補(bǔ)償。
　　為了簡化電路，對(duì)前面產(chǎn)生的九個(gè)PP所需的位擴(kuò)展進(jìn)行一次性補(bǔ)償，補(bǔ)償項(xiàng)就構(gòu)成第十項(xiàng)部分積，也就是說對(duì)每個(gè)PP的位擴(kuò)展都采用符號(hào)補(bǔ)償技術(shù)，并把所有的補(bǔ)償項(xiàng)預(yù)先加好，用補(bǔ)償向量V表示，其求導(dǎo)過程如圖2所示，得到V=11010101010101011。

3 混合壓縮比樹型結(jié)構(gòu)及乘法器仿真與下載
　　在對(duì)部分積求和的過程中，重復(fù)陣列IA結(jié)構(gòu)與Wallace樹結(jié)構(gòu)是兩種典型的壓縮結(jié)構(gòu)。IA結(jié)構(gòu)規(guī)整，采用串加的形式，利于產(chǎn)生版圖，但速度較慢；Wallace樹結(jié)構(gòu)采用并行結(jié)構(gòu)，可將求和級(jí)數(shù)從O(N)降為O(log2N)，大幅提高運(yùn)算速度^[3]，但缺點(diǎn)是布線困難。兩種結(jié)構(gòu)都不適合實(shí)際應(yīng)用。因此，大多采用折中的策略^[4～7]把二者結(jié)合起來，使乘法器在速度和占用資源兩方面都有較好的性能，例如ZM樹結(jié)構(gòu)和OS樹結(jié)構(gòu)等。
　　對(duì)于16位×16位有/無符號(hào)數(shù)乘法器，由上所述，總共有10個(gè)部分乘積項(xiàng)，需要通過某種樹型結(jié)構(gòu)壓縮為兩項(xiàng)，即需要一個(gè)10-2壓縮器，再通過超前進(jìn)位加法器得到最終乘積結(jié)果。IA陣列的結(jié)構(gòu)如圖3所示，Wallace樹結(jié)構(gòu)如圖4所示。在比較各種樹型結(jié)構(gòu)的基礎(chǔ)上，本文提出了一種適合于16×16有/無符號(hào)數(shù)乘法器的改進(jìn)樹型結(jié)構(gòu)，即混合壓縮比結(jié)構(gòu)，如圖5所示。

　　各圖中的4-2壓縮器，也稱為5-3加法器，功能是將四個(gè)輸入量壓縮為兩個(gè)輸出量。其代數(shù)運(yùn)算式為：D +C×2+C_o×2=I₀+I₁+I₂+I₃+C_i。在本設(shè)計(jì)中采用的輸入輸出邏輯關(guān)系如下：
　　
　　混合壓縮比結(jié)構(gòu)中的3-2壓縮器也稱為保留進(jìn)位加法器(CSA)，其功能是將三個(gè)輸入量壓縮為兩個(gè)輸出量。3-2壓縮器的輸入輸出邏輯關(guān)系為：
　　
　　分別按照?qǐng)D3～圖5的樹型結(jié)構(gòu)設(shè)計(jì)出對(duì)應(yīng)的乘法器，再對(duì)這三種乘法器的性能進(jìn)行比較。由于構(gòu)成乘法器的其它模塊相同，所以整個(gè)乘法器占用資源多少與延遲大小的區(qū)別完全取決于各自所采用樹型結(jié)構(gòu)的性能優(yōu)劣情況。
　　在QuartusII環(huán)境中分別對(duì)這三種乘法器進(jìn)行系統(tǒng)級(jí)的仿真比較，結(jié)果列于表1中。其中，logical element參數(shù)反映所設(shè)計(jì)乘法器占用的資源，Worst-case tpd參數(shù)反映乘法器的速度性能，兩者之積可以反映乘法器的綜合性能。從仿真結(jié)果可以看出，采用Mercury EP1M120F484C5與FLEX10KE EPF10K30EFC256-1芯片，混合壓縮比結(jié)構(gòu)乘法器占用資源與速度的性能都優(yōu)于IA乘法器和Wallace樹乘法器；而采用APEX20K EP20K100TC144-1V芯片，混合壓縮比結(jié)構(gòu)乘法器雖然占用資源較多，但是速度最快，資源與延遲二者之積仍為最小。因此可以得出結(jié)論：本文提出的混合壓縮比結(jié)構(gòu)適合于16×16有／無符號(hào)數(shù)乘法器，優(yōu)于IA結(jié)構(gòu)和Wallace樹結(jié)構(gòu)。

　　基于混合壓縮比結(jié)構(gòu)的乘法器時(shí)序仿真如圖6所示，時(shí)序仿真采用的芯片為主流系列的FLEX10KE EPF10K30EFC256-1。圖6中所舉算例為：無符號(hào)數(shù)BCD8×F794；有符號(hào)數(shù)FFFF×FFFF；無符號(hào)數(shù)A7FA×FF9C；有符號(hào)數(shù)FF00×7FFF。仿真結(jié)果驗(yàn)證了乘法器運(yùn)算正確。需要指出的是，本乘法器移植在具體系統(tǒng)或者集成芯片時(shí)，其延遲將小于表中的Worst-case tpd數(shù)值。
　　最后將所設(shè)計(jì)的乘法器下載到智能型可編程數(shù)字開發(fā)系統(tǒng)CIC-310中，如圖7所示。通過大量有/無符號(hào)數(shù)算例乘法進(jìn)行硬件驗(yàn)證，表明該乘法器設(shè)計(jì)正確，性能驗(yàn)證與軟件仿真相符，可用作數(shù)字系統(tǒng)中的乘法器運(yùn)算單元。

?

　　本文提出了一種適合16×16乘法器的混合壓縮比結(jié)構(gòu)，其性能優(yōu)于IA結(jié)構(gòu)和Wallace結(jié)構(gòu)?；谠摻Y(jié)構(gòu)所設(shè)計(jì)出的乘法器通過了軟件仿真和硬件驗(yàn)證，可以作為單元模塊移植在具體系統(tǒng)或者集成芯片中。所提出的混合壓縮比結(jié)構(gòu)還可以作為10-2壓縮器應(yīng)用于更高位數(shù)乘法器的設(shè)計(jì)中，具有較強(qiáng)的實(shí)用價(jià)值。
參考文獻(xiàn)
1 Booth A D. A Signed Binary Multiplication Technique[J]．Quarterly Journal of Mechanics and Applied Mathematics, 1951；4(2)：236～240
2 Kwentus A Y，Hung H T，Wilson AN，et A1．An Architecture for High-performance/small-area Multipliers for Use in Digital filtering Applications[J]. IEEE J Sol Sta Circ,1994;29(2)：117～121
3 Wallace C S. A Suggestion for a Fast Multiplier[J]．IEEE Transactions on Electronic Computers, 1964；13(2):14～17
4 許 琪，原 巍，沈緒榜.一種新的樹型乘法器的設(shè)計(jì)［J］．西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2002;29(5)：580～583
5 Wen-Chang Yeh, Chein-Wei Jen. High-speed Booth En-coded Parallel Multiplier Design[J]. IEEE Transactions on Computers, 2000;49(7):692～701
6 K.H.Cheng et al. The Improvement of Conditional Sum Adder for Low Power Applications. Proc,11th,Ann.IEEE Int’l ASIC Conf.1998;131～134
7 Fadavi-Ardekani J.M×N Booth Encoded Multiplier Generator Using Optimized Wallace Trees, Very Large Scale Integration (VLSI) Systems. IEEE Transactions on, 1993;1(2):120～125