基于常规逻辑门和原理图方式的可逆逻辑描述

郭荣田，赵曙光，梁晓雄

(东华大学 信息科学与技术学院，上海201620)



基于常规逻辑门和原理图方式的可逆逻辑描述

郭荣田，赵曙光，梁晓雄

(东华大学 信息科学与技术学院，上海201620)

针对可逆逻辑综合在设计较大规模可逆逻辑电路(ALU)时遇到的瓶颈问题。文中借用现行EDA技术的逻辑描述和验证能力，可逆逻辑门的功能表达式为依据，设计具有等功能的常规逻辑组合电路，通过等功能代换的方法，设计实现以常规原理图方式描述的可逆ALU。仿真图中显示的16种运算结果表明，该方法具有一定的可行性和有效性。

原理图方式；常规逻辑；可逆逻辑；等功能代换；功能性描述和验证

可逆逻辑可根除源于信息损失的功耗，因而被视为未来集成电路发展的必由之路，同时也是研究和实现量子计算(机)的专业基础[1]。但目前对于可逆逻辑的研究尚处于起步阶段，在可综合(设计)的电路规模及其复杂程度上遇到了瓶颈[2]。而常规(非可逆)逻辑设计经过长期发展，已形成相当成熟的理论体系和技术平台，特别是功能强大、使用方便的EDA技术和工具[3]。若能将其巧妙移植、复用于可逆逻辑设计，极有可能获得突破性的成功。本文研究和利用常规逻辑门(组合)与可逆逻辑门(组合)之间的等功能代换，以原理图的方式描述可逆逻辑电路，进而利用QuartusII对其进行功能仿真。仿真结果表明该方法具有一定可行性和有效性。

1　非可逆逻辑门的量子可逆实现

1.1非可逆逻辑的量子可行性分析

在量子信息理论中，量子信息的基本单位是量子比特，n位量子态可以写成

(1)

不同于经典逻辑网络，量子态在量子网络上的演化是可逆的[4-5]。因此，经典非可逆门用量子逻辑网络来实现时，必须添加辅助量子位，或称冗余量子位。

假设要实现的n位逻辑函数的向量形式

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

(2)

其中，ai=aj，输入量子态i和j有相同的输出量子态ai，输出与输入不是一一映射，所以函数关系为非可逆。添加冗余量子位后变为

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

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

(3)

由上式可以看出，输出中有2个2ai和2个2ai+l，并没有解决原来输出与输入不一一对应的问题。在定义域和值域间附加约束条件

(4)

最终逻辑函数的向量形式为

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，因此总的输出结果也不相等。可见，从数学结构上看，非可逆逻辑电路可以通过添加辅助位实现可逆化。因此实现非可逆逻辑门的可逆转化也是有可能的。

1.2可逆逻辑门的等功能转换

经典逻辑门中，除了非门是可逆的以外，其他都是不可逆的，但通过引入辅助位或者等功能转换的方法，分别构造可实现各种可逆逻辑门规定的常规逻辑门组合，用于替代可逆网络中的可逆逻辑门，即可利用常规逻辑门和原理图方式描述可逆逻辑功能。常用可逆逻辑门有CNOT门[6]、Toffoli系列门[7]、Fredkin门等。下面给出Toffoli系列门的等功能表达式、转换替代后的电路图。

(1)CCNOT(Toffoli门)。当ToffoliGate(TG)门的两个控制位元都是“1”时，才会使目标位C做取反操作[6]。与其功能相同的常规逻辑门组合图如图1所示，这里可以用异或门和与门组合实现替换。

图1　与Toffoli门等功能的常规逻辑电路

(2)4输入Toffoli门。4输入TG门其实就是在Toffoli门的基础上又加入了一个控制位元，当3个控制位元都是“1”时，才会使目标位X4做取反操作[8]。与其功能相同的常规逻辑门组合图如图2所示，由两个与门和异或门级联构成。

图2　与4输入Toffoli门等功能的常规逻辑电路

