A heuristic for decomposition in multilevel logic optimization

A heuristic for finding common subexpressions of given Boolean functions based on Shannon-type factoring is proposed. This heuristic limits the search space considerably by applying a top-down approach in which synthesis of a Boolean network flows from the primary outputs to the primary inputs. The common subexpressions and their complements in N variables are extracted before common subexpressions and their complements in (N-1) variables. This decomposition of the network depends on a permutation of Boolean variables and has a polynomial complexity for restricted extraction of complements. A multilevel logic optimization system, MULTI, has been implemented using this heuristic. Good results on several benchmark circuits show its effectiveness.<>