Geodesic
On length of Boolean functions of a small number of variables in the class of pseudo-polynomials
The Bulletin of Irkutsk State University. Series Mathematics, Tome 33 (2020), pp. 96-105 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Minimization of Boolean functions in their various representations is required in logic design of digital devices. EXOR sums (polynomial forms) are considered among other representations. An EXOR sum (a polynomial form) is an expression that is an EXOR sum of products of factors in a certain form. We can accentuate some classes of EXOR sums (of polynomial forms) such that Fixed Polarized Reed-Muller forms, FPRMs (polarized polynomial forms, PPFs), EXOR Sums of Products, ESOPs (polynomial normal forms, PNFs), EXOR Sums of Pseudo-Products, ESPPs (pseudo-polynomial forms, PSPFs), etc. In series of works, minimization algorithms are devised, and bounds are obtained for the length of functions in these classes of EXOR sums. Herewith, there are different aspects in these researches, in particular, to obtain bounds of the length for the most complex functions of $n$ variables for an arbitrary number $n$ and to find the exact length for functions of a small number of variables. The present work is devoted to finding the exact length for functions of a small number of variables. EXOR Sums of Pseudo-Products, ESPPs (pseudo-polynomial forms, PSPFs) for Boolean functions are considered in it. An EXOR Sum of Pseudo-Products, ESPP (a pseudo-polynomial form, PSPF) is an expression that is an EXOR sum of products of linear functions. The length of an ESPP is the number of its summands; the length of a function in the class of ESPPs is the smallest length among all ESPPs, representing this function. In the work, the complete classification by the length in the class of ESPPs is obtained for functions of four variables. The largest length and the average length in the class of ESPPs are found for functions of five variables.
Keywords: Boolean function, Zhegalkin polynomial, EXOR Sum of Pseudo-Products, length, classification by the length.
Mots-clés : ESPP (pseudo-polynomial form, PSPF) 
@article{IIGUM_2020_33_a6,
     author = {S. N. Selezneva and A. A. Lobanov},
     title = {On length of {Boolean} functions of a small number of variables in the class of pseudo-polynomials},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {96--105},
     year = {2020},
     volume = {33},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2020_33_a6/}
}
TY  - JOUR
AU  - S. N. Selezneva
AU  - A. A. Lobanov
TI  - On length of Boolean functions of a small number of variables in the class of pseudo-polynomials
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2020
SP  - 96
EP  - 105
VL  - 33
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2020_33_a6/
LA  - en
ID  - IIGUM_2020_33_a6
ER  - 
%0 Journal Article
%A S. N. Selezneva
%A A. A. Lobanov
%T On length of Boolean functions of a small number of variables in the class of pseudo-polynomials
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2020
%P 96-105
%V 33
%U http://geodesic.mathdoc.fr/item/IIGUM_2020_33_a6/
%G en
%F IIGUM_2020_33_a6
S. N. Selezneva; A. A. Lobanov. On length of Boolean functions of a small number of variables in the class of pseudo-polynomials. The Bulletin of Irkutsk State University. Series Mathematics, Tome 33 (2020), pp. 96-105. http://geodesic.mathdoc.fr/item/IIGUM_2020_33_a6/

[1] Baliuk A. S., “Complexity lower bound for Boolean functions in the class of extended operator forms”, The Bulletin of Irkutsk State University. Series Mathematics, 30 (2019), 125–140 | DOI | Zbl

[2] Ishikawa R., Hirayama T., Koda G., Shimizu K., “New three-level Boolean expression based on EXOR gates”, IEICE Trans. Inf. Syst., E87-D:5 (2004), 214–1222

[3] Kirichenko K. D., “An upper bound for complexity of polynomial normal forms of Boolean functions”, Discrete Math. Appl., 15:4 (2005), 351–360 | DOI | MR | Zbl

[4] Lozhkin S. A., Shupletsov M. S., Konovodov V. A., Danilov B. R., Zhukov V. V., Bagrov N. Yu., “Raspredelennaya sistema i algoritmy poiska minimal'nyh i blizkih k nim kontaktnyh shem dlya bolevyh funkthiy malogo chisla peremennyh”, Sbornik trudov vserossiyskih nauchno-tehnicheskih konferentsiy “Problemy razrabotki perspektivnyh mikro- i nanoelektronnyh sistem (MES)”, v. 1, 2016, 40–47 (in Russian)

[5] Peryazev N. A., “Complexity of Boolean functions in the class of polarized polynomial forms”, Algebra and Logic, 34 (1995), 177–179 | DOI | MR | Zbl

[6] Sasao T., Besslich P., “On the complexity of mod-2 sum PLA's”, IEEE Trans. on Comput., 39:2 (1990), 262–266 | DOI

[7] Selezneva S. N., “On the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts”, Moscow University Computational Mathematics and Cybernetics, 38:2 (2014), 64–68 | DOI | MR | Zbl

[8] Selezneva S. N., “Order on the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts”, Moscow University Computational Mathematics and Cybernetics, 40:3 (2016), 123–127 | DOI | MR | Zbl

[9] Suprun V. P., “Complexity of Boolean functions in a class of canonical polarized polynomials”, Discrete Math. Appl., 4:3 (1994), 273–277 | DOI | MR | Zbl

[10] Ugryumov E. P., Digital Circuitry, BHV-Petersburg Publ., Saint-Petersburg, 2004, 528 pp.

[11] Vinokurov S. F., Kazimirov A. S., “On the complexity of one class of Boolean functions”, The Bulletin of Irkutsk State University. Series Mathematics, 4 (2010), 2–6 (in Russian) | Zbl

[12] Yablonski S. V., Introduction in Discrete Mathematics, Higher School Publ., M., 2001, 384 pp.