Journal "Software Engineering"
a journal on theoretical and applied science and technology
ISSN 2220-3397

Issue N8 2017 year

DOI: 10.17587/prin.8.369-384
The Use of Zhegalkin Polynomials for Minimization of Multilevel Representations of Boolean Functions Based on Shannon Expansion
P. N. Bibilo, bibilo@newman.bas-net.by, Yu. Yu. Lankevich, yurafreedom18@gmail.com, The United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk, 220012, Belarus
Corresponding author: Bibilo Petr N., Head of Laboratory, The United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk, 220012, Belarus, E-mail: bibilo@newman.bas-net.by
Received on April 26, 2017
Accepted on May 15, 2017

The synthesis of combinational logic is an actual task of automatic design of digital circuits. It is usually divided into two stages: technologically independent optimization and technological mapping to a given basis of logical elements. The first stage is the most significant one because the minimization of different forms of Boolean function representation is fulfilled in this stage. If the functions of a system are given in DNF (Disjunctive Normal Form) then change to multilevel representations based on Shannon expansion is expedient when synthesizing circuits from logic library elements. The graphical form of this representation is called BDD (Binary Decision Diagram). As a rule, the synthesis of circuits using logical equations that correspond to minimized BDD representation gives better results in comparison with the synthesis using minimized DNF. A minimization of multilevel representation of Boolean function systems based on Shannon expansion with finding equal coefficients (accurate within inversion) and using Zhegalkin polynomials for these purposes is proposed. Zhegalkin polynomials are easily comparable and can be used to get function inversion. It reduces considerably the computation time. Application of a program that implements the proposed algorithms allows obtaining smaller areas of VLSI schemes in comparison with the circuits that are synthesized using minimized circuits of DNF and Shannon expansion where the coefficient inversion is not considered.

Keywords: synthesis of logical circuits, minimization of Boolean functions, Shannon expansion, Zhegalkin polynomial
pp. 369–384
For citation:
Bibilo P. N., Lankevich Yu. Yu. The Use of Zhegalkin Polynomials for Minimization of Multilevel Representations of Boolean Functions Based on Shannon Expansion, Programmnaya Ingeneria, 2017, vol. 8, no. 8, pp. 369—384.