摘 要： 基于改進波茲編碼的乘法器" title="乘法器">乘法器設計中，在處理部分積累加時, 為了提高速度、減小面積，可以單獨對符號位擴展部分進行優(yōu)化處理。本文就符號位擴展運算提出了一種使用‘或’-‘異或’處理的快速算法。該方法有效地減少了門的使用數(shù)量，提高了處理速度。
關鍵詞： 乘法器 改進波茲算法" title="改進波茲算法">改進波茲算法 部分積 符號位擴展陣列
設計快速乘法器，通常要重點處理三個關鍵問題：減少部分積產生、加速部分積累加和提高最終多位數(shù)相加速度。例如，用傳統(tǒng)的乘法運算模式處理16位×16位所用的時間為t總=t產生16行部分積+t16行部分積累加成最終積。若運用改進波茲(Booth)算法以后，可以減少部分積的產生。而基于改進波茲算法的乘法器設計，在后續(xù)部分積相加的過程中，無論采用哪種處理方式，如華萊氏樹結構等，都不可避免地要解決符號位擴展陣列問題。本文提出了一種新的基于改進波茲算法的邏輯設計" title="邏輯設計">邏輯設計來處理符號位部分：通過簡單地運用‘或門’、‘異或門’來優(yōu)化乘法器的局部速度和面積兩方面的性能。
1 改進波茲算法
改進波茲算法MBA(Modified Booth′s Algorithm)[1]是建立在波茲算法[2]基礎上的。對乘數(shù)三位一組的劃分包含了一個重疊位，每一組的三位按表1編碼，并形成一個部分積。由此而產生5個系數(shù)：±1、±2、0。在部分積的累加過程中，減法也就是補碼相加。經過編碼以后，通過高低電平信號對符號位進行指示。n位乘數(shù)乘以m位被乘數(shù)會產生n+m位積。因此累加過程中由于對負數(shù)補碼的相加，每個部分積必須把符號位擴展到最高位(第n+m-1位)，以此來保證后續(xù)運算的正確性。若以8位X×8位Y為例，產生的部分積陣列如圖1所示。由于部分積含有±2X，因此其字長為9位，即A0～A8，第10位A9為符號位。在做減法補碼運算時，其符號位應擴充至最高位(第15位)，再加上相應每組最高位，即y1。B、C、D、E也按此規(guī)律產生。8位×8位最終產生16位積。
?
觀察圖1可以發(fā)現(xiàn)在部分積陣列中，有相當大的一部分是符號位擴展陣列，并且隨著兩個相乘數(shù)的位數(shù)成倍地增加，符號位擴展陣列也不斷擴大，因此考慮對這個特殊陣列的處理就相當有價值。
2 ‘或’-‘異或’快速算法處理符號位部分
對符號位擴展陣列單獨處理，邏輯設計則按照下面順序來進行：
(1)若乘數(shù)有偶數(shù)個位即2k(k=1,2……n)，那么就會產生k+1行部分積。在部分積中，有k行符號擴展位，符號擴展位陣列的最大寬度為2k-1個位；若乘數(shù)有奇數(shù)個位，即2k+1(k=0,1,2......n)，那么就會產生k+1行部分積。在部分積中，有k行符號擴展位，符號擴展位陣列的最大寬度為2k個位。
(2) 若編碼結果為負數(shù)，那么產生該行的所有符號位都是1，否則都為0。
(3) 除了第0列，對符號位擴展陣列每一列進行奇偶劃分，即第1、3、5……為奇數(shù)列，第2、4、6……為偶數(shù)列。
(4) 符號位擴展陣列和的偶數(shù)位與該列上(從上至下)最后一位相關聯(lián)。該陣列和的奇數(shù)位等于該列上所涉及位的‘或’運算，偶數(shù)位等于與該位相關聯(lián)的那位與低一位的奇數(shù)列的和位的‘異或’運算，第0位等于第0行的編碼產生的符號信號。
以8位×8位的例子來說明：r0~r6是符號位陣列累加的和位，s0~s3表示陣列第0行到第3行，如圖2所示。
當乘數(shù)有奇數(shù)個位時，符號位擴展陣列排布如圖4所示。
求證方法類似于偶數(shù)位乘數(shù)，得到的結論為：
r2i-1=sign[i-1]|…|sign[1]|sign[0],r2i-2=sign[i-1]^r2i-3。
4 算法實現(xiàn)
實現(xiàn)這一設計很容易：根據(jù)設計規(guī)則，r3、r5……r2i-1
位全部由‘或門’來實現(xiàn)，r2、r4、r6……r2i-2位全部由‘異或門’來實現(xiàn)，r0、r1用編碼產生的符號指示信號表示。把8位×8位的例子用‘或門’和‘異或門’實現(xiàn)如圖5所示，圖中用了2個‘或門’和3個‘異或門’。
5 性能評估
該設計方案的性能評價從如下兩方面考慮：
(1)從速度和面積兩方面性能考慮，符號位擴展陣列作為一個模塊單獨設計。
首先，把原本符號位之間的累加轉換成用‘或’-‘異或’進行處理，既大大降低了門的使用數(shù)量，從而減小了該硬件乘法器模塊所占的面積，也避免了累加過程中的進位等待問題而提高了速度。如果不對符號位擴展陣列單獨處理，而是在后續(xù)處理的過程中選擇特殊壓縮器來進一步解決累加的速度問題，其面積上的增加是顯而易見的。
(2)考慮該設計結果對后續(xù)部分積處理的影響。
因為通過符號位擴展陣列的特性可以知道，和的位數(shù)就是以第0行部分積中的符號擴展位的位數(shù)，不產生多余的累加行。因此陣列最終產生一行和位，與現(xiàn)在所知的其他處理方法相比，沒有多余的位與除去符號位擴展陣列的部分積進行相加。并且該行和位也不作為額外的累加行介入部分積累加。在相關文獻中，對符號位擴展陣列處理有使用預求和并加上修正位的方法：先假設所有n位×n位符號位擴展陣列中每個位都是1，預算出最后的和，然后根據(jù)符號指示信號對相應行加1，并將這個1作為符號修正位[3]。也有根據(jù)等式
，對符號擴展部分做相應恒等變形處理的方法[4]。這些方法除了產生與符號位擴展陣列寬度相同的一行位以外，還有額外的位要累加到部分積上。以8位×8位乘法用三種" title="三種">三種不同方案處理符號位部分所得部分積如圖6所示。圖中r0~r6作為符號位陣列累加的和位，
作為符號修正位。
?
把符號位擴展陣列的結果嵌入到后續(xù)部分積累加過程中，可以發(fā)現(xiàn)運用‘或’-‘異或’處理符號位擴展陣列的方案與另外兩個方案相比，所用的加法單元少，在乘法器設計中盡可能地減少了部分積累加延遲。圖6三種方案的比較結果如表4所示。由此可以得出：運用‘或門’和‘異或門’處理符號位部分對后續(xù)處理的意義很大(由于后續(xù)處理有不同的方式，不同的設計可能對使用的門數(shù)產生略微的變化)，并且這種設計方案具有良好的通用性。隨著兩個相乘位數(shù)的遞增，運用‘或’-‘異或’處理符號位擴展陣列的方法同樣適用，并且能很快地產生結果。
乘法運算在數(shù)字信號處理中是個瓶頸，通過不斷改進算法和結構的設計來提高乘法器的運算速度" title="運算速度">運算速度，并同時兼顧面積和功耗問題，變得越來越重要。隨著運算位的成倍增加：從16×16到32×32，再到64×64，若設計中使用了改進波茲算法，其符號位擴展陣列也可成倍地遞增，因此，研究其算法和結構設計很重要。本文提出使用‘或’-‘異或’邏輯來解決符號位部分的設計方案，符合設計目標，在降低面積和提高運算速度方面有顯著的優(yōu)勢。
參考文獻
1 MacSorely O L. High speed arithmetic in binary computers. Proc IRE, 1961;(49):67~91
2 Booth A D. A signed binary multiplication technique.Mech- anics and Applied Mathematics Quarterly J, 1951;4(2): 236~240
3 應 征, 吳 金. 高速浮點乘法器設計. 電路與系統(tǒng)學報, 2005;(10):6~11
4 鄭 偉, 姚慶棟, 張 明等. 一種高性能、低功耗乘法器的設計. 浙江大學學報(工學版), 2004;(38):534~538