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

Рассматриваются различные алгоритмы синтеза обратимых схем. Приведены результаты сравнения этих алгоритмов по основным характеристикам. Предложен новый быстрый алгоритм синтеза обратимых схем, основанный на теории групп подстановок и позволяющий получить схему с вентильной сложностью $\mathrm O(n2^m)$ за время $\mathrm O(n2^m)$ без использования дополнительных входов, где $n$ – количество входов схемы, $m$ – верхняя граница логарифма количества подвижных точек заданного преобразования.