Geodesic
The complexity of the representation of multiple-output Boolean functions
The Bulletin of Irkutsk State University. Series Mathematics, Tome 16 (2016), pp. 30-42 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

This paper considers cost of logic circuits that implement Boolean functions. The realization of Boolean functions is considered in the class of reversible logic circuits. Reversible circuits are constructed with elementary reversible circuits known as Toffoli gates or Toffoli basis. Traditional Boolean functions are not reversible except for two unary functions. However, Boolean functions can be modeled as so-called multiple-output functions for which the number of outputs is equal to the number of arguments and that are permutations on the set of arguments sets. In the paper, Boolean function is implemented as the multiple-output function that in turn is realized as a reversible circuit constructed in the Toffoli basis. The circuit implementing this function is not uniquely defined. Thus the complexity of the function can be defined as the complexity of the minimal circuit implementing this function. This paper presents results on the complexity of most complex functions and on Shannon function value for the Boolean functions in the class of reversible circuits implemented in a subset of Toffoli basis. The solution to the problem is reduced to solving the problem of finding the Shannon function value for the Boolean functions class in the class of extended Reed–Muller forms. A special sequence of functions is constructed for this class. We have proved that this sequence consists of the most complex functions and found the complexity of these functions.
Keywords: Boolean function, Shannon function, complexity, Toffoli gates, Reed–Muller forms.
Mots-clés : reversible circuits 
@article{IIGUM_2016_16_a2,
     author = {S. F. Vinokurov and A. S. Frantseva},
     title = {The complexity of the representation of multiple-output {Boolean} functions},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {30--42},
     year = {2016},
     volume = {16},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2016_16_a2/}
}
TY  - JOUR
AU  - S. F. Vinokurov
AU  - A. S. Frantseva
TI  - The complexity of the representation of multiple-output Boolean functions
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2016
SP  - 30
EP  - 42
VL  - 16
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2016_16_a2/
LA  - ru
ID  - IIGUM_2016_16_a2
ER  - 
%0 Journal Article
%A S. F. Vinokurov
%A A. S. Frantseva
%T The complexity of the representation of multiple-output Boolean functions
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2016
%P 30-42
%V 16
%U http://geodesic.mathdoc.fr/item/IIGUM_2016_16_a2/
%G ru
%F IIGUM_2016_16_a2
S. F. Vinokurov; A. S. Frantseva. The complexity of the representation of multiple-output Boolean functions. The Bulletin of Irkutsk State University. Series Mathematics, Tome 16 (2016), pp. 30-42. http://geodesic.mathdoc.fr/item/IIGUM_2016_16_a2/

[1] Vinokurov S. F., Frantseva A. S., “An approximate algorithm for computing the complexity of reversible functions in the basis of Toffoli”, Izvestiya Irkutskogo gosudarstvennogo universiteta. Series “Mathematics”, 4:4 (2011), 12–26 (in Russian)

[2] Vinokurov S. F., Frantseva A. S., “Complexity of Boolean functions in some classes of reversible circuits”, Synthesis and complexity of control systems, Articles XVIII International school-seminar (Penza, 28 Sept.–Oct. 2009), ed. O. M. Kasim-Zade, Publishing House of the Mechanics and Mathematics Faculty of Moscow State University, M., 2009, 20–22

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

[4] T. Toffoli, “Bicontinuous Extensions of Invetible Combinatorial Functions”, Mathematical Systems Theory, 14 (1981), 13–23 | DOI | MR | Zbl

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