3　设计实例

首先基于可逆逻辑门的可逆算术/逻辑单元ALU[9]包括若干个可逆函数发生器(FUNC)和若干个可逆可控单元(DXOR)，其中FUNC和DXOR单元通过若干个TG级联。通过封装常规逻辑门组合电路，将替代对应等功能的可逆逻辑门，构成基于常规逻辑门的ALU[10-11]。图3是FUNC的电路图，其逻辑表达式为

(6)

(7)

图4是DXOR的电路图，其逻辑表达式为

F1=A⊕B⊕C

(8)

图3　FUNC的电路图

图4　DXOR的电路图

图5　基于常规逻辑门的可逆ALU电路图

图5为级联构成的可逆ALU的整体逻辑图，只运用了Toffoli门。即由输入端输入Ai、Bi、S0-S3信号，经过FUNC之后产生输出Xi、Yi，Xi、Yi信号除了作为DXOR输入信号A、B，而且与M信号进行运算得到DXOR输入信号C。为了实现算术和逻辑两种运算方式，引入M控制信号，M最终决定了控制C输入端的信号，其关系如下：Cin是最低位进位输入，M用来控制计算模式，M=1时封锁各位进位输出，实现逻辑运算，M=0且Cin=1时实现算术运算。图中输出端未标字母的输出端是垃圾输出。

(9)

(10)

当i≥2时， Ci=Yi+XiCi-1+M

(11)

表1是可逆ALU的功能表。其中给出的算术运算使用补码表示；“+”表示逻辑加，不考虑进位；“加”表示算术加，考虑进位；减法使用补码相加方法进行。

图6是可逆ALU的算术运算仿真结果，图中function是功能方式的选择位S0～S3信号，A、B是两个输入值，最右端是低位。sum是在选择不同的功能时对应的结果，除了最右边的是最高位之外，其余4位的读值顺序是依次由左到右，例如，M= 0且Cin= 1，在S0-S3=01101时，也就是减法功能：A 减B加1。A=0011，B=0101，sum=11011，最高位1是下一次位的借位输入。图7是可逆ALU的逻辑运算的仿真结果，此时有M=1时，在S0-S3=0110时，也就是逻辑功能异或运算。A=0011，B=0101，sum=01101。

图6　算术运算仿真结果

图7　逻辑运算仿真结果

4　结束语

从上述分析和设计实例可见，文中提出的基于常规逻辑门和原理图方式的可逆逻辑描述方法，在一定程度上对于其功能描述和验证是可行和有效的，有助于显著提高可逆逻辑的综合胜任规模和复杂程度。而且当前计算机处理的字长越来越多，文中的ALU在原理上恰好可以级联成任意位数的运算单元，实现多种算术和逻辑运算。其次，在设计过程中，最大限度的使用转化后的可逆逻辑部分的输出端信号，从而减少了可逆逻辑门和垃圾输出的个数，使得电路的实现代价有所减少。

但经典逻辑门大多是多输入输出，通过组合电路，或增加输出位数使输出输入位相等，所构成的电路图会有复杂性的短板，还需进一步地优化和改善电路。另外，文中利用与门、或门、或非门组合等功能替换相应可逆逻辑门构建可逆逻辑电路的方法，对于拥有反馈的常规逻辑电路无法实现其可逆化，所以常规时序电路的可逆化开发也亟待解决。

[1]沈先坤. 可逆逻辑电路综合技术研究[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].计算机工程与科学,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]赵曙光.可编程器件技术原理与技术开发[M]. 西安：西安电子科技大学出版社,2011.

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

[10] 施洋. 量子可逆组合逻辑器件的设计与研究[D]. 南昌：华东交通大学,2012.

[11] 李彦成. 量子可逆逻辑电路的设计及优化[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-)，女，硕士研究生。研究方向：电子设计。

10.16180/j.cnki.issn1007-7820.2016.09.038

TN79+1

A

1007-7820(2016)09-139-04