Biomedical Engineering Reference
In-Depth Information
include simplification of the logic, mapping the logic to specific technology or li-
braries, timing optimization, and testing or verification of the design. Logic synthesis
is an essential step in the process of digital integrated circuit (IC) design, given the
ever increasing complexity of modern digital ICs. For example, state of the art micro-
processors comprise millions of gates, and their design is made possible only with
the help of computer-aided design (CAD) tools
1
, which include logic synthesis tools
as well.
Logic synthesis techniques can take gene expression observations as inputs and
infer and construct the GRN as a Boolean network (logic circuit), which represents
the
g
i
(
x
) functions of all the genes of the GRN. The resulting circuit can be simulated
using logic synthesis tools to query the long term behavior of the GRN and analyze its
attractor cycles. This thesis employs several logic synthesis techniques, all of which
are based on Boolean Satisfiability (SAT). While SAT is an NP-complete problem,
many Boolean logic problems translate naturally to SAT. Furthermore, SAT is heavily
used in logic synthesis algorithms and in the EDA industry, and as such there are
many efficient SAT solvers that are available for public download. In the remainder
of this chapter, we first present an overview of logic synthesis and SAT, and later
describe the operation of SAT solvers.
1.5.1
Logic Functions and Representation
. The
Boolean
n
-cube
B
n
is a representation
of the
n
-dimensional hyperspace constructed by combining
n
instances of
B
.
Some examples of Boolean
n
-cubes are shown below and in Fig.
1.10
.
Definition I.1:
Suppose that
B
={
0, 1
}
B
1
=
B
={
0, 1
}
B
2
={
0, 1
}
X
{
0, 1
}={
00, 01, 10, 11
}
B
3
={
0, 1
}
X
{
0, 1
}
X
{
0, 1
}={
000, 001, 010, 011, 100, 101, 110, 111
}
Definition I.2:
A
Boolean function
f
is a mapping
f
(
x
1
,
x
2
,
...
,
x
n
):
B
n
→
B
.
In other words,
f
maps each vertex of the Boolean
n
-cube (
B
n
)to0or1.
There are several types of representations for Boolean functions. Some common
representation used in logic synthesis include the Boolean
n
-cube (where each vertex
is mapped toa0or1value), the truth table, the Karnaugh map, and the Boolean
formula.
1
Computer-Aided Design (CAD) tools for IC design are also often referred to as Electronic Design
Automation (EDA) tools.
