Two level Boolean Logic Synthesis Notes | EduRev

Created by: Ankita Sharma

: 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. 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!