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

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.