188
H. Riener et al.
with
T cube (l) =
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
0,
l≤ 1
7,
l= 2
16,
l= 3
8(l − 1),
l > 3 ∧ n ≥
3l+1
2
16(l − 1), else.
(8.20)
8.5 Experimental Evaluation
We have implemented Algorithm 4 in easy, an open-source toolkit for manipulating
ESOP forms 2 using the prominent state-of-the-art SAT-solver Glucose 4.1 [2] as
decision procedure for Boolean satisfiability.
We have evaluated the SAT-based synthesis approach in four experiments 3 :
1. NPN4: We synthesized all ESOP forms of minimal size for the representatives
of the NPN4 equivalence class.
2. LUT mapping: We synthesized one ESOP form of fixed-size and one of minimal
size for each of the Boolean functions that occurred during LUT mapping of
Boolean networks.
3. Random: We synthesized one ESOP form of fixed-size and one of minimal size
for randomly generated Boolean functions.
4. Reversible logic synthesis: We generate Pseudo-Kronecker Expressions
(PKRMs)—a special case of ESOPs—and ESOP using our exact method and
analyze the effect of ESOP size minimization on the size of the corresponding
quantum circuits. For evaluation, we use the T -metric presented in Sect. 8.4.
All experiments have been conducted on an Intel ® Core ™ i7-7567U CPU @
3.50 GHz with 16 GB RAM.
Correctness All computed ESOP forms have been verified against their specifications, i.e., we simulated all ESOP forms for all possible values and compared the
results of simulation with the initial truth tables of the provided Boolean functions.
Note that it is not possible to verify the minimality of the ESOP forms.
NPN4 We synthesized all ESOP forms of minimum size for all 222 representatives
of the NPN4 equivalence classes [12]. Computing one minimal ESOP form for
each representatives takes 1.6 s, computing all minimal ESOP forms for each
representatives takes 9.2 s. Figure 8.3 shows the histogram of the size of the minimal
2 Easy, https://github.com/hriener/easy.
3 The benchmarks and a detailed evaluation of the synthesis results can be found at https://hriener.
github.io/misc/2018_easy.html.
H. Riener et al.
with
T cube (l) =
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
0,
l≤ 1
7,
l= 2
16,
l= 3
8(l − 1),
l > 3 ∧ n ≥
3l+1
2
16(l − 1), else.
(8.20)
8.5 Experimental Evaluation
We have implemented Algorithm 4 in easy, an open-source toolkit for manipulating
ESOP forms 2 using the prominent state-of-the-art SAT-solver Glucose 4.1 [2] as
decision procedure for Boolean satisfiability.
We have evaluated the SAT-based synthesis approach in four experiments 3 :
1. NPN4: We synthesized all ESOP forms of minimal size for the representatives
of the NPN4 equivalence class.
2. LUT mapping: We synthesized one ESOP form of fixed-size and one of minimal
size for each of the Boolean functions that occurred during LUT mapping of
Boolean networks.
3. Random: We synthesized one ESOP form of fixed-size and one of minimal size
for randomly generated Boolean functions.
4. Reversible logic synthesis: We generate Pseudo-Kronecker Expressions
(PKRMs)—a special case of ESOPs—and ESOP using our exact method and
analyze the effect of ESOP size minimization on the size of the corresponding
quantum circuits. For evaluation, we use the T -metric presented in Sect. 8.4.
All experiments have been conducted on an Intel ® Core ™ i7-7567U CPU @
3.50 GHz with 16 GB RAM.
Correctness All computed ESOP forms have been verified against their specifications, i.e., we simulated all ESOP forms for all possible values and compared the
results of simulation with the initial truth tables of the provided Boolean functions.
Note that it is not possible to verify the minimality of the ESOP forms.
NPN4 We synthesized all ESOP forms of minimum size for all 222 representatives
of the NPN4 equivalence classes [12]. Computing one minimal ESOP form for
each representatives takes 1.6 s, computing all minimal ESOP forms for each
representatives takes 9.2 s. Figure 8.3 shows the histogram of the size of the minimal
2 Easy, https://github.com/hriener/easy.
3 The benchmarks and a detailed evaluation of the synthesis results can be found at https://hriener.
github.io/misc/2018_easy.html.