Lower Bounds on Size of Periodic Functions in Exclusive-OR Sum-of-Products Expressions

Yasuaki NISHITANI; Kensuke SHIMIZU

Lower Bounds on Size of Periodic Functions in Exclusive-OR Sum-of-Products Expressions

Yasuaki NISHITANI, Kensuke SHIMIZU

Full Text Views

0

Share
Cite this

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 n5. 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 2^t+1-periodic function with rank r is proportional to n^2t+r, where t0 and 0r2^t, i.e., in polynomial order,and thet the size of a (2s+1)2^t-periodic function with s0 and t0 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E77-A No.3 pp.475-482

Publication Date: 1994/03/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on the 6th Karuizawa Workshop on Circuits and Systems)

Category: Computer Aided Design (CAD)

Cite this

Copy

Yasuaki NISHITANI, Kensuke SHIMIZU, "Lower Bounds on Size of Periodic Functions in Exclusive-OR Sum-of-Products Expressions" in IEICE TRANSACTIONS on Fundamentals, vol. E77-A, no. 3, pp. 475-482, March 1994, doi: .
Abstract: 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 n5. 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 2^t+1-periodic function with rank r is proportional to n^2t+r, where t0 and 0r2^t, i.e., in polynomial order,and thet the size of a (2s+1)2^t-periodic function with s0 and t0 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e77-a_3_475/_p

Copy

@ARTICLE{e77-a_3_475,
author={Yasuaki NISHITANI, Kensuke SHIMIZU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Lower Bounds on Size of Periodic Functions in Exclusive-OR Sum-of-Products Expressions},
year={1994},
volume={E77-A},
number={3},
pages={475-482},
abstract={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 n5. 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 2^t+1-periodic function with rank r is proportional to n^2t+r, where t0 and 0r2^t, i.e., in polynomial order,and thet the size of a (2s+1)2^t-periodic function with s0 and t0 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.},
keywords={},
doi={},
ISSN={},
month={March},}

Copy

TY - JOUR
TI - Lower Bounds on Size of Periodic Functions in Exclusive-OR Sum-of-Products Expressions
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 475
EP - 482
AU - Yasuaki NISHITANI
AU - Kensuke SHIMIZU
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E77-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 1994
AB - 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 n5. 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 2^t+1-periodic function with rank r is proportional to n^2t+r, where t0 and 0r2^t, i.e., in polynomial order,and thet the size of a (2s+1)2^t-periodic function with s0 and t0 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.
ER -