A Boolean Heuristic for Disjoint SOP Synthesis

We propose a new heuristic algorithm for Disjoint Sum-of-Products (DSOP) minimization of a Boolean function f, based on a new algebraic criterion for product selection. The basic idea behind the new algorithm is to transform a given irredundant Sum-of-Products (SOP), i.e., a set of products covering the on-set minterms of f, into a disjoint SOP by repeated applications of two transformations. The first transformation selects pairs of suitable overlapping products in the initial SOP and replaces them with pairs of non-overlapping products covering the same minterms. By this step, some products are made disjoint, while keeping the overall number of products in the SOP unchanged. Next, a second transformation returns a completely disjoint SOP. By this second step, the number of products will increase. A set of experiments on a standard collection of combinational benchmarks shows that this new method is efficient and produces better results compared to the current best heuristic, achieving a 34.4% average cost reduction in about the 46% of the benchmarks, with less computation time.