DECOMPOS : An integrated system for functional decomposition
T. Sasao · 1998
This paper presents a system for disjoint decompositions of logic functions with many inputs. It is a combination of three different methods: 1) Disjoint decompositions with a few bound set variables; 2) Disjoint bi-decompositions; and 3) Decompositions using Jacobian. 1) and 2) are quick, but find only limited classes of decompositions, while 3) finds all disjoint decompositions by spending more time. Weshow the results of decompositions for more than four thousand functions. We also define a new class of functions: Completely bi-decomposable functions. Experimental results show that many practical logic functions have disjoint decompositions and some are completely bi-decomposable functions. I Introduction In general, an n-variable function f requires about 2 n =n gates [23]. Suppose that the function f can be decomposed into twonetworks as shown in Fig. 1.1. Let the numbers of inputs for the network H and G be n 1 and n 2 + 1, respectively, where n 1 + n 2 = n. Then, H and ...