基于常規(guī)邏輯門和原理圖方式的可逆邏輯描述

郭榮田，趙曙光，梁曉雄

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

?

基于常規(guī)邏輯門和原理圖方式的可逆邏輯描述

郭榮田，趙曙光，梁曉雄

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

針對可逆邏輯綜合在設(shè)計較大規(guī)?？赡孢壿嬰娐?ALU)時遇到的瓶頸問題。文中借用現(xiàn)行EDA技術(shù)的邏輯描述和驗證能力，可逆邏輯門的功能表達式為依據(jù)，設(shè)計具有等功能的常規(guī)邏輯組合電路，通過等功能代換的方法，設(shè)計實現(xiàn)以常規(guī)原理圖方式描述的可逆ALU。仿真圖中顯示的16種運算結(jié)果表明，該方法具有一定的可行性和有效性。

原理圖方式；常規(guī)邏輯；可逆邏輯；等功能代換；功能性描述和驗證

可逆邏輯可根除源于信息損失的功耗，因而被視為未來集成電路發(fā)展的必由之路，同時也是研究和實現(xiàn)量子計算(機)的專業(yè)基礎(chǔ)[1]。但目前對于可逆邏輯的研究尚處于起步階段，在可綜合(設(shè)計)的電路規(guī)模及其復(fù)雜程度上遇到了瓶頸[2]。而常規(guī)(非可逆)邏輯設(shè)計經(jīng)過長期發(fā)展，已形成相當成熟的理論體系和技術(shù)平臺，特別是功能強大、使用方便的EDA技術(shù)和工具[3]。若能將其巧妙移植、復(fù)用于可逆邏輯設(shè)計，極有可能獲得突破性的成功。本文研究和利用常規(guī)邏輯門(組合)與可逆邏輯門(組合)之間的等功能代換，以原理圖的方式描述可逆邏輯電路，進而利用QuartusII對其進行功能仿真。仿真結(jié)果表明該方法具有一定可行性和有效性。

1　非可逆邏輯門的量子可逆實現(xiàn)

1.1非可逆邏輯的量子可行性分析

在量子信息理論中，量子信息的基本單位是量子比特，n位量子態(tài)可以寫成

(1)

不同于經(jīng)典邏輯網(wǎng)絡(luò)，量子態(tài)在量子網(wǎng)絡(luò)上的演化是可逆的[4-5]。因此，經(jīng)典非可逆門用量子邏輯網(wǎng)絡(luò)來實現(xiàn)時，必須添加輔助量子位，或稱冗余量子位。

假設(shè)要實現(xiàn)的n位邏輯函數(shù)的向量形式

fq(0,1,…,2n-1)=(a0,a1,…,ai,…,aj,…,a2n-1)

(2)

其中，ai=aj，輸入量子態(tài)i和j有相同的輸出量子態(tài)ai，輸出與輸入不是一一映射，所以函數(shù)關(guān)系為非可逆。添加冗余量子位后變?yōu)?/p>

fq(0,1,…,2n+1-1)=(2a0,2a0+1,…,2ai,

2ai+1,…,2aj,2aj+1,…,2a2n-1+1)

(3)

由上式可以看出，輸出中有2個2ai和2個2ai+l，并沒有解決原來輸出與輸入不一一對應(yīng)的問題。在定義域和值域間附加約束條件

(4)

最終邏輯函數(shù)的向量形式為

fq(2(a0,a1,…,a2n-1))=

2(0,1,…,2n-1)+(a0,a1,…,a2n-1)

(5)

此時，新的2i和2j的輸出值分別為2i+ai和2j+aj。ai=aj但2i≠2j，因此總的輸出結(jié)果也不相等?？梢?，從數(shù)學結(jié)構(gòu)上看，非可逆邏輯電路可以通過添加輔助位實現(xiàn)可逆化。因此實現(xiàn)非可逆邏輯門的可逆轉(zhuǎn)化也是有可能的。

1.2可逆邏輯門的等功能轉(zhuǎn)換

