Bounds on the average number of products in the minimum sum-of-products expressions for multiple-value input two-valued output functions

The authors derive an upper and a lower bound on the average number of products in the minimum sum-of-products expressions (SOPEs). The upper bound is obtained by using the minimization results of functions with fewer variables. The lower bound is based on an assumption, so it is incorrect until this assumption is proven. A lower bound L_p(n,u) and an upper bound U_p(n,u) on S_p( n,u) are derived, where S_p(n ,u) is the average number of products in minimum SOPE for p-valued input two-valued output functions, n is the number of the inputs, and u is the number of minterms. The values of S_p(n,u) are obtained by minimizing randomly generated functions, and they are compared to the calculated values of U_p(n,u) and L_p(n,u). These bounds are useful for estimating the size of programming logic arrays