Geodesic
An algorithm for minimization of Boolean functions in the class of Toffoli reversible logic circuits
The Bulletin of Irkutsk State University. Series Mathematics, Tome 25 (2018), pp. 144-158
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper, the problem of Boolean function's representation by the reversible circuits constructed of the Toffoli gates is considered. Interest in this problem is connected with actual studies of the possibility for realization of "cold" computations. It means that when performing such computations, there is no heat dissipation. In general, reversible circuits realize reversible functions. Therefore, Toffoli–Fredkin's method for representation of the Boolean function by the reversible function is used. In work, an algorithm for finding the minimal representation of the Boolean function in a class of the reversible circuits, which are constructed from Toffoli elements is described. The algorithm uses the polynomial normal forms or exclusive-or sum-of-products expressions (ESOPs) of the Boolean function in the operator representation and the problem of finding the minimal representation of the Boolean function in the certain class of operator bundles. The chosen class of operator bundles corresponds to a class of the extended polarized Zhegalkin polynomials, which includes a well-known class of the polarized Zhegalkin polynomials or Reed–Muller forms. In conclusion, the computational results of the algorithm for minimizing the Boolean functions in the class of reversible circuits are given.
Mots-clés : reversible circuit
Keywords: Toffoli functions, Boolean functions, polarized Zhegalkin polynomials or Reed–Muller forms. 
@article{IIGUM_2018_25_a9,
     author = {A. S. Frantseva},
     title = {An algorithm for minimization of {Boolean} functions in the class of {Toffoli} reversible logic circuits},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {144--158},
     year = {2018},
     volume = {25},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2018_25_a9/}
}
TY  - JOUR
AU  - A. S. Frantseva
TI  - An algorithm for minimization of Boolean functions in the class of Toffoli reversible logic circuits
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2018
SP  - 144
EP  - 158
VL  - 25
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2018_25_a9/
LA  - ru
ID  - IIGUM_2018_25_a9
ER  - 
%0 Journal Article
%A A. S. Frantseva
%T An algorithm for minimization of Boolean functions in the class of Toffoli reversible logic circuits
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2018
%P 144-158
%V 25
%U http://geodesic.mathdoc.fr/item/IIGUM_2018_25_a9/
%G ru
%F IIGUM_2018_25_a9
A. S. Frantseva. An algorithm for minimization of Boolean functions in the class of Toffoli reversible logic circuits. The Bulletin of Irkutsk State University. Series Mathematics, Tome 25 (2018), pp. 144-158. http://geodesic.mathdoc.fr/item/IIGUM_2018_25_a9/

[1] Vinokurov S. F., Kazimirov A. S., “Enumeration of operator classes of Boolean functions”, The Bulletin of Irkutsk state University. Series Mathematics, 2:2 (2009), 40–55 (in Russian) | Zbl

[2] Vinokurov S. F., Frantseva A. S., “An approximate algorithm for computing the complexity of reversible functions in the basis of Toffoli”, The Bulletin of Irkutsk state University. Series Mathematics, 4:4 (2011), 12–26 (in Russian)

[3] Vinokurov S. F., Frantseva A. S., “The Complexity of the Representation of Multiple-Output Boolean Functions”, The Bulletin of Irkutsk state University. Series Mathematics, 16 (2016), 30–42 (in Russian) | Zbl

[4] Vinokurov S. F., Peryazev N. A. (eds.), Selected problems of the theory of Boolean functions, Fizmatlit Publ., M., 2001, 192 pp. (in Russian)

[5] The Irkutsk Supercomputer Center of Siberian Branch of the Russian Academy of Science (date of access: 05.05.2018)

[6] Vinokurov S. F., Frantseva A. S., Ryabets L. V., Program for Constructing Minimal Representations of Multiple-output Boolean Functions in The Reversible Logic Circuits, Patent RF, No 2017619310, 2017 (in Russian)

[7] Ryabets L. V., Vinokurov S. F., “An Algorithm of Exact Minimization of Boolean Functions in the Class of Kronecker Forms”, Algebra and theory of models, v. 4, Novosibirsk, 2003, 148–159

[8] Knuth D. E., MMIXware: A RISC Computer for the Third Millennium, Sublibrary: SL 2 – Programming and Software Engineering, LNCS, 1750, Springer, Heidelberg–New York–Dordrecht–London, 2003, 550 pp. | DOI

[9] Fredkin E., Toffoli T., “Conservative Logic”, International Journal of Theoretical Physics, 21:3 (1982), 219–253 | DOI | MR | Zbl

[10] Toffoli T., “Reversible Computing”, Automata, Languages and Programming, Lecture Notes in Computer Science, 85, 1980, 632–644 | DOI | MR | Zbl