TY - JOUR

T1 - Synthesizing cubes to satisfy a given intersection pattern

AU - Qian, Weikang

AU - Riedel, Marc D.

AU - Rosenberg, Ivo

N1 - Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.

PY - 2015/10/1

Y1 - 2015/10/1

N2 - In two-level logic synthesis, the typical input specification is a set of minterms defining the on set and a set of minterms defining the don't care set of a Boolean function. The problem is to synthesize an optimal set of product terms, or cubes, that covers all the minterms in the on set and some of the minterms in the don't care set. In this paper, we consider a different specification: instead of the on set and the don't care set, we are given a set of numbers, each of which specifies the number of minterms covered by the intersection of one of the subsets of a set of λ cubes. We refer to the given set of numbers as an intersection pattern. The problem is to determine whether there exists a set of λ cubes that satisfies the given intersection pattern and, if it exists, to synthesize the set of cubes. We show a necessary and sufficient condition for the existence of λ cubes to satisfy a given intersection pattern. We also show that the synthesis problem can be reduced to the problem of finding a non-negative solution to a set of linear equations and inequalities.

AB - In two-level logic synthesis, the typical input specification is a set of minterms defining the on set and a set of minterms defining the don't care set of a Boolean function. The problem is to synthesize an optimal set of product terms, or cubes, that covers all the minterms in the on set and some of the minterms in the don't care set. In this paper, we consider a different specification: instead of the on set and the don't care set, we are given a set of numbers, each of which specifies the number of minterms covered by the intersection of one of the subsets of a set of λ cubes. We refer to the given set of numbers as an intersection pattern. The problem is to determine whether there exists a set of λ cubes that satisfies the given intersection pattern and, if it exists, to synthesize the set of cubes. We show a necessary and sufficient condition for the existence of λ cubes to satisfy a given intersection pattern. We also show that the synthesis problem can be reduced to the problem of finding a non-negative solution to a set of linear equations and inequalities.

KW - Boolean product

KW - Cube

KW - Minterm

KW - Two-level logic synthesis

UR - http://www.scopus.com/inward/record.url?scp=84938285316&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84938285316&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2015.03.012

DO - 10.1016/j.dam.2015.03.012

M3 - Article

AN - SCOPUS:84938285316

SN - 0166-218X

VL - 193

SP - 11

EP - 38

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -