GRAPH-THEORETIC ALGORITHM FOR FINDING MAXIMAL SUPERGATES IN COMBINATIONAL LOGIC-CIRCUITS

Disjunctive decomposition of a large switching function into several s maller switching functions is an efficient way of solving many problem s in logic design and testing areas. Finding disjunctive decomposition of an arbitrary switching function, however, is known to be a very di fficult problem for which no practical solutions have been reported. A lternatively, a practical solution is to identify maximal supergates d efined by Seth er al. (1985) which represent disjunctive decomposition of a logic circuit which realises a given switching function. An algo rithm is presented which identifies maximal supergates in combinationa l logic circuits. The algorithm is based on both the graph-theoretic a lgorithms and the set manipulation algorithms such as depth-first sear ch, biconnectivity and UNION/FIND. The time complexity of the algorith m is O(n + e), where n is the number of gates and e is the number of l inks between gates. Finally, the authors demonstrate experimental resu lts of maximal supergates in ISCAS85 and ISCAS89 benchmark circuits.