經(jīng)典邏輯門中，除了非門是可逆的以外，其他都是不可逆的，但通過引入輔助位或者等功能轉(zhuǎn)換的方法，分別構(gòu)造可實現(xiàn)各種可逆邏輯門規(guī)定的常規(guī)邏輯門組合，用于替代可逆網(wǎng)絡(luò)中的可逆邏輯門，即可利用常規(guī)邏輯門和原理圖方式描述可逆邏輯功能。常用可逆邏輯門有CNOT門[6]、Toffoli系列門[7]、Fredkin門等。下面給出Toffoli系列門的等功能表達式、轉(zhuǎn)換替代后的電路圖。

(1)CCNOT(Toffoli門)。當ToffoliGate(TG)門的兩個控制位元都是“1”時，才會使目標位C做取反操作[6]。與其功能相同的常規(guī)邏輯門組合圖如圖1所示，這里可以用異或門和與門組合實現(xiàn)替換。

圖1　與Toffoli門等功能的常規(guī)邏輯電路

(2)4輸入Toffoli門。4輸入TG門其實就是在Toffoli門的基礎(chǔ)上又加入了一個控制位元，當3個控制位元都是“1”時，才會使目標位X4做取反操作[8]。與其功能相同的常規(guī)邏輯門組合圖如圖2所示，由兩個與門和異或門級聯(lián)構(gòu)成。

圖2　與4輸入Toffoli門等功能的常規(guī)邏輯電路

3　設(shè)計實例

首先基于可逆邏輯門的可逆算術(shù)/邏輯單元ALU[9]包括若干個可逆函數(shù)發(fā)生器(FUNC)和若干個可逆可控單元(DXOR)，其中FUNC和DXOR單元通過若干個TG級聯(lián)。通過封裝常規(guī)邏輯門組合電路，將替代對應(yīng)等功能的可逆邏輯門，構(gòu)成基于常規(guī)邏輯門的ALU[10-11]。圖3是FUNC的電路圖，其邏輯表達式為

(6)

(7)

圖4是DXOR的電路圖，其邏輯表達式為

F1=A⊕B⊕C

(8)

圖3　FUNC的電路圖

圖4　DXOR的電路圖

圖5　基于常規(guī)邏輯門的可逆ALU電路圖

圖5為級聯(lián)構(gòu)成的可逆ALU的整體邏輯圖，只運用了Toffoli門。即由輸入端輸入Ai、Bi、S0-S3信號，經(jīng)過FUNC之后產(chǎn)生輸出Xi、Yi，Xi、Yi信號除了作為DXOR輸入信號A、B，而且與M信號進行運算得到DXOR輸入信號C。為了實現(xiàn)算術(shù)和邏輯兩種運算方式，引入M控制信號，M最終決定了控制C輸入端的信號，其關(guān)系如下：Cin是最低位進位輸入，M用來控制計算模式，M=1時封鎖各位進位輸出，實現(xiàn)邏輯運算，M=0且Cin=1時實現(xiàn)算術(shù)運算。圖中輸出端未標字母的輸出端是垃圾輸出。

(9)

(10)

當i≥2時， Ci=Yi+XiCi-1+M

(11)

表1是可逆ALU的功能表。其中給出的算術(shù)運算使用補碼表示；“+”表示邏輯加，不考慮進位；“加”表示算術(shù)加，考慮進位；減法使用補碼相加方法進行。

圖6是可逆ALU的算術(shù)運算仿真結(jié)果，圖中function是功能方式的選擇位S0～S3信號，A、B是兩個輸入值，最右端是低位。sum是在選擇不同的功能時對應(yīng)的結(jié)果，除了最右邊的是最高位之外，其余4位的讀值順序是依次由左到右，例如，M= 0且Cin= 1，在S0-S3=01101時，也就是減法功能：A 減B加1。A=0011，B=0101，sum=11011，最高位1是下一次位的借位輸入。圖7是可逆ALU的邏輯運算的仿真結(jié)果，此時有M=1時，在S0-S3=0110時，也就是邏輯功能異或運算。A=0011，B=0101，sum=01101。

圖6　算術(shù)運算仿真結(jié)果

圖7　邏輯運算仿真結(jié)果

4　結(jié)束語

