arXiv:1408.3586

Embedding of Large Boolean Functions for Reversible Logic

Mathias Soeken, Robert Wille, Oliver Keszöcze, D. Michael Miller, Rolf Drechsler

Published Aug 15, 2014• 4 citations

Abstract

Reversible logic represents the basis for many emerging technologies and has recently been intensively studied. However, most of the Boolean functions of practical interest are irreversible and must be embedded into a reversible function before they can be synthesized. Thus far, an optimal embedding is guaranteed only for small functions, whereas a significant overhead results when large functions are considered. In this paper, we study this issue. We prove that determining an optimal embedding is coNP-hard already for restricted cases. Then, we propose heuristic and exact methods for determining both the number of additional lines as well as a corresponding embedding. For the approaches we considered sums of products and binary decision diagrams as function representations. Experimental evaluations show the applicability of the approaches for large functions. Consequently, the reversible embedding of large functions is enabled as a precursor to subsequent synthesis.

DOI: 10.48550/arxiv.1408.3586

Related papers

Embedding of Large Boolean Functions for Reversible Logic

Mathias Soeken, Robert Wille, Oliver Keszöcze +2 more

Reversible logic represents the basis for many emerging technologies and has recently been intensively studied. However, most of the Boolean functions of practical interest are irreversible and must be embedded into a reversible function before they can be synthesized. Thus far, an optimal embedding is guaranteed only for small functions, whereas a significant overhead results when large functions are considered. We study this issue in this article. We prove that determining an optimal embedding is coNP-hard already for restricted cases. Then, we propose heuristic and exact methods for determining both the number of additional lines and a corresponding embedding. For the approaches, we considered sum of products and binary decision diagrams as function representations. Experimental evaluations show the applicability of the approaches for large functions. Consequently, the reversible embedding of large functions is enabled as a precursor to subsequent synthesis.

ACM Journal on Emerging Technologies in Computing SystemsDec 9, 201558 citations

Efficient Reversible Logic Synthesis via Isomorphic Subgraph Matching

Mridul Krishna, Anupam Chattopadhyay

Reversible logic is being studied extensively due to its applications in the design of nanoscale circuits with ultra-low power dissipation and future technologies such as quantum computing. Most methods that synthesize reversible logic circuits are restricted to small functions and are thus, not scalable. Previous methods based on Binary Decision Diagrams (BDD) are scalable but introduce a large number of additional circuit lines. In this paper, we present a technique that maps subgraphs of the BDD to structures with known reversible-circuit templates by posing this as a subgraph isomorphism problem. Experimental results show that this approach reduces the number of additional circuit lines introduced by previous approaches while retaining their scalability. We further show that for small functions, there is also an improvement in the quantum cost.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)May 1, 201413 citations

Determining the minimal number of lines for large reversible circuits

Robert Wille, Oliver Keszöcze, Rolf Drechsler

Synthesis of reversible circuits is an active research area motivated by its applications e.g. in quantum computation or low-power design. The number of used circuit lines is thereby a crucial criterion. In this paper, we introduce several methods (including a theoretical upper bound) for the efficient computation or at least approximation of the minimal number of lines needed to realize a given function in reversible logic. While the proposed exact approach requires a significant amount of run-time (exponential in the worst case), the heuristic methods lead to very precise approximations in very short run-time. Using this, it can be shown that current synthesis approaches for large functions are still far away from producing optimal circuits with respect to the number of lines.

Design, Automation, and Test in EuropeMar 1, 201146 citations

Effect of BDD Optimization on Synthesis of Reversible and Quantum Logic

Robert Wille, Rolf Drechsler

Synthesis of reversible and quantum logic has become an intensely studied topic in the last years. However, most synthesis methods are limited, since they rely on a truth table representation of the function to be synthesized. BDD-based synthesis offers an alternative. Here, reversible or quantum circuits are derived from a function given as Binary Decision Diagram (BDD) by substituting all nodes of the BDD with a cascade of Toffoli or elementary quantum gates, respectively. As a result, the application of the approach is not limited by the truth table of the function but by the (quite more efficient) BDD representation. Furthermore, many optimization techniques for BDDs exist which can be exploited. In this work, we evaluate the effect of three optimization methods for BDDs (namely shared nodes, complement edges, and advanced orderings) on the resulting reversible and quantum circuits. We describe in detail the adjustments, which have to be done to support these optimizations for synthesis, and discuss possible improvements and drawbacks. In a case study, the effects are experimentally evaluated. The results showed, that applying these optimization techniques leads to significant smaller circuits (with respect to number of gates and lines) in most of the cases.

Electronic Notes in Theoretical Computer ScienceMar 1, 201053 citations

BDD-Based Synthesis of Reversible Logic

Robert Wille, Rolf Drechsler

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.

International Journal of Applied Metaheuristic ComputingOct 1, 20108 citations

Make it reversible: Efficient embedding of non-reversible functions

Alwin Zulehner, Robert Wille

Reversible computation became established as a promising concept due to its application in various areas like quantum computation, energy-aware circuits, and further areas. Unfortunately, most functions of interest are non-reversible. Therefore, a process called embedding has to be conducted to transform a non-reversible function into a reversible one - a coNP-hard problem. Existing solutions suffer from the resulting exponential complexity and, hence, are limited to rather small functions only. In this work, an approach is presented which tackles the problem in an entirely new fashion. We divide the embedding process into matrix operations, which can be conducted efficiently on a certain kind of decision diagram. Experiments show that improvements of several orders of magnitudes can be achieved using the proposed method. Moreover, for many benchmarks exact results can be obtained for the first time ever.

Design, Automation, and Test in EuropeMar 1, 201744 citations