Many logic design automation procedures would benefit from a priori knowledge of complexity of the resulting realization. There are no universally accepted notions of space/time complexity criteria, as such measures are greatly influenced by the target topologies and technology. Even though an accurate measure of logic complexity is extremely difficult to compute, it is possible to obtain rough estimates of relative logic complexities with the use of simple estimators. It is shown that functional complexity criteria are very reliable as relative predictors of logic complexity for functions in particular classes (such as adders, arithmetic functions, etc.) or functions that otherwise have similar structures but do not perform as well when random functions are considered. The functional complexity criterion used in this study can relate the complexities of two adders with different number of bits very well, but cannot predict the relative complexities of two functions in entirely different classes.>

A description is given of linear and disjoint decompositions of completely specified Boolean functions using transform methods. Since previously known transform methods are impractical for automation due to their enormous computational complexity, polynomial approximations to the linear decomposition procedure that use reduced representations of functions are used. Experimental results are reported which establish that such decompositions can often result in improved implementations of logic functions. The disjoint decomposition problem is in the spectral domain, allowing the development of an algorithm that can simultaneously detect multiple decompositions of a given function. This algorithm has low average complexity and has the ability to detect the nonexistence of decompositions quickly.>

A state-assignment procedure is presented that uses only abstract complexity criteria and produces assignments that are not targeted toward particular implementations. It produces networks similar in complexity to those obtained by contemporary methods but is an order of magnitude faster, because it does not use computationally expensive logic synthesis algorithms to predict the effect of assignment on synthesis. Assignments for finite-state machines typically took about 10 minutes on a VAX 11/780.>