{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T23:39:11Z","timestamp":1718667551016},"reference-count":39,"publisher":"IGI Global","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,10,1]]},"abstract":"<p>Reversible logic became a promising alternative to traditional circuits because of its applications in emerging technologies such as quantum computing, low-power design, DNA computing, or nanotechnologies. As a result, synthesis of the respective circuits is an intensely studied topic. However, most synthesis methods are limited, because they rely on a truth table representation of the function to be synthesized. In this paper, the authors present a synthesis approach that is based on Binary Decision Diagrams (BDDs). The authors propose a technique to derive reversible or quantum circuits from BDDs by substituting all nodes of the BDD with a cascade of Toffoli or quantum gates, respectively. Boolean functions containing more than a hundred of variables can efficiently be synthesized. More precisely, a circuit can be obtained from a given BDD using an algorithm with linear worst case behavior regarding run-time and space requirements. Furthermore, using the proposed approach, theoretical results known from BDDs can be transferred to reversible circuits. Experiments show better results (with respect to the circuit cost) and a significantly better scalability in comparison to previous synthesis approaches.<\/p>","DOI":"10.4018\/jamc.2010100102","type":"journal-article","created":{"date-parts":[[2011,10,19]],"date-time":"2011-10-19T15:57:56Z","timestamp":1319039876000},"page":"25-41","source":"Crossref","is-referenced-by-count":6,"title":["BDD-Based Synthesis of Reversible Logic"],"prefix":"10.4018","volume":"1","author":[{"given":"Robert","family":"Wille","sequence":"first","affiliation":[{"name":"University of Bremen, Germany"}]},{"given":"Rolf","family":"Drechsler","sequence":"additional","affiliation":[{"name":"University of Bremen, Germany"}]}],"member":"2432","reference":[{"key":"jamc.2010100102-0","first-page":"3457","article-title":"Elementary gates for quantum computation.","volume":"52","author":"A.Barenco","year":"1995","journal-title":"The American Physical Society"},{"key":"jamc.2010100102-1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.176.0525"},{"key":"jamc.2010100102-2","doi-asserted-by":"publisher","DOI":"10.1109\/12.537122"},{"key":"jamc.2010100102-3","doi-asserted-by":"crossref","unstructured":"Brace, K. S., Rudell, R. L., & Bryant, R. E. (1990). Efficient implementation of a BDD package. In Proceedings of the Design Automation Conference (pp. 40-45).","DOI":"10.1145\/123186.123222"},{"key":"jamc.2010100102-4","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676819"},{"key":"jamc.2010100102-5","doi-asserted-by":"publisher","DOI":"10.1364\/OL.12.000542"},{"key":"jamc.2010100102-6","doi-asserted-by":"crossref","unstructured":"Desoete, B., & De Vos, A. (2002). A reversible carry-look-ahead adder using control gates. Integration, the VLSI Journal, 33(1-2), 89-104.","DOI":"10.1016\/S0167-9260(02)00051-2"},{"key":"jamc.2010100102-7","doi-asserted-by":"publisher","DOI":"10.1109\/43.833206"},{"key":"jamc.2010100102-8","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/s100090100056","article-title":"Binary decision diagrams in theory and practice.","volume":"3","author":"R.Drechsler","year":"2001","journal-title":"Software Tools for Technology Transfer"},{"key":"jamc.2010100102-9","first-page":"1378","author":"D. Y.Feinstein","year":"2008","journal-title":"Partially redundant logic detection using symbolic equivalence checking in reversible and irreversible logic circuits"},{"key":"jamc.2010100102-10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01857727"},{"issue":"5","key":"jamc.2010100102-11","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1109\/TCAD.2009.2017215","article-title":"Exact multiple control Toffoli network synthesis with SAT techniques.","volume":"28","author":"D.Gro\u00dfe","year":"2009","journal-title":"IEEE Trans. On CAD"},{"key":"jamc.2010100102-12","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.871622"},{"key":"jamc.2010100102-13","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.858352"},{"key":"jamc.2010100102-14","doi-asserted-by":"crossref","unstructured":"Kerntopf, P. (2004). A new heuristic algorithm for reversible logic synthesis. In Proceedings of the Design Automation Conference (pp. 834-837).","DOI":"10.1145\/996566.996789"},{"key":"jamc.2010100102-15","doi-asserted-by":"publisher","DOI":"10.1147\/rd.53.0183"},{"key":"jamc.2010100102-16","doi-asserted-by":"publisher","DOI":"10.1109\/12.144618"},{"key":"jamc.2010100102-17","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2004.836735"},{"key":"jamc.2010100102-18","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.847911"},{"key":"jamc.2010100102-19","doi-asserted-by":"publisher","DOI":"10.1145\/1278349.1278355"},{"key":"jamc.2010100102-20","doi-asserted-by":"publisher","DOI":"10.1049\/iet-cdt:20060070"},{"key":"jamc.2010100102-21","doi-asserted-by":"publisher","DOI":"10.1088\/0957-4484\/4\/1\/002"},{"key":"jamc.2010100102-22","doi-asserted-by":"crossref","unstructured":"Miller, D. M., Maslov, D., & Dueck, G. W. (2003). A transformation based algorithm for reversible logic synthesis. In Proceedings of the Design Automation Conference (pp. 318-323).","DOI":"10.1145\/775832.775915"},{"key":"jamc.2010100102-23","author":"M.Nielsen","year":"2000","journal-title":"Quantum Computation and Quantum Information"},{"issue":"3-4","key":"jamc.2010100102-24","doi-asserted-by":"crossref","first-page":"282","DOI":"10.26421\/QIC8.3-4-4","article-title":"Optimal synthesis of linear reversible circuits.","volume":"8","author":"K.Patel","year":"2008","journal-title":"Quantum Information and Computation"},{"key":"jamc.2010100102-25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.32.3266"},{"key":"jamc.2010100102-26","doi-asserted-by":"publisher","DOI":"10.1145\/1216396.1216399"},{"key":"jamc.2010100102-27","doi-asserted-by":"crossref","unstructured":"Rudell, R. (1993). Dynamic variable ordering for ordered binary decision diagrams. In Proceedings of the International Conference on CAD (pp. 42-47).","DOI":"10.1109\/ICCAD.1993.580029"},{"key":"jamc.2010100102-28","first-page":"713","article-title":"A symbolic analysis of relay and switching circuits.","volume":"57","author":"C. E.Shannon","year":"1938","journal-title":"Transactions of the AIEE"},{"key":"jamc.2010100102-29","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.811448"},{"key":"jamc.2010100102-30","author":"F.Somenzi","year":"2001","journal-title":"CUDD: CU Decision Diagram Package Release 2.3.1"},{"key":"jamc.2010100102-31","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1007\/3-540-10003-2_104","article-title":"Reversible computing","author":"T.Toffoli","year":"1980","journal-title":"Automata, Languages and Programming"},{"key":"jamc.2010100102-32","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719789","author":"I.Wegener","year":"2000","journal-title":"Branching programs and binary decision diagrams: theory and applications"},{"key":"jamc.2010100102-33","doi-asserted-by":"crossref","unstructured":"Wille, R., & Drechsler, R. (2009). BDD-based synthesis of reversible logic for large functions. In Proceedings of the Design Automation Conference (pp. 270-275).","DOI":"10.1145\/1629911.1629984"},{"key":"jamc.2010100102-34","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2010.02.006"},{"key":"jamc.2010100102-35","doi-asserted-by":"crossref","unstructured":"Wille, R., Gro\u00dfe, D., Teuber, L., Dueck, G. W., & Drechsler, R. (2008). RevLib: an online resource for reversible functions and reversible circuits. In Proceedings of the International Symposium on Multi-Valued Logic (pp. 220-225). Retrieved from http:\/\/www.revlib.org","DOI":"10.1109\/ISMVL.2008.43"},{"key":"jamc.2010100102-36","unstructured":"Yang, S. (1991). Logic synthesis and optimization benchmarks user guide (Tech. Rep. No. 1\/95). Durham, NC: Microelectronic Center of North Carolina."},{"key":"jamc.2010100102-37","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2003.818324"},{"key":"jamc.2010100102-38","doi-asserted-by":"crossref","unstructured":"Zhong, J., & Muzio, J. C. (2006). Using crosspoint faults in simplifying Toffoli networks. In Proceedings of the IEEE Northeast Workshop on Circuits and Systems (pp. 129-132).","DOI":"10.1109\/NEWCAS.2006.250942"}],"container-title":["International Journal of Applied Metaheuristic Computing"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=51676","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T23:56:47Z","timestamp":1654127807000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/jamc.2010100102"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2010,10,1]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,10]]}},"URL":"https:\/\/doi.org\/10.4018\/jamc.2010100102","relation":{},"ISSN":["1947-8283","1947-8291"],"issn-type":[{"value":"1947-8283","type":"print"},{"value":"1947-8291","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,1]]}}}