A Relational Approach to Functional Decomposition of Logic Circuits
  Functional decomposition of logic circuits has profound influence on all
quality aspects of the cost-effective implementation of modern digital systems.
In this paper, a relational approach to the decomposition of logic circuits is
proposed. This approach is parallel to the normalization of relational
databases, they are governed by the same concepts of functional dependency (FD)
and multi-valued dependency (MVD). It is manifest that the functional
decomposition of switching function actually exploits the same idea and serves
a similar purpose as database normalization. Partitions play an important role
in the decomposition. The interdependency of two partitions can be represented
by a bipartite graph. We demonstrate that both FD and MVD can be represented by
bipartite graphs with specific topological properties, which are delineated by
partitions of minterms. It follows that our algorithms are procedures of
constructing those specific bipartite graphs of interest to meet the
information-lossless criteria of functional decomposition.
