Logical optimization of Boolean nets using Shannon expansion
A synthesis of logical circuits, comprising functional combination blocks of very large scale integration circuits, is one of the most important tasks of computer-aided design. As the data size of design tasks increases, the execution time of synthesis of logic circuits also increases. The global te...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
National Academy of Sciences of Belarus, the United Institute of Informatics Problems
2019-06-01
|
| Series: | Informatika |
| Subjects: | |
| Online Access: | https://inf.grid.by/jour/article/view/658 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849336310849863680 |
|---|---|
| author | P. N. Bibilo Yu. Y. Lankevich |
| author_facet | P. N. Bibilo Yu. Y. Lankevich |
| author_sort | P. N. Bibilo |
| collection | DOAJ |
| description | A synthesis of logical circuits, comprising functional combination blocks of very large scale integration circuits, is one of the most important tasks of computer-aided design. As the data size of design tasks increases, the execution time of synthesis of logic circuits also increases. The global technological independent optimization as the first stage of synthesis of logical circuit is especially labor-consuming. The second stage is technological mapping of optimized logical representations of functions to the logical elements of technological library. The main features of logical circuit, such as area, performance, power consumption, depend on the efficiency of the first stage – global logical optimization. The evolution of methods of global logical optimization has revealed the efficiency of Shannon expansion in case of optimization of multi-level representations of the systems of fully defined Boolean function. A number of methods and programs were developed using graphical representations of Shannon expansions – BDD representations. Most of the developed methods of optimization of BDD-representations use the initial representations of functions systems in the form of disjunctive normal form (DNF).In the article an algorithm of minimization of nodes number of Boolean net, which is a multi-level representation of the system of fully defined Boolean function, is proposed. Minimization is based on Shannon expansion and a search of equal (with accuracy up to inversion) nodes in Boolean net. Such algorithm of logical optimization was implemented as application. The experiments have shown that this algorithm and the application is reasonable to use in cases when the initial multi-level representation of functions is impossible to define as DNF system, or when DNF system contains a large number of elementary conjunctions. |
| format | Article |
| id | doaj-art-e0e15946d37c4d6894d32388b7037530 |
| institution | Kabale University |
| issn | 1816-0301 |
| language | Russian |
| publishDate | 2019-06-01 |
| publisher | National Academy of Sciences of Belarus, the United Institute of Informatics Problems |
| record_format | Article |
| series | Informatika |
| spelling | doaj-art-e0e15946d37c4d6894d32388b70375302025-08-20T03:45:01ZrusNational Academy of Sciences of Belarus, the United Institute of Informatics ProblemsInformatika1816-03012019-06-011627389696Logical optimization of Boolean nets using Shannon expansionP. N. Bibilo0Yu. Y. Lankevich1The 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 BelarusA synthesis of logical circuits, comprising functional combination blocks of very large scale integration circuits, is one of the most important tasks of computer-aided design. As the data size of design tasks increases, the execution time of synthesis of logic circuits also increases. The global technological independent optimization as the first stage of synthesis of logical circuit is especially labor-consuming. The second stage is technological mapping of optimized logical representations of functions to the logical elements of technological library. The main features of logical circuit, such as area, performance, power consumption, depend on the efficiency of the first stage – global logical optimization. The evolution of methods of global logical optimization has revealed the efficiency of Shannon expansion in case of optimization of multi-level representations of the systems of fully defined Boolean function. A number of methods and programs were developed using graphical representations of Shannon expansions – BDD representations. Most of the developed methods of optimization of BDD-representations use the initial representations of functions systems in the form of disjunctive normal form (DNF).In the article an algorithm of minimization of nodes number of Boolean net, which is a multi-level representation of the system of fully defined Boolean function, is proposed. Minimization is based on Shannon expansion and a search of equal (with accuracy up to inversion) nodes in Boolean net. Such algorithm of logical optimization was implemented as application. The experiments have shown that this algorithm and the application is reasonable to use in cases when the initial multi-level representation of functions is impossible to define as DNF system, or when DNF system contains a large number of elementary conjunctions.https://inf.grid.by/jour/article/view/658boolean functionboolean netshannon expansiondisjunctive normal formsynthesis of logical circuitsbdd |
| spellingShingle | P. N. Bibilo Yu. Y. Lankevich Logical optimization of Boolean nets using Shannon expansion Informatika boolean function boolean net shannon expansion disjunctive normal form synthesis of logical circuits bdd |
| title | Logical optimization of Boolean nets using Shannon expansion |
| title_full | Logical optimization of Boolean nets using Shannon expansion |
| title_fullStr | Logical optimization of Boolean nets using Shannon expansion |
| title_full_unstemmed | Logical optimization of Boolean nets using Shannon expansion |
| title_short | Logical optimization of Boolean nets using Shannon expansion |
| title_sort | logical optimization of boolean nets using shannon expansion |
| topic | boolean function boolean net shannon expansion disjunctive normal form synthesis of logical circuits bdd |
| url | https://inf.grid.by/jour/article/view/658 |
| work_keys_str_mv | AT pnbibilo logicaloptimizationofbooleannetsusingshannonexpansion AT yuylankevich logicaloptimizationofbooleannetsusingshannonexpansion |