For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 Lower Bounds on Size of Periodic Functions in Exclusive-OR Sum-of-Products ExpressionsYasuaki NISHITANI  Kensuke SHIMIZU  Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E77-A   No.3   pp.475-482Publication Date: 1994/03/25Online ISSN:  DOI: Print ISSN: 0916-8508Type of Manuscript: Special Section PAPER (Special Section on the 6th Karuizawa Workshop on Circuits and Systems)Category: Computer Aided Design (CAD)Keyword: exclusive-OR sum-of-products,  size of circuits,  lower bound,  logic minimization,  logic design,  Full Text: PDF>> Buy this Article Summary:  This paper deals with the size of switching functions in Exclusive-OR sum-of-products expressions (ESOPs). The size is the number of products in ESOP. There are no good algorithms to find an exact minimum ESOP. Since the exact minimization algorithms take a time in double exponential order, it is almost impossible to minimize ESOPs for an arbitrary n-variable functions with n 5. Then,it is necessary to study the size of some concrete functions. These concrete functions are useful for testing heuristic minimization algorithms. In this paper we present the lower bounds on size of periodic functions in ESOPs. A symmetric function is said to be periodic when the vector of weights of inputs X such that f(X) 1 is periodic. We show that the size of a 2t+1-periodic function with rank r is proportional to n2t+r, where t 0 and 0 r 2t, i.e., in polynomial order,and thet the size of a (2s+1)2t-periodic function with s 0 and t 0 is greater than or equal to (3/2)n-(2s+1)2t, i.e., in exponential order. The concrete function the size of which is greater than or equal to 32 (3/2)n-8 is presented. This function requires the largest size among the concrete functions the sizes of which are known. Some results for non-periodic symmetric functions are also given.