Computer Science – Discrete Mathematics
Scientific paper
2006-11-06
Computer Science
Discrete Mathematics
29 pages, 12 figures, submitted to Discrete Applied Mathematics
Scientific paper
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.
Lee Tony T.
Ye Tong
No associations
LandOfFree
A Relational Approach to Functional Decomposition of Logic Circuits does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Relational Approach to Functional Decomposition of Logic Circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Relational Approach to Functional Decomposition of Logic Circuits will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-297212