A minimization method for AND-EXOR expression using lower bound theorem

This paper presents properties of Exclusive-OR Sum-of-Products expressions (ESOPs) and their minimization algorithm. First, lower bounds on the number of products in minimum ESOPs (MESOPs) are shown. Then an algorithm to simplify ESOPs is presented. In most cases, the algorithm proves their minimality for functions of up to five variables. It utilizes a table of MESOPs for all the functions of four variables, and: 1) finds a lower bound on the number of products in the MESOP; 2) obtains an initial solution for the given function; 3) simplifies the ESOP by an iterative improvement method; and 4) stops the iterative improvement when the solution is proved to be minimum. Experimental results show that this algorithm proves the minimality of about 98 percent of the five-variable functions