Fast synthesis of invertible circuits based on permutation group theory

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.