Chapter 8
Exact Synthesis of ESOP Forms
Heinz Riener, Rüdiger Ehlers, Bruno de O. Schmitt, and Giovanni De Micheli
8.1 Introduction
In the design of Very Large-Scale Integration (VLSI) systems, two-level logic
representations are classically used to represent and manipulate Boolean functions.
Exclusive-or Sum-of-Products (ESOP) is a two-level normal form representation of
a Boolean function that consists of one level of multi-input AND gates followed on
the next level by one multi-input XOR gate. ESOP forms play an important role in
logic synthesis due to their improved compactness for arithmetic or communication
circuits with respect to other two-level representations [26] and their excellent testability properties [13]. The inherent reversibility of the XOR operation, moreover,
makes ESOP forms particularly suitable in applications such as security [16, 21] or
quantum computation [8].
The ESOP representation of a Boolean function is not unique, i.e., the same
Boolean function can be expressed as multiple structurally different, but semantically equivalent ESOP forms. In practice, it is important to find a small representation of an ESOP form to reduce the overall costs for realizing it in hardware or
implementing it in software. The problem of synthesizing an ESOP form for a given
Boolean function is to identify a set of product terms over the Boolean variables of
the function such that each minterm in the OFF-set of the function is covered by
the product terms an even number of times and each minterm in the ON-set of the
Boolean function is covered an odd number of times.
H. Riener () · B. d. O. Schmitt · G. De Micheli
EPFL, Lausanne, Switzerland
e-mail: heinz.riener@epfl.ch
R. Ehlers
University of Bremen, Bremen, Germany
© Springer Nature Switzerland AG 2020
R. Drechsler, M. Soeken (eds.), Advanced Boolean Techniques,
https://doi.org/10.1007/978-3-030-20323-8_8
177
Exact Synthesis of ESOP Forms
Heinz Riener, Rüdiger Ehlers, Bruno de O. Schmitt, and Giovanni De Micheli
8.1 Introduction
In the design of Very Large-Scale Integration (VLSI) systems, two-level logic
representations are classically used to represent and manipulate Boolean functions.
Exclusive-or Sum-of-Products (ESOP) is a two-level normal form representation of
a Boolean function that consists of one level of multi-input AND gates followed on
the next level by one multi-input XOR gate. ESOP forms play an important role in
logic synthesis due to their improved compactness for arithmetic or communication
circuits with respect to other two-level representations [26] and their excellent testability properties [13]. The inherent reversibility of the XOR operation, moreover,
makes ESOP forms particularly suitable in applications such as security [16, 21] or
quantum computation [8].
The ESOP representation of a Boolean function is not unique, i.e., the same
Boolean function can be expressed as multiple structurally different, but semantically equivalent ESOP forms. In practice, it is important to find a small representation of an ESOP form to reduce the overall costs for realizing it in hardware or
implementing it in software. The problem of synthesizing an ESOP form for a given
Boolean function is to identify a set of product terms over the Boolean variables of
the function such that each minterm in the OFF-set of the function is covered by
the product terms an even number of times and each minterm in the ON-set of the
Boolean function is covered an odd number of times.
H. Riener () · B. d. O. Schmitt · G. De Micheli
EPFL, Lausanne, Switzerland
e-mail: heinz.riener@epfl.ch
R. Ehlers
University of Bremen, Bremen, Germany
© Springer Nature Switzerland AG 2020
R. Drechsler, M. Soeken (eds.), Advanced Boolean Techniques,
https://doi.org/10.1007/978-3-030-20323-8_8
177