Minimization of AND-EXOR Expressions Using Rewrite Rules

This paper considers conditions for generating optimal two-level AND-EXOR representations using rewrite rules. Four results are presented. First, a necessary condition for obtaining minimality is a temporary increase in the size of expressions during minimization. Second, a sufficient condition for obtaining minimality consists of adding certain two rules to rule sets proposed in the literature. Third, we define transformations that allow the minimization of an expression to proceed by minimizing a transformed expression instead. Fourth, we determine experimentally that the above three theoretical results lead to better benchmarks results as well. © 1993 IEEE