基于BoothCSD混合編碼的模2n+1乘法器的設(shè)計(jì)

王 敏，徐祖強(qiáng)，邱陳輝

(江蘇科技大學(xué)電子信息系，江蘇鎮(zhèn)江212003)

基于BoothCSD混合編碼的模2n+1乘法器的設(shè)計(jì)

王 敏，徐祖強(qiáng)，邱陳輝

(江蘇科技大學(xué)電子信息系，江蘇鎮(zhèn)江212003)

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

電子電路設(shè)計(jì);模2n+1乘法器;Booth/CSD編碼;余數(shù)系統(tǒng)

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

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

1.1 基8-Booth編碼模2n+1乘法器結(jié)構(gòu)

基8-Booth編碼的模2n+1乘法器［4-6］結(jié)構(gòu)圖如圖1所示，該結(jié)構(gòu)主要包括Booth編碼器、模部分積生成器、華萊士樹(shù)壓縮器［7］以及超前進(jìn)位模2n+ 1加法器。其中華萊士樹(shù)是由進(jìn)位保留加法器構(gòu)成，它能夠?qū)Σ糠址e進(jìn)行壓縮，將3個(gè)部分積壓縮成2個(gè)，從而減少相加部分積的個(gè)數(shù)，其結(jié)構(gòu)如圖2所示。

圖1 基8-Booth編碼模2n+1乘法器結(jié)構(gòu)

圖2 華萊士樹(shù)形結(jié)構(gòu)

1.2 基8-Booth編碼模2n+1乘法器設(shè)計(jì)算法推導(dǎo)

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

所以對(duì)AB的乘積取模2n+1運(yùn)算方法如下

為求出AB乘積取模的一般表達(dá)式，先假設(shè)一個(gè)中間變量PPi，并令

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

求出S1，S2，j，k的表達(dá)式如下

現(xiàn)求解|S1A2j|2n+1和|S2A2k|2n+1的值

由于

當(dāng) S1=1時(shí)，，對(duì)于無(wú)符號(hào)數(shù)m，有(m+ˉm)=2j-1，ˉm表示對(duì)m的二進(jìn)制表示各位取反。所以-m =ˉm-(2j-1)，最后得出:

當(dāng)S1=0時(shí)

當(dāng)S1=-1時(shí)

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

當(dāng)S2=0時(shí)

當(dāng)S2=1時(shí)

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

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

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

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

2.1 CSD/Booth編碼原理

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

表2 CSD/Booth編碼表

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

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

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

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

所以

而

令

可得出

2.2 FPGA仿真驗(yàn)證結(jié)果及性能比較

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

圖4 模28+1乘法器驗(yàn)證結(jié)果

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

表3 硬件資源消耗對(duì)比

3 結(jié)語(yǔ)

本文利用CSD/Booth混合編碼的方法實(shí)現(xiàn)了一個(gè)模2n+1乘法器，該乘法器同時(shí)結(jié)合了CSD編碼和Booth編碼的優(yōu)點(diǎn)，在取模運(yùn)算的譯碼過(guò)程中，利用簡(jiǎn)單的截位運(yùn)算替代查找表，有效的節(jié)省了硬件資源，并在一定程度上提高了模乘法器的運(yùn)算速度，為更加高效的模乘法器的設(shè)計(jì)提供了良好的思路。

［1］ 湯曉慧，楊軍，吳艷.基于Booth算法的32×32乘法器IP核設(shè)計(jì)［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］ 王定，余寧梅，張玉倫，等.改進(jìn)型booth華萊士樹(shù)的低功耗、高速并行乘法器的設(shè)計(jì)［J］.電子器件，2007，30(1):253-255.

［8］ 胡劍浩，馬上.余數(shù)系統(tǒng)原理與在高速數(shù)字信號(hào)處理中的應(yīng)用［M］.北京:科學(xué)出版社，2012:2-11.

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

［10］Meyer-Baese U.數(shù)字信號(hào)處理的FPGA實(shí)現(xiàn)［M］.北京:清華大學(xué)出版社，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并行乘法器設(shè)計(jì)［J］.現(xiàn)代電子技術(shù)，2003(5):21-25.

［13］周蜿婷，李磊.基4BOOTH編碼的高速32×32乘法器的設(shè)計(jì)與實(shí)現(xiàn)［J］.電子科技大學(xué)學(xué)報(bào)，2008，37:106-108.

王 敏(1974- )，女，漢族，重慶豐都人，江蘇科技大學(xué)副教授，碩士，主要研究方向?yàn)樾盘?hào)與信息處理，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