4-Variable Boolean Functions Representations Classification in the Form of Nonlinearity Minimal Degree Separating Surfaces

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

In this paper, a classification study was carried out on the construction of 4-variable Boolean functions representations classification in the form of nonlinearity minimal degree separating surfaces. To construct these surfaces was used an adaptive ellipsoid algorithm based on the Khachiyan algorithm for solving systems of linear inequalities with integer coefficients. To define Boolean functions, we used its graphical representation on the projection of a four-dimensional cube. The classification study carried out was not limited only to the search for a separating surface of the minimum degree of nonlinearity. Additionally, the task was set to find the surface with the smallest number of non-zero nonlinear terms in accordance with a given lexicographic order. Based on the results of the study, a catalog of separating surfaces of the nonlinearity minimum degree with the smallest number of nonlinear terms for Boolean functions of 4 variables is constructed, and it is also determined that 15 classes of geometric equivalence functions have a minimum degree of nonlinearity of 1, 166 - degree 2, 40 - degree 3, and 1 function degree 4.

Full Text

Restricted Access

About the authors

Igor I. Lapikov

MIREA - Russian Technological University

Email: lapikov.i.i@yandex.ru
Cand. Sci. (Eng.); аssociate professor at the Cybersecurity and Digital Technologies Institute of the Russian Technological Moscow, Russian Federation

Vladimir G. Nikonov

Russian Academy of Natural Sciences

Email: nikonovu@yandex.ru
Dr. Sci. (Eng.), Professor, Member at the Presidium of the Russian Academy of Natural Sciences Moscow, Russian Federation

Kristina V. Kasyanenko

S.M.Kirov Military Medical Academy

Email: dr.snegur@gmail.com
lecturer Saint-Petersburg, Russian Federation

References

  1. Balakin G.V., Nikonov V.G. Methods of reducing Boolean equations to systems of threshold relations. Review of the appl. Industrial. Math. 1994. Vol. 1. No. 3. Pp. 389-401. (In Rus.)
  2. Ivanescu P.L., Rudeanu S. Boolean methods in operator research and related areas. Berlin; Heidelberg; New York: Springer Verlag, 1968. 331 p.
  3. Khachiyan L.G. Polynomial algorithms in linear programming. ZHVMIMF. 1980. Vol. 20. No. 1. Pp. 51-68. (In Rus.)
  4. Lapikov I.I. On the possibility of constructing a spatial decomposition algorithm based on geometric parallelization of an adaptive ellipsoid algorithm. Computational Nanotechnology. 2018. No. 1. Pp. 140-145. (In Rus.)
  5. Harisson M.A. Introduction to switching and automata theory. NY: McGraw-Hill, 1964. 499 p.
  6. Ninomiya I. A study of the structures of Boolean functions and its application to the synthesis of switching circuits // Mem. Faculty Engineering, Nagoya Univ. 1961. Vol. 13. No. 2. Pp. 149-363.
  7. Nikonov V.G. Classification of minimal basic representations of all Boolean functions from four variables. Review of the Appl. Industrial. Math. 1994. Vol. 1. No. 3. Pp. 458-545. (In Rus.)

Supplementary files

Supplementary Files
Action
1. JATS XML
Download