可逆逻辑电路逻辑图及波形图图示化方法

段雪利，赵曙光，冯若飞

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



可逆逻辑电路逻辑图及波形图图示化方法

段雪利，赵曙光，冯若飞

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

针对以逻辑表达式给定的可逆逻辑电路进行分析，并绘制出其可逆逻辑电路图，仿真出波形图，并将由仿真结果得到的真值表进行可逆化构造。利用C语言编程实现，将相关结果以更直观的形式展现，这在可逆逻辑电路的研究中具有创新性。

可逆逻辑电路；逻辑电路图；仿真波形图；可逆真值表

可逆逻辑电路及相关问题的研究源于对可逆计算理论的探索。可逆计算[1]是一门新兴的研究领域。可逆逻辑电路[2-3](Reversible Logic Circuit)是能实现可逆计算的电路，由若干量子逻辑门[4]级联而成，是对量子信息作一系列幺正变换以实现指定的逻辑功能，代表着可逆信息处理中以软/硬件实现的可逆操作序列。虽对于可逆逻辑的研究，国内外均取得了一定的研究成果，但可逆逻辑电路的研究仍处于初级阶段。

本文针对以可逆逻辑表达式组给定的可逆逻辑电路，通过智能分析绘制出其可逆逻辑电路图，进而根据其输入状态进行仿真，将仿真结果图形化显示，并对其真值表可逆性进行判断，针对不可逆的真值表进行可逆化构造。以上算法通过C语言实现，并通过具体的实验实例来对结果进行验证。

1 可逆逻辑电路图及波形图图示化方法

1.1 可逆逻辑电路图构造

可逆逻辑门的表示方法是以异或运算为基础，可逆逻辑函数采用“积之异或和”(ESOP)表达式取代“积之和”(SOP)表达式，所以可逆逻辑电路的构造采用ESOP表达式(组)进行可逆逻辑门的级联[5]。利用MCMT门即可实现可逆逻辑电路图的构造[6]，具体步骤如下：

步骤1 根据输入变量数设置控制位集合；

步骤2 添加一位辅助位作为目标位，并初始化到0状态；

步骤3 依次为每个积项(AND项)添加一个MCMT门，这个MCMT门的控制端作用于该积项中的各个变量；

步骤4 每个MCMT门的控制位作用于目标位，作为最后的输出。

图1 用MCMT门构造可逆电路

其中，“●”和“○”表示控制端；“●”表示当该控制位的值为真时才对目标位起作用；“○”表示当该控制位的值为假时才对目标位起作用；“⊕”表示受控端。

1.2 电路仿真及真值表可逆化构造

因可逆逻辑电路的逻辑函数[7]是以“积之异或和”(ESOP)表达式给出的，所以针对给定的可逆逻辑电路表达式组，在对其仿真之前要先获取其的全部输入状态，然后根据其给定的具体表达式进行相应的逻辑运算，即可仿真出其全部输出状态。

三输入-三输出的逻辑电路表达式组为

(1)

此电路表达式的输入状态分别为000、001、010、011、100、101、110、111。将8个状态代入表达式中,进行相应的逻辑运算得到该三输入三输出表达式的真值表。输出状态中有4个同时为000，这就违背了可逆逻辑电路输入与输出相映射的原则[8]。因此，要对该逻辑函数的真值表进行可逆化构造[9]，构造的基本原则是添加辅助位，其中,c为输入辅助位；g为输出辅助位，输入添至前端，输出添至后端。构造后的真值表如表1所示。

表1 构建后的可逆真值表

2 编程实现与结果验证

上文阐述了针对给定的可逆逻辑表达式组，绘制其可逆逻辑电路、仿真以及对非可逆真值表可逆化构造的详细步骤，以下将用C语言实现上述功能，以更形象的方式表现可逆逻辑组合电路的输入输出关系，并分析可逆逻辑电路的功能与需求。

2.1 可逆逻辑电路图构造

步骤1 表达式输入。可逆逻辑电路的表达式为“积之异或和”(ESOP)形式，输入表达式时无法直接输入“⊕”，故采用键盘上的“*”键替代，并用A、B、C、D等字母代替各输入(其中大写字母代表输入为真，小写字母代表输入为假)，上文中三输入三输出函数即可表示为

(2)

步骤2 表达式读入与检测。将步骤1中的表达式在txt文件中输入，如图2所示。由程序来访问该txt文件，程序依次读入3个表达式，得出输入和输出的个数，并将输入中相应的“A”、“B”、“C”、“D”等字母转化为对应的ASCII码存入数组中待用。根据输入和输出的个数确定控制线和目标线的个数。

图2 txt中表达式输入

步骤3 绘制区域划分。根据屏幕的分辨率划分绘制区域，并根据输入输出数的多少决定可逆逻辑网络中每一个乘积项之间的距离；

