A new heuristic algorithm for reversible logic synthesis

ABSTRACT

Reversible logic has applications in many fields, including quantum computing. Synthesis techniques for reversible circuits are not well developed, even for functions with a small number of inputs and outputs. This paper proposes an approach to reversible logic synthesis using a new complexity measure based on shared binary decision diagrams with complemented edges (instead of truth tables or PPRM forms, as in the previous algorithms). The approach can be used with arbitrary libraries of reversible logic gates and arbitrary cost functions. Experiments show promising results in comparison with the known approaches.

REFERENCES

• 1: Abhinav Agrawal , Niraj K. Jha, Synthesis of Reversible Logic, Proceedings of the conference on Design, automation and test in Europe, p.21384, February 16-20, 2004
• 2: Dueck, G. W., Maslov, D., and Miller, D. M. Transformation-based synthesis of networks of Toffoli/Fredkin gates. In IEEE Canadian Conference on Electrical and Computer Engineering, Montreal, Canada, May 2003.
• 3: Kazuo Iwama , Yahiko Kambayashi , Shigeru Yamashita, Transformation rules for designing CNOT-based quantum circuits, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514026]
• 4: Pawel Kerntopf, An Approach to Minimization of Decision Diagrams, Proceedings of the Euromicro Symposium on Digital Systems Design, p.79, September 04-06, 2001
• 5: Kerntopf, P. Binary decision diagrams based on single and multiple generalized Shannon expansions. In Proc. 6th International Symposium on Representations and Methodology of Future Computing Technology, Trier, Germany, March 2003, 183--190.
• 6: Khlopotine, A., Perkowski, M., and Kerntopf, P. Reversible logic synthesis by gate composition. In Notes of the 11th IEEE/ACM International Workshop on Logic and Synthesis, New Orleans, LA, June 2002, 261--266.
• 7: Maslov, D., and Dueck, G. W. Garbage in reversible design of multiple output functions. In Proc. 6th International Symposium on Representations and Methodology of Future Computing Technology, Trier, Germany, March 2003, 162--170.
• 8: Maslov, D., and Dueck, G. W. Asymptotically optimal regular synthesis of reversible logic networks. In Notes of the 12th IEEE/ACM International Workshop on Logic and Synthesis, Laguna Beach, CA, May 2003, 226--230.
• 9: Maslov, D., and Dueck, G. W. Templates for Toffoli network synthesis. In Notes of the 12th IEEE/ACM International Workshop on Logic and Synthesis, Laguna Beach, CA, June 2003, 320--325.
• 10: Dmitri Maslov , GerhardW. Dueck , D. Michael Miller, Simplification of Toffoli Networks via Templates, Proceedings of the 16th symposium on Integrated circuits and systems design, p.53, September 08-11, 2003
• 11: Dmitri Maslov , Gerhard W. Dueck , D. Michael Miller, Fredkin/Toffoli Templates for Reversible Logic Synthesis, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.256, November 09-13, 2003 [doi>10.1109/ICCAD.2003.73]
• 12: Miller, D. M., and Dueck, G. W. Spectral techniques for reversible logic synthesis. In Proc. 6th International Symposium on Representations and Methodology of Future Computing Technology, Trier, Germany, March 2003, 56--62.
• 13: D. Michael Miller , Dmitri Maslov , Gerhard W. Dueck, A transformation based algorithm for reversible logic synthesis, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775915]
• 14: Mishchenko, A., and Perkowski, M. Logic synthesis of reversible wave cascades. In Notes of the 11th IEEE/ACM International Workshop on Logic and Synthesis, New Orleans, LA, June 2002, 197--202.
• 15: Perkowski, M., Jozwiak, L., Kerntopf, P., Mishchenko, A., Al-Rabadi, A., Coppola, A., Buller, A., Xiaoyu Song, Khan, M. H. A., Yanushkevich, S. N., Shmerko, V. P., and Chrzanowska-Jeske, M. A General Decomposition for Reversible Logic. Proc. 5th International Workshop on Applications of Reed-Muller Expansion in Circuit Design, Starkville, MS, Aug. 2001, 119--138.
• 16: Shende, V. V., Prasad, A. K., Markov, I. L., and Hayes, J. P. Reversible logic circuit synthesis. IEEE Trans. CAD, 22, 6 (June 2003), 710--722.
• 17: Tsutomu Sasao , Masahiro Fujita, Representations of Discrete Functions, Kluwer Academic Publishers, Norwell, MA, 1996

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

General Terms:
Design, Theory

Keywords:
reversible logic circuits, synthesis