A New Heuristic for DSOP Minimization

We give a 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 1's 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 weight to the cubes that, if selected in DSOP, would generate a higher fragmentation of the other cubes. Disjoint cubes are then selected for increasing value of w, and possibly for decreasing size, recomputing the SOP on the residual function at different possible stages as a trade-off between quality of result and computational time. 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 one based on a BDD representation of f.