Technology independent optimization when implementing sparse systems of disjunctive normal forms of Boolean functions in ASIC
Objectives. The problem of choosing the best methods and programs for circuit implementation as part of digital ASIC (Application-Specific Integrated Circuit) sparse systems of disjunctive normal forms (DNF) of completely defined Boolean functions is considered. For matrix forms of sparse DNF system...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
National Academy of Sciences of Belarus, the United Institute of Informatics Problems
2024-03-01
|
| Series: | Informatika |
| Subjects: | |
| Online Access: | https://inf.grid.by/jour/article/view/1276 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832543381408972800 |
|---|---|
| author | P. N. Bibilo S. N. Kardash |
| author_facet | P. N. Bibilo S. N. Kardash |
| author_sort | P. N. Bibilo |
| collection | DOAJ |
| description | Objectives. The problem of choosing the best methods and programs for circuit implementation as part of digital ASIC (Application-Specific Integrated Circuit) sparse systems of disjunctive normal forms (DNF) of completely defined Boolean functions is considered. For matrix forms of sparse DNF systems, the ternary matrix specifying elementary conjunctions contains a large proportion of undefined values corresponding to missing literals of Boolean input variables, and the Boolean matrix specifying the occurrences of conjunctions in DNF functions contains a large proportion of zero values.Methods. It is proposed to investigate various methods of technologically independent logical optimization performed at the first stage of logical synthesis: joint minimization of systems of functions in the DNF class, separate and joint minimization in classes of multilevel representations in the form of Boolean networks and BDD representations using mutually inverse cofactors, as well as the division of a system of functions into subsystems with a limited number of input variables and the method of block cover of DNF systems, focused on minimizing the total area of the blocks forming the cover.Results. When implementing sparse DNF systems of Boolean functions in ASIC, along with traditional methods of joint minimization of systems of functions in the DNF class, methods for optimizing multilevel representations of Boolean function systems based on Shannon expansions can be used for technologically independent optimization, while separate minimization and joint minimization of the entire system as a whole turn out to be less effective compared with block partitions and coatings of the DNF system and subsequent minimization of multilevel representations. Schemes obtained as a result of synthesis using minimized representations of Boolean networks often have a smaller area than schemes obtained using minimized BDD representations.Conclusion. For the design of digital ASIC, the effectiveness of combined approach is shown, when initially the block coverage programs of the DNF system is used, followed by the use of programs to minimize multilevel block representations in the form of Boolean networks minimized based on Shannon expansion. |
| format | Article |
| id | doaj-art-aee86a3f36df4ab19214b0db9eb3dbdb |
| institution | Kabale University |
| issn | 1816-0301 |
| language | Russian |
| publishDate | 2024-03-01 |
| publisher | National Academy of Sciences of Belarus, the United Institute of Informatics Problems |
| record_format | Article |
| series | Informatika |
| spelling | doaj-art-aee86a3f36df4ab19214b0db9eb3dbdb2025-02-03T11:46:29ZrusNational Academy of Sciences of Belarus, the United Institute of Informatics ProblemsInformatika1816-03012024-03-01211284710.37661/1816-0301-2024-21-1-28-471059Technology independent optimization when implementing sparse systems of disjunctive normal forms of Boolean functions in ASICP. N. Bibilo0S. N. Kardash1The 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 problem of choosing the best methods and programs for circuit implementation as part of digital ASIC (Application-Specific Integrated Circuit) sparse systems of disjunctive normal forms (DNF) of completely defined Boolean functions is considered. For matrix forms of sparse DNF systems, the ternary matrix specifying elementary conjunctions contains a large proportion of undefined values corresponding to missing literals of Boolean input variables, and the Boolean matrix specifying the occurrences of conjunctions in DNF functions contains a large proportion of zero values.Methods. It is proposed to investigate various methods of technologically independent logical optimization performed at the first stage of logical synthesis: joint minimization of systems of functions in the DNF class, separate and joint minimization in classes of multilevel representations in the form of Boolean networks and BDD representations using mutually inverse cofactors, as well as the division of a system of functions into subsystems with a limited number of input variables and the method of block cover of DNF systems, focused on minimizing the total area of the blocks forming the cover.Results. When implementing sparse DNF systems of Boolean functions in ASIC, along with traditional methods of joint minimization of systems of functions in the DNF class, methods for optimizing multilevel representations of Boolean function systems based on Shannon expansions can be used for technologically independent optimization, while separate minimization and joint minimization of the entire system as a whole turn out to be less effective compared with block partitions and coatings of the DNF system and subsequent minimization of multilevel representations. Schemes obtained as a result of synthesis using minimized representations of Boolean networks often have a smaller area than schemes obtained using minimized BDD representations.Conclusion. For the design of digital ASIC, the effectiveness of combined approach is shown, when initially the block coverage programs of the DNF system is used, followed by the use of programs to minimize multilevel block representations in the form of Boolean networks minimized based on Shannon expansion.https://inf.grid.by/jour/article/view/1276boolean function systemdnfdnf minimizationbinary decision diagramboolean networkshannon expansionblock cover of the dnf systemlogic synthesisasicvhdl |
| spellingShingle | P. N. Bibilo S. N. Kardash Technology independent optimization when implementing sparse systems of disjunctive normal forms of Boolean functions in ASIC Informatika boolean function system dnf dnf minimization binary decision diagram boolean network shannon expansion block cover of the dnf system logic synthesis asic vhdl |
| title | Technology independent optimization when implementing sparse systems of disjunctive normal forms of Boolean functions in ASIC |
| title_full | Technology independent optimization when implementing sparse systems of disjunctive normal forms of Boolean functions in ASIC |
| title_fullStr | Technology independent optimization when implementing sparse systems of disjunctive normal forms of Boolean functions in ASIC |
| title_full_unstemmed | Technology independent optimization when implementing sparse systems of disjunctive normal forms of Boolean functions in ASIC |
| title_short | Technology independent optimization when implementing sparse systems of disjunctive normal forms of Boolean functions in ASIC |
| title_sort | technology independent optimization when implementing sparse systems of disjunctive normal forms of boolean functions in asic |
| topic | boolean function system dnf dnf minimization binary decision diagram boolean network shannon expansion block cover of the dnf system logic synthesis asic vhdl |
| url | https://inf.grid.by/jour/article/view/1276 |
| work_keys_str_mv | AT pnbibilo technologyindependentoptimizationwhenimplementingsparsesystemsofdisjunctivenormalformsofbooleanfunctionsinasic AT snkardash technologyindependentoptimizationwhenimplementingsparsesystemsofdisjunctivenormalformsofbooleanfunctionsinasic |