Compact DSOP and partial DSOP Forms

Details Compact DSOP and partial DSOP Forms Compact DSOP and partial DSOP Forms

2012-04-24

arxiv.org/abs/1204.5306v1

Computer Science

Discrete Mathematics

Scientific paper

Given a Boolean function f on n variables, a Disjoint Sum-of-Products (DSOP) of f is a set of products (ANDs) of subsets of literals whose sum (OR) equals f, such that no two products cover the same minterm of f. DSOP forms are a special instance of partial DSOPs, i.e. the general case where a subset of minterms must be covered exactly once and the other minterms (typically corresponding to don't care conditions of $f$) can be covered any number of times. We discuss finding DSOPs and partial DSOP with a minimal number of products, a problem theoretically connected with various properties of Boolean functions and practically relevant in the synthesis of digital circuits. Finding an absolute minimum is hard, in fact we prove that the problem of absolute minimization of partial DSOPs is NP-hard. Therefore it is crucial to devise a polynomial time heuristic that compares favorably with the known minimization tools. To this end we develop a further piece of theory starting from the definition of the weight of a product p as a functions of the number of fragments induced on other cubes by the selection of p, and show how product weights can be exploited for building a class of minimization heuristics for DSOP and partial DSOP synthesis. A set of experiments conducted on major benchmark functions show that our method, with a family of variants, always generates better results than the ones of previous heuristics, including the method based on a BDD representation of f.

Affiliated with

Also associated with

No associations

Rating

Compact DSOP and partial DSOP Forms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Compact DSOP and partial DSOP Forms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compact DSOP and partial DSOP Forms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-519435