Corresponding author: Cheburakhin Igor F., PhD, Professor, MAI (NRU) — Moscow Aviation Institute (National Research University), Moscow, 125993, Russian Federation, e-mail: logicifch@yandex.ru

Received on September 20, 2016
Accepted on October 26, 2016

Currently relevance of modeling problems of analysis and synthesis of mathematical models of discrete logic control and computing devices persists. Particularly important is the task of estimating the output of difficulty in presenting a Boolean function (BF) in the classes of formulas and schemes of functional elements (FE). This problem is still relevant today. Because of ongoing research in the field of mathematical cybernetics and discrete mathematics should be that obtaining the required minimum solutions using dimensions of complexity inevitably involves the use of nature exhaustive search algorithms. The result is a greater complexity (including computational complexity and labor input) obtaining such a decision has the functions of small dimension. This required the development of new approaches formulation of the problem and its solutions, significantly differ in the complexity of exhaustive search [1—3]. So, the problem of the realization of Boolean functions in the class of formulas and — circuits made of functional elements in different bases. Obtained in this scheme are applied in discrete logic devices, and management information processing, the complexity (quality) of the main characteristics of which depend on computing and control engineering. And it noted that the symmetric Boolean functions are increasingly being used in the design of computing devices due to their specific properties [7—8].The purpose of this paper is to clarify the upper bounds for the complexity of symmetric BF in standard and Zhegalkin bases, as well as the development of algorithms to automate the synthesis of discrete information processing devices. An efficient constructive method synthesis of digital circuits and formulas is offered. This method is based on recurrence relations (functional equations — FE [9]) and is accompanied by a receipt in advance analytically upper estimates of various indicators of complexity (the number of letters, number of subformulas; according to the number of functional elements), including schemes for minimum complexity. In this paper we consider some classes of functions, which are accurate upper bounds for the complexity metrics. To automate the process and expanding the study of individual cases the algorithm implemented structural and functional decomposition [2] is used. A convenient model for the representation of a Zhegalkin polynomial form that used in the algorithm the matrix representation has been designed. The results are applicable as in the synthesis device (at the logical design) in multiprocessor computing and control systems, and the development of algorithms for the effective operation of these systems.
Keywords: boolean function, syntheses formula and circuit, decomposition, difficulty, minimization, functional of the equation, symmetric functions

For citation:
Cheburakhin I. F., Gavrish O. N. About One Efficient Method of Synthesis of Boolean Formulas and Circuits of Functional Elements, Mekhatronika, Avtomatizatsiya, Upravlenie, 2017, vol. 18, no. 6, pp. 407—414.

DOI: 10.17587/mau.18.407-414

To the contents