基于ESOP最大加权输出相容类的可逆电路综合方法

doi:10.3969/j.issn.0372-2112.2018.08.010

电子学报 ›› 2018, Vol. 46 ›› Issue (8): 1866-1875.DOI: 10.3969/j.issn.0372-2112.2018.08.010

基于ESOP最大加权输出相容类的可逆电路综合方法

卜登立

1. 井冈山大学电子与信息工程学院, 江西吉安 343009;
2. 流域生态与地理环境监测国家测绘地理信息局重点实验室, 江西吉安 343009

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

Reversible Circuit Synthesis Method Based on Maximum Weighted Output-Compatibility Class of ESOP

BU Deng-li

1. School of Electronics and Information Engineering, Jinggangshan University, Ji'an, Jiangxi 343009, China;
2. Key Laboratory of Watershed Ecology and Geographical Environment Monitoring, NASG, Ji'an, Jiangxi 343009, China

Received:2017-08-07 Revised:2018-03-02 Online:2018-08-25 Published:2018-08-25
- Supported by:
- National Natural Science Foundation of China (No.61640412, No.61762052); Science and Technology Project of Education Department of Jiangxi Provicne (No.GJJ160746); Key laboratory of Watershed Ecology and Geographical Environment Monitoring, NASG (No.WE2016012); Natural Science Foundation of Jiangxi Province, China (No.20171BAB202010); Ph.D Research Program of Jinggangshan University (No.JZB1803)

摘要/Abstract

摘要： 充分挖掘乘积项在多个函数输出之间的共享因素来降低可逆电路的量子成本是基于积之异或和（Exclusive-Sums-Of-Products，ESOP）的可逆电路综合方法要解决的一个重要问题.提出一种基于最大加权输出相容类的可逆电路综合方法.该方法先借助零抑制多输出决策图对立方体集合进行输出等价类划分，并采用贪心策略计算最大加权输出相容类，然后对最大加权输出相容类进行综合，以使混合极性多控制Toffoli门以及可逆子电路在尽可能多的输出变量线之间共享.通过立方体聚类挖掘等价类中立方体间的结构相似性，并对文字数较多的立方体实施分解，进一步降低可逆电路的量子成本.使用RevLib多输出函数对所提出方法进行了验证，结果表明所提出方法可以很好地挖掘乘积项在多个函数输出之间的共享因素，能够降低由ESOP综合所得可逆电路的量子成本，并且具有较高的时间效率.

关键词: 可逆电路, 逻辑综合, 积之异或和, 输出相容, 零抑制多输出决策图

Abstract: Reducing quantum cost of reversible circuit by exploiting sharing of product terms among multiple function outputs is one crucial problem to be solved for ESOP (Exclusive-Sums-Of-Products) based reversible circuit synthesis.A maximum weighted output-compatibility class based reversible circuit synthesis method is proposed.The proposed method first partitions cubes set into several output-equivalence classes by utilizing zero-suppressed multiple-output decision diagram,and obtains maximum weighted output-compatibility class by using greedy strategy,then synthesizes the maximum weighted output-compatibility class to share mixed-polarity multiple-control Toffoli gates and reversible sub-circuits among as many output variable lines as possible.In order to further reduce quantum cost,the proposed method clusters cubes in equivalence class by exploiting structural similarity among cubes,and decomposes those cubes that have more literals.The proposed method is validated by using several RevLib multi-output functions.Results show that the proposed method can fine exploit sharing of product terms among multiple function outputs,can reduce quantum cost of reversible circuit synthesized from ESOP,and has high time efficiency.

Key words: reversible circuit, logic synthesis, exclusive sums of products, output-compatibility, zero-suppressed multiple-output decision diagram

中图分类号:

卜登立. 基于ESOP最大加权输出相容类的可逆电路综合方法[J]. 电子学报, 2018, 46(8): 1866-1875.

BU Deng-li . Reversible Circuit Synthesis Method Based on Maximum Weighted Output-Compatibility Class of ESOP[J]. Acta Electronica Sinica, 2018, 46(8): 1866-1875.

参考文献

[1] Bennett C H.Logical reversibility of computation[J].IBM Journal of Research and Development,1973,17(6):525-532.
[2] Nielsen M A,Chuang I L.Quantum Computation and Quantum Information[M].10^th anniversary edition.New York:Cambridge University Press,2010.
[3] Abdessaied N,Drechsler R.Reversible and Quantum Circuits:Optimization and Complexity Analysis[M].Bremen:Springer Press,2016.
[4] 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.
[5] 陈汉武,李文骞,阮越,等.基于汉明距离递减变换的可逆逻辑综合算法[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)
[6] 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):Article 41:1-26.
[7] 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.
[8] 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.
[9] 王友仁,沈先坤,周影辉.基于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 Electronica Sinica,2014,42(5):1025-1029.(in Chinese)
[10] Saeedi M,Markov I L.Synthesis and optimization of reversible circuits-a survey[J].ACM Computing Surveys,2013,45(2):Article 21:1-34.
[11] Fazel K,Thornton M A,Rice J E.ESOP-based Toffoli gate cascade generation[A].Proceedings of the IEEE Pacific Rim Conference on Communications,Computers and Signal Processing[C].Victoria,BC,Canada:IEEE,2007.206-209.
[12] Zulehner A,Wille R.Make it reversible:efficient embedding of non-reversible functions[A].Proceedings of Design,Automation & Test in Europe Conference & Exhibition[C].Lausanne,Switzerland:IEEE Press,2017.458-463.
[13] Adnan N A B,Yamashita S,Mishchenko A.Reduction of quantum cost by making temporary changes to the function[J].IEICE Transactions on Information & Systems,2017,E100.D(7):1393-1402.
[14] Chaki R,Saeed K,Choudhury S,et al.Applied Computation and Security Systems[M].New Delhi:Springer Press,2015.131-144.
[15] Bandyopadhyay C,Parekh S,Rahaman H.A synthesis approach for ESOP-based reversible circuit[A].Proceedings of the International Conference on Advances in Computing,Communications and Informatics[C].Jaipur,India:IEEE Press,2016.1741-1745.
[16] 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,USA:IEEE Press,2008.220-225.
[17] Revkit2.0.Revkit:a toolkit for reversible circuit design[DB/OL].http://www.revkit.org/.2015-8-9.
[18] Maslov D.Reversible logic synthesis benchmarks page[DB/OL].http://webhome.cs.uvic.ca/~dmaslov/.2017-05-15.
[19] Kao M-Y.Encyclopedia of Algorithms[M].New York:Springer Press,2008.
[20] Minato S-I.Zero-suppressed BDDs and their applications[J].International Journal on Software Tools for Technology Transfer,2001,3(2):156-170.
[21] Sasao T,Butler J T.Applications of Zero-Suppressed Decision Diagrams[M].San Rafael:Morgan & Claypool Publishers.2014.1-34.
[22] Mishchenko A,Perkowski M.Fast heuristic minimization of exclusive-sums-of-products[A].Proceedings of Reed-Muller Workshop[C].Mississippi,USA:IEEE Press,2001.241-249.

基于ESOP最大加权输出相容类的可逆电路综合方法

Reversible Circuit Synthesis Method Based on Maximum Weighted Output-Compatibility Class of ESOP

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

[1]	卜登立, 郭鸣. 基于布尔表达式图的可逆电路综合方法[J]. 电子学报, 2020, 48(3): 494-502.
[2]	吴钰, 张莹, 王伦耀, 储著飞, 夏银水. 一种可逆有限状态机的电路设计[J]. 电子学报, 2020, 48(11): 2226-2232.
[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.