Informatika (Sep 2020)
Algorithms for partitioning logical circuits into subcircuits
Abstract
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.
Keywords
