Algorithms for extracting subsystems from a multilevel representation of a system of Boolean functions for joint minimization
Objectives. The purpose of experimental research is to determine the effectiveness of new algorithms for extracting the so-called connected subsystems from formula descriptions of the original system of Boolean functions. Subsequently each of the extracted subsystems is minimized independently of th...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
National Academy of Sciences of Belarus, the United Institute of Informatics Problems
2024-12-01
|
| Series: | Informatika |
| Subjects: | |
| Online Access: | https://inf.grid.by/jour/article/view/1310 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849771481280544768 |
|---|---|
| author | P. N. Bibilo N. A. Kirienko V. I. Romanov |
| author_facet | P. N. Bibilo N. A. Kirienko V. I. Romanov |
| author_sort | P. N. Bibilo |
| collection | DOAJ |
| description | Objectives. The purpose of experimental research is to determine the effectiveness of new algorithms for extracting the so-called connected subsystems from formula descriptions of the original system of Boolean functions. Subsequently each of the extracted subsystems is minimized independently of the others, but the functions that make up each connected subsystem are minimized jointly.Methods. Minimization of subsystems is performed in the class of multilevel BDD representations (BDD – Binary Decision Diagram) or Boolean networks. After obtaining minimized descriptions of circuits, specified as a set of interconnected Shannon expansion formulas that correspond to BDD, or as two-operand logical equations corresponding to Boolean networks, synthesis of logic circuits is carried out in the design library of custom digital CMOS ASIC (Application-Specific Integrated Circuits made using complementary metal oxide semiconductor technology). In Boolean networks, node functions can be the logical operations “conjunction” or “disjunction” over literals of Boolean variables. A literal is a Boolean variable or its inversion. Minimization of BDD representations is carried out according to the number of Shannon decomposition formulas, minimization of Boolean networks – according to the number of literals in the formulas defining the networks.Results. The resulting logic circuits are compared in terms of chip area and speed (time delay). Experiments were carried out on 39 industrial circuit examples. The advantage (in 29 cases) of using the proposed subsystem extraction algorithms is shown compared to joint or separate minimization of the original system of Boolean functions, which is usually performed as the first stage of the synthesis of logic circuits.Conclusion. The new algorithms for subsystem extraction proposed in the paper have proven their effectiveness in the execution of various programs for optimizing multilevel representations of systems of Boolean functions. The developed software package allows improving the results of technologically independent optimization used in the implementation of digital system projects in custom digital CMOS ASIC. |
| format | Article |
| id | doaj-art-0726d1f90fe043889015547e9271f069 |
| institution | DOAJ |
| issn | 1816-0301 |
| language | Russian |
| publishDate | 2024-12-01 |
| publisher | National Academy of Sciences of Belarus, the United Institute of Informatics Problems |
| record_format | Article |
| series | Informatika |
| spelling | doaj-art-0726d1f90fe043889015547e9271f0692025-08-20T03:02:37ZrusNational Academy of Sciences of Belarus, the United Institute of Informatics ProblemsInformatika1816-03012024-12-0121472310.37661/1816-0301-2024-21-4-7-231075Algorithms for extracting subsystems from a multilevel representation of a system of Boolean functions for joint minimizationP. N. Bibilo0N. A. Kirienko1V. I. Romanov2The United Institute of Informatics Problems of the National Academy of Sciences of BelarusThe United Institute of Informatics Problems of the National Academy of Sciences of BelarusThe United Institute of Informatics Problems of the National Academy of Sciences of BelarusObjectives. The purpose of experimental research is to determine the effectiveness of new algorithms for extracting the so-called connected subsystems from formula descriptions of the original system of Boolean functions. Subsequently each of the extracted subsystems is minimized independently of the others, but the functions that make up each connected subsystem are minimized jointly.Methods. Minimization of subsystems is performed in the class of multilevel BDD representations (BDD – Binary Decision Diagram) or Boolean networks. After obtaining minimized descriptions of circuits, specified as a set of interconnected Shannon expansion formulas that correspond to BDD, or as two-operand logical equations corresponding to Boolean networks, synthesis of logic circuits is carried out in the design library of custom digital CMOS ASIC (Application-Specific Integrated Circuits made using complementary metal oxide semiconductor technology). In Boolean networks, node functions can be the logical operations “conjunction” or “disjunction” over literals of Boolean variables. A literal is a Boolean variable or its inversion. Minimization of BDD representations is carried out according to the number of Shannon decomposition formulas, minimization of Boolean networks – according to the number of literals in the formulas defining the networks.Results. The resulting logic circuits are compared in terms of chip area and speed (time delay). Experiments were carried out on 39 industrial circuit examples. The advantage (in 29 cases) of using the proposed subsystem extraction algorithms is shown compared to joint or separate minimization of the original system of Boolean functions, which is usually performed as the first stage of the synthesis of logic circuits.Conclusion. The new algorithms for subsystem extraction proposed in the paper have proven their effectiveness in the execution of various programs for optimizing multilevel representations of systems of Boolean functions. The developed software package allows improving the results of technologically independent optimization used in the implementation of digital system projects in custom digital CMOS ASIC.https://inf.grid.by/jour/article/view/1310system of boolean functionsdisjunctive normal formbinary decision diagramboolean networklogic synthesisvhdlasic |
| spellingShingle | P. N. Bibilo N. A. Kirienko V. I. Romanov Algorithms for extracting subsystems from a multilevel representation of a system of Boolean functions for joint minimization Informatika system of boolean functions disjunctive normal form binary decision diagram boolean network logic synthesis vhdl asic |
| title | Algorithms for extracting subsystems from a multilevel representation of a system of Boolean functions for joint minimization |
| title_full | Algorithms for extracting subsystems from a multilevel representation of a system of Boolean functions for joint minimization |
| title_fullStr | Algorithms for extracting subsystems from a multilevel representation of a system of Boolean functions for joint minimization |
| title_full_unstemmed | Algorithms for extracting subsystems from a multilevel representation of a system of Boolean functions for joint minimization |
| title_short | Algorithms for extracting subsystems from a multilevel representation of a system of Boolean functions for joint minimization |
| title_sort | algorithms for extracting subsystems from a multilevel representation of a system of boolean functions for joint minimization |
| topic | system of boolean functions disjunctive normal form binary decision diagram boolean network logic synthesis vhdl asic |
| url | https://inf.grid.by/jour/article/view/1310 |
| work_keys_str_mv | AT pnbibilo algorithmsforextractingsubsystemsfromamultilevelrepresentationofasystemofbooleanfunctionsforjointminimization AT nakirienko algorithmsforextractingsubsystemsfromamultilevelrepresentationofasystemofbooleanfunctionsforjointminimization AT viromanov algorithmsforextractingsubsystemsfromamultilevelrepresentationofasystemofbooleanfunctionsforjointminimization |