從上述分析和設(shè)計實例可見，文中提出的基于常規(guī)邏輯門和原理圖方式的可逆邏輯描述方法，在一定程度上對于其功能描述和驗證是可行和有效的，有助于顯著提高可逆邏輯的綜合勝任規(guī)模和復(fù)雜程度。而且當前計算機處理的字長越來越多，文中的ALU在原理上恰好可以級聯(lián)成任意位數(shù)的運算單元，實現(xiàn)多種算術(shù)和邏輯運算。其次，在設(shè)計過程中，最大限度的使用轉(zhuǎn)化后的可逆邏輯部分的輸出端信號，從而減少了可逆邏輯門和垃圾輸出的個數(shù)，使得電路的實現(xiàn)代價有所減少。

但經(jīng)典邏輯門大多是多輸入輸出，通過組合電路，或增加輸出位數(shù)使輸出輸入位相等，所構(gòu)成的電路圖會有復(fù)雜性的短板，還需進一步地優(yōu)化和改善電路。另外，文中利用與門、或門、或非門組合等功能替換相應(yīng)可逆邏輯門構(gòu)建可逆邏輯電路的方法，對于擁有反饋的常規(guī)邏輯電路無法實現(xiàn)其可逆化，所以常規(guī)時序電路的可逆化開發(fā)也亟待解決。

[1]沈先坤. 可逆邏輯電路綜合技術(shù)研究[D]. 南京：南京航空航天大學,2014.

[2]MahammadSN,VeezhinathanK.Constructingonlinetestablecircuitsusingreversiblelogic[J].IEEETransactionsonInstrumentationandMeasurement, 2010,59(1):101-109.

[3]管致錦，秦小麟，葛自明.量子電路可逆邏輯綜合的研究及進展[J].南京郵電大學學報,2007,2(27):24-26.

[4]BarencoA,BennettCH,CleveR,etal.Elementarygatesforquantumcomputation[J].PhysicsReviewA, 1995, 52(5):3457-3467.

[5]林家逖,任德龍,田欣,等.經(jīng)典邏輯門與量子邏輯門之比較[J].計算機工程與科學,2005,27(11):93-97.

[6]RichardPFeynman.Quantummechanicalcomputers[J].OpticalNews, 1985,11(2):11-20.

[7]SultanaS,RadeckaK.Rev-map:adirectgatewayfromclassicalirreversiblenetworktoreversiblenetwork[C].Tuusula：41stIEEEInternationalSymposiumonMultiple-ValuedLogic, 2011.

[8]趙曙光.可編程器件技術(shù)原理與技術(shù)開發(fā)[M]. 西安：西安電子科技大學出版社,2011.

[9]HaghparastM,JassbiSJ,NaviK,etal.DesignofanovelreversiblemultipliercircuitusingHNGgateinnanotechnology[J].WorldAppliedSciences, 2008,3(6):974-978.

[10] 施洋. 量子可逆組合邏輯器件的設(shè)計與研究[D]. 南昌：華東交通大學,2012.

[11] 李彥成. 量子可逆邏輯電路的設(shè)計及優(yōu)化[D]. 南昌：華東交通大學,2014.

Reversible Logic Description Based on Conventional Logic Gates and Schematics

GUORongtian,ZHAOShuguang,LIANGXiaoxiong

(SchoolofInformationScienceandTechnology,DonghuaUniversity,Shanghai201620,China)

Foroftheencountered,thispaperadoptsthelogicdescriptionandverificationcapabilityofthecurrentEDAtechnologytodesignclassicallogiccircuitsasthereplacementofreversiblelogicgatesbasedonfunctionalexpressionstosolvethebottlenecksofreversiblelogicsynthesisincaseofgreatcircuitscaleandcomplexity.ThereversibleALU,describedwithconventionallogicdiagram,implementssixteenlogicoperations.Experimentalresultsshowthattheproposedmethodisfeasibleandeffective.

schematic;conventionallogic;reversiblelogic;functionreplacement;functiondescriptionandsimulation

2015- 12- 11

郭榮田(1992-)，女，碩士研究生。研究方向：電子設(shè)計。

10.16180/j.cnki.issn1007-7820.2016.09.038

TN79+1

A

1007-7820(2016)09-139-04