Compact DSOP and partial DSOP forms

DOI10.1007/S00224-013-9447-2MaRDI QIDQ385501zbMATH OpenOpenAlexFDO

Authors A. Bernasconi, Valentina Ciriani, Fabrizio Luccio, L. Pagli

Publication date 2 December 2013

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.5306

zbMATH Keywords

computational complexitydisjoint sum-of-productsheuristicsminimal formproduct weightsum-of-products

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: 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.

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1294428 (Why is no real title available?)
• MINI: A Heuristic Approach for Logic Minimization
• Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table
• Reducibility among combinatorial problems

Cited in

(5)

• An efficient interpolation-based projected sum of product decomposition via genetic algorithm
• Exact Synthesis of ESOP Forms
• An Abstract CNF-to-d-DNNF Compiler Based on Chronological CDCL
• On enumerating short projected models
• On CNF conversion for SAT and SMT enumeration

This page was built for publication: Compact DSOP and partial DSOP forms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q385501)