Decomposing a System of Boolean Functions into Subsystems of Connected Functions
- Authors: Bibilo P.N.1
-
Affiliations:
- United Institute of Informatics Problems, National Academy of Sciences of Belarus
- Issue: Vol 58, No 2 (2019)
- Pages: 167-182
- Section: Computer Methods
- URL: https://journals.rcsi.science/1064-2307/article/view/220313
- DOI: https://doi.org/10.1134/S1064230719020059
- ID: 220313
Cite item
Abstract
This paper suggests some algorithms for decomposing a system of Boolean functions into subsystems of connected functions for representations such as truth tables (TTs), systems of disjunctive normal forms (DNFs), and binary decision diagrams (BDDs). The connectivity of functions consists of the presence of identical parts in the domains of functions from a given system. The algorithms are heuristic and can be used in computer-aided synthesis systems for real-dimension problems with several hundred functions, each having several tens of arguments. The experiments described below prove the efficiency of this decomposition approach in the logic optimization of a system of Boolean functions based on Shannon’s decomposition with the possible use of subfunction inversions.
About the authors
P. N. Bibilo
United Institute of Informatics Problems, National Academy of Sciences of Belarus
Author for correspondence.
Email: bibilo@newman.bas-net.by
Belarus, Minsk