L2: Combinational Logic Design (Construction and Boolean Algebra)Review: Noise MarginTTL Logic Style (1970’s-early 80’s)MOS Technology: The NMOS SwitchNMOS Device CharacteristicsPMOS: The Complementary SwitchThe CMOS InverterInverter VTC: Load Line AnalysisPossible Function of Two InputsCommon Logic GatesExclusive (N)OR GateGeneric CMOS RecipeTheorems of Boolean Algebra (I)Theorems of Boolean Algebra (II)Simple Example: One Bit AdderSimplify Boolean ExpressionsSum-of-Products & Product-of-SumMapping Between FormsThe Uniting TheoremBoolean CubesHigher Dimension CubesKarnaugh MapsK-Map ExamplesFour Variable Karnaugh MapK-Map Example: Don’t CaresHazardsFixing HazardsL2: 6.111 Spring 2006 1Introductory Digital Systems LaboratoryL2: Combinational Logic Design L2: Combinational Logic Design (Construction and Boolean Algebra)(Construction and Boolean Algebra)Acknowledgements: Lecture material adapted from Chapter 2 of R. Katz, G. Borriello, “Contemporary Logic Design” (second edition), Pearson Education, 2005. Some lecture material adapted from J. Rabaey, A. Chandrakasan, B. Nikolic, “Digital Integrated Circuits: A Design Perspective” Copyright 2003 Prentice Hall/Pearson.L2: 6.111 Spring 2006 2Introductory Digital Systems LaboratoryReview: Noise Margin Review: Noise Margin Truth TableIN OUT0110INOUT"1""0"VOHVIHVILVOLUndefinedRegionV(x)VIHVILSlope = -1Slope = -1VOLVOHV(y)VOHNML= VIL -VOLNMH= VOH -VIHVOL Large noise margins protect against various noise sourcesL2: 6.111 Spring 2006 3Introductory Digital Systems LaboratoryTTL Logic Style (1970TTL Logic Style (1970’’ss--early 80early 80’’s)s)74LS04(courtesy TI)+-vBEvCEECBQ1Q2Q3+-L2: 6.111 Spring 2006 4Introductory Digital Systems LaboratoryMOS Technology: The NMOS SwitchMOS Technology: The NMOS SwitchDGSgateN+P-substrateN+drainsourceRNMOSSwitchModelVT= 0.5VVsRNMOSOFFONVGS< VTVGS> VTNMOS ON when Switch Input is HighL2: 6.111 Spring 2006 5Introductory Digital Systems LaboratoryNMOS Device Characteristics NMOS Device Characteristics 0 0.5 1 1.5 2 2.50123456x 10-4VDS(V)ID(A)VGS= 2.5 VVGS= 2.0 VVGS= 1.5 VVGS= 1.0 VResistive SaturationPolysiliconAluminumDGSVT= 0.5VID+-VGS¾ MOS is a very non-linear. ¾ Switch-resistor model sufficient for first order analysis.L2: 6.111 Spring 2006 6Introductory Digital Systems LaboratoryPMOS: The Complementary SwitchPMOS: The Complementary SwitchSGDgateP+N-substrateP+drainsourceVT= -0.5VVDDRPMOSRPMOSOFFSwitchModelONVGS> VTVGS< VTPMOS ON when Switch Input is LowL2: 6.111 Spring 2006 7Introductory Digital Systems LaboratoryThe CMOS InverterThe CMOS InverterINOUTVDDVDDSwitch ModelSRPMOSGGOUTRNMOSININDDSRail-to-rail Swing in CMOSL2: 6.111 Spring 2006 8Introductory Digital Systems LaboratoryInverter VTC: Load Line AnalysisInverter VTC: Load Line AnalysisIDnVoutVin = 2.5Vin = 2Vin = 1.5Vin = 0Vin = 0.5Vin = 1NMOSVin = 0Vin = 0.5Vin = 1Vin = 1.5Vin = 2Vin = 2.5Vin = 1Vin = 1.5PMOS0 0.5 1 1.5 2 2.500.511.522.5Vin (V)Vout(V)INOUTVDDSGDDSGCMOS gates have: Rail-to-rail swing (0V to VDD) Large noise margins “zero” static power dissipationL2: 6.111 Spring 2006 9Introductory Digital Systems LaboratoryPossible Function of Two InputsPossible Function of Two InputsXYFX Y 16 possible functions (F0–F15)0 000000000111111110 100001111000011111 000110011001100111 10101010101010101XYX NOR YNOT (X OR Y)X NAND YNOT (X AND Y)10NOT XX AND YX OR YNOT YX XOR YX = YThere are 16 possible functions of 2 input variables:In general, there are 2 (2^n)functions of n inputsL2: 6.111 Spring 2006 10Introductory Digital Systems LaboratoryCommon Logic GatesCommon Logic GatesGate Symbol Truth-Table ExpressionXY Z001101110110XYZNANDZ = X • YXY Z001100100011XYANDZZ = X • YXY Z001101100010ZXYZ = X + YNORXY Z001100110111ZXYORZ = X + YL2: 6.111 Spring 2006 11Introductory Digital Systems LaboratoryExclusive (N)OR GateExclusive (N)OR GateXY Z001100110110Z = X Y + X YX or Y but not both ("inequality", "difference")XYZXOR(X ⊕ Y)XY Z001101100011XNOR(X ⊕ Y)Z = X Y + X YX and Y the same ("equality")ZXYWidely used in arithmetic structures such as adders and multipliersL2: 6.111 Spring 2006 12Introductory Digital Systems LaboratoryGeneric CMOS RecipeGeneric CMOS RecipeVddA1F(A1,…,An)pullup: make this connectionwhen we want F(A1,…,An) = 1pulldown: make this connectionwhen we want F(A1,…,An) = 0An.........Note: CMOS gates result in inverting functions!(easier to build NAND vs. AND)ABBAPUNA B PDN PUN O0 0 0ff 0n 10 1 0ff 0n 11 0 0ff 0n 11 1 0n 0ff 0OABCLPDNHow do you build a 2-input NOR Gate?L2: 6.111 Spring 2006 13Introductory Digital Systems LaboratoryTheorems of Boolean Algebra (I)Theorems of Boolean Algebra (I) Elementary1. X + 0 = X 1D. X • 1 = X2. X + 1 = 1 2D. X • 0 = 03. X + X = X 3D. X • X = X4. (X) = X5. X + X = 1 5D. X • X = 0 Commutativity:6. X + Y = Y + X 6D. X • Y = Y • X Associativity:7. (X + Y) + Z = X + (Y + Z) 7D. (X • Y) • Z = X • (Y • Z) Distributivity:8. X • (Y + Z) = (X • Y) + (X • Z) 8D. X + (Y • Z) = (X + Y) • (X + Z) Uniting:9. X • Y + X • Y = X 9D. (X + Y) • (X + Y) = X Absorption:10. X + X • Y = X 10D. X • (X + Y) = X11. (X + Y) • Y = X • Y 11D. (X • Y) + Y = X + YL2: 6.111 Spring 2006 14Introductory Digital Systems LaboratoryTheorems of Boolean Algebra (II)Theorems of Boolean Algebra (II) Factoring:12. (X • Y) + (X • Z) = 12D. (X + Y) • (X + Z) = X • (Y + Z) X + (Y • Z) Consensus:13. (X • Y) + (Y • Z) + (X • Z) = 13D. (X + Y) • (Y + Z) • (X + Z) =X • Y + X • Z (X + Y) • (X + Z) De Morgan's:14. (X + Y + ...) = X • Y • ... 14D. (X • Y • ...) = X + Y + ... Generalized De Morgan's:15. f(X1,X2,...,Xn,0,1,+,•) = f(X1,X2,...,Xn,1,0,•,+) Duality Dual of a Boolean expression is derived by replacing • by +, + by •, 0 by 1, and 1 by 0, and leaving variables unchanged f (X1,X2,...,Xn,0,1,+,•) ⇔ f(X1,X2,...,Xn,1,0,•,+)L2: 6.111 Spring 2006 15Introductory Digital Systems LaboratorySimple Example: One Bit AdderSimple Example: One Bit Adder 1-bit binary adder inputs: A, B, Carry-in outputs: Sum, Carry-outABCinCoutSA B Cin S Cout0000010100111001011101110110100100010111Sum-of-Products Canonical FormS = A B Cin + A B Cin + A B Cin + A B CinCout = A B Cin + A B Cin + A B Cin + A B Cin Product term (or minterm) ANDed product of literals – input
View Full Document