L2: 6.111 Spring 2005 1Introductory Digital Systems LaboratoryL2: Combinational Logic Design L2: Combinational Logic Design (Construction and Boolean Algebra)(Construction and Boolean Algebra)(Most) Lecture material derived from Chapter 2 of R. Katz, G. Borriello, “Contemporary Logic Design” (second edition), Pearson Education, 2005.L2: 6.111 Spring 2005 2Introductory Digital Systems LaboratoryThe InverterThe InverterINOUTOUTIN1001V(x)V(y)VOHVOLVIHVILSlope = -1Slope = -1VOLVOH"1""0"VOHVIHVILVOLUndefinedRegion Large noise margins protect against various noise sourcesNML= VIL -VOLNMH= VOH -VIHTruth TableL2: 6.111 Spring 2005 3Introductory Digital Systems LaboratoryTTL Logic Style (1970’sTTL Logic Style (1970’s--early 80’s)early 80’s)74LS04(courtesy TI)+-vBE+-vCEECBQ1Q2Q3L2: 6.111 Spring 2005 4Introductory Digital Systems LaboratoryMOS Technology: The NMOS SwitchMOS Technology: The NMOS SwitchDGSgateN+P-substrateN+drainsourceRNMOSSwitchModelVT= 1VVGS< VTOFFRNMOSVGS> VTONVsNMOS ON when Switch Input is HighL2: 6.111 Spring 2005 5Introductory Digital Systems LaboratoryPMOS: The Complementary SwitchPMOS: The Complementary SwitchSGDgateP+N-substrateP+drainsourceRPMOSSwitchModelVT= -1VVGS> VTOFFRPMOSVGS< VTONPMOS ON when Switch Input is LowVsL2: 6.111 Spring 2005 6Introductory Digital Systems LaboratoryThe CMOS InverterThe CMOS InverterINOUTVDDVDDOUTRPMOSRNMOSININSwitch ModelSGDDSGRail-to-rail Swing in CMOSL2: 6.111 Spring 2005 7Introductory 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 2005 8Introductory Digital Systems LaboratoryCommon Logic GatesCommon Logic GatesXYZZXY1100XZY10111001NANDGate Symbol Truth-Table Expression1100XZY10010001NORZ = X • YZ = X + YZXY1100XZY00111011ORZ = X + YXYZ1100XZY00010011ANDZ = X • YL2: 6.111 Spring 2005 9Introductory Digital Systems LaboratoryExclusive (N)OR GateExclusive (N)OR GateXYZZXY1100XZY001110011100XZY10010011XOR(X ⊕ Y)XNOR(X ⊕ Y)Widely used in arithmetic structures such as adders and multipliersZ = X Y + X YX or Y but not both ("inequality", "difference")Z = X Y + X YX and Y the same ("equality")L2: 6.111 Spring 2005 10Introductory 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.........ABA B PDN PUN O0 0 0ff 0n 10 1 0ff 0n 11 0 0ff 0n 11 1 0n 0ff 0BACLPUNPDNHow do you build a 2-input NOR Gate?ABNote: CMOS gates result in inverting functions!(easier to build NAND vs. AND)OL2: 6.111 Spring 2005 11Introductory 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 2005 12Introductory 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 2005 13Introductory 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 combination for which output is true Each variable appears exactly once, in true or inverted form (but not both)L2: 6.111 Spring 2005 14Introductory Digital Systems LaboratorySimplify Boolean ExpressionsSimplify Boolean ExpressionsCout = A B Cin + A B Cin + A B Cin + A B Cin= A B Cin + A B Cin + A B Cin + A B Cin + A B Cin + A B Cin= (A + A) B Cin + A (B + B) Cin + A B (Cin + Cin)= B Cin + A Cin + A B= (B + A) Cin + A BS = A B Cin + A B Cin + A B Cin + A B Cin=( A B + A B )Cin + (A B + A B) Cin=(A ⊕ B) Cin + (A ⊕ B) Cin= A ⊕ B ⊕ CinL2: 6.111 Spring 2005 15Introductory Digital Systems LaboratorySumSum--ofof--Products & ProductProducts & Product--ofof--Sum Sum short-hand notation form in terms of 3 variablesABCminterms000A B C m0001 A B C m101 0A B C m2011A B C m31 00A B C m4101A B C m5110A B C m6111A B C m7F in canonical form:F(A, B, C) = Σm(1,3,5,6,7)= m1 + m3 + m5 + m6 + m7canonical form ≠ minimal formF(A, B, C) = A B C + A B C + AB C + ABC + ABC = (A B + A B + AB + AB)C + ABC = ((A + A)(B + B))C + ABC = C + ABC = ABC + C = AB + C Product term (or minterm): ANDed product of literals – input combination for which output is trueF =+ A B C+ A B C + A B C + ABCA B CA B C maxterms000A + B + CM00 0 1 A + B + C M101 0A + B + CM20 1 1 A + B + C M31 0 0 A + B + C M4101A + B+ C M51 1 0 A + B +C M6111A +B + C M7short-hand notation for maxterms of 3 variablesF in canonical form:F(A, B, C) = ΠM(0,2,4)= M0 • M2 • M4= (A + B + C) (A + B + C) (A + B + C)canonical form ≠ minimal formF(A, B, C) = (A + B + C) (A + B + C) (A + B + C)= (A + B + C) (A + B + C)(A + B + C) (A + B +
View Full Document
Unlocking...