胡薇++崔曉平++陳鑫

摘 要： 冗余二進(jìn)制（RB）加法的進(jìn)位無關(guān)特性和規(guī)整的壓縮結(jié)構(gòu)，可以設(shè)計高速冗余二進(jìn)制乘法器。冗余二進(jìn)制乘法器由RB部分積產(chǎn)生、RB部分積壓縮樹和RB?二進(jìn)制數(shù)轉(zhuǎn)換器三個關(guān)鍵模塊構(gòu)成。在此基于基?16 RB Booth編碼結(jié)構(gòu)提出了一種由進(jìn)位跳躍加法器和并行前綴/進(jìn)位選擇混合加法器構(gòu)成的冗余二進(jìn)制?二進(jìn)制數(shù)轉(zhuǎn)換器。用Verilog HDL對該轉(zhuǎn)換器進(jìn)行描述，在Synopsys的VCS平臺上進(jìn)行仿真驗(yàn)證，在SMIC 45 nm的工藝下，通過Design Compiler 對轉(zhuǎn)換器進(jìn)行綜合，比較普通的并行前綴/進(jìn)位選擇轉(zhuǎn)換器，設(shè)計的64位轉(zhuǎn)換器在延時、面積和功耗得到有效的改善。

關(guān)鍵詞： RB?NB轉(zhuǎn)換器； 并行前綴加法器； 進(jìn)位跳躍加法器； 冗余二進(jìn)制乘法器

中圖分類號： TN710?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2015）10?0103?04

0 引 言

乘法器作為高速數(shù)字信號處理器（DSP）、微處理器、RISC和FIR數(shù)字濾波器等各類芯片中的必不可少的運(yùn)算邏輯單元，其性能的好壞對整個芯片系統(tǒng)有著極其重大的影響。因此，高速、低耗乘法器的設(shè)計一直是研究重點(diǎn)。乘法器能被分成3個步驟：

（1） 部分積的產(chǎn)生；

（2） 由部分積壓縮樹將所有的部分積壓縮至二行；

（3） 通過快速的二進(jìn)制加法器將最終的二行部分積相加得到乘積。

冗余二進(jìn)制（Redundant Binary，RB）數(shù)由Avizients最早提出的一種有符號數(shù)的表示方法[1]，利用冗余二進(jìn)制算法的進(jìn)位無關(guān)特性以及規(guī)整的結(jié)構(gòu)，可以設(shè)計出高速的RB并行乘法器[2?6]。RB并行乘法器主要由RB部分積產(chǎn)生、RB部分積壓縮樹和RB?NB轉(zhuǎn)換器3個關(guān)鍵模塊構(gòu)成。與一般二進(jìn)制（Normal Binary，NB）乘法器相類似，RB乘法器首先采用修正Booth算法（MBE）[7]將部分積的數(shù)目減少一半并將兩個相鄰的二行NB部分積轉(zhuǎn)換為一行RB部分積，然后采用由RB半加器和RB全加器構(gòu)成的RB部分積壓縮樹將RB部分積壓縮至一行，最終采用RB?NB轉(zhuǎn)換器[8?10]將RB部分積轉(zhuǎn)換成NB乘積。由RB并行乘法器的結(jié)構(gòu)可以看出，RB?NB轉(zhuǎn)換器處于整個RB乘法器的關(guān)鍵路徑上，它的性能對于整個乘法器的性能有著至關(guān)重要的影響。

RB部分積的產(chǎn)生過程中會產(chǎn)生一行修正字。由MBE算法產(chǎn)生部分積時，當(dāng)被乘數(shù)需要乘以-1或-2時，需要對被乘數(shù)取反，然后在部分積的最低位加1，因此產(chǎn)生+1修正值。當(dāng)兩行相鄰的NB部分積構(gòu)成一行RB部分積時，產(chǎn)生[-1]修正值。將修正 Booth編碼和RB編碼產(chǎn)生的修正值合并成一行修正字，可以一次性完成糾錯。對于N位權(quán)2字長N=2n的乘法器，共產(chǎn)生[N4]個RB部分積和額外的一行修正字，將[N4+1]個RB部分積，經(jīng)[log2N4+1=n-2]級壓縮后得到一行冗余二進(jìn)制數(shù)[2?6]。因此對于2n位乘法器，額外的一行修正字增加了一級壓縮，去除該行修正字可以減少一級壓縮，因此可以提高乘法器的速度并減少功耗。

比修正Booth編碼（又稱之為基?4 Booth編碼）更高級的Booth編碼可以進(jìn)一步減少部分積的個數(shù)，但是是以增加難倍數(shù)的數(shù)目為代價[11?13]。一個難倍數(shù)是指不是權(quán)2的倍數(shù)（例如3，5，6，7），因此對應(yīng)的部分積不能用簡單地左移和取補(bǔ)得到。文獻(xiàn)[13]提出由2個權(quán)2倍數(shù)的差來獲得難倍數(shù)（例如±3M=±（4M-1M），±6M=±（8M-2M）。文獻(xiàn)[12]提出了一個新的基-16 RB Booth編碼算法用來產(chǎn)生RB部分積，該算法可以避免高級Booth編碼的難倍數(shù)并且不產(chǎn)生額外的一行修正字。本文提出的64位RB?NB轉(zhuǎn)換器適用于消除修正字的RB Booth編碼乘法器。

RB?NB轉(zhuǎn)換器和加法器的硬件電路結(jié)構(gòu)是類似的[8?10，14]，因此定點(diǎn)加法器的結(jié)構(gòu)可以被應(yīng)用到RB?NB轉(zhuǎn)換器上。在64位基于基-16 RB Booth編碼的乘法器設(shè)計中，由于RB部分積壓縮后生成的RB數(shù)是逐級壓縮產(chǎn)生的，先產(chǎn)生的16位RB部分積采用結(jié)構(gòu)簡單的進(jìn)位跳躍加法器（Carry?Skip Adder，CSKA）完成轉(zhuǎn)換，最終產(chǎn)生的48位RB數(shù)采用并行前綴/進(jìn)位選擇混合加法器的結(jié)構(gòu)，最終得到一種新的進(jìn)位跳躍、并行前綴/進(jìn)位選擇混合的RB?NB轉(zhuǎn)換器。

用Verilog HDL對該轉(zhuǎn)換器進(jìn)行描述，在Synopsys的VCS平臺上進(jìn)行仿真驗(yàn)證，在SMIC 45 nm的工藝下，通過Design Compiler 對轉(zhuǎn)換器進(jìn)行綜合。比較普通的并行前綴/進(jìn)位選擇轉(zhuǎn)換器，建議的64位RB?NB轉(zhuǎn)換器在延時、面積和功耗得到有效的改善。

1 RB?NB轉(zhuǎn)換器與加法器

下面介紹一種RB?NB轉(zhuǎn)換器與加法器之間的映射關(guān)系，并且以此類推出所有加法器的硬件結(jié)構(gòu)可以被應(yīng)用到RB?NB轉(zhuǎn)換器上。

假設(shè)兩個n位二進(jìn)制數(shù)A、B組成一行RB數(shù)（A?B），其中[A=i=0n-1ai2i， B=i=0n-1bi2i， ai，bi∈{1，0} ；]設(shè)第i位的RB數(shù) [ri=ai-bi]，可以得到式（1）：

[A-B =i=0n-1（ai-bi）2i =i=0n-1ri2i， ri∈{-1，0，1}] （1）

可以得到RB?NB轉(zhuǎn)換方式。

同理，假設(shè)兩個n位正二進(jìn)制數(shù)A、B相加（A+B），其中[A=i=0n-1ai2i， B=i=0n-1bi2i， ai，bi∈{1，0} ；]設(shè)[ni=ai+bi]，可以得到式（2）：

[A+B =i=0n-1（ai+bi）2i =i=0n-1ni2i， ni∈{0，1，2}] （2）

可以得到兩個正NB數(shù)相加的編碼方式。

RB?NB轉(zhuǎn)換方式以及正NB數(shù)相加編碼方式如表1所示，ni和ri之間存在箭頭方向所示的映射關(guān)系：ni=1-ri。由ni和ri之間映射關(guān)系對ni和ri查找編碼表可以反推得到兩種編碼之間的映射關(guān)系為：x+位不變，x-位取反，如表2所示。由此可知，二進(jìn)制加法器中的所有結(jié)構(gòu)都可以用于構(gòu)成RB?NB轉(zhuǎn)換器，由RB?NB轉(zhuǎn)換器到加法器的映射關(guān)系，其他位不變，x-位取反，即在整個轉(zhuǎn)換設(shè)計中，反相器是惟一需要添加的硬件，也就是說，加法器的硬件結(jié)構(gòu)都可以被應(yīng)用到RB?NB轉(zhuǎn)換器上來。endprint

表1 編碼表

表2 映射關(guān)系表

第i位RB?NB轉(zhuǎn)換真值表[7]如表3所示。

表3 RB?NB轉(zhuǎn)換真值表

根據(jù)表3，可以得到[si]和[ci+1]的邏輯表達(dá)式如式（3）和式（4）所示：

[si=ci⊕x-i⊕x+i ] （3）

[ci+1=x-i+x+i+x-ix+i ?ci] （4）

從邏輯表達(dá)式（4）可以得出，加法器的電路結(jié)構(gòu)可以用于RB?NB轉(zhuǎn)換器的設(shè)計中，其進(jìn)位產(chǎn)生信號是[Gi=x-i+x+i]，進(jìn)位傳遞信號是[Pi=x-i?x+i]。

2 經(jīng)典加法器的原理

加法器是最通用的算術(shù)運(yùn)算，是計算機(jī)中最基本的運(yùn)算單元，有著極其廣泛的應(yīng)用。在計算速度要求的推動下，各種高性能的加法運(yùn)算不斷被推出。經(jīng)典的加法器結(jié)構(gòu)包括行波進(jìn)位加法器（Carry?Ripple Adder，CRA）、進(jìn)位跳躍加法器（Carry?Skip Adder，CSKA）、進(jìn)位選擇加法器（Carry Select Adder）、超前進(jìn)位加法器（Carry Look?ahead Adder，CLA）和并行前綴加法器（Parallel Prefix Adder，PPA）等[15?20]。其中最簡單的加法器是CRA，其速度也是最慢的，CLA能夠有效的提高進(jìn)位傳播的速度，進(jìn)位跳躍加法器和進(jìn)位選擇加法器的進(jìn)位傳播的速度居于兩者中間，他們的結(jié)構(gòu)相較于CLA來說相對簡單，PPA可以看成是CLA的改進(jìn)結(jié)構(gòu)。下面分別對進(jìn)位跳躍加法器和并行前綴加法器做具體的分析。

假設(shè)兩個n位二進(jìn)制數(shù)A和B相加，其第i位的被加數(shù)和加數(shù)分別為ai和bi，ci是低位的進(jìn)位輸入，則該位的進(jìn)位產(chǎn)生信號gi、進(jìn)位傳遞信號pi、和和位si以及向高位的進(jìn)位輸出信號ci+1由式（5）表示：

[gi =aibi pi =ai+bi si =ai⊕bi⊕ci ci+1=gi+pici ] （5）

4位進(jìn)位跳躍加法器的進(jìn)位輸出可以由式（6）表示如下：

[ci+4=gi+3+pi+3ci+3 =gi+3+pi+3gi+2+pi+3pi+2gi+1 +pi+3pi+2pi+1gi+pi+3pi+2pi+1pici =Gi+3：i+Pi+3：ici] （6）

式中：Gi+3：i是4位加法器的方塊進(jìn)位產(chǎn)生信號；Pi+3：i是4位加法器的方塊進(jìn)位傳遞信號。4位進(jìn)位跳躍加法器的結(jié)構(gòu)如圖1所示，它由一個4位CRA模塊外加一個4輸入的與門和一個二選一的數(shù)據(jù)選擇器組成。與門用來產(chǎn)生i～i+3位的方塊進(jìn)位傳遞信號Pi+3：i=pi+3pi+2pi+1pi，當(dāng)ci=0，初始化的方塊進(jìn)位輸出值ci+4′=Gi+3：i。當(dāng)進(jìn)位輸入信號產(chǎn)生時且方塊的初始化進(jìn)位輸出信號穩(wěn)定后，進(jìn)位輸出信號ci+4較進(jìn)位輸入信號有一個二選一數(shù)據(jù)選擇器的延時時間。將多個4位進(jìn)位跳躍加法器級聯(lián)起來可以以低的復(fù)雜度獲得較快的加法運(yùn)算[19]。

定義一種運(yùn)算，其運(yùn)算符為“[?]”。運(yùn)算規(guī)則為：

[（gi，pi）?（gi-1，pi-1）=（gi+pigi-1 ， pi-1pi）] （7）

則：

[（Gi：0，Pi：0）=（gi，pi）?（gi-1，pi-1）?????（g1，p1）?（g0，p0）] （8）

由式（5）可得第i位的進(jìn)位輸出信號為：

[ci+1=gi+pi·ci=gi+pi·（gi-1+pi-1·（gi-2+ pi-2·（gi-3+pi-3·（…+p0·cin）））） =gi+pi·gi-1+pi·pi-1·（gi-2+pi-2·（gi-3+pi-3· （…+p0·cin））） =Gi：0+Pi：0·cin] （9）

由式（8），式（9）可以看出，（Gi：0，Pi：0）可以由若干個式（7）所示的“[?]”運(yùn)算級聯(lián)得到。這就是并行前綴結(jié)構(gòu)的運(yùn)算原理，“[?]”運(yùn)算被稱為并行前綴運(yùn)算。

圖1 4位進(jìn)位跳躍加法器方塊

并行前綴加法器（PPA）可以看成是超前進(jìn)位加法器的改進(jìn)版，它通過前綴運(yùn)算單元進(jìn)行運(yùn)算，每個前綴運(yùn)算單元產(chǎn)生兩個信號：進(jìn)位產(chǎn)生信號和進(jìn)位傳遞信號。將每個前綴運(yùn)算單元以遞歸的方式連接起來，產(chǎn)生的進(jìn)位信號與被加數(shù)和加數(shù)一起異或運(yùn)算求和即可構(gòu)成并行前綴加法器。運(yùn)算時間方面，并行前綴結(jié)構(gòu)最快只需要log2 n級前綴運(yùn)算即可完成進(jìn)位輸出。從實(shí)現(xiàn)的角度看，并行前綴加法器將許多相同的前綴運(yùn)算單元采用樹形結(jié)構(gòu)連接而成，因此有著規(guī)整的結(jié)構(gòu)，易于VLSI設(shè)計。

3 64位RB?NB轉(zhuǎn)換器的優(yōu)化設(shè)計

采用基?16 RB Booth編碼，32位冗余二進(jìn)制乘法器產(chǎn)生8個RB部分積，經(jīng)3級壓縮（8→4→2→1）后得到一個冗余二進(jìn)制數(shù)，最后通過64位RB?NB轉(zhuǎn)換器得到二進(jìn)制數(shù)的乘積。為了提高轉(zhuǎn)換器的性能，64位RB?NB轉(zhuǎn)換器采用進(jìn)位跳躍、并行前綴/進(jìn)位選擇混合的二進(jìn)制加法器進(jìn)行設(shè)計。該轉(zhuǎn)換器由16位進(jìn)位跳躍加法器和48位并行前綴/進(jìn)位選擇混合加法器構(gòu)成。

RB部分積產(chǎn)生模塊由基?16 RB Booth編碼電路和解碼電路構(gòu)成，最終一行RB部分積的0～3位由Booth 解碼電路直接輸出，4～7位由第一級壓縮得到，8～15位由第二級壓縮得到，其余的48位RB部分積由第三級部分積壓縮的輸出得到。根據(jù)先產(chǎn)生先求和的原則，低16位RB數(shù)首先逐級進(jìn)行轉(zhuǎn)換，如果在高48位RB部分積產(chǎn)生之前，0～15位RB部分積已轉(zhuǎn)換完成，則轉(zhuǎn)換器的延時時間僅僅取決于高48位RB部分積的轉(zhuǎn)換時間。

16位進(jìn)位跳躍加法器的結(jié)構(gòu)圖如圖2所示，由于RB部分積的0～3 位由Booth 解碼電路直接輸出，它僅需1個4位CRA和3個4位CSKA模塊級聯(lián)即可。初始的一級為1個4位CRA，如果Δg表示進(jìn)位產(chǎn)生信號的延時時間，Δp表示gi+pici（或一級前綴運(yùn)算）的延時時間。則4位CRA進(jìn)位輸出信號的延時時間為Δg+3Δp，每多出一個4位CSKA模塊則增加一個二選一數(shù)據(jù)選擇器的延時，因此16位進(jìn)位跳躍加法器的進(jìn)位輸出信號的延時時間為Δg+6Δp。為了加快該加法器的速度，每個4位行波進(jìn)位加法器內(nèi)部采用由與或非和或與非門構(gòu)成互補(bǔ)的進(jìn)位輸出。

圖2 4個4位進(jìn)位跳躍加法器級聯(lián)

在加法器的眾多樹形結(jié)構(gòu)中，Kogge?Stone （KS）樹是理論上最快的樹形結(jié)構(gòu)，對于一個n位的加法，最終進(jìn)位信號只需要log2 n級延時即可產(chǎn)生。如圖3所示，高48位轉(zhuǎn)換器選取基于KS優(yōu)化結(jié)構(gòu)的并行前綴/進(jìn)位選擇混合加法器結(jié)構(gòu)。

圖3 設(shè)計的RB?NB轉(zhuǎn)換器結(jié)構(gòu)圖

與普通的并行前綴/進(jìn)位選擇混合加法器構(gòu)成的RB?NB轉(zhuǎn)換器相比，建議的 RB?NB轉(zhuǎn)換器的低16位采用改進(jìn)的進(jìn)位跳躍加法器，其復(fù)雜度和延時得到有效的改善。為了得到建議的64位RB?NB轉(zhuǎn)換器和并行前綴/進(jìn)位選擇混合加法器的延時、面積和功耗，使用Verilog HDL語言對其進(jìn)行描述并在VCS平臺上進(jìn)行仿真驗(yàn)證。在SMIC 45 nm CMOS標(biāo)準(zhǔn)工藝庫下，通過Synopsys公司綜合工具DC進(jìn)行綜合，最終得到64位RB?NB轉(zhuǎn)換器的綜合結(jié)果如表4 所示，優(yōu)化過的轉(zhuǎn)換器比普通的并行前綴/進(jìn)位選擇轉(zhuǎn)換器在延時、功耗、面積方面分別優(yōu)化了23.9%，13.0%，12.6%。

表4 64位RB?NB轉(zhuǎn)換器綜合結(jié)果

4 結(jié) 語

RB?NB轉(zhuǎn)換器處于RB乘法器的關(guān)鍵路徑上，它的性能對乘法器有著至關(guān)重要的影響。根據(jù)最終RB部分積生成的先后順序，對先生成的低16位數(shù)采取復(fù)雜度比較低的電路結(jié)構(gòu)以降低功耗，針對后生成的48位數(shù)據(jù)采用邏輯級數(shù)最少的KS結(jié)構(gòu)的并行前綴加法器以減少延時，雙管齊下，提高整個轉(zhuǎn)換器的性能。在SMIC 45 nm CMOS標(biāo)準(zhǔn)工藝庫下，通過Synopsys公司綜合工具Design Compiler進(jìn)行綜合，64位RB?NB轉(zhuǎn)換器的延時可達(dá)0.80 ns，功耗為327 μW，面積是1 639 μm2，與普通的并行前綴/進(jìn)位選擇轉(zhuǎn)換器相比，這些指標(biāo)分別優(yōu)化了23.9%，13.0%，12.6%。

參考文獻(xiàn)

[1] AVIZIENIS A. Signed?digit number representations for fast parallel arithmetic [J]. IRE Transactions on Electronic Computers， 1961， EC?10：389?400.

[2] TAKAGI N， YASUURA H， YAJIMA S. High?speed VLSI multiplication algorithm with a redundant binary addition tree [J]. IEEE Transactions on Computers， 1985， 100（9）： 789?796.

[3] EDAMATSU H， TANIGUCHI T， NISHIYAMA T， et al. A 33 MFLOPS floating point processor using redundant binary representation [C]// Proceedings of 1988 IEEE International Solid?State Circuits Conference. [S.l.]： IEEE， 1988： 152?159.

[4] MAKINO H， NAKASE Y， SUZUKI H， et al. An 8.8?ns 54×54?bit multiplier with high speed redundant binary architecture [J]. IEEE Journal of Solid?State Circuits， 1996， 31（6）： 773?783.

[5] KIM Y， SONG B S， GROSSPIETSCH J， et al. A carry?free 54b×54b multiplier using equivalent bit conversion algorithm [J]. IEEE Journal of Solid?State Circuits， 2001， 36（10）： 1538?1545.

[6] 崔曉平，高鵬輝，尹潔珺，等.54位高速冗余二進(jìn)制乘法器的設(shè)計[J].微電子學(xué)與計算機(jī)，2014（4）：140?143.

[7] MACSORLEY O L. High?speed arithmetic in binary computers [J]. Proceedings of the IRE， 1961， 49（1）： 67?91.

[8] HE Y， CHANG C H. A power?delay efficient hybrid carry?lookahead/carry?select based redundant binary to two's complement converter [J]. IEEE Transactions on Circuits and Systems I： Regular Papers， 2008， 55（1）： 336?346.

[9] WANG G， TULL M P. A new redundant binary number to 2's?complement number converter [C]// Proceedings of 2004 Region 5 Conference： Annual Technical and Leadership Workshop. [S.l.]： IEEE， 2004： 141?143.

[10] YEN S M， LAIH C S， CHEN C H， et al. An efficient redundant?binary number to binary number converter [J]. IEEE Journal of Solid?State Circuits， 1992， 27（1）： 109?112.

[11] LYU C N， MATULA D W. Redundant binary booth recoding [C]// Proceedings of 1995 the 12th Symposium on Computer Arithmetic. [S.l.]： IEEE， 1995： 50?57.

[12] HE Y， CHANG C H， GU J， et al. A novel covalent redundant binary Booth encoder [C]// Proceedings of 2005 IEEE International Symposium on Circuits and Systems. [S.l.]： IEEE， 2005： 69?72.

[13] BESLI N， DESHMUKH R G. A novel redundant binary signed?digit （RBSD） Booth's encoding [C]// Proceedings of 2002 IEEE Southeast Conference. [S.l.]： IEEE， 2002： 426?431.

[14] BLAIR G M. The equivalence of twos?complement addition and the conversion of redundant?binary to twos?complement numbers [J]. IEEE Transactions on Circuits and Systems Part 1： Fundamental Theory and Applications， 1998， 45： 669?671.

[15] SKLANSKY J. Conditional?sum addition logic [J]. IRE Transactions on Electronic Computers， 1960 （2）： 226?231.

[16] KOGGE P M， STONE H S. A parallel algorithm for the efficient solution of a general class of recurrence equations [J]. IEEE Transactions on Computers， 1973， 100（8）： 786?793.

[17] BRENT R P， KUNG H T. A regular layout for parallel adders [J]. EEE Transactions on Computers 1982， 31： 34?41.

[18] DIMITRAKOPOULOS G， NIKOLOS D. High?speed parallel?prefix VLSI ling adders [J]. IEEE Transactions on Computers， 2005， 54（2）： 225?231.

[19] 崔曉平，王成華.二級進(jìn)位跳躍加法器的優(yōu)化方塊分配[J].北京航空航天大學(xué)學(xué)報，2007，33（4）：495?499.endprint