Multi-level logic synthesis using communication complexity

The authors present a novel multilevel logic synthesis technique based on minimizing communication complexity. Intuitively, this approach is viable because for many types of circuits lower bounds on the area needed to implement the circuits have been obtained considering only communication complexity. It performs especially well for functions which are hierarchically decomposable (e.g., adders, parity generators, comparators, etc.). Unlike many other multilevel logic synthesis techniques, this technique enables a lower bound to be computed to determine how well the synthesis was performed. A novel multilevel logic synthesis program based on the techniques described for reducing communication complexity is presented.