基于布尔表达式图的可逆电路综合方法

doi:10.3969/j.issn.0372-2112.2020.03.011

电子学报 ›› 2020, Vol. 48 ›› Issue (3): 494-502.DOI: 10.3969/j.issn.0372-2112.2020.03.011

基于布尔表达式图的可逆电路综合方法

卜登立, 郭鸣

井冈山大学电子与信息工程学院, 江西吉安 343009

收稿日期:2018-10-31 修回日期:2019-11-23 出版日期:2020-03-25
- 作者简介:
- 卜登立 男,1975年出生,河北定州人.博士,副教授,中国电子学会高级会员,主要研究领域为电路设计与优化、可逆逻辑综合、量子电路综合、启发式优化算法.E-mail:bodengli@163.com;郭鸣女,1978年出生,江西吉安人.博士,副教授,主要研究领域为电路设计与优化.E-mail:guoming@jgsu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61961023，No.61640412，No.61762052）; 江西省教育厅科技计划项目 (No.GJJ160746）; 井冈山大学博士科研启动项目 (No.JZB1803）; 流域生态与地理环境监测国家测绘地理信息局重点实验室资助课题 (No.WE2016012）; 江西省自然科学基金项目 (No.20171BAB202010）

Reversible Circuit Synthesis Method Based on Boolean Expression Diagram

BU Deng-li, GUO Ming

School of Electronics and Information Engineering, Jinggangshan University, Ji'an, Jiangxi 343009, China

Received:2018-10-31 Revised:2019-11-23 Online:2020-03-25 Published:2020-03-25
- Supported by:
- National Natural Science Foundation of China (No.61961023, No.61640412, No.61762052); Science and Technology Project of Education Department of Jiangxi Provicne (No.GJJ160746); Ph.D Research Program of Jinggangshan University (No.JZB1803); Supported by the Key Laboratory of Watershed Ecology and Geoenvironmental Monitoring, National Administration of Surveying, Mapping and GeoInformation (No.WE2016012); Natural Science Foundation of Jiangxi Province, China (No.20171BAB202010)

摘要/Abstract

摘要： 本文基于布尔表达式图（Boolean Expression Diagram，BED）提出一种可逆电路综合方法.该方法使用BED表示函数，采用逐BED结点方式综合可逆电路.在综合一个结点时，通过考虑其子结点函数的值是否还会被后续电路使用，基于由NOT、CNOT以及混合极性Peres门构成的门库构建该结点的局部最优可逆子电路.为进一步改善所得电路的成本，根据函数表达式的乘积项中变量对的共享度对变量进行分组实现BED中变量的排序.使用一组基准函数对所提出方法进行了验证.结果表明所提出方法具有较高时间效率.与现有使用决策图作为函数表示模型的综合方法相比，所提出方法能改善综合所得可逆电路的量子成本，且在许多情况下还能减少量子位数和垃圾线数.

关键词: 可逆电路, 逻辑综合, 布尔表达式图, 变量排序

Abstract: A reversible circuit synthesis method based on BED (Boolean Expression Diagram) is proposed. The proposed method utilizes a BED to represent a Boolean function, and synthesizes a reversible circuit through mapping BED nodes to reversible cascades. Using a gate library consisting of NOT, CNOT and mixed-polarity Peres gates, the proposed method constructs a locally optimal reversible cascade for each BED node by considering whether the values of the child nodes of this node will be used by subsequent reversible cascades. In order to improve the cost of the circuit synthesized from the BED of a function, according to the sharing of pairs of variables among products of the function expression, variable ordering for the BED is achieved by variable grouping. The proposed method is validated using a set of benchmark functions. The results show that the proposed method is time efficient. Compared to the existing reversible circuit synthesis methods using decision diagram as a representation model, the proposed method can improve the quantum cost of the synthesized reversible circuits for almost all of the used benchmark functions, and can also reduce the number of qubits and the number of garbage lines in many cases.

Key words: reversible circuit, logic synthesis, Boolean expression diagram, variable ordering

中图分类号:

卜登立, 郭鸣. 基于布尔表达式图的可逆电路综合方法[J]. 电子学报, 2020, 48(3): 494-502.

BU Deng-li, GUO Ming . Reversible Circuit Synthesis Method Based on Boolean Expression Diagram[J]. Acta Electronica Sinica, 2020, 48(3): 494-502.

参考文献

[1] Wille R,Drechsler R.Towards a Design Flow for Reversible Logic[M].New York:Springer,2010.
[2] Chattopadhyay A,Littarru A,Amaru L,et al.Reversible logic synthesis via biconditional binary decision diagrams[A].Proceedings of the 45th International Symposium on Multiple-Valued Logic[C].Waterloo:IEEE Press,2015.2-7.
[3] Bennett C H.Logical reversibility of computation[J].IBM Journal of Research and Development,1973,17:525-532.
[4] Shukla V,Singh O P,Mishra G R,et al.Reversible realization of n-bit arithmetic circuit for low power loss ALU applications[J].Procedia Computer Science,2018,125:847-854.
[5] Nielsen M A,Chuang I L.Quantum Computation and Quantum Information[M].Cambridge:Cambridge University Press,2010.
[6] Abdessaied N,Drechsler R.Reversible and Quantum Circuits:Optimization and Complexity Analysis[M].Bremen:Springer Press,2016.
[7] Zulehner A,Wille R.One-pass design of reversible circuits:combining embedding and synthesis for reversible logic[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2018,37(5):996-1008.
[8] Yang G,Xie F,Hung W N N,et al.Realization and synthesis of reversible functions[J].Theoretical Computer Science,2011,412(17):1606-1613.
[9] 陈汉武,李文骞,阮越,等.基于汉明距离递减变换的可逆逻辑综合算法[J].计算机学报,2014,37(8):1839-1845. Chen Hanwu,Li Wenqian,Ruan Yue,et al.A synthesis algorithm of reversible logic circuit based on the decreasing transform of hamming distance[J].Chinese Journal of Computers,2014,37(8):1839-1845.(in Chinese)
[10] Lin C-C,Jha N K.RMDDS:Reed-Muller decision diagram synthesis of reversible logic circuits[J].ACM Journal on Emerging Technologies in Computing Systems,2014,10(2):14:1-14:25.
[11] Soeken M,Tague L,Dueck G W,et al.Ancilla-free synthesis of large reversible functions using binary decision diagrams[J].Journal of Symbolic Computation,2016,73:1-26.
[12] Soeken M,Wille R,Keszocze O,et al.Embedding of large Boolean functions for reversible logic[J].ACM Journal on Emerging Technologies in Computing Systems,2015,12(4):41:1-41:26.
[13] 卜登立.基于ESOP最大加权输出相容类的可逆电路综合方法[J].电子学报,2018,46(8):1866-1875. Bu Dengli.Reversible circuit synthesis method based on maximum weighted output-compatibility class of ESOP[J].Acta Electronica Sinica,2018,46(8):1866-1875.(in Chinese)
[14] Drechsler R,Wille R.Synthesis of reversible circuits using decision diagrams[A].Proceedings of the International Symposium on Electronic System Design[C].Kolkata,India:IEEE Press,2012.1-5.
[15] Krishna M,Chattopadhyay A.Efficient reversible logic synthesis via isomorphic subgraph matching[A].Proceedings of the IEEE 44th International Symposium on Multiple-Valued Logic[C].Bremen,Germany:IEEE Press,2014.103-108.
[16] Pang Y,Yan Y,Lin J,et al.An efficient method to synthesize reversible logic by using positive Davio decision diagrams[J].Circuits,Systems,and Signal Processing,2014,33(10):3107-3121.
[17] 王友仁,沈先坤,周影辉.基于KFDD的可逆逻辑电路综合设计方法[J].电子学报,2014,42(5):1025-1029. Wang Youren,Shen Xiankun,Zhou Yinghui.Synthesis design method of reversible logic circuit based on Kronecker functional decision diagram[J].Acta Electronic Sinica,2014,42(5):1025-1029.(in Chinese)
[18] Schonborn E,Datta K,Wille R,et al.Optimizing DD-based synthesis of reversible circuits using negative control lines[A].Proceedings of the 17th International Symposium on Design and Diagnostics of Electronic Circuits & Systems[C].Warsaw:IEEE Press,2014.129-134.
[19] Law J J,Rice J E.Line reduction in reversible circuits using KFDDs[A].Proceedings of the 2015 IEEE Pacific Rim Conference on Communications,Computers and Signal Processing[C].Victoria,BC,Canada:IEEE Press,2015.113-118.
[20] Andersen H R,Hulgaard H.Boolean expression diagrams[J].Information and Computation,2002,179(2):194-212.
[21] Hagjam F Z,Moraga C.RIMEP2:evolutionary design of reversible digital circuits[J].ACM Journal on Emerging Technologies in Computing Systems,2014,11(3):27:1-27:23.
[22] Wille R,Groβe D,Teuber L,et al.RevLib:an online resource for reversible functions and reversible circuits[A].Proceedings of the 38th International Symposium on Multiple-Valued Logic[C].Dallas,TX:IEEE Press,2008.220-225.
[23] Hansen J P,Sekine M.Synthesis by spectral translation using Boolean decision diagrams[A].Proceedings of the 33rd Design Automation Conference[C].Las Vegas,NV,USA:IEEE Press,1996.248-253.
[24] Mishchenko A,Perkowski M.Fast heuristic minimization of exclusive-sums-of-products[A].Proceedings of Reed-Muller Workshop[C].Mississippi,USA:IEEE Press,2001.242-250.
[25] Wille R,Drechsler R.BDD-based synthesis of reversible logic for large functions[A].Proceedings of the 46th ACM/IEEE Design Automation Conference[C].San Francisco,CA,USA:IEEE Press,2009.270-275.
[26] Wille R,Drechsler R.Effect of BDD optimization on synthesis of reversible and quantum logic[J].Electronic Notes in Theoretical Computer Science,2010,253(6):57-70.

基于布尔表达式图的可逆电路综合方法

Reversible Circuit Synthesis Method Based on Boolean Expression Diagram

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

[1]	吴钰, 张莹, 王伦耀, 储著飞, 夏银水. 一种可逆有限状态机的电路设计[J]. 电子学报, 2020, 48(11): 2226-2232.
[2]	卜登立. 基于ESOP最大加权输出相容类的可逆电路综合方法[J]. 电子学报, 2018, 46(8): 1866-1875.
[3]	卜登立, 江建慧. 基于对偶逻辑的混合极性RM电路极性转换和优化方法[J]. 电子学报, 2015, 43(1): 79-85.
[4]	徐明强, 管致锦, 张海豹. 基于最小混乱度的三值可逆逻辑综合算法[J]. 电子学报, 2013, 41(7): 1352-1357.
[5]	管致锦;秦小麟;陶涛;施 . 可逆逻辑门网络的表示与级联[J]. 电子学报, 2010, 38(10): 2370-2376.
[6]	胡靖;马光胜;李东海;冯刚. 考虑串扰因素的可逆电路的符号综合方法[J]. 电子学报, 2008, 36(5): 1029-1034.
[7]	李志强;陈汉武;徐宝文;肖芳英;薛希玲. 四量子可逆逻辑电路快速综合算法[J]. 电子学报, 2008, 36(11): 2081-2089.