BDD-based synthesis of reversible logic for large functions

ABSTRACT

Reversible logic is the basis for several emerging technologies such as quantum computing, optical computing, or DNA computing and has further applications in domains like low-power design and nanotechnologies. However, current methods for the synthesis of reversible logic are limited, i.e. they are applicable to relatively small functions only. In this paper, we propose a synthesis approach, that can cope with Boolean functions containing more than a hundred of variables. We present a technique to derive reversible circuits for a function given by a Binary Decision Diagram (BDD). The circuit is obtained using an algorithm with linear worst case behavior regarding run-time and space requirements. Furthermore, the size of the resulting circuit is bounded by the BDD size. This allows to transfer theoretical results known from BDDs to reversible circuits. Experiments show better results (with respect to the circuit cost) and a significantly better scalability in comparison to previous synthesis approaches.

REFERENCES

• 1: R. Landauer. Irreversibility and heat generation in the computing process. IBM J. Res. Dev., 5:183, 1961.
• 2: C. H. Bennett. Logical reversibility of computation. IBM J. Res. Dev, 17(6):525--532, 1973.
• 3: T. Toffoli. Reversible computing. In W. de Bakker and J. van Leeuwen, editors, Automata, Languages and Programming, page 632. Springer, 1980. Technical Memo MIT/LCS/TM-151, MIT Lab. for Comput. Sci.
• 4: M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge Univ. Press, 2000.
• 5: R. Cuykendall and D. R. Andersen. Reversible optical computing circuits. Optics Letters, 12(7):542--544, 1987.
• 6: R. C. Merkle. Reversible electronic logic using switches. Nanotechnology, 4:21--40, 1993.
• 7: W. N. N. Hung, X. Song, G. Yang, J. Yang, and M. Perkowski. Optimal synthesis of multiple output Boolean functions using a set of quantum gates by symbolic reachability analysis. IEEE Trans. on CAD, 25(9):1652--1663, 2006.
• 8: D. Große, R. Wille, G. W. Dueck, and R. Drechsler. Exact multiple control toffoli network synthesis with SAT techniques. IEEE Trans. on CAD, 28(5):703--715, 2009.
• 9: V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes. Synthesis of reversible logic circuits. IEEE Trans. on CAD, 22(6):710--722, 2003.
• 10: D. M. Miller, D. Maslov, and G. W. Dueck. A transformation based algorithm for reversible logic synthesis. In Design Automation Conf., pages 318--323, 2003.
• 11: P. Kerntopf. A new heuristic algorithm for reversible logic synthesis. In Design Automation Conf., pages 834--837, 2004.
• 12: D. Maslov, G. W. Dueck, and D. Michael Miller. Toffoli network synthesis with templates. IEEE Trans. on CAD, 24(6):807--817, 2005.
• 13: P. Gupta, A. Agrawal, and N. K. Jha. An algorithm for synthesis of reversible logic circuits. IEEE Trans. on CAD, 25(11):2317--2330, 2006.
• 14: D. Maslov, G. W. Dueck, and D. M. Miller. Techniques for the synthesis of reversible toffoli networks. ACM Trans. on Design Automation of Electronic Systems, 12(4), 2007.
• 15: R. E. Bryant. Graph-based algorithms for Boolean function manipulation. IEEE Trans. on Comp., 35(8):677--691, 1986.
• 16: I. Wegener. Branching programs and binary decision diagrams: theory and applications. Society for Industrial and Applied Mathematics, 2000.
• 17: R. Drechsler and D. Sieling. Binary decision diagrams in theory and practice. Software Tools for Technology Transfer, 3:112--136, 2001.
• 18: E. F. Fredkin and T. Toffoli. Conservative logic. International Journal of Theoretical Physics, 21(3/4):219--253, 1982.
• 19: A. Peres. Reversible logic and quantum computers. Phys. Rev. A, (32):3266--3276, 1985.
• 20: A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVinchenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter. Elementary gates for quantum computation. The American Physical Society, 52:3457--3467, 1995.
• 21: D. Maslov and D. M. Miller. Comparison of the cost metrics through investigation of the relation between optimal ncv and optimal nct 3-qubit reversible circuits. IET Computers & Digital Techniques, 1(2):98--104, 2007.
• 22: D. Maslov and G. W. Dueck. Reversible cascades with minimal garbage. IEEE Trans. on CAD, 23(11):1497--1509, 2004.
• 23: K. S. Brace, R. L. Rudell, and R. E. Bryant. Efficient implementation of a BDD package. In Design Automation Conf., pages 40--45, 1990.
• 24: R. Wille and R. Drechsler. Effect of BDD optimization on synthesis of reversible and quantum logic. Workshop on Reversible Computation, 2009.
• 25: F. Somenzi. CUDD: CU Decision Diagram Package Release 2.3.1. University of Colorado at Boulder, 2001.
• 26: K. Patel, I. Markov, and J. Hayes. Optimal synthesis of linear reversible circuits. Quantum Information and Computation, 8(3--4):282--294, 2008.
• 27: R. Rudell. Dynamic variable ordering for ordered binary decision diagrams. In Int'l Conf. on CAD, pages 42--47, 1993.
• 28: R. Wille, D. Große, L. Teuber, G. W. Dueck, and R. Drechsler. RevLib: An online resource for reversible functions and reversible circuits. In Int'l Symp. on Multi-Valued Logic, pages 220--225. RevLib is available at http://www.revlib.org.
• 29: J. Zhong and J. C. Muzio. Using crosspoint faults in simplifying toffoli networks. In IEEE North-East Workshop on Circuits and Systems, pages 129--132, 2006.
• 30: A. K. Prasad, V. V. Shende, I. L. Markov, J. P. Hayes, and K. N. Patel. Data structures and algorithms for simplifying reversible circuits. J. Emerg. Technol. Comput. Syst., 2(4):277--293, 2006.
• 31: D. Y. Feinstein, M. A. Thornton, and D. M. Miller. Partially redundant logic detection using symbolic equivalence checking in reversible and irreversible logic circuits. In Design, Automation and Test in Europe, pages 1378--1381, 2008.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN

General Terms:
Algorithms

Keywords:
decision diagrams, quantum logic, reversible logic, synthesis