1-MOD-1- Digital Logic-18-07-2024.pdf

DIGITAL SYSTEMS DESIGN by Dr. Penchalaiah Palla Department of Micro and Nanoelectronics School of Electronics Engineering Vellore Institu...

DIGITAL SYSTEMS DESIGN by Dr. Penchalaiah Palla Department of Micro and Nanoelectronics School of Electronics Engineering Vellore Institute of Technology Vellore, TN Boolean Algebra and Logic Gates 1 MOD-1:DIGITAL LOGIC  Definitions ◆ Switching network One or more inputs One or more outputs ✓ Two Types Combinational The output depends only on the present values of the inputs Logic gates are used Sequential The output depends on present and past input values Boolean Algebra and Logic Gates 9  Boolean Algebra.. Inputs. Network. Outputs.. ◆ Boolean Algebra is used to describe the relationship between inputs and outputs ◆ Boolean Algebra is the logic mathematics used for understanding of digital systems Boolean Algebra and Logic Gates 10  Basic Operations ◆ COMPLEMENT (INVERSE) 0 = 1 and 1 = 0 ' ' A = 1 if A = 0 and A = 0 if A = 1 ' ' 0 is low voltage 1 is high voltage Boolean Algebra and Logic Gates 11  Basic Operations ◆ AND F is 1 if and only if A and B are both 1 Boolean Algebra and Logic Gates 12  Basic Operations ◆ OR F is 1 if and only if A or B (or both) are 1 Boolean Algebra and Logic Gates 13  Basic Theorems Let’s prove each one Boolean Algebra and Logic Gates 14  Simplification Theorems 1. XY + XY = X' 2. ( X + Y )( X + Y ) = X ' 3. X + XY = X 4. X (X +Y) = X 5. ( X + Y )Y = XY ' 6. XY + Y = X + Y ' Boolean Algebra and Logic Gates 15  ◆ Proof 6. R.H.S. = X+Y = X(Y+Y’)+Y(X+X’) = XY+XY’+XY+X’Y = XY+XY’+X’Y = (X+X’)Y+XY’ = Y+XY’ = L.H.S. Boolean Algebra and Logic Gates 16  Truth Table ◆ It can represent a boolean function ◆ For possible input combinations it shows the output value n ◆ There are 2 rows (n is the number of input variables) It ranges from 0 to − 1 n ◆ 2 Boolean Algebra and Logic Gates 17  Examples ◆ Show the truth table for F = X + YZ ' ◆ Show the followings by constructing truth tables X (Y + Z ) = XY + XZ X + YZ = ( X + Y )( X + Z ) Boolean Algebra and Logic Gates 18  Example ◆ Draw the network diagram for F = X + YZ ' Boolean Algebra and Logic Gates 19  Example ◆ Draw the network diagram for F = XYZ + XY Z + X Y ' ' ' ' Boolean Algebra and Logic Gates 20  Operator Precedence ◆ Parenthesis ◆ NOT ◆ AND ◆ OR Boolean Algebra and Logic Gates 21  Inversion ( X + Y ) ' = X 'Y ' Prove with the truth tables… ( XY ) ' = X ' + Y ' ( X 1 + X 2 +... + X n ) = X X...X ' ' 1 ' 2 ' n ( X 1 X 2...X n ) = X + X +... + X ' ' 1 ' 2 ' n ◆ The complement of the product is the sum of the complements ◆ The complement of the sum is the product of the complements Boolean Algebra and Logic Gates 22  Examples ◆ Find the complements of [( A + B )C ] = ? ' ' ' [( AB + C ) D + E ] = ?' ' ' A + (( BC ) ' ' + D)  ' '' =? Boolean Algebra and Logic Gates 23  Study Problems 1. Draw a network to realize the following by using only one AND gate and one OR gate Y = ABCD + ABCE + ABCF 2. Draw a network to realize the following by using two OR gates and two AND gates F = (V + W + X )(V + X + Y )(V + Z ) 3. Prove the following equations using truth table W ' XY + WZ = (W ' + Z )(W + XY ) ( A + C )( AB + C ' ) = AB + AC ' Boolean Algebra and Logic Gates 24  Solution of problem 2 L.H.S.=(V+X+W)(V+X+Y)(V+Z) =[(V+X)+W(V+X)+Y(V+X)+WY](V+Z) =[(V+X)(1+W+Y)+WY](V+Z) =(V+X+WY)(V+Z) This can be implemented by two OR gates and two AND gate. Boolean Algebra and Logic Gates 25  Minterms ◆ Consider variables A and B ◆ Assume that they are somehow combined with AND operator ◆ There are 4 possible combinations AB, A' B, AB ' , A' B ' ◆ Each of those terms is called a minterm (standard product) ◆ In general, if there are n variables, there are 2 n minterms Boolean Algebra and Logic Gates 26  Exercise ◆ List the minterms for 3 variables A B C Minterm Designation 0 0 0 A ' B ' C' m0 0 0 1 A'B'C m1 0 1 0 A ' B C' m2 0 1 1 A'B C m3 1 0 0 A B ' C' m4 1 0 1 A B'C m5 1 1 0 A B C' m6 1 1 1 A B C m7 Boolean Algebra and Logic Gates 27  Maxterms ◆ Consider variables A and B ◆ Assume that they are somehow combined with OR operator ◆ There are 4 possible combinations A + B, A' + B , A + B' , A' + B ' ◆ Each of those terms is called a maxterm (standard sums) ◆ In general, if there are n variables, there are 2 n maxterms Boolean Algebra and Logic Gates 28  Exercise ◆ List the maxterm for 3 variables A B C Maxterm Designation 0 0 0 A+B+C M0 0 0 1 A+B+C' M1 0 1 0 A+B'+C M2 0 1 1 A+B'+C' M3 1 0 0 A'+B+C M4 1 0 1 A'+B+C' M5 1 1 0 A'+B'+C M6 1 1 1 A'+B'+C' M7 Boolean Algebra and Logic Gates 29  Example ◆ Express F in the sum of minterms and product of maxterms formats F = A + BC ' F = A + BC ' = A( B + B ' )(C + C ' ) + ( A + A' ) BC ' = ABC + ABC ' + AB 'C + AB 'C ' + ABC ' + A' BC ' = ABC + ABC ' + AB 'C + AB 'C ' + A' BC ' = m7 + m6 + m5 + m4 + m2 =  (2,4,5,6,7 ) = (0,1,3) Boolean Algebra and Logic Gates 30  Sum-of-Products ◆ All products are the product of single variable only AB + CD E + AC E ' ' ' ' YES A+ B +C + D E' ' YES ( A + B)CD + EF NO Boolean Algebra and Logic Gates 31  Sum-of-Products ◆ One or more AND gates feeding a single OR gate at the output AB + CD E + AC E ' ' ' ' A B' C D' E A C' E' Boolean Algebra and Logic Gates 32  Product-of-Sums ◆ All sums are the sums of single variables ( A + B )(C + D + E )( A + C + E ) ' ' ' ' YES AB C ( D + E ) ' ' YES ( A + B)(C + D) + EF NO Boolean Algebra and Logic Gates 33  Product-of-Sums ◆ One or more OR gates feeding a single AND gate at the output ( A + B ' )(C + D ' + E )( A + C ' + E ' ) A B' C D' E A C' E' Boolean Algebra and Logic Gates 34  Logic Gates F = A B F = A B Boolean Algebra and Logic Gates 35  Exclusive-OR A0 = A A  1 = A' A A = 0 A  A' = 1 A B = B  A ( A  B)  C = A  ( B  C ) = A  B  C A( B  C ) = AB  AC ( A  B) ' = A  B ' = A'  B = AB + A' B ' A  B = 1  A = 1 or B = 1 but not both Boolean Algebra and Logic Gates 36  Equivalence ◆ Equivalence is the complement of exclusive-OR ( A  B) ' = ( A' B + AB ' ) ' = ( A + B ' )( A' + B) = = AB + A' B ' = ( A  B)  A ( A  B) B F = ( A B  C ) + ( B  AC ) ' ' Simplify it… Boolean Algebra and Logic Gates 37  Integrated Circuits ◆ SSI (Small Scale) Less than 10 gates in a package ◆ MSI (Medium Scale) 10-1000 gates in a package ◆ LSI (Large Scale) 1000s of gates in a single package ◆ VLSI (Very Large Scale) Hundred of thousands of gates in a single package Boolean Algebra and Logic Gates 38  Study Problems ◆ Course Book Chapter – 2 Problems 2–1 2–3 2–5 2–8 2 – 12 2 – 14 Boolean Algebra and Logic Gates 39  What is minimization? ◆ Simplifying boolean expressions ◆ Algebraic manipulations is hard since there is not a uniform way of doing it ◆ Karnaugh map or K-map techniques is very commonly used Gate-Level Minimization 40  Two-Variable K-Map Gate-Level Minimization 41  Example F = AB + A' B = B Gate-Level Minimization 42  Example F = AB + A' B + A' B' = A'+ B Gate-Level Minimization 43  Three-Variable K-Map Gate-Level Minimization 44  Three-Variable K-Map Gate-Level Minimization 45  Example F = ABC '+ A' B' C '+ AB ' C + ABC = AB + AC + A' B' C ' Gate-Level Minimization 46  Note ◆ In K-maps, you can have groups of 2, 4, 8, or 16 ◆ You cannot have groups of other combinations such as a group of 6 Gate-Level Minimization 47  Exercises F1 = A' BC + AB ' C '+ AB ' C '+ AB F2 = A' C + A' C '+ AB ' C '+ ABC ' F3 = A' B + A' BC'+C ' Gate-Level Minimization 48  Example ◆ Represent F in the minimal format and draw the network diagram Gate-Level Minimization 49  Example ◆ Represent F in the minimal format and draw the network diagram Gate-Level Minimization 50  Example F =  (0,2,3,4,5,7 ) ◆ Represent F in the minimal format and draw the network diagram Gate-Level Minimization 51  Four-Variable K-Map Gate-Level Minimization 52  Four-Variable K-Map Gate-Level Minimization 53  Example F ( A, B, C , D) =  (0,1,2,4,5,6,8,12,13) ◆ Represent F in the minimal format and draw the network diagram F ( A, B, C, D) = A' C '+ A' D'+C ' D'+ ABC ' Gate-Level Minimization 54  Example F ( A, B, C , D) =  (3,5,6,8,10,11,12,13,15) ◆ Represent F in the minimal format and draw the network diagram Gate-Level Minimization 55  Example ◆ Represent F in the minimal format and draw the network diagram Gate-Level Minimization 56  Prime Implicants ◆ You must cover all of the minterms ◆ You must avoid redundancy ◆ You must follow some rules ◆ Prime Implicant A product term that is generated by combining the maximum number of adjacent squares in the map ◆ Essential Prime Implicant A minterm that is covered by only one prime implicant Gate-Level Minimization 57  Maxterm Simplification ◆ Remember F = (F ' )' Gate-Level Minimization 58  Example ◆ Simplify F in product of sums F ( A, B, C , D) =  (1,2,3,5,6,8,10,11,12 ) Gate-Level Minimization 59  Example (cont) ◆ Step – 1 Fill the K-map for F Gate-Level Minimization 60  Example (cont) ◆ Step – 1 Fill the K-map for F Gate-Level Minimization 61  Example (cont) ◆ Step – 2 Fill zeros in the rest of the squares Gate-Level Minimization 62  Example (cont) ◆ Step – 3 Cover zeros. This is your F’ F ( A, B, C , D)' = A' C ' D'+ AC ' D + BCD + ABC  F ( A, B, C , D) = ( A + C + D)( A'+C + D' )( B'+C '+ D' )( A'+ B'+C ' ) Gate-Level Minimization 63  Important ( A + B )' = A' B ' ( AB )' = A'+ B ' Gate-Level Minimization 64  Don’t Care Conditions ◆ A network is usually composed of sub- networks ◆ Net-1 may not produce all combinations of A,B, and C ◆ In this case, F don’t care about those combinations A Net-1 B Net-2 F C Gate-Level Minimization 65  Don’t Care Conditions X can be A B C F considered 0 0 0 1 as 0 or 1, 0 0 1 x whichever 0 1 0 0 is more 0 1 1 1 convenient 1 0 0 0 1 0 1 0 1 1 0 x 1 1 1 1 F = A' B 'C ' + A' BC + ABC F = A' B 'C ' + A' BC + A' B 'C + ABC = A' B ' + BC F = A' B 'C ' + A' BC + A' B 'C + ABC + ABC ' = A' B ' + BC + AB Gate-Level Minimization 66  NAND/NOR Implementations ◆ AND, OR, and NOT gates can be used to construct the digital systems ◆ However, it is easier to fabricate NAND and NOR gates ◆ So try to replace AND, OR, and NOT gates with NAND or NOR gates Gate-Level Minimization 67  NAND Implementation ◆ First implement with AND-OR ◆ Put bubble at the output of each AND gate ◆ Put bubbles at the inputs of each OR gate ◆ Place necessary inverters Gate-Level Minimization 68  Example F ( A, B) = AB + CD + E Gate-Level Minimization 69  Example F ( A, B) = A' ( BC + D) + AB Gate-Level Minimization 70  Example F ( A, B) = A' ( BC + D) + AB Gate-Level Minimization 71  NOR Implementation ◆ First implement with AND-OR ◆ Put bubble at the inputs of each AND gate ◆ Put bubbles at the output of each OR gate ◆ Place necessary inverters Gate-Level Minimization 72  Example F ( A, B) = ( A + B)C ( D + E ) Gate-Level Minimization 73  Logic Families RTL DCTL IIL saturated DTL HTL Bipolar TTL ECL Logic Family Non-saturated Schottky TTL PMOS Unipolar NMOS CMOS  Integration Levels Gate/transistor ratio is roughly 1/10 – SSI < 12 gates/chip – MSI < 100 gates/chip – LSI …1K gates/chip – VLSI …10K gates/chip – ULSI …100K gates/chip – GSI …1Meg gates/chip  Moore’s law A prediction made by Moore (a co-founder of Intel) in 1965: “… a number of transistors to double every 2 years.”  Characteristics of Logic Families 1. Speed 2. Fan-out 3. Fan-in 4. Power dissipation 5. Propagation delay 6. Noise Margin 7. Figure of Merit = propagation delay X Power dissipation 8. Logic Swing (VOH – VOL) 9. Breadth : No. of functions the we can take from the circuit Resistor-Transistor Logic (RTL) replace diode switch with a transistor switch can be cascaded = large power draw Diode-Transistor Logic (DTL) essentially diode logic with transistor amplification reduced power consumption faster than RTL = DL AND gate Saturating inverter  TTL Bipolar Transistor-Transistor Logic (TTL) first introduced by in 1964 (Texas Instruments) TTL has shaped digital technology in many ways Standard TTL family (e.g. 7400) is obsolete Newer TTL families still used (e.g. 74ALS00) Distinct features Multi-emitter transistors Totem-pole transistor arrangement 2-input NAND Emitter-Coupled Logic (ECL) PROS: Fastest logic family available (~1ns) CONS: low noise margin and high power dissipation Operated in emitter coupled geometry (recall differential amplifier or emitter-follower), transistors are biased and operate near their Q-point (never near saturation!) Logic levels. “0”: –1.7V. “1”: –0.8V Such strange logic levels require extra effort when interfacing to TTL/CMOS logic families. BASIC MOSFET APPLICATIONS: SWITCH, DIGITAL LOGIC GATE MOSFETs may be used to: switch currents, voltages, and power; perform digital logic functions; and amplify small time-varying signals. NMOS Inverter The transistor switch provides an advantage over mechanical switches in both speed and reliability. The transistor switch considered here is also called an inverter. If vI < VT N , the transistor is in cut-off and iD = 0. vO = VDD. When vI = VDD, the transistor is biased in the nonsaturation region vO reaches a minimum value, and the drain current reaches a maximum value. Digital Logic Gate: A two-input NMOS NOR logic gate ▪ If the two inputs are zero, both M1 and M2 are cut off, and VO = 5V. ▪ When V1 = 5V and V2 = 0, the transistor M1 turns on and M2 is still cut off. Transistor M1 is biased in the non-saturation region, and VO reaches a low value. ▪ If we reverse the input voltages such that V1 = 0 and V2 = 5V, then M1 is cut off and M2 is biased in the non-saturation region. Again, VO is at a low value. ▪ If both inputs are high, at V1 = V2 = 5V, then both transistors are biased in the non-saturation region and VO is low. ▪ In actual NMOS logic circuits, the resistor RD is replaced by another NMOS transistor.  CMOS Logic and their characteristics CMOS stands for “Complementary metal Oxide Semiconductor”. Structure of CMOS: CMOS consists of P- channel MOSFET (PMOS) and N-channel MOSFET (NMOS). ▪ NMOS is built over a P substrate. Source and drain are made up of n type material. Here the majority carriers are electrons. NMOS is faster than the PMOS, because the electrons which is the majority carriers travel twice the time faster than the holes. It conducts when the voltage is high and does not conduct when the voltage is low. ▪ PMOS is built over an N substrate. Source and drain are made up of p type material. Here the majority carriers are holes. PMOS is slower than the NMOS. It conducts when the voltage is low and does not conduct when the voltage is high. Working of CMOS: ▪ Both NMOS and PMOS together design the logic function. Same input voltage is used to turn ON one MOSFET and turn OFF other MOSFET. So there is no need of pull up resistor in CMOS. ▪ NMOS is arranged in the pull down network between the output and the ground. PMOS is arranged in the pull up network. This pull up and pull down network is arranged in such a way that when one network is ON, the other network will be OFF. ▪ NMOS is connected with VSS or ground and PMOS is connected with VDD. Characteristics of CMOS: (i) Fan in and Fan out: Number of inputs and outputs connected to the gate, which does not affect the usual performance and does not degrade the voltage. Fan in and Fan out is usually 10 for CMOS. (ii) Power dissipation: It is amount of power the device needs. It is the product of the voltage which is supplied and current needed to produce the output. It is measured in mW. Usually it is 10mW at 1MHZ and 0.1mW at 100KHZ. (iii) Noise Margin:It is the amount of noise voltage allowed at the input and it should not affect the output. The noise margin in CMOS is 45% of the supply voltage. It is usually 2.25V for 5V input. (iV) Propagation Delay: It is the time taken from applying the input to the output produced. It is normally 25 to 150ns. Applications of CMOS: Advantages of CMOS: Analog to digital converter Power consumption is less Image sensors Large fan-out capability Amplifiers High noise immunity and noise margin Power dissipation is low Static RAM Faster than NMOS Registers Microchip Disadvantages of CMOS: Microprocessors and microcontrollers Manufacturing cost is high Transceivers Propagation delay is higher than TTL and ECL  CMOS INVERTER Complementary MOS, or CMOS, circuits contain both n-channel and p-channel MOSFETs. The power dissipation in CMOS logic circuits is much smaller than in NMOS circuits, which makes CMOS very attractive DC Analysis of the CMOS Inverter Both transistors are enhancement-mode devices The parameters of the NMOS: Kn and VT N, where VT N > 0, PMOS: Kp and VT P, where VT P < 0.  CMOS Inverter NMOS VGS=Vin Vin=VDD (high) PMOS VGS= Vin -VDD NMOS VGS= VDD ON, PMOS VGS= 0 OFF, Vout=0 (low) Vin=0 (low) NMOS VGS= 0 OFF PMOS VGS= -VDD ON, Vout= VDD (high) CMOS NAND Gate 1. A= high & B= high M1 and M2 OFF M3 and M4 ON Vout low 2. A= low & B= low M1 and M2 ON M3 and M4 OFF Vout high CMOS NAND Gate 3. A= high & B= low M1 OFF and M2 ON M3 ON and M4 OFF Vout high 4. A= low & B= high M1 ON and M2 OFF M3 OFF and M4 ON Vout high CMOS NOR Gate 1. A= low & B= low 3. A= high & B= high M1 and M2 ON M1 and M2 OFF M3 and M4 OFF M3 and M4 ON Vout high Vout low 2. A= high & B= low M1 and M4 OFF M2 and M3 ON Vout low Logic gates – COMS NOR gate Exercise Draw switch level circuits for different inputs and derive the truth table for this gate Logic gates – COMS NOR gate A B V out Logic truth table 0 0 1 0 1 0 1 0 0 1 1 0