Courses

# Two level Boolean Logic Synthesis Notes | EduRev

## : Two level Boolean Logic Synthesis Notes | EduRev

``` Page 1

Design Verification and Test of
Digital VLSI Circuits
NPTEL Video Course
Module-III
Lecture-I, II and III
Two level Boolean Logic Synthesis
Page 2

Design Verification and Test of
Digital VLSI Circuits
NPTEL Video Course
Module-III
Lecture-I, II and III
Two level Boolean Logic Synthesis
Introduction
•In the last two modules, we discussed that in case of digital VLSI design we start
with high-level system specifications, which are transformed into optimal Register
Transfer Level (RTL) circuits using High Level Synthesis (HLS) algorithms.

•Once the RTL circuit is available, we need to transform it to gate level design,
which can then be processed by backend algorithm; this process is called Logic
Synthesis.  Formally speaking, Boolean logic synthesis is a process by which an
abstract form of desired circuit behavior, typically RTL, is transformed into a design
implementation in terms of logic gates and flip-flops. This module is dedicated to
logic synthesis of combinational and sequential circuits.
•
• It may be noted that two levels of logic are minimum required to implement an
arbitrary Boolean function. Generally, we assume that the primitives are AND and
OR gates and Inverters. AND gates are used at the first level and OR gates are used
in the second level. Inverters may be present at some inputs of the gates of the
first level, but it is not considered as an additional level.
Page 3

Design Verification and Test of
Digital VLSI Circuits
NPTEL Video Course
Module-III
Lecture-I, II and III
Two level Boolean Logic Synthesis
Introduction
•In the last two modules, we discussed that in case of digital VLSI design we start
with high-level system specifications, which are transformed into optimal Register
Transfer Level (RTL) circuits using High Level Synthesis (HLS) algorithms.

•Once the RTL circuit is available, we need to transform it to gate level design,
which can then be processed by backend algorithm; this process is called Logic
Synthesis.  Formally speaking, Boolean logic synthesis is a process by which an
abstract form of desired circuit behavior, typically RTL, is transformed into a design
implementation in terms of logic gates and flip-flops. This module is dedicated to
logic synthesis of combinational and sequential circuits.
•
• It may be noted that two levels of logic are minimum required to implement an
arbitrary Boolean function. Generally, we assume that the primitives are AND and
OR gates and Inverters. AND gates are used at the first level and OR gates are used
in the second level. Inverters may be present at some inputs of the gates of the
first level, but it is not considered as an additional level.
Introduction
•Many other choices are also possible namely, using OR gates at first level and AND
gates in the second, using NOR and NAND gates etc.

•It is also possible to implement a circuit in more than two levels, however, it is
more complex procedure.

•In this triple lecture, we will first discuss two level logic synthesis procedures.
Latter in this module, we will discuss multilevel synthesis.

•There are two main reasons why we may want to implement a circuit in two
levels, rather than multiple levels namely, speed of operation and simplicity of the
algorithms. However, in practical cases two level implementation may not be
possible. Reducing the number of levels increase the fanin and fanout counts of
gates. Gates having high fanins and fanouts are slow. Therefore, design libraries do
not generally have gates with more than four fanins; this requires multiple level
synthesis.
Page 4

Design Verification and Test of
Digital VLSI Circuits
NPTEL Video Course
Module-III
Lecture-I, II and III
Two level Boolean Logic Synthesis
Introduction
•In the last two modules, we discussed that in case of digital VLSI design we start
with high-level system specifications, which are transformed into optimal Register
Transfer Level (RTL) circuits using High Level Synthesis (HLS) algorithms.

•Once the RTL circuit is available, we need to transform it to gate level design,
which can then be processed by backend algorithm; this process is called Logic
Synthesis.  Formally speaking, Boolean logic synthesis is a process by which an
abstract form of desired circuit behavior, typically RTL, is transformed into a design
implementation in terms of logic gates and flip-flops. This module is dedicated to
logic synthesis of combinational and sequential circuits.
•
• It may be noted that two levels of logic are minimum required to implement an
arbitrary Boolean function. Generally, we assume that the primitives are AND and
OR gates and Inverters. AND gates are used at the first level and OR gates are used
in the second level. Inverters may be present at some inputs of the gates of the
first level, but it is not considered as an additional level.
Introduction
•Many other choices are also possible namely, using OR gates at first level and AND
gates in the second, using NOR and NAND gates etc.

•It is also possible to implement a circuit in more than two levels, however, it is
more complex procedure.

•In this triple lecture, we will first discuss two level logic synthesis procedures.
Latter in this module, we will discuss multilevel synthesis.

•There are two main reasons why we may want to implement a circuit in two
levels, rather than multiple levels namely, speed of operation and simplicity of the
algorithms. However, in practical cases two level implementation may not be
possible. Reducing the number of levels increase the fanin and fanout counts of
gates. Gates having high fanins and fanouts are slow. Therefore, design libraries do
not generally have gates with more than four fanins; this requires multiple level
synthesis.
Introduction
we have a Boolean function as 1. 2. 3. 4. 5. 6 7. 8. 9. 10. 11. 12 f x x x x x x x x x x x x ?? .
x1
x2
x3
x4
x5
x6
(a) Two level Implementation
x7
x8
x9
x10
x11
x12
x1
x3
x4
x5
x6
x2
x7
x8
x9
x10
x11
x12
(a) Multi-level Implementation
Page 5

Design Verification and Test of
Digital VLSI Circuits
NPTEL Video Course
Module-III
Lecture-I, II and III
Two level Boolean Logic Synthesis
Introduction
•In the last two modules, we discussed that in case of digital VLSI design we start
with high-level system specifications, which are transformed into optimal Register
Transfer Level (RTL) circuits using High Level Synthesis (HLS) algorithms.

•Once the RTL circuit is available, we need to transform it to gate level design,
which can then be processed by backend algorithm; this process is called Logic
Synthesis.  Formally speaking, Boolean logic synthesis is a process by which an
abstract form of desired circuit behavior, typically RTL, is transformed into a design
implementation in terms of logic gates and flip-flops. This module is dedicated to
logic synthesis of combinational and sequential circuits.
•
• It may be noted that two levels of logic are minimum required to implement an
arbitrary Boolean function. Generally, we assume that the primitives are AND and
OR gates and Inverters. AND gates are used at the first level and OR gates are used
in the second level. Inverters may be present at some inputs of the gates of the
first level, but it is not considered as an additional level.
Introduction
•Many other choices are also possible namely, using OR gates at first level and AND
gates in the second, using NOR and NAND gates etc.

•It is also possible to implement a circuit in more than two levels, however, it is
more complex procedure.

•In this triple lecture, we will first discuss two level logic synthesis procedures.
Latter in this module, we will discuss multilevel synthesis.

•There are two main reasons why we may want to implement a circuit in two
levels, rather than multiple levels namely, speed of operation and simplicity of the
algorithms. However, in practical cases two level implementation may not be
possible. Reducing the number of levels increase the fanin and fanout counts of
gates. Gates having high fanins and fanouts are slow. Therefore, design libraries do
not generally have gates with more than four fanins; this requires multiple level
synthesis.
Introduction
we have a Boolean function as 1. 2. 3. 4. 5. 6 7. 8. 9. 10. 11. 12 f x x x x x x x x x x x x ?? .
x1
x2
x3
x4
x5
x6
(a) Two level Implementation
x7
x8
x9
x10
x11
x12
x1
x3
x4
x5
x6
x2
x7
x8
x9
x10
x11
x12
(a) Multi-level Implementation
Introduction
•If we want to have two level implementation, then we need an AND gate having 6
fanins.  If we have gates with 3 maximum fanins, a multilevel implementation  is
required

• However, two-level implementation is important to be studied. Two-level
implementations are easier to design and analyze because the solution space is
greatly restricted.

Further, before the development of CMOS logic gates, Boolean functions were
realized using Programmable Logic Array (PLAs) and Programmable Array Logic
(PALs).

•These programmable arrays can implement any combinational logic circuit.
Broadly speaking, they have a set of programmable AND planes, which connect to
a set of programmable OR planes; this arrangement is two level AND-OR
realization that can implement functions in terms of sum of products. In addition,
the outputs could be conditionally complemented when required. As PLAs and
PALs worked on “ pr oduc t of sum (POS)/sum of product (SOP)” based
representation, the algorithms for the optimum implementation of two-level
functions were developed in the fifties.
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!