Polarization of functions when minimizing of Boolean nets

Cover Page

Cite item

Full Text

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

Abstract

The results of an experimental study of a program for technologically independent minimization of multilevel representations of systems of fully defined functions in the form of Boolean nets, which are based on Shannon expansions of systems of disjunctive normal forms (DNF) of Boolean functions, are described. The main attention is paid to the effectiveness of using the choice of the best (in terms of the number of literals of Boolean variables) function polarization option when minimizing of Boolean nets. Polarization refers to the choice of an inverse or conventional form of assignment of each of the system functions. For minimized polarized Boolean nets, logic circuits are synthesized in the design library of digital ASIC (Application-Specific Integrated Circuits). The obtained results are compared in terms of crystal area and speed (time delay) with the synthesis results for minimized unpolarized Boolean nets and for jointly and separately minimized Boolean nets built using polarized DNF systems.

About the authors

P. N. Bibilo

The United Institute of Informatics Problems of the National Academy of Sciences of Belarus

Author for correspondence.
Email: bibilo@newman.bas-net.by

Dr. Sci. (Eng.), Professor

Belarus, Minsk

V. I. Romanov

The United Institute of Informatics Problems of the National Academy of Sciences of Belarus

Email: rom@newman.bas-net.by

Ph. D. (Eng.), Associate Prof.

Belarus, Minsk

References

  1. Brayton R. K., Hachtel G. D., Sangiovanni-Vincentel- li А. L. Synthesis of multi-level combinational logic circuits, Trudy Institute inzhenerov po jelektronike i radiotehnike, 1990, vol. 78, no. 2, pp. 38—83 (In Russian).
  2. Zakrevskij А. D. Logical Synthesis of Cascading Circuit, Moscow, Nauka, 1981, 416 р. (in Russian).
  3. Brayton K. R., Hachtel G. D., McMullen C., Sangiovanni-Vincentelli А. L. Logic Minimization Algorithm for VLSI Synthesis, Boston, Kluwer Academic Publishers, 1984, 193 p.
  4. Zakrevskii A. D. ed. Synthesis of Asynchronous Automata on a Computer, Minsk, Nauka i tekhnika, 1975, 184 p. (in Russian).
  5. Brayton K. R. Factoring logic functions, IBM J. Res. and Developm., 1987, vol. 31, no. 2, pp. 187—198.
  6. Brayton R. K., Rudell R., Sangiovanni-Vincentelli A. L., Wang A. R. MIS: А multiple-level logic optimization systems, IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 1987, vol. CAD-6, no. 6, pp. 1062—1081.
  7. Wey C., Chang S.-M., Jou J.-Y. OPAM: an efficient output phase assignment for multilevel logic minimization, Proceedings 1989 IEEE International Conference on Computer Design: VLSI in Computers and Processors, pp. 271—273, DOI: 10.1109/ ICCD.1989.63369.
  8. Bibilo P. N. Binary decision diagrams in logical design, Moscow, LENAND, 2024, 560 p. (in Russian).
  9. Wey C. L., Chang T. Y. An efficient output assignment for PLA minimization, IEEE Trans. Computer-Aided Design, 1990, vol. 9, no. 1, pp. 1—7.
  10. Bibilo P. N., Romanov V. I. The system of logical optimization of functional structural descriptions of digital circuits based on production-frame knowledge representation model, Problemy razrabotki perspektivnyh mikro- i nanoelektronnyh system, 2020, Sb. trudov pod obshch. red. akad. RANA. L. Stempkovskogo, Moscow, IPPMRAN, 2020, no. 4, pp. 9—16 (in Russian).
  11. Toropov N. R. Minimization of systems of Boolean functions in the class DNF, Logicheskoe proektirovanie, Minsk, Institut tehnicheskoj kibernetiki Nacional’noj akademii nauk Belarusi. 1999, no. 4, pp. 4—19 (in Russian).
  12. Sasao T. Input Variable Assignment and Output Phase Optimization of PLA’s, IEEE Trans. Comput., 1984, vol. C-33, no. 10, pp. 879—894.
  13. Das A., Pradhan S. N. Thermal-aware Output Polarity Selection Based on And-Inverter Graph Manipulation, Recent Advances in Electrical & Electronic Engineering, 2019, vol.12, no. 1, pp. 30—39, doi: 10.2174/2352096511666180320120016
  14. Bibilo P. N., Lankevich Yu. Yu. Experimental investigation of effectiveness of algorithms for minimizing BDD representations of Boolean function systems. Software & Systems, 2020, vol. 33, no. 3, pp. 449—463 (in Russian), doi: 10.15827/0236-235X.131.449-463.
  15. Bibilo P. N. Integrated Circuit Design Systems Based on the VHDL Language. StateCAD, ModelSim, LeonardoSpectrum, Moscow, SOLON-Press Publ., 2005, 384 p. (in Russian).
  16. Kirienko N. A. An algorithm for converting functional descriptions of logic circuits using inverse representations, Tanaevskie chteniya: doklady Devyatoj Mezhdunarodnoj nauchnoj konferencii (29—30 marta 2021, Minsk), Minsk, OIPI NAN Belarusi, 2021, pp. 39—43 (in Russian).
  17. Bibilo P. N. Joint and separate minimization of multilevel representations of Boolean function systems, Informacionnye tehnologii, 2023, vol. 29, no. 11, pp. 574—582, DOI: 10.17587/ it.29.574-582 (in Russian).

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Informacionnye Tehnologii


СМИ зарегистрировано Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор).
Регистрационный номер и дата принятия решения о регистрации СМИ: серия ПИ № 77 - 15565 от 02 июня 2003 г.