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

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅或者付费存取

详细

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.

全文:

受限制的访问

作者简介

Igor 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 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 Kasyanenko

S.M.Kirov Military Medical Academy

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

参考

  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.)

补充文件

附件文件
动作
1. JATS XML
下载