HomeIssuesFast synthesis of invertible circuits based on permutation group theory

Fast synthesis of invertible circuits based on permutation group theory | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 2(24).

Various algorithms for the synthesis of inver-tible logic circuits are considered and their main characteristics are presented. A new fast synthesis algorithm based on permutation group theory is proposed. This algorithm allows to synthesize schemes with the gate complexity O(n2 m) and with the time complexity O(n2 m) without using additional inputs. Here, n is the number of scheme's inputs and m is the upper bound for log к where к is the number of non-fixed points of the given invertible transformation.
Download file
Counter downloads: 77
  • Title Fast synthesis of invertible circuits based on permutation group theory
  • Headline Fast synthesis of invertible circuits based on permutation group theory
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(24)
  • Date:
  • DOI
Keywords
обратимые схемы, алгоритм синтеза, группы подстановок, invertible logic, synthesis algorithm, permutation groups
Authors
References
Закаблуков Д. В., Жуков А. Е. Исследование схем из обратимых логических элементов // Информатика и системы управления в XXI веке: сб. трудов №9 молодых ученых, аспирантов и студентов. М.: МГТУ им. Н. Э. Баумана, 2012. С. 148-157.
Saeedi M., Sedighi M., and Zamani M. S. A novel synthesis algorithm for reversible circuits // Int. Conf. on Computer-Aided Design (ICCAD), USA, 2007. P.65-68
Yang G., SongX., HungW.N., et al. Group theory based synthesis of binary reversible circuits // 3rd Annual Conf. Theory Appl. of Models of Comput. (TAMC), Beijing, China, 2006. P. 365-374
Miller D. M., MaslovD., and Dueck G. W. A transformation based algorithm for reversible logic synthesis // Design Automation Conference (DAC), Anaheim, CA, 2003. P. 318-323.
Miller D. M. and Dueck G. W. Spectral techniques for reversible logic synthesis // 6th Int. Symp. Representations and Methodology of Future Comput. Technol., Trier, Germany, 2003. P. 56-62.
ShendeV.V., Prasad A. K., Markov I. L., and Hayes J. P. Synthesis of reversible logic circuits // IEEE Trans. CAD. 2003. V.22. No. 6. P. 710-722.
Yang G., Song X., Hung W. N., and Perkowski M. A. Fast synthesis of exact minimal reversible circuits using group theory // Proc. ASP DAC'05, Shanghai, China, January 18-21, 2005. P. 1002-1005.
Bennett C. H. Logical reversibility of computation // IBM J. Res. Dev. 1973. V. 17. P. 525-532.
Khlopotine A. B., Perkowski M. A., and Kerntopf P. Reversible logic synthesis by iterative compositions // Int. Workshop Logic Synthesis, New Orleans, Louisiana, June 4-7, 2002. P. 261-266.
Fast synthesis of invertible circuits based on permutation group theory | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 2(24).
Fast synthesis of invertible circuits based on permutation group theory | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 2(24).
Download full-text version
Counter downloads: 203