Application of decision diagrams of incompletely specified of k-valued logic functions in the synthesis of logical circuits
Objectives. The problem of circuit implementation of incompletely specified (partial) k-valued logic functions given by tabular representations is considered. The stage of technologically independent optimization is studied to obtain minimized representations of systems of completely specified Boole...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
National Academy of Sciences of Belarus, the United Institute of Informatics Problems
2023-06-01
|
| Series: | Informatika |
| Subjects: | |
| Online Access: | https://inf.grid.by/jour/article/view/1240 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832543385104154624 |
|---|---|
| author | P. N. Bibilo |
| author_facet | P. N. Bibilo |
| author_sort | P. N. Bibilo |
| collection | DOAJ |
| description | Objectives. The problem of circuit implementation of incompletely specified (partial) k-valued logic functions given by tabular representations is considered. The stage of technologically independent optimization is studied to obtain minimized representations of systems of completely specified Boolean functions from tabular representations of partial functions of k-valued logic. According to these representations of Boolean functions, technological mapping is performed at the second stage of the synthesis of logic circuits.Methods. Using additional definitions of Multi-valued Decision Diagrams (MDD) representing partial functions of k-valued logic, and Binary Decision Diagrams (BDD) representing partial systems of Boolean functions at the stage of technologically independent optimization is proposed. The task of additional definition of MDD is oriented to reducing the number of vertices of the MDD graph that correspond to the cofactors of the Shannon expansion of a multi-valued function.Results. The MDD minimization problem is reduced to solving the problems of coloring undirected graphs of incompatibility of cofactors by minimum number of colors. Encoding of multi-valued values of arguments and values of functions of k-valued logic by binary codes leads to systems of partial Boolean functions, which are also further defined in order to minimize their multi-level BDD representations.Conclusion. The proposed approach makes it possible to define partial multi-valued functions to fully defined Boolean functions in two stages. At the second stage, well-known and effective methods are used to redefine BDD representing systems of partial Boolean functions. As a result of this two-step approach, minimized BDD representations of systems of completely defined functions are obtained. According to completely defined Boolean functions, a technological mapping into a given library of logical elements is performed, i.e. the optimized descriptions of Boolean function systems are covered with descriptions of logical elements |
| format | Article |
| id | doaj-art-c167c0a7b5484e638db9a30e6bf0f6c2 |
| institution | Kabale University |
| issn | 1816-0301 |
| language | Russian |
| publishDate | 2023-06-01 |
| publisher | National Academy of Sciences of Belarus, the United Institute of Informatics Problems |
| record_format | Article |
| series | Informatika |
| spelling | doaj-art-c167c0a7b5484e638db9a30e6bf0f6c22025-02-03T11:46:29ZrusNational Academy of Sciences of Belarus, the United Institute of Informatics ProblemsInformatika1816-03012023-06-01202396410.37661/1816-0301-2023-20-2-39-641031Application of decision diagrams of incompletely specified of k-valued logic functions in the synthesis of logical circuitsP. N. Bibilo0The United Institute of Informatics Problems of the National Academy of Sciences of BelarusObjectives. The problem of circuit implementation of incompletely specified (partial) k-valued logic functions given by tabular representations is considered. The stage of technologically independent optimization is studied to obtain minimized representations of systems of completely specified Boolean functions from tabular representations of partial functions of k-valued logic. According to these representations of Boolean functions, technological mapping is performed at the second stage of the synthesis of logic circuits.Methods. Using additional definitions of Multi-valued Decision Diagrams (MDD) representing partial functions of k-valued logic, and Binary Decision Diagrams (BDD) representing partial systems of Boolean functions at the stage of technologically independent optimization is proposed. The task of additional definition of MDD is oriented to reducing the number of vertices of the MDD graph that correspond to the cofactors of the Shannon expansion of a multi-valued function.Results. The MDD minimization problem is reduced to solving the problems of coloring undirected graphs of incompatibility of cofactors by minimum number of colors. Encoding of multi-valued values of arguments and values of functions of k-valued logic by binary codes leads to systems of partial Boolean functions, which are also further defined in order to minimize their multi-level BDD representations.Conclusion. The proposed approach makes it possible to define partial multi-valued functions to fully defined Boolean functions in two stages. At the second stage, well-known and effective methods are used to redefine BDD representing systems of partial Boolean functions. As a result of this two-step approach, minimized BDD representations of systems of completely defined functions are obtained. According to completely defined Boolean functions, a technological mapping into a given library of logical elements is performed, i.e. the optimized descriptions of Boolean function systems are covered with descriptions of logical elementshttps://inf.grid.by/jour/article/view/1240partial functionsk-valued logicmulti-valued decision diagram (mdd)boolean functionsbinary decision diagram (bdd)shannon expansiondigital logic synthesisvhdlvlsi |
| spellingShingle | P. N. Bibilo Application of decision diagrams of incompletely specified of k-valued logic functions in the synthesis of logical circuits Informatika partial functions k-valued logic multi-valued decision diagram (mdd) boolean functions binary decision diagram (bdd) shannon expansion digital logic synthesis vhdl vlsi |
| title | Application of decision diagrams of incompletely specified of k-valued logic functions in the synthesis of logical circuits |
| title_full | Application of decision diagrams of incompletely specified of k-valued logic functions in the synthesis of logical circuits |
| title_fullStr | Application of decision diagrams of incompletely specified of k-valued logic functions in the synthesis of logical circuits |
| title_full_unstemmed | Application of decision diagrams of incompletely specified of k-valued logic functions in the synthesis of logical circuits |
| title_short | Application of decision diagrams of incompletely specified of k-valued logic functions in the synthesis of logical circuits |
| title_sort | application of decision diagrams of incompletely specified of k valued logic functions in the synthesis of logical circuits |
| topic | partial functions k-valued logic multi-valued decision diagram (mdd) boolean functions binary decision diagram (bdd) shannon expansion digital logic synthesis vhdl vlsi |
| url | https://inf.grid.by/jour/article/view/1240 |
| work_keys_str_mv | AT pnbibilo applicationofdecisiondiagramsofincompletelyspecifiedofkvaluedlogicfunctionsinthesynthesisoflogicalcircuits |