Algorithms for partitioning logical circuits into subcircuits
The problem of partitioning a logical circuit into subcircuits is considered. It is of great importance when performing optimization transformations in the process of circuit synthesis. The brief review of partitioning methods and algorithms is given, and two groups of algorithms are identified: con...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
National Academy of Sciences of Belarus, the United Institute of Informatics Problems
2020-09-01
|
| Series: | Informatika |
| Subjects: | |
| Online Access: | https://inf.grid.by/jour/article/view/1073 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832543416584503296 |
|---|---|
| author | N. A. Kirienko |
| author_facet | N. A. Kirienko |
| author_sort | N. A. Kirienko |
| collection | DOAJ |
| description | The problem of partitioning a logical circuit into subcircuits is considered. It is of great importance when performing optimization transformations in the process of circuit synthesis. The brief review of partitioning methods and algorithms is given, and two groups of algorithms are identified: constructive and iterative one. The interpretation of a logical circuit in the form of a graph is presented. The problem of partitioning in terms of a graph-theoretic model is defined and some algorithms for solving the partitioning problem are proposed. Logic circuit functions are defined by a system of logical equations. Algorithms perform the partitioning the system of logical equations into subsystems with the restrictions of the number of input and output variables. The data structures to execute the algorithms are defined. Various types of equations connections, obtaining better solutions for partitioning are described. The problems of the use of partitioning algorithms to improve the quality of the circuit at the stage of technology-independent optimization are investigated. The results of an experimental study carried out by the BDD optimization procedure for the functional description of the circuit and LeonardoSpectrum synthesis confirm the effectiveness of the developed algorithms. The algorithms are implemented as partitioning circuit procedures in the experimental FLC system for logical design. |
| format | Article |
| id | doaj-art-43d30e3afc6e4e6c9034372fe305f03d |
| institution | Kabale University |
| issn | 1816-0301 |
| language | Russian |
| publishDate | 2020-09-01 |
| publisher | National Academy of Sciences of Belarus, the United Institute of Informatics Problems |
| record_format | Article |
| series | Informatika |
| spelling | doaj-art-43d30e3afc6e4e6c9034372fe305f03d2025-02-03T11:40:29ZrusNational Academy of Sciences of Belarus, the United Institute of Informatics ProblemsInformatika1816-03012020-09-01173546310.37661/1816-0301-2020-17-3-54-63939Algorithms for partitioning logical circuits into subcircuitsN. A. Kirienko0The United Institute of Informatics Problems of the National Academy of Sciences of BelarusThe problem of partitioning a logical circuit into subcircuits is considered. It is of great importance when performing optimization transformations in the process of circuit synthesis. The brief review of partitioning methods and algorithms is given, and two groups of algorithms are identified: constructive and iterative one. The interpretation of a logical circuit in the form of a graph is presented. The problem of partitioning in terms of a graph-theoretic model is defined and some algorithms for solving the partitioning problem are proposed. Logic circuit functions are defined by a system of logical equations. Algorithms perform the partitioning the system of logical equations into subsystems with the restrictions of the number of input and output variables. The data structures to execute the algorithms are defined. Various types of equations connections, obtaining better solutions for partitioning are described. The problems of the use of partitioning algorithms to improve the quality of the circuit at the stage of technology-independent optimization are investigated. The results of an experimental study carried out by the BDD optimization procedure for the functional description of the circuit and LeonardoSpectrum synthesis confirm the effectiveness of the developed algorithms. The algorithms are implemented as partitioning circuit procedures in the experimental FLC system for logical design.https://inf.grid.by/jour/article/view/1073logical circuitlogical circuit partitioningsystems of boolean functionsconstructive algorithmstechnology-independent optimizationsynthesis of logical circuits |
| spellingShingle | N. A. Kirienko Algorithms for partitioning logical circuits into subcircuits Informatika logical circuit logical circuit partitioning systems of boolean functions constructive algorithms technology-independent optimization synthesis of logical circuits |
| title | Algorithms for partitioning logical circuits into subcircuits |
| title_full | Algorithms for partitioning logical circuits into subcircuits |
| title_fullStr | Algorithms for partitioning logical circuits into subcircuits |
| title_full_unstemmed | Algorithms for partitioning logical circuits into subcircuits |
| title_short | Algorithms for partitioning logical circuits into subcircuits |
| title_sort | algorithms for partitioning logical circuits into subcircuits |
| topic | logical circuit logical circuit partitioning systems of boolean functions constructive algorithms technology-independent optimization synthesis of logical circuits |
| url | https://inf.grid.by/jour/article/view/1073 |
| work_keys_str_mv | AT nakirienko algorithmsforpartitioninglogicalcircuitsintosubcircuits |