Exact Synthesis of ESOP Forms

We present an exact synthesis approach for computing Exclusive-or Sum-of-Products (ESOP) forms with a minimum number of product terms using Boolean satisfiability. Our approach finds one or more ESOP forms for a given Boolean function. The approach can deal with incompletely specified Boolean functions defined over many Boolean variables and is particularly fast if the Boolean function can be expressed with only a few product terms. We describe the formalization of the ESOP synthesis problem with a fixed number of terms as a decision problem and present search procedures for determining ESOP forms of minimum size. We further discuss how the search procedures can be relaxed to find ESOP forms of small sizes in reasonable time. We experimentally evaluate the performance of the SAT-based synthesis procedures on completely and incompletely specified Boolean functions.


Editor(s):
Drechsler, Rolf
Soeken, Mathias
Published in:
Advanced Boolean Techniques. Selected Papers from the 13th International Workshop on Boolean Problems, 177-194
Year:
Jul 09 2019
Publisher:
Springer
ISBN:
978-3-030-20323-8
Laboratories:




 Record created 2019-09-28, last modified 2019-10-01


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)