基于BoothCSD混合編碼的模2n+1乘法器的設計

王 敏，徐祖強，邱陳輝

(江蘇科技大學電子信息系，江蘇鎮江212003)

基于BoothCSD混合編碼的模2n+1乘法器的設計

王 敏，徐祖強，邱陳輝

(江蘇科技大學電子信息系，江蘇鎮江212003)

在余數系統的設計中，模加法器和模乘法器的設計處于核心地位，尤其是模乘法器的性能，是衡量余數系統系能的主要標志之一。文中先推導出Booth編碼下的模2n+1乘法器設計的算法，然后針對Booth編碼模乘法器設計中譯碼電路復雜的問題，提出了一種基于Booth/CSD混合編碼的模乘法器設計方法，基于Booth/CSD編碼的模乘法器部分積的位寬相對傳統的Booth編碼乘法器而言，減少了50%;經試驗證明，與傳統的基-Booth編碼的模乘法器相比這種混合編碼的模乘法器的速度提高了5%，面積減少24.7%。

電子電路設計;模2n+1乘法器;Booth/CSD編碼;余數系統

近年來，隨著大規模集成電路的發展，余數系統以其內在的并行特性越來越受到業內人士的重視;在圖像處理、CDMA通信系統以及DSP處理器設計等領域余數系統都有較好的應用前景。在乘法器設計中，基于Booth編碼的乘法器［1-3］在二進制系統中得到了廣泛的應用，Booth編碼的核心是通過減少乘法運算中的部分積個數來達到提高乘法器運算速度的目的，而CSD編碼則是在乘數的二進制表示有較多連續的“1”時，通過某種轉換，增加“0”的個數，減少“1”的個數。我們知道“0”在實際運算過程中和被乘數相乘結果為0，可看做不參加運算。文中將兩種編碼的優點有效結合起來，雖然CSD編碼并不是每一次都能簡化乘法運算，但在統計學的角度看，兩者的結合可以有效的提高乘法運算速度。為表示方便，以下論文中凡出現右下角標，均表示對該值進行取模運算。

1 基于8-Booth編碼的模2n+1乘法器

1.1 基8-Booth編碼模2n+1乘法器結構

基8-Booth編碼的模2n+1乘法器［4-6］結構圖如圖1所示，該結構主要包括Booth編碼器、模部分積生成器、華萊士樹壓縮器［7］以及超前進位模2n+ 1加法器。其中華萊士樹是由進位保留加法器構成，它能夠對部分積進行壓縮，將3個部分積壓縮成2個，從而減少相加部分積的個數，其結構如圖2所示。

圖1 基8-Booth編碼模2n+1乘法器結構

圖2 華萊士樹形結構

1.2 基8-Booth編碼模2n+1乘法器設計算法推導

余數系統中設計模加法器和模乘法器的用意是，將乘法或加法運算的結果經過取模運算轉換成較小的數，然后再用較小的數參加各類運算。比如，選定余數基為28-1，假定有兩個數相乘，結果為遠大于255的數，這類數參加各類算術運算時得到的結果一般也較大，但如果對其進行取模運算，取模后的結果在0～255之間，實際參加運算的操作數就小的多了，當然計算起來也更加簡便。最后利用某些方法，比如中國剩余定理，將余數系統下的結果轉換成人們易于接受的形式。模乘法器的設計過程中，可以先計算出乘法運算的結果，然后對該結果進行取模運算;也可以基于如下公式所提供的思路:〈x1+x2+…xk〉m=〈〈x1〉m+〈x2〉m+…，其中xi為乘法運算過程中產生的部分積，加上xi即在部分積累加前先對部分積進行一次取模運算，然后對累加的結果再次取模。由于基8-Booth運算中，每次對乘數取3位，因此首先對B進行位擴展，使其二進制表示的位寬為3的倍數，因此B可以表示成

所以對AB的乘積取模2n+1運算方法如下

為求出AB乘積取模的一般表達式，先假設一個中間變量PPi，并令

令Ei=-4b3i+2+2b3i+1，E'i=b3i+b3i-1，那么Ei的取值為{-4，-2，0，2}，E、i的取值為{0，1，2};假設Ei23i=，則

求出S1，S2，j，k的表達式如下

現求解|S1A2j|2n+1和|S2A2k|2n+1的值

由于

當 S1=1時，，對于無符號數m，有(m+ˉm)=2j-1，ˉm表示對m的二進制表示各位取反。所以-m =ˉm-(2j-1)，最后得出:

當S1=0時

當S1=-1時

同理可求出|S2A2k|2n+1

當S2=0時

當S2=1時

根據上面的運算結果給出基8-Booth編碼的模2n+1乘法運算部分積如表1所示。

表1 基8Booth編碼的模2n+1乘法運算部分積

1.3 Booth編碼下模乘法器性能分析

2 基于CSD/Booth混合編碼的模2n+1乘法器

2.1 CSD/Booth編碼原理

采用CSD編碼的優勢在于:當乘數的二進制表示含有較多連續的“1”時，可以用較多的“0”代替，CSD編碼［10］的內容是:從最低有效位開始，用10…取代所有的大于等于2的“1”序列.如11112= 1000CSD。基于 CSD/Booth混合編碼同時結合了CSD編碼可以減少乘數中“1”的個數和Booth編碼可以減少部分積的特點，CSD/Booth編碼的原理如下，(以8-Booth為例)假定一個數B，表示成b3k-1b3k-2…b0，將其分組，每3位為1組，即 b2b1b0，b5b4b3，…，b3k-1b3k-2b3k-3，然后將各組Booth碼轉換成CSD碼，如111→100，011→10等，具體的CSD/Booth編碼規則如表2所示。需要注意的是，在由Booth碼轉換成CSD碼時，有時候會遇到位寬擴展的問題，如上111→100轉換，就需要擴展一位，類似這種情況，采用修正的方法來得到最終的部分積和。

