8 Exact Synthesis of ESOP Forms
189
0
1
2
3
4
5
0
20
40
60
80
100
Minimal size of ESOP
0
50
100
150
0
50
100
Number of ESOPs per function
Fig. 8.3 Synthesis of minimal ESOP forms for NPN4
Fig. 8.4 Karnaugh map of 0x166A
ESOP forms for the representatives (on the left) and the number of ESOP forms
of minimal size per representative (on the right). On average a representative has
12 structurally different minimal ESOP forms. Some representatives can have 100
or more ESOP forms of minimal size. The Boolean function 0x166A (shown in
Fig. 8.4) has the most minimal ESOP forms (in total 126) within the NPN4 classes.
LUT Mapping We synthesized one ESOP form for a fixed number of ESOP
terms and one ESOP form of minimal size using downward and upward search,
respectively, for each Boolean function that occurred in LUT mapping of the EPFL
benchmark suite. For LUT mapping, we used the ABC command if -K 8 [4].
After LUT mapping, we applied exactmine [28] to extract all Boolean functions
from the benchmarks. We obtained 4001 different Boolean functions with up to 8
Boolean variables and used SAT-based ESOP synthesis to compute ESOP forms.
For this experiment, we consider a fixed conflict limit of 10,000. The synthesis
results are presented in Table 8.1: the first column (Terms) is a user-specified
upper limit on the number of terms. The rest of the table is organized in three