A SIMPLIFICATION ALGORITHM OF AND-EXOR EXPRESSIONS GUARANTEEING MINIMALITY FOR SOME CLASS OF LOGIC FUNCTIONS

Among all AND-EXOR expressions that represent a logic function f, thos e with a minimum number of products are called minimum AND-EXOR expres sions of f. The number of products in the minimum AND-EXOR expressions of f is denoted by tau(f). The minimization algorithms of AND-EXOR ex pressions take a great deal of time for computing (time complexity O(2 (2n))), where n is the number of variables. Thus it is necessary to de velop a simplification algorithm that does not always find the exact m inimum AND-EXOR expressions but runs fast. This paper presents a simpl ification algorithm of AND-EXOR expressions, which partially guarantee s minimality and has the following properties: (1) it computes a minim um AND-EXOR expression for a logic function f with tau(f) < 3(k + 1), where k is a nonnegative integer; (2) if an AND-EXOR expression obtain ed by this algorithm takes less than or equal to 3(k + 1) of products, then it is minimum; and (3) its time complexity is O(root 3(kn2)+((kC)n)). From the experimental results for k = 0, 1, 2, we can conclude that its computational time is practical for n = 20, 7, 6, respectivel y. Modifying this algorithm, we present an exact minimization algorith m for 5-variable functions, which is faster than previously known ones .