A Graph Theoretic Approach to Switching Function Minimization

✍ Scribed by Kabekode V.S. Bhat

• Publisher: Elsevier Science
• Year: 1982
• Tongue: English
• Weight: 924 KB
• Volume: 313
• Category: Article
• ISSN: 0016-0032
• DOI: 10.1016/0016-0032(82)90005-9

✦ Synopsis

In this paper we pursue the graph theoretic approach to the switching function minimization problem which is still important in view of today's technological innovations such as programmable Logic arrays. We use switching functions graphs (SFG) for studying the structure of switching functions and the minimization problem. The graph theoretic interpretation of the classical minimization problem leads to an alternative and powerful approach to logic design that is suitable for computer implementations. The approach is particularly useful in the analysis and design of suboptimum algorithms for minimization of arbitrarily complex switching functions arising in practice for which exact algorithms are known to be computationally intractable. A few graph theoretic algorithms leading to minimization of switching functions are presented and examples indicating the power of our approach,

and algorithms are worked out. Further work needed in the area is indicated.

IL Switching Function Graph and its Properties

A graph G = (V, E), where V is a set of vertices and E c {[u, vllu, v E V, uf v} is the set of edges. If V can be partitioned into two sets VI and VT such that every edge in G joins a vertex in VI with a vertex in V2, then G is said to be bipartite. An ordering of V is a bijection {1,2, , . . . , ( VI} c, V. We denote the ordering by V = {S}!'l. Vertices Vi and Uj are said to be adjacent if