Exact Synthesis for Logic Synthesis Applications with Complex Constraints

Exact synthesis is the problem of finding logic networks that represent given Boolean functions and respect given constraints. With exact synthesis it is possible to find optimum networks, e.g., in size or depth; consequently, it primarily finds application in logic optimization. However, exact synthesis is also very helpful in logic synthesis applications necessitating complex constraints that are present in the hardware primitives or the logic representations for which the synthesis has to be performed. Conventional heuristic logic synthesis algorithms are not considering such constraints. They still can be employed to optimize networks, but they cannot guarantee that optimized networks meets all requirements. Being faced with a logic synthesis application that seeks for low-depth majority-based networks with limited fan-out for small functions, we demonstrate how state-of-the-art exact synthesis algorithms can be adapted and used to find logic networks that match these constraints. To emphasize the need for exact synthesis, we also demonstrate how conventional logic synthesis either fails to find constraint-satisfying logic networks or yields networks of inferior quality.