MINIMIZING THE MULTILEVEL REPRESENTATIONS OF SYSTEMS OF BOOLEAN FUNCTIONS BASED ON SHANNON DECOMPOSITION
A locally optimal algorithm is proposed to form a permutation of variables, which are used to obtain successive Shannon decompositions of a system of disjunctive normal forms of completely specified Boolean functions. The goal of it is a multilevel representation of functions which is called a reduc...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
2017-06-01
|
| Series: | Informatika |
| Online Access: | https://inf.grid.by/jour/article/view/211 |
| _version_ | 1797877366408609792 |
|---|---|
| author | P. N. Bibilo Y. Y. Lankevich |
| author_facet | P. N. Bibilo Y. Y. Lankevich |
| author_sort | P. N. Bibilo |
| collection | DOAJ |
| description | A locally optimal algorithm is proposed to form a permutation of variables, which are used to obtain successive Shannon decompositions of a system of disjunctive normal forms of completely specified Boolean functions. The goal of it is a multilevel representation of functions which is called a reduced ordered Binary Decision Diagram. The results of experimental comparison of the program implementing the proposed algorithm and the program implementing the algorithm for enumeration of random permutations are given. The results show the advantage of the proposed algorithm when it is used for synthesis of logical circuits on the basis of library elements. |
| first_indexed | 2024-04-10T02:15:56Z |
| format | Article |
| id | doaj.art-3b56a87838b745769ce023e02985aa20 |
| institution | Directory Open Access Journal |
| issn | 1816-0301 |
| language | Russian |
| last_indexed | 2024-04-10T02:15:56Z |
| publishDate | 2017-06-01 |
| publisher | The United Institute of Informatics Problems of the National Academy of Sciences of Belarus |
| record_format | Article |
| series | Informatika |
| spelling | doaj.art-3b56a87838b745769ce023e02985aa202023-03-13T08:32:18ZrusThe United Institute of Informatics Problems of the National Academy of Sciences of BelarusInformatika1816-03012017-06-0102(54)4557210MINIMIZING THE MULTILEVEL REPRESENTATIONS OF SYSTEMS OF BOOLEAN FUNCTIONS BASED ON SHANNON DECOMPOSITIONP. N. Bibilo0Y. Y. Lankevich1Объединенный институт проблем информатики НАН БеларусиОбъединенный институт проблем информатики НАН БеларусиA locally optimal algorithm is proposed to form a permutation of variables, which are used to obtain successive Shannon decompositions of a system of disjunctive normal forms of completely specified Boolean functions. The goal of it is a multilevel representation of functions which is called a reduced ordered Binary Decision Diagram. The results of experimental comparison of the program implementing the proposed algorithm and the program implementing the algorithm for enumeration of random permutations are given. The results show the advantage of the proposed algorithm when it is used for synthesis of logical circuits on the basis of library elements.https://inf.grid.by/jour/article/view/211 |
| spellingShingle | P. N. Bibilo Y. Y. Lankevich MINIMIZING THE MULTILEVEL REPRESENTATIONS OF SYSTEMS OF BOOLEAN FUNCTIONS BASED ON SHANNON DECOMPOSITION Informatika |
| title | MINIMIZING THE MULTILEVEL REPRESENTATIONS OF SYSTEMS OF BOOLEAN FUNCTIONS BASED ON SHANNON DECOMPOSITION |
| title_full | MINIMIZING THE MULTILEVEL REPRESENTATIONS OF SYSTEMS OF BOOLEAN FUNCTIONS BASED ON SHANNON DECOMPOSITION |
| title_fullStr | MINIMIZING THE MULTILEVEL REPRESENTATIONS OF SYSTEMS OF BOOLEAN FUNCTIONS BASED ON SHANNON DECOMPOSITION |
| title_full_unstemmed | MINIMIZING THE MULTILEVEL REPRESENTATIONS OF SYSTEMS OF BOOLEAN FUNCTIONS BASED ON SHANNON DECOMPOSITION |
| title_short | MINIMIZING THE MULTILEVEL REPRESENTATIONS OF SYSTEMS OF BOOLEAN FUNCTIONS BASED ON SHANNON DECOMPOSITION |
| title_sort | minimizing the multilevel representations of systems of boolean functions based on shannon decomposition |
| url | https://inf.grid.by/jour/article/view/211 |
| work_keys_str_mv | AT pnbibilo minimizingthemultilevelrepresentationsofsystemsofbooleanfunctionsbasedonshannondecomposition AT yylankevich minimizingthemultilevelrepresentationsofsystemsofbooleanfunctionsbasedonshannondecomposition |