表2 CSD/Booth編碼表

表2中之所以將3A寫成4A-A，5A寫成4A+ A是為了將乘法運算轉換成簡單的移位運算，基于CSD/Booth混合編碼的模2n+1乘法器的流程圖如圖3所示。

圖3 模2n+1乘法器流程圖

而最終對部分積之和取模運算，可以采取如下高效的方法:設A、B的二進制表示為n位，AB兩數相乘的結果表示為:

其中K=(AB)/2n，U=(AB)mod 2n。

所以

而

令

可得出

2.2 FPGA仿真驗證結果及性能比較

本文以基28+1模乘法器為例驗證，至于更高階基的模乘法器的設計方法類似。采用上面的方法得到的仿真驗證結果如圖4，圖中a、b為相乘的兩個整數，result為乘積，modresult為對28+1取模運算的結果，本設計在quartus ii軟件中，采用VHDL語言編寫，并用ALTERA公司的cyclone ii系列FPGA芯片進行綜合驗證，實驗表明，單純采用基8-Booth編碼的模28+1乘法器需要在更低的時鐘頻率下才能得到正確結果，因而在速度上，基于CSD/ Booth混合編碼的模2n+1乘法器的效率要高。

圖4 模28+1乘法器驗證結果

兩種編碼方法的硬件消耗比較如表3所示。

表3 硬件資源消耗對比

3 結語

本文利用CSD/Booth混合編碼的方法實現了一個模2n+1乘法器，該乘法器同時結合了CSD編碼和Booth編碼的優點，在取模運算的譯碼過程中，利用簡單的截位運算替代查找表，有效的節省了硬件資源，并在一定程度上提高了模乘法器的運算速度，為更加高效的模乘法器的設計提供了良好的思路。

［1］ 湯曉慧，楊軍，吳艷.基于Booth算法的32×32乘法器IP核設計［J］.電子器件，2005，28(1):231-233.

［2］ Deepal Chandel，Gagan Kumawat，Pranay Lahoty.Booth Multiplier: Ease of Multiplication［J］.International Journal of Emerging Technology and Advanced Engineering，2013，3(3):326-329.

［3］ Dina Younes，Pavel Steffan.Novel Modulo 2n+1 Subtractor and Mulitiplier［C］//The Sixth International Conference on Systems，2011:36-38.

［4］ Reto Zimmermann.Efficient VLSI Implementation of Modulo 2n±1 Addition and Multiplication［C］//Proceedings of the 14th Symposium on Computer Arithmetic，1999:51-54.

［5］ Yi-Jung C，Dyi-Rong D，Yunghsiang S H.Improved Modulo 2n+1 Multiplier for IDEA［J］.Journal of Information Science and Engineering，2007，23:907-919.

［6］ Soojin Kim，Kyeongsoon Cho.Design of High-Speed Modified Booth Multipliers Operation at GHz Ranges［R］.World Academy of Science，Engineering and Technology，2010:37-38.

［7］ 王定，余寧梅，張玉倫，等.改進型booth華萊士樹的低功耗、高速并行乘法器的設計［J］.電子器件，2007，30(1):253-255.

［8］ 胡劍浩，馬上.余數系統原理與在高速數字信號處理中的應用［M］.北京:科學出版社，2012:2-11.

［9］ 李磊，胡劍浩，敖思遠.高速Booth編碼模2n-1乘法器的設計［J］.微電子學與計算機，2011，28(11):191-193.

［10］Meyer-Baese U.數字信號處理的FPGA實現［M］.北京:清華大學出版社，2011:50-55.

［11］Marc Hunger，Daniel Marienfeld.New Self-Checking Booth Multiplier［J］.Math，Comput Sci，2008，18(3):319-328.

［12］劉東.采用Booth算法的16×16并行乘法器設計［J］.現代電子技術，2003(5):21-25.

［13］周蜿婷，李磊.基4BOOTH編碼的高速32×32乘法器的設計與實現［J］.電子科技大學學報，2008，37:106-108.

王 敏(1974- )，女，漢族，重慶豐都人，江蘇科技大學副教授，碩士，主要研究方向為信號與信息處理，wangmin94 @163.com。

The Design of Modulo 2n+1 Multiplier Based on Booth/CSD Hybrid Encoding

WANG Ming，XU Zuqiang，QIU Chenhui
(Department of Electronic and Information，Jiangsu University of Science and Technology，Zhenjiang Jiangsu 212003，China)

In the design of RNS system the designs of，the modulo multiplier and adder are in a core position，espically the performance of the modulo mulitipliers，which is the main mark of a successfully RNS system.In this paper，we deduce the arithmetic used in the design of the Booth-based modulo multiplier first，and then in order to solve the problem of complex decoding circuit in design，we put forward a new method，in which we bring the efficient CSD enconding technology and radix-booth encoding techniques together，the partial product of Booth/CSD encoding module multiplier has a decrease of fifty percent compared with traditional Booth based module multiplier;the test results demonstrate that，in comparision with the traditional Booth based module multiplier the speed which we take Booth/ CSD encoding method has an increase of five percent and the area has a decrease of twenty four point seven.

electronic circuit design;module 2n+1 multiplier;Booth/CSD encoding;RNS system

10.3969/j.issn.1005－9490.2014.02.044

TN710

A

1005－9490(2014)02－0373－05

2013-06-03修改日期:2013-07-16

EEACC:6120B