雙字節(jié)Booth乘法器的優(yōu)化設(shè)計

1、第 44卷 第 1期復(fù) 旦 學(xué) 報 (自然科學(xué)版 V o1. 44, N o. 12005年 2月 Journal of Fudan University (Natural Science Feb. , 2005 文章編號 :042727104(2005 0120085205雙字節(jié) Booth 乘法器的優(yōu)化設(shè)計朱一杰 , 張 曦 , 俞 軍(復(fù)旦大學(xué) 專用集成電路與系統(tǒng)國家重點實驗室 , 上海 200433 摘 要 :在分析改進(jìn) Booth 算法雙字節(jié) (16bit 乘法器的基礎(chǔ)上 , 提出一種并行的乘法器結(jié)構(gòu) , 并且在最后的快速 進(jìn)位鏈中運用了新的設(shè)計 , 提高了乘法器的速度 , 相對于傳

2、統(tǒng)的結(jié)構(gòu)減少了一位全加器的數(shù)量 , 達(dá)到減小電路規(guī) 模和芯片面積 , 降低乘法器功耗的目的 .關(guān)鍵詞 :專用集成電路 ; 改進(jìn) Booth 算法 ; 進(jìn)位保留加法器 ; 陣列操作 ; 并行乘法器中圖分類號 :T N 403 文獻(xiàn)標(biāo)識碼 :A在數(shù)字信號處理中 , 2法 , 即通過連續(xù)地進(jìn)行加法和移位來實現(xiàn) . , 則 ×2個乘法器 的時鐘周期才能給出 2N 位乘積 , 1.2, .這 2. 前者的 N ×N 乘法器需 N 個加法器和 , N ×N 乘法器需 N 2個加法器和 N 2個部分積的與門 .為了進(jìn)一步提高運算速度 , 通常采用下面 2種方法改進(jìn) : 用斜向進(jìn)

3、位代替橫向進(jìn)位 , 加速部分積的 相加 , 即采用 Carry 2Save Adder (以下簡稱 CS A ; 根據(jù)乘數(shù)中 0/1結(jié)構(gòu)的特征 , 對于成串的 “ 1” , 利用 2i +k -1+2i +k -2+ +2i =2i +k -2i , 減少部分積的數(shù)目 .在第 2種方法中 , 根據(jù)移位位數(shù)可將此類算法分為兩類 :變長位數(shù)移位方式和固定位數(shù)移位方式 . 通 過變長位數(shù)移位進(jìn)行的乘法充分考慮了乘數(shù)中不同長度的 “ 1” 串 , 但這必然使算法的速度強烈依賴于乘數(shù) 中 0/1的結(jié)構(gòu) , 因此難以進(jìn)行統(tǒng)一時序控制和陣列化設(shè)計 . 固定位數(shù)移位方式克服了這些缺點 , 因而獲得 了廣泛的運

4、用 , 特別是改進(jìn) Booth 算法 2很受歡迎 .在經(jīng)典 Booth 算法中 , 每次檢驗 2位 , 完成 N 位乘法需 N 次移位和平均 N /2次加法 ; 在改進(jìn) Booth 算法 中 , 每次檢驗 3位 , 完成 N 位乘法需 N /2次移位和平均 N /2次加法 3.表 1列舉了改進(jìn) Booth 算法的編碼規(guī)則 , 其中 y i +1與 y i 為考察位 , y i -1為附加考察位 , PP i 為產(chǎn)生的部 分積 . 雖然有 8種組合 , 但真正進(jìn)行的運算只有 3種 :+0, +X , +2X , 負(fù)項通過補碼運算變成加法 .為了提高乘法器的速度 , 部分積的相加均采用 CS A

5、來實現(xiàn) , 一種實用的 8位乘法器的加法陣列結(jié)構(gòu) 如圖 1所示 . 圖中的小框為基本陣列單元 1bit 全加器 , 框中標(biāo)識的變量就是全加器的輸入 , 如果沒有標(biāo) 識 , 說明本全加器除了連線輸入外 , 其他輸入均為 0. 最后一次輸出終值的加法不采用 CS A , 而是采用了帶 超前進(jìn)位鏈的高速加法器 4. 當(dāng)乘數(shù)和被乘數(shù)變?yōu)殡p字節(jié) (16bit 后 , 加法陣列結(jié)構(gòu)在位數(shù)上和層次上也隨之增大 . 所需的 CS A 單 元總數(shù)將達(dá)到 173之多 , 而且串行運算的級數(shù)也增大到 7級 CS A 加上一級高速加法器 . 這樣的結(jié)構(gòu)無論在面積和速度上都是不理想的 . 本文提出用并行結(jié)構(gòu)代替串行結(jié)構(gòu)

6、來提高電路的整體性能 .收稿日期 :2004203222作者簡介 :朱一杰 (1978 , 男 , 碩士 ; 通訊聯(lián)系人俞 軍 . 表 1 改進(jìn) Booth 算法規(guī)則T ab. 1 M odified Booth Alg orithmy i +1y i y i -1PP i 000+0001+X 010+X 011+2X 100-2X 101-X 110-X 111- 圖 1 8位乘法器中的加法陣列結(jié)構(gòu)Fig. 1 CS A architecture of 82bit multiplier1 并行 Booth 乘法器在改進(jìn) Booth 算法中 , 每一次檢驗 3位 , , . 所以對于 16位

7、的乘法一共需要檢驗 8次 , 1個檢 驗解碼器的話 , 那么這 8. 如果同時使用 2, , 這也就是并行結(jié)構(gòu)的雛形 5.CS A 單元 . 每次檢驗解碼結(jié)果真正有效的數(shù)據(jù)實際 上只有 16位 , 由于存在最低位的位差 , 要將低位的檢驗解碼結(jié)果進(jìn)行符號 位擴展 . 檢驗位的位差越大 , 所需進(jìn)行的符號位擴展也越大 . 所以將高 8位的檢驗解碼結(jié)果和低 8位的檢 驗解碼結(jié)果分別累加 , 這樣所用加法陣列的規(guī)模應(yīng)該是最小的 .圖 2 加法陣列Fig. 2 CS A Architecture還有一點需要考慮就是補碼的校正位 Y , 如圖 1中的 Y 1、 Y 3等 . 當(dāng)檢驗解碼結(jié)果是 0、 +X

8、 或 +2X 時 , Y 取 0; 當(dāng)檢驗解碼結(jié)果是 -X 和 -2X 時 , 結(jié)果取反且 Y 取 1. 如圖 1所示 , 每次檢驗解碼后所需加的 校正位都和下一次的檢驗解碼結(jié)果放在同一行加法器中累加 , 所以最后會有一行加法器只用來累加最后 一次檢驗解碼中的校正位 . 在并行結(jié)構(gòu)中 , 兩邊分別累加 , 兩邊也各有一行加法器只用來累加最后的校正 68復(fù) 旦 學(xué) 報 (自然科學(xué)版 第 44 卷位 . 不過由于兩邊最后的校正位不在同一位 , 所以可以把兩行并成一行 , 以減少 CS A 單元的數(shù)量 .基于上述討論 , 本文設(shè)計的并行結(jié)構(gòu)如下 . 將高 8位的檢驗解碼結(jié)果和低 8位的檢驗解碼結(jié)果分

9、別累加 . 兩邊的第 1、 第 2行加法陣列和圖 1相似 , 只是高 8位的加法陣列中最低位是 bit15. 在設(shè)計第 3行加法陣列時兩邊有所不同 . 高 8位處使用快速進(jìn)位鏈加法器得出臨時結(jié)果 ; 低 8位處 再用一行加法器將 2個校正位加上 . 然后將高 8位的臨時結(jié)果累加入低 8位 , 最后用快速進(jìn)位鏈加法器得出最終的結(jié)果 .圖 2(a 中 E ,F , G 和 H 為高 8位的檢驗解碼結(jié)果 ,T 23 T 0為臨時結(jié)果 , 將累加到低 8位的加法陣列 中 . 第 1行中 E16(E 的符號位擴展 , 下同 共 8位 ,F16共 6位 ,G 16共 4位 ; 第 2行中 H16共 2位

10、, 且最低位 不需要 CS A 單元 , 所以共需 47個 CS A 單元 .圖 2(b 中 A 、 B 、 C 和 D 為低 8位的檢驗解碼結(jié)果 ,T 23 T 0為高 8位中得到的臨時結(jié)果 . 第 1行中 A16共 16位 ,B16共 14位 ,C16共 12位 ; 第 2行中 D16共 10位 , 最低位不需要 CS A 單元 ; 第 3行中 Y 15是最高 檢驗解碼中的校正位 , 在 bit14處 ,Y 7是乘數(shù)第 7、 8位檢驗解碼中的校正位 , 在 bit6處 , 且最低 2位不需要 CS A 單元 ; 第 4行中 24個 CS A 單元用于累加臨時結(jié)果 T. 所以共需 117個

11、CS A 單元 .將圖 2(a 與 (b 合并就得到并行結(jié)構(gòu)的雙字節(jié) Booth 乘法器 . 該乘法器一共需要 CS A 單元 , 運 算一次所需級數(shù)為 4級 CS A 加上 1級高速加法器 .無論是串行結(jié)構(gòu)還是并行結(jié)構(gòu) , 在 Booth , 號位擴展 , . . 對于任意一個有符 號數(shù) SXXX , S , , 可以將其改寫為 :=1111 S XXX +1, 1能預(yù)先加好 , 形成一個補償向量 . 乘法器的字節(jié)越長 , 采用此方法所能 節(jié)省的計算時間和硬件資源就越少 .如果在加法陣列中每一行之間加入寄存器 , 那么就能形成一個流水線型的 Booth 乘法器 , 進(jìn)一步加快 速度 . 設(shè)計

12、低 8位加法陣列時 , 先加 2位校正位 , 再加高 8位的臨時結(jié)果 , 以配合高 8位加法陣列的時序 . 當(dāng)然 , 這樣做也是有代價的 , 即所需的解碼和控制電路將會比較復(fù)雜 6, 這里就不作詳細(xì)論述了 . 2 快速進(jìn)位鏈的設(shè)計在加法陣列的最后一行需要得出最終的結(jié)果 , 而不像前面行那樣可以將和與進(jìn)位一起傳給下一行 . 如果使用串連的進(jìn)位鏈 , 那么 N 位的加法就需要 N 個全加器的延遲時間之和 . 如果使用超前進(jìn)位鏈又使 用了太多的面積 7.很多文獻(xiàn)都對上面介紹的 2種進(jìn)位鏈有詳細(xì)的描述 , 可以發(fā)現(xiàn)這 2種進(jìn)位鏈有一個共同點 , 就是所有 的計算都是從最低位開始往高位計算 . 那么能否

13、從最低位和最高位兩端同時開始計算 , 最后在中間某一 位連接上以節(jié)省時間呢 ?將圖 2(b 中的 6位快速加法器展開如圖 3(見第 88頁 . 從圖中可以看出 , 每 1位都有 2個輸入端 , 而 這一位的進(jìn)位不僅與這 2個輸入端有關(guān) , 而且還與低一位的進(jìn)位有關(guān) . 但是如果這 2位輸入都是 0或都是 1的話 , 進(jìn)位就與低一位的進(jìn)位沒有關(guān)系了 . 利用這一原理將這 2位的輸入分成 3種情況 , 如表 2(見第 88頁 . (說明位的狀態(tài)有 3種 , u 表示不確定 , r 表示本位保持輸入之和 , i 表示本位為輸入之和的非 表 2中的第 1列為該位當(dāng)前的判定結(jié)果 , 第 2例為比該位低的

14、某位的 2個或者 3個輸入之和 . 如果一 位已經(jīng)被它低的某位輸入判定為 r 或者 i , 那么就無需由更低的位輸入判斷了 , 所以表中沒有列出 . 表中 的第 3,4列為由輸入判定的結(jié)果 , 以該位是否為最低位分成 2例 , 其中的差別就是輸入的個數(shù)和在輸入端 為 1時的判定結(jié)果 . 這里的最低位就是指算法中兩頭運算在中間接連的那一位 . 如果是最低位 , 則有 3個 (多出 1個次低位的進(jìn)位 , 當(dāng)輸入為 1時 , 最終的判定結(jié)果為 r .78第 1期 朱一杰等 :雙字節(jié) Booth 乘法器的優(yōu)化設(shè)計表 2 進(jìn)位預(yù)先判斷規(guī)則表T ab. 2 Prejudging rule of carry

15、 位的初狀態(tài) 低位輸入 中間位 最低位 Dk =u 0Dk +1=r Dk +1=r Dk =u 1Dk +1=u Dk +1=r Dk =u 2Dk +1=i Dk +1= i圖 3 6位高速加法器Fig. 3 62bit high 2speed adder以圖 3中的 6位高速加法器為例 . 輸出端的起初狀態(tài)都為 u . C out 的狀態(tài)先由 bit5的輸入 M5和 N5判斷 , 如果判定結(jié)果仍為 u , 則與 P5一起再由 bit4的輸入 M4和 N4判斷 , 依次類推 . 當(dāng)判斷完最低位 (中 間位 后 , 所有位的狀態(tài)都已確定 , 然后根據(jù)本位的狀態(tài)與輸入之和得出最終的結(jié)果 . 至

16、于中間位的選擇 . 就顯得相當(dāng)靈活 , 可以根據(jù)工藝條件選定 , 使得兩邊所需的邏輯運算時間大致相等即可 .3 實際驗證對本文設(shè)計的雙字節(jié)并行 Booth (其中加 法器為 6位 , 改進(jìn)進(jìn)位鏈的中間位取為 bit3 . , DC , . 可以看出 , 并行結(jié)構(gòu)無論在面積 (S 、 門數(shù)和時延 (t芯片面積 、 降低功耗的目的 ; , 而超前進(jìn)位鏈在面積上是 最大的 , 10%左右 , 達(dá)到了預(yù)期效果 .表T ab. 3 C on of parallel and serial architecture 結(jié)構(gòu)類型 S /m 2門數(shù) t dmax /ns 并行結(jié)構(gòu) 905445526. 34串行結(jié)

17、構(gòu) 1075216488. 84表 4 各種進(jìn)位鏈的驗比較T ab. 4 C om paris on of each kinds of Carry 2chain 進(jìn)位鏈類型 S /m 2t dmax /ns 串行進(jìn)位鏈 2816. 62. 36超前進(jìn)位鏈 5103. 41. 67改進(jìn)進(jìn)位鏈 4596. 41. 67本文介紹了改進(jìn) Booth 算法及 8位乘法器的結(jié)構(gòu) , 并指出了這種結(jié)構(gòu)在實現(xiàn) 16位乘法器中暴露出來 的弊端 . 提出了一種用并行結(jié)構(gòu)設(shè)計的改進(jìn) Booth 乘法器結(jié)構(gòu) . 該并行結(jié)構(gòu)將運算級數(shù)由原來的 7級 CS A 加上 1級高速加法器改進(jìn)為現(xiàn)在的 4級 CS A 加上 1級

18、高速加法器 , 提高了運算速度 . 在規(guī)模上 , 所需 CS A 單元個數(shù)由原來的 173減少至 164, 達(dá)到了減小電路規(guī)模和芯片面積 , 降低乘法器功耗的目的 . 另外還提 出了一種新的快速進(jìn)位鏈算法 , 這種算法在控制電路規(guī)模的基礎(chǔ)上加快了運算速度 , 并且可以通過調(diào)節(jié)中 間位來達(dá)到最佳效果 . 參考文獻(xiàn) :1 李偉華 . V LSI 設(shè)計基礎(chǔ) M.北京 :電子工業(yè)出版社 ,2002.2 韓 雁 . 專用集成電路設(shè)計技術(shù)基礎(chǔ) M.成都 :電子科技大學(xué)出版社 ,2000.3 E fstathiou C , Verg os H T ,Nikolos D. M odified booth m

19、odulo 2n 21multipliers J.Computer s , IEEE Transactions on , 2004, 53(3 :3702374.4 沈緒榜 . 超大規(guī)模集成系統(tǒng)設(shè)計 M.北京 :科學(xué)出版社 ,1991.5 C ooper A R. Parallel architecture m odified Booth multiplier J.Circuits , Devices and Systems , IEEE Proceedings G, 1988, 135(3 :1252128.6 Rao V M ,N owrouzian B. A novel approach

20、 to the design and hardware im plementation of high 2speed digit 2serial m odi 2 fied 2Booth digital multipliers J.Circuits and Systems ,1997, 3:1952219551.88復(fù) 旦 學(xué) 報 (自然科學(xué)版 第 44 卷7 謝永瑞 . V LSI 概論 M.北京 :清華大學(xué)出版社 ,2002. Architecture Optimization of Word 2length Booth MultiplierZHU Y i 2jie ,Zhang X i ,

21、Y u J un(ASIC &System State K ey Laboratory , Fudan Univer sity , Shanghai 200433, China Abstract :Based on introducing m odified Booth alg orithm and its realization in w ord 2length multiply ,a novel parallel multiplier architecture is developed , and a new architecture is als o used in high 2

22、speed adder. These im provements accelerate the whole multiplier and decrease the number of carry 2save adders.K eyw ords :ASIC ; m odified Booth alg orithm ; carry 2save adder ; array processing ; parallel multiplier (上接第 79頁 4 Proakis J G. Digital C ommunications ,4th Ed M.New :25 Ed fors O ,Sandell M ,Wils on S K, et position J.IEEE TransCommun (7 A N e w Adaptive Modulation Algorithmfor OFDM SystemCHEN Hao 2min , X U Qiao 2yong , WAN G Z ong 2xin(Department o f Communication Science and E