ГлавнаяАрхивБыстрый алгоритм синтеза обратимых схем на основе теории групп подстановок

Быстрый алгоритм синтеза обратимых схем на основе теории групп подстановок | Прикладная дискретная математика. 2014. № 2(24).

Рассматриваются различные алгоритмы синтеза обратимых схем. Приведены результаты сравнения этих алгоритмов по основным характеристикам. Предложен новый быстрый алгоритм синтеза обратимых схем, основанный на теории групп подстановок и позволяющий получить схему с вентильной сложностью O(n2 m) за время O(n2 m) без использования дополнительных входов, где n - количество входов схемы, m - верхняя граница логарифма количества подвижных точек заданного преобразования.
  • Title Быстрый алгоритм синтеза обратимых схем на основе теории групп подстановок
  • Headline Быстрый алгоритм синтеза обратимых схем на основе теории групп подстановок
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(24)
  • Date:
  • DOI
Ключевые слова
обратимые схемы, алгоритм синтеза, группы подстановок, invertible logic, synthesis algorithm, permutation groups
Авторы
Ссылки
Закаблуков Д. В., Жуков А. Е. Исследование схем из обратимых логических элементов // Информатика и системы управления в 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.
Быстрый алгоритм синтеза обратимых схем на основе теории групп подстановок | Прикладная дискретная математика. 2014. № 2(24).
Быстрый алгоритм синтеза обратимых схем на основе теории групп подстановок | Прикладная дискретная математика. 2014. № 2(24).