Compact DSOP Forms Derived from SOP Expressions

  We give a new heuristic for Disjoint Sum-of-Products (DSOP) minimization of a Boolean function $f$, based on a new criterion for product selection. Starting from a Sum-of-Products (SOP) $S$ of $f$, i.e., a set of cubes covering the minterms of $f$, we assign a weight $w(p)$ to each product (cube) $p$ in $S$, where $w(p)$ depends on the intersection of $p$ with the other cubes of $S$. We assign higher weights to the cubes that, if selected in a DSOP, would generate a higher fragmentation of the other cubes. Disjoint cubes are then selected for increasing value of $w$ and decreasing size,  recomputing the SOP on the residual function at different possible stages as a trade-off between quality of result and computational time.
We also propose a heuristic for computing partial DSOP forms, i.e., SOP forms whose cubes cover exactly once a given subset of minterms of the function, and more than once the remaining minterms.
A set of experiments conducted on major benchmark functions show that our method, with all its variants, always generates better results than the ones of previous heuristics, including the one based on a BDD representation of $f$. These experiments have also outlined how re-synthesizing the
residual function in SOP form seems to be crucial for obtaining compact DSOPs.