RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



The Bulletin of Irkutsk State University. Series Mathematics:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


The Bulletin of Irkutsk State University. Series Mathematics, 2016, Volume 16, Pages 30–42 (Mi iigum259)  

This article is cited in 1 scientific paper (total in 1 paper)

The complexity of the representation of multiple-output Boolean functions

S. F. Vinokurov, A. S. Frantseva

Irkutsk State University, 1, K. Marx st., Irkutsk, 664003

Abstract: 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, reversible circuits, Reed–Muller forms.

Funding Agency Grant Number
Ministry of Education and Science of the Russian Federation RFMEFI57914X0092


Full text: PDF file (267 kB)
References: PDF file   HTML file
UDC: 519.673
MSC: 94C10

Citation: S. F. Vinokurov, A. S. Frantseva, “The complexity of the representation of multiple-output Boolean functions”, The Bulletin of Irkutsk State University. Series Mathematics, 16 (2016), 30–42

Citation in format AMSBIB
\Bibitem{VinFra16}
\by S.~F.~Vinokurov, A.~S.~Frantseva
\paper The complexity of the representation of multiple-output Boolean functions
\jour The Bulletin of Irkutsk State University. Series Mathematics
\yr 2016
\vol 16
\pages 30--42
\mathnet{http://mi.mathnet.ru/iigum259}


Linking options:
  • http://mi.mathnet.ru/eng/iigum259
  • http://mi.mathnet.ru/eng/iigum/v16/p30

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. S. Frantseva, “Algoritm minimizatsii funktsii algebry logiki v klasse obratimykh skhem Toffoli”, Izvestiya Irkutskogo gosudarstvennogo universiteta. Seriya Matematika, 25 (2018), 144–158  mathnet  crossref
  • Number of views:
    This page:111
    Full text:29
    References:15

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020