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