Reversible computing: from mathematical group theory to electronical circuit experiment

ABSTRACT

Reversible logic gates of a certain logic width w form a group (isomorphic to the symmetric group of order (2 w )!). Study of the subgroups of this group both teaches us a lot about properties of reversible gates and guides us to synthesize particular circuits. After design, circuits are implemented in prototype silicon chips.

REFERENCES

• 1: I. Markov: "An introduction to reversible circuits", Proceedings of the International Workshop on Logic and Synthesis, Laguna Beach (May 2003), pp. 318--319.
• 2: A. De Vos: "Lossless computing", Proceedings of the I.E.E.E. Workshop on Signal Processing, Poznań(October 2003), pp. 7--14.
• 3: R. Feynman: "Quantum mechanical computers", Optics News 11 (1985), pp. 11--20.
• 4: E. Fredkin and T. Toffoli: "Conservative logic", International Journal of Theoretical Physics 21 (1982), pp. 219--253.
• 5: K. Patel, I. Markov, and J. Hayes: "Optimal synthesis of linear reversible circuits", Proceedings of the 13th International Workshop on Logic and Synthesis, Temecula (June 2004), pp. 470--477.
• 6: P. Kerntopf: "On universality of binary reversible logic gates", Proceedings of the 5 th Workshop on Boolean Problems, Freiberg (September 2002), pp. 47--52.
• 7: A. De Vos and L. Storme: "r-Universal reversible logic gates", Journal of Physics A: Mathematical and General 37 (2004), pp. 5815--5824.
• 8: L. Storme, A. De Vos, and G. Jacobs: "Group theoretical aspects of reversible logic gates", Journal of Universal Computer Science 5 (1999), pp. 307--321.
• 9: D. Maslov and G. Dueck: "Reversible cascades with minimal garbage", I.E.E.E. Transactions on Computer-Aided Design of Integrated Circuits and Systems 23 (2004), pp. 1497--1509.
• 10: V. Shende, A. Prasad, I. Markov, and J. Hayes: "Synthesis of reversible logic circuits", I.E.E.E. Transactions on Computer-Aided Design of Integrated Circuits and Systems 22 (2003), pp. 710--722.
• 11: 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
• 12: Pawel Kerntopf, A new heuristic algorithm for reversible logic synthesis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996789]
• 13: P. Kerntopf: "Reversible logic circuit synthesis based on a new complexity measure", Proceedings of the 13th International Workshop on Logic and Synthesis, Temecula (July 2004), pp. 106--113.
• 14: Y. Van Rentergem, A. De Vos, and L. Storme: "Implementing an arbitrary reversible logic gate", Journal of Physics A: Mathematical and General, to be published.
• 15: K. Krohn and J. Rhodes: "Algebraic theory of machines", Transactions of the American Mathematical Society 116 (1965), pp. 450--464.
• 16: A. Ginzburg: "Algebraic theory of automata", Academic Press, New York (1968), pp. 130--156.
• 17: A. De Vos, B. Raa, and L. Storme: "Generating the group of reversible logic gates", Journal of Physics A: Mathematical and General 35 (2002), pp. 7063--7078.
• 18: I. Chuang and Y. Yamamoto: "The dual-rail quantum bit and quantum error correction", Proceedings of the 4 th Workshop on Physics and Computation, Boston (November 1996), pp. 82--91.
• 19: E. Forsberg: "Reversible logic based on electron waveguide Y-branch switches", Nanotechnology 15 (2004), pp. S298 - S302.
• 20: A. Schlaffer and J. Nossek: "Is there a connection between adiabatic switching and reversible computing?", Proceedings of the European Conference on Circuit Theory and Design, Budapest (August 1997), pp. 944--948.
• 21: Robert W. Floyd , Jeffrey D. Ullman, The Compilation of Regular Expressions into Integrated Circuits, Journal of the ACM (JACM), v.29 n.3, p.603-622, July 1982 [doi>10.1145/322326.322327]
• 22: B. Desoete, A. De Vos, M. Sibiński, and T. Widerski: "Feynman's reversible logic gates, implemented in silicon", Proceedings of the 6 th International Conference on Mixed Design of Integrated Circuits and Systems, Kraków (June 1999), pp. 497--502.
• 23: Bart Desoete , Alexis De Vos, A reversible carry-look-ahead adder using control gates, Integration, the VLSI Journal, v.33 n.1, p.89-104, December 2002 [doi>10.1016/S0167-9260(02)00051-2]
• 24: Y. Van Rentergem and A. De Vos: "Optimal design of a reversible full adder", International Journal of Unconventional Computing, to be published.
• 25: A. De Vos and Y. Van Rentergem: "Energy dissipation in reversible logic addressed by a ramp voltage", Proceedings of the 15th International PATMOS Workshop, Leuven (September 2005), to be published.
• 26: A. De Vos: "Introduction to r-MOS systems", Proceedings of the 4 th Workshop on Physics and Computation, Boston (November 1996), pp. 92--96.
• 27: P. Patra and D. Fussell: "On efficient adiabatic design of MOS circuits", Proceedings of the 4th Workshop on Physics and Computation, Boston (November 1996), pp. 260--269.
• 28: M. Alioto and G. Palumbo: "Analysis and comparison on full adder block in submicron technology", I.E.E.E. Transactions on Very Large Scale Integration Systems 10 (2002), pp. 806--823.
• 29: M. Frank: "Common mistakes in adiabatic logic design and how to avoid them", Proceedings of the Workshop on Methodologies in Low-Power Design, Las Vegas (June 2003), pp. 216--222.
• 30: M. Schönert: "GAP", Computer Algebra Nederland Nieuwsbrief 9 (1992), pp. 19--28.
• 31: R. Singer: "Group Unit : permutation groups", http://www.fractions-plus.com/Ab%20Alg/Permutation_Groups.doc (2003).
• 32: N. Sloane, S. Plouffe, and A. Hulpke : "The on-line encyclopedia of integer sequences", http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A005432 (2004).

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles

General Terms:
Algorithms, Design

Keywords:
coset, double coset, group theory, power dissipation, reversible computing, subgroup