梁曉雄，趙曙光，郭榮田

(東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海 201620)

?

基于硬件描述語(yǔ)言的可逆邏輯描述與驗(yàn)證方法

梁曉雄，趙曙光，郭榮田

(東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海 201620)

針對(duì)可逆邏輯綜合在設(shè)計(jì)較大規(guī)?？赡孢壿嬰娐分杏龅降钠款i，文中借助于硬件描述語(yǔ)言的高層次抽象描述能力以及現(xiàn)有EDA平臺(tái)的仿真驗(yàn)證功能，通過(guò)在模塊中添加輔助位的方法，使得模塊在具有相應(yīng)功能的同時(shí)具備可逆性，并對(duì)模塊進(jìn)行實(shí)例化，實(shí)現(xiàn)對(duì)可逆算術(shù)邏輯單元的描述與綜合。仿真驗(yàn)證表明，該方法具有一定的可行性和有效性。

可逆邏輯電路；硬件描述語(yǔ)言；可逆算術(shù)邏輯單元；仿真驗(yàn)證

LIANG Xiaoxiong, ZHAO Shuguang, GUO Rongtian

(School of Information Science and Technology, Donghua University, Shanghai 201620, China)

傳統(tǒng)邏輯的不可逆性是造成集成電路發(fā)熱的重要原因，也是影響集成電路發(fā)展的主要因素，為了降低能耗，可將不可逆操作改造為可逆操作[1]。由于可逆邏輯門(mén)均是可逆的，可以用可逆的設(shè)計(jì)方法級(jí)聯(lián)可逆邏輯門(mén)網(wǎng)絡(luò)，而不會(huì)因信息丟失產(chǎn)生熱耗散，從理論上解決芯片的發(fā)熱問(wèn)題。目前可逆邏輯優(yōu)化的規(guī)模性研究還處于起步階段，現(xiàn)有可逆邏輯功能電路的設(shè)計(jì)僅能勝任可逆加法器之類(lèi)的小規(guī)模簡(jiǎn)單電路[2]，因此，需要研究新的方法和途徑，實(shí)現(xiàn)較大規(guī)模、較復(fù)雜可逆邏輯電路的(半)自動(dòng)設(shè)計(jì)。

本文利用硬件描述語(yǔ)言高層次描述能力強(qiáng)，易于移植等特點(diǎn)，并借助現(xiàn)有EDA工具進(jìn)行仿真和驗(yàn)證，對(duì)自動(dòng)綜合后的電路根據(jù)預(yù)想要求進(jìn)行簡(jiǎn)單的人工干預(yù)，使得電路既能實(shí)現(xiàn)相應(yīng)功能，又能滿(mǎn)足可逆邏輯電路的設(shè)計(jì)要求。

1 Verilog描述可逆邏輯的一般方法

可逆邏輯可看作不可逆邏輯的一種特殊情況，Verilog作為一種專(zhuān)門(mén)用于描述常規(guī)邏輯的硬件描述語(yǔ)言[3]，也可嘗試用Verilog描述可逆邏輯電路。用Verilog描述電路時(shí)[4]，必須適當(dāng)添加控制位或者垃圾位保證輸入和輸出的數(shù)目相等。下面給出了不同可逆邏輯門(mén)的Verilog描述。

(1)CNOT門(mén)[5]。CNOT門(mén)有一個(gè)控制位和一個(gè)目標(biāo)位，當(dāng)控制位為1時(shí)，目標(biāo)位取反，當(dāng)控制位取0時(shí)，目標(biāo)位不變[6]，CNOT門(mén)可表示為

(1)

代碼如下：

module CNOT(A,T,A1,T1);

inputA,T;

outputA1;

wirey;

assignA1=A;

xor xor1(T1,T,A);

endmodule

CNOT門(mén)的RTL視圖如圖1所示。

圖1 CNOT門(mén)的RTL視圖

