This article is cited in 4 papers

Logical Design of Discrete Automata

Fast synthesis of invertible circuits based on permutation group theory

D. V. Zakablukov

N. E. Bauman Moscow State Technical University, Moscow, Russia

Abstract: Various algorithms for the synthesis of invertible 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 $\mathrm O(n2^m)$ and with the time complexity $\mathrm O(n2^m)$ without using additional inputs. Here, $n$ is the number of scheme's inputs and $m$ is the upper bound for $\log k$, where $k$ is the number of non-fixed points of the given invertible transformation.

Keywords: invertible logic, synthesis algorithm, permutation groups.

UDC: 004.312+530.145