步骤4 控制线绘制。根据输入个数绘制输入控制线，并根据输入输出的个数确定控制线下方辅助线的个数，在控制线及辅助线的左端标注字母进行区分，控制线的左端标注字母从“A”开始依次类推，辅助线左端全部置“0”；

步骤5 控制点绘制。从逻辑函数中的“F1”开始绘制控制点，其中大写字母表示输入为真，在相应位置绘制实心圆，小写字母表示输入为假，在相应位置绘制空心圆，绘制的具体位置根据每个字母的ASCII码与“A”的ASCII差值决定。

步骤6 目标位绘制。根据“F1”、“F2”、“F3”3个表达式中“*”符号的个数，在该表达式对应的辅助线上绘制异或圆，异或圆的半径要大于控制点的半径以便区分。

此时所有步骤完成，点击程序运行按键开始执行，绘制出的可逆逻辑电路如图3所示。

图3 可逆逻辑电路图显示结果

2.2 电路仿真及可逆化真值表构造

识别表达式后根据表达式中输入的个数生成输入状态，如有3个状态则输入状态为000～111，有4个输入则输入状态为0000～1111，依此类推。然后根据输入状态进行相应的逻辑运算生成输出状态：计算出单独每个积项的值之后，再根据异或运算的规则运算出该输出的状态。根据输入输出状态绘制的仿真波形图，如图4所示。

图4 仿真波形图结果

下面将对该仿真结果的可逆性进行检测：将输出状态由二进制转化为十进制存放于数组，然后对数组中数字检测是否有相同数字，并将该相同数字的二进制输出。该例中检测出有3个相同的“0”，输出其二进制“000”，其对应的真值表不可逆，需为其添加辅助位进行可逆化构造。判断相同输出的个数，并根据相同的个数决定添加辅助位的个数，其中输入辅助位添加至输入前端，输出辅助位添加至输出后端[10]，本例具体添加情况详见表1。最后将可逆构造后的真值表输出至txt文件中，如图5所示。

图5 构造后的可逆真值表输出结果

其中，“i”、“o”分别表示输入和输出，经过可逆化构造后输入和输出实现了相互映射。

3 结束语

介绍了可逆逻辑电路，进而阐述识别输入的可逆逻辑表达式组生成可逆逻辑电路的具体步骤，以及通过仿真生成波形图并加以图示化的详细过程，判断生成真值表的可逆性，对于不可逆真值表进行可逆化构造。通过C语言实现上述算法，并用具体实例验证，实现了由逻辑表达式到逻辑电路、波形图、真值表之间的转化，这些研究为分析、理解和优化可逆逻辑电路提供了帮助。

[1] Nielsen M,Chuang I. Quantum computation and quantum information[M]. Cambridge:Cambridge University Press, 2000.

[2] Bennett C H. Logical reversibility of computation[J].IBM Journal of Research & Development, 1973, 17(6):525-532.

[3] Shende V V, Prasad A K, Markov I L, et al. Synthesis of reversible logic circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003, 22(6):710-722.

[4] Fu Youfan,Chao Zhao,Qian Qile.The research on matrix transformation of 2-level quantum logic gates[C].Lanzhou:International Computer Conference on Wavelet Active Media Technology & Information Processing, 2013,9(3):231-234.

[5] 管致锦.可逆逻辑综合[M].北京:科学出版社,2011.

[6] Maslov D, Dueck G W. Reversible cascades with minimal garbage[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004, 23(11):1497-1509.

[7] Sleator T, Weinfurter H. Realizable universal quantum logic gates [J]. Physical Review Letters, 1995, 74(20):4087-4090.

[8] Rosenblum A. The quantum mechanical computer[M].MA,USA:Information Dynamics, Springer US, 1991.

[9] Gupta P, Agrawal A, Jha N K. An algorithm for synthesis of reversible logic circuits[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(11):2317-2330.

[10] Iwama K, Kambayashi Y, Yamashita S. Transformation rules for designing CNOT-based quantum circuits[C].Soul:Design Automation Conference,IEEE, 2002.

Method of Logic Diagram and Waveform Visualizing of Reversible Logic Circuit

DUAN Xueli, ZHAO Shuguang, FENG Ruofei

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

The logic expressions for the reversible logic circuit are analyzed, and the reversible logic circuit diagram and the simulation waveform are given. The reversible structure of the truth table obtained from the simulation results is provided. The relevant results are presented in an intuitive form by the use of C language programming, an innovative approach in the reversible logic circuit research.

reversible logic circuit; logic circuit diagram; simulation waveform; reversible truth table

2016- 01- 01

国家自然科学基金资助项目(61271114)

段雪利(1987-)，男，硕士研究生。研究方向：电子设计等。

10.16180/j.cnki.issn1007-7820.2016.11.002

TN79+

A