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.
[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.
2020, Vol. 48 
