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!