Geodesic
Fast synthesis of invertible circuits based on permutation group theory
Prikladnaâ diskretnaâ matematika, no. 2 (2014), pp. 101-109.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{PDM_2014_2_a8,
     author = {D. V. Zakablukov},
     title = {Fast synthesis of invertible circuits based on permutation group theory},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {101--109},
     publisher = {mathdoc},
     number = {2},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2014_2_a8/}
}
TY  - JOUR
AU  - D. V. Zakablukov
TI  - Fast synthesis of invertible circuits based on permutation group theory
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2014
SP  - 101
EP  - 109
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2014_2_a8/
LA  - ru
ID  - PDM_2014_2_a8
ER  - 
%0 Journal Article
%A D. V. Zakablukov
%T Fast synthesis of invertible circuits based on permutation group theory
%J Prikladnaâ diskretnaâ matematika
%D 2014
%P 101-109
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2014_2_a8/
%G ru
%F PDM_2014_2_a8
D. V. Zakablukov. Fast synthesis of invertible circuits based on permutation group theory. Prikladnaâ diskretnaâ matematika, no. 2 (2014), pp. 101-109. http://geodesic.mathdoc.fr/item/PDM_2014_2_a8/

[1] Bennett C. H., “Logical reversibility of computation”, IBM J. Res. Dev., 17 (1973), 525–532 | DOI | MR | Zbl

[2] Khlopotine A. B., Perkowski M. A., Kerntopf P., “Reversible logic synthesis by iterative compositions”, Int. Workshop Logic Synthesis (New Orleans, Louisiana, June 4–7, 2002), 261–266

[3] Shende V. V., Prasad A. K., Markov I. L., Hayes J. P., “Synthesis of reversible logic circuits”, IEEE Trans. CAD, 22:6 (2003), 710–722 | DOI

[4] Yang G., Song X., Hung W. N., Perkowski M. A., “Fast synthesis of exact minimal reversible circuits using group theory”, Proc. ASP DAC' 05 (Shanghai, China, January 18–21, 2005), 1002–1005

[5] Miller D. M., Dueck G. W., “Spectral techniques for reversible logic synthesis”, 6th Int. Symp. Representations and Methodology of Future Comput. Technol., Trier, Germany, 2003, 56–62

[6] Miller D. M., Maslov D., Dueck G. W., “A transformation based algorithm for reversible logic synthesis”, Design Automation Conference (DAC), Anaheim, CA, 2003, 318–323

[7] Saeedi M., Sedighi M., Zamani M. S., “A novel synthesis algorithm for reversible circuits”, Int. Conf. on Computer-Aided Design (ICCAD), USA, 2007, 65–68

[8] Yang G., Song X., Hung W. N., et al., “Group theory based synthesis of binary reversible circuits”, 3rd Annual Conf. Theory Appl. of Models of Comput. (TAMC), Beijing, China, 2006, 365–374 | MR | Zbl

[9] Zakablukov D. V., Zhukov A. E., “Issledovanie skhem iz obratimykh logicheskikh elementov”, Informatika i sistemy upravleniya v XXI veke, Cb. trudov molodykh uchenykh, aspirantov i studentov, 9, MGTU im. N. E. Baumana, M., 2012, 148–157