Automated Synthesis of Generalized Reversible Cascades using Genetic Algorithms

Martin Lukac, Mihail Pivtoraiko, Alan Mischenko, and Marek Perkowski. Automated Synthesis of Generalized Reversible Cascades using Genetic Algorithms. In Proceedings of the International Symposium on Boolean Problems, Freiberg, Germany, 2002.

Download

[320.3kB pdf] 

Abstract

We propose an automated synthesis of Reversible logic (RL) circuits using Darwinian and Lamarckian Genetic Algorithms (GA). Our designs are in a form of cascades of generalized gates which generalize factorized Exclusive-Or-Sum-of-Products (ESOP) circuits. GA can be used to explore the problem space of combinational functions and here it is used to evolve reversible logic circuits. We emphasize the role of problem encoding - a well-designed encoding leads to improved results. Our method with well-encoded circuits is compared to standard method on classical benchmarks in GA, and shows good results for synthesis of both random functions and benchmark functions with practical meaning, such as adders.

BibTeX

@INPROCEEDINGS{lukac_etal_sbp02,
  author = {Martin Lukac and Mihail Pivtoraiko and Alan Mischenko and Marek Perkowski},
  title = {Automated Synthesis of Generalized Reversible Cascades using Genetic
	Algorithms},
  booktitle = {Proceedings of the International Symposium on Boolean Problems},
  year = {2002},
  address = {Freiberg, Germany},
  abstract = {We propose an automated synthesis of Reversible logic
                  (RL) circuits using Darwinian and Lamarckian Genetic
                  Algorithms (GA). Our designs are in a form of
                  cascades of generalized gates which generalize
                  factorized Exclusive-Or-Sum-of-Products (ESOP)
                  circuits. GA can be used to explore the problem
                  space of combinational functions and here it is used
                  to evolve reversible logic circuits. We emphasize
                  the role of problem encoding - a well-designed
                  encoding leads to improved results. Our method with
                  well-encoded circuits is compared to standard method
                  on classical benchmarks in GA, and shows good
                  results for synthesis of both random functions and
                  benchmark functions with practical meaning, such as
                  adders.},
  bib2html_pubtype = {Refereed Conference Papers},
  bib2html_rescat = {Reversible Circuit Synthesis},
  owner = {mihail},
  timestamp = {2010.08.07}
}