Design automation tools for efficient implementation of logic functions by decomposition

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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>