Decomposing a System of Boolean Functions into Subsystems of Connected Functions

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.