Synthesizing cubes to satisfy a given intersection pattern

Weikang Qian, Marc D. Riedel, Ivo Rosenberg

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)11-38
Number of pages28
JournalDiscrete Applied Mathematics
Volume193
DOIs
StatePublished - Oct 1 2015

Bibliographical note

Funding Information:
This work is supported in part by a National Science Foundation (NSF) CAREER Award, No. 0845650 , NSF grant (No. CCF-1241987 ), and National Natural Science Foundation of China (NSFC) grant (No. 61204042 ). The authors would like to thank the anonymous reviewers for their constructive comments which greatly improved the quality of this work.

Keywords

  • Boolean product
  • Cube
  • Minterm
  • Two-level logic synthesis

Fingerprint Dive into the research topics of 'Synthesizing cubes to satisfy a given intersection pattern'. Together they form a unique fingerprint.

Cite this