8 Exact Synthesis of ESOP Forms
181
function is provided as specification. In case of completely specified Boolean
functions, this objective can be formally described as follows: given a single-output
Boolean function f : B n → B over n Boolean variables x 1 , . . . , x n , find an integer
k and constants l i,j ∈ B 3 for 1 ≤ i ≤ n and 1 ≤ j ≤ k such that
k
j =1
n
i=1
x
l i,j
i
= f (x 1 , . . . , x n ) for all x 1 , . . . , x n ∈ B
n
(8.6)
and k is minimal. The case of incompletely specified Boolean functions can be
addressed similarly to (8.6).
Example 8.1 As an introductory example, consider the incompletely specified
Boolean function described by the truth table 0x688C802028222222 1 over 6
Boolean variables with care function 0x6AAEFF3FFEBFEAA6. A minimal ESOP
form, for instance, is
¯
x 1 x 3 ¯
x 4 ¯
x 5 x 6 ⊕ ¯
x 1 x 2 ¯
x 3 x 5 ¯
x 6 ⊕ ¯
x 1 ¯
x 3 ¯
x 4 ¯
x 6 ⊕ ¯
x 2 ¯
x 5 ¯
x 6 ⊕ ¯
x 1 x 2 x 6 ,
(8.7)
which requires 5 product terms and can be equivalently written as
0-1001 0-00-0 -0--00 010-10 01---1.
(8.8)
In general, minimal ESOPs are not unique. The same Boolean function may also
be represented as the ESOP form
0-1001 0100-0 -0--00 0-0-10 01---1
(8.9)
or
0-1001 0-00-0 ----00 011-10 01----.
(8.10)
Finding minimal ESOP forms is, due to the large combinational search space, a
challenging problem. In [23], a minimal ESOP form for the Boolean function in the
previous example was found on average in roughly 668.22 s using integer non-linear
programming using different starting points and Matlab as a solving engine. The
authors, moreover, point out that decomposition-based ESOP synthesis approaches,
e.g., [25], require up to 4 h for synthesizing minimal ESOP forms for incompletely
specified Boolean functions over 6 Boolean variables.
1 We use hexadecimal notation to shorten the string representation of the (binary) truth tables of
Boolean functions.
181
function is provided as specification. In case of completely specified Boolean
functions, this objective can be formally described as follows: given a single-output
Boolean function f : B n → B over n Boolean variables x 1 , . . . , x n , find an integer
k and constants l i,j ∈ B 3 for 1 ≤ i ≤ n and 1 ≤ j ≤ k such that
k
j =1
n
i=1
x
l i,j
i
= f (x 1 , . . . , x n ) for all x 1 , . . . , x n ∈ B
n
(8.6)
and k is minimal. The case of incompletely specified Boolean functions can be
addressed similarly to (8.6).
Example 8.1 As an introductory example, consider the incompletely specified
Boolean function described by the truth table 0x688C802028222222 1 over 6
Boolean variables with care function 0x6AAEFF3FFEBFEAA6. A minimal ESOP
form, for instance, is
¯
x 1 x 3 ¯
x 4 ¯
x 5 x 6 ⊕ ¯
x 1 x 2 ¯
x 3 x 5 ¯
x 6 ⊕ ¯
x 1 ¯
x 3 ¯
x 4 ¯
x 6 ⊕ ¯
x 2 ¯
x 5 ¯
x 6 ⊕ ¯
x 1 x 2 x 6 ,
(8.7)
which requires 5 product terms and can be equivalently written as
0-1001 0-00-0 -0--00 010-10 01---1.
(8.8)
In general, minimal ESOPs are not unique. The same Boolean function may also
be represented as the ESOP form
0-1001 0100-0 -0--00 0-0-10 01---1
(8.9)
or
0-1001 0-00-0 ----00 011-10 01----.
(8.10)
Finding minimal ESOP forms is, due to the large combinational search space, a
challenging problem. In [23], a minimal ESOP form for the Boolean function in the
previous example was found on average in roughly 668.22 s using integer non-linear
programming using different starting points and Matlab as a solving engine. The
authors, moreover, point out that decomposition-based ESOP synthesis approaches,
e.g., [25], require up to 4 h for synthesizing minimal ESOP forms for incompletely
specified Boolean functions over 6 Boolean variables.
1 We use hexadecimal notation to shorten the string representation of the (binary) truth tables of
Boolean functions.