(2)Fredkin門(mén)[7]。Fredkin門(mén)即控制交換門(mén)，有3個(gè)輸入位，其中一個(gè)作為控制位，兩個(gè)作為目標(biāo)位當(dāng)控制位的值為1時(shí)，就交換兩個(gè)目標(biāo)位；當(dāng)控制位的值為0時(shí)，則輸出位保持不變。Fredkin門(mén)可表示為

(2)

代碼如下：

module

fredkin(X1,X2,X3,Y1,Y2,Y3);

inputX1,X2,X3;

wirew1,w2,w3,w4;

assignY1=X1;

and and 1(w2,X1,X3);

xor xor1(Y2,w1,w2);

and and4(w4,X1,X2);

xor xor2(Y3,w3,w4);

endmodule

Fredkin門(mén)的RTL視如圖2所示。

圖2 Fredkin門(mén)的RTL視圖

2 應(yīng)用分析

本文以可逆算術(shù)邏輯單元(ALU)為實(shí)例分析的對(duì)象，ALU作為較大規(guī)模、較復(fù)雜的常用功能單元電路，既是檢驗(yàn)和改進(jìn)可逆邏輯綜合方法的理想設(shè)計(jì)對(duì)象，又是未來(lái)量子計(jì)算機(jī)必不可缺的核心部件。因此，研究和設(shè)計(jì)可逆ALU[8-9]具有重要的理論價(jià)值和實(shí)際意義。

圖3 1位可逆加法器

2.1 可逆全加器的設(shè)計(jì)

對(duì)經(jīng)典全加器函數(shù)表達(dá)式進(jìn)行變換可得和函數(shù)

(3)

進(jìn)位函數(shù)

(4)均是異或表達(dá)式的形式，所以可通過(guò)可逆邏輯門(mén)相互級(jí)聯(lián)的形式得到如圖3所示的1位可逆加法器[10]。當(dāng)Ci=0時(shí)，實(shí)現(xiàn)可逆加法器的功能。將一位可逆加法器相互級(jí)聯(lián)便能得到如圖4所示的4位可逆全加器。

圖4 4位可逆加法器

2.2 可逆ALU的設(shè)計(jì)

為實(shí)現(xiàn)算術(shù)邏輯功能[11]，需要在可逆全加器的基礎(chǔ)上加一些輔助位和垃圾位。

(1)減法操作。減法操作可由加法操作變換而來(lái)，可在全加器的基礎(chǔ)上，以ai為目標(biāo)位添加一個(gè)控制位Cnot組成一個(gè)CNOT門(mén)，以Si為目標(biāo)位添加一個(gè)控制位Snot組成一個(gè)CNOT門(mén)，當(dāng)控制位Cnot和Snot同時(shí)為0時(shí)，實(shí)現(xiàn)加法操作，當(dāng)控制位同時(shí)為1時(shí)，實(shí)現(xiàn)減法操作；

(3)非操作。以ai為目標(biāo)位添加一個(gè)控制位Canot組成一個(gè)CNOT門(mén)，當(dāng)控制位Cnot為1時(shí)，實(shí)現(xiàn)ai取反操作，同理，bi取反也是如此；

圖5 4位可逆ALU的RLT視圖

圖6 16位可逆ALU的RLT視圖

如圖5所示，通過(guò)Verilog描述之后自動(dòng)生成4位可逆算術(shù)邏輯單元的RTL視圖，運(yùn)用Verilog特有的結(jié)構(gòu)化描述方式，對(duì)已定義好的可逆模塊實(shí)例化，使得模塊與模塊之間盡可能以最小的減少邏輯門(mén)和垃圾位的輸出，從而降低可逆邏輯電路的量子代價(jià)和功耗。圖6是在上述設(shè)計(jì)好的4位可逆ALU的基礎(chǔ)上進(jìn)一步通過(guò)級(jí)聯(lián)的方式生成的16位可逆ALU。表1詳細(xì)說(shuō)明了改變不同控制位時(shí)，相應(yīng)得到的不同算術(shù)邏輯功能。

表1 16位可逆ALU的功能表

圖7 16位可逆ALU仿真結(jié)果

如圖7是對(duì)設(shè)計(jì)出的16位可逆ALU進(jìn)行功能仿真結(jié)果，當(dāng)控制位Canot，Cbnot，Ccnot，Cccnot，Csnot，Cab分別取特定值時(shí)，能實(shí)現(xiàn)算術(shù)和邏輯功能。在仿真中，令A(yù)= 0110101001011010，B=0110100 101101100。由圖7可以看出，仿真結(jié)果符合預(yù)期目標(biāo)，本設(shè)計(jì)實(shí)現(xiàn)了可逆算術(shù)運(yùn)算和邏輯運(yùn)算，并通過(guò)硬件描述語(yǔ)言綜合出了可逆邏輯電路。

3 結(jié)束語(yǔ)

本文根據(jù)提出的基于硬件描述語(yǔ)言的可逆邏輯描述與驗(yàn)證方法，成功設(shè)計(jì)了16位可逆ALU，在一定程度上驗(yàn)證了方法的可行性，為設(shè)計(jì)較大規(guī)模、較復(fù)雜可逆邏輯電路提供了一種簡(jiǎn)潔和有效的途徑。此外，本文采用的結(jié)構(gòu)化描述方式能夠?qū)o(wú)用輸出最大程度轉(zhuǎn)化為有用輸入，減少了可逆電路中垃圾位的輸出，從而進(jìn)一步減少了電路的能耗損失。

[1] 管致錦.可逆邏輯綜合[M].北京:科學(xué)出版社,2011.[2] 管致錦,秦小麟,葛自明.量子電路可逆邏輯綜合的研究及進(jìn)展[J].南京郵電大學(xué)學(xué)報(bào)：自然科學(xué)版,2007,27(2):24-27.

[3] 吳繼華,王誠(chéng).設(shè)計(jì)與驗(yàn)證:Verilog HDL[M].北京:人民郵電出版社,2006.

[4] Drechsler R, Wille R. From truth tables to programming languages: progress in the design of reversible circuits[J]. Proceedings of the International Symposium on Multiple Valued Logic,2011,4(10):78-85.

[5] Feynman R.Quantum mechanical com-puters[J].Foundations of Physics,1986,16(6):507-531.

[6] Sayeeda Sultana，Katarzyna Radecka.Rev-map: a direct gateway from classical irreversible net-work to reversible networks[C].Tuusula:IEEE on Multiple-Valued Logic,2011.

[7] Fredkin E,Toffoli T.Conservative logic[J].International Journal of Theoretical Physics,1982(21):219-253.

[8] Oskin M,Chong F T，Chuang I L.A practical architecture for reliable quantum com-puters[J].Computer,2002(35):79-87.

[9] Matthew Morrison，Nagarajan Ranganathan.Design of a reversible ALU based on novel pro-grammable reversible logic gate struc-tures[C].Chennai:IEEE Computer Society Annual Symposium on VLSI,2011.

[10] Cheng K W,Tseng C C.Quantum full adder and subtractor[J].Electronic Letters,2002,38(22):1343-1344.

[11] Guan Zhijin,Li Wenjuan,Ding Weiping,et al. An arithmetic logic unit design based on reversible logic gates[C].Victoria:IEEE Pacific Rim Conference on Communications, Computers and Signal Processing,2011.

Reversible Logic Description and Verification Based on Hardware Description Language

The high level abstract description capability of the hardware description language and simulation capability of the current EDA platform are combined to resolve the bottleneck in the design of large-scale reversible logic circuits by reversible logic synthesis. Service bits are added to the module, which offers the module both a corresponding function and reversibility. The module is also instantiated for the reversible arithmetic logic unit to be described and synthesized. The simulations show that the proposed method is feasible and effective.

reversible logic circuit; hardware description language; reversible arithmetic logic unit; simulation verification

2015-12-21

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272224)

梁曉雄(1991-)，男，碩士研究生。研究方向：可逆邏輯綜合等。趙曙光(1965-)，男，博士，教授。研究方向：電子設(shè)計(jì)伺動(dòng)化等。

10.16180/j.cnki.issn1007-7820.2016.10.001

TN79+1

A

1007-7820(2016)10-001-04