Combinational logicPossible logic functions of two variablesCost of different logic functionsMinimal set of functionsAn algebraic structureBoolean algebraLogic functions and Boolean algebraAxioms and theorems of Boolean algebraAxioms and theorems of Boolean algebra (cont’d)Axioms and theorems of Boolean algebra (cont’)Slide 11Proving theorems (rewriting)Proving theorems (perfect induction)A simple exampleApply the theorems to simplify expressionsFrom Boolean expressions to logic gatesFrom Boolean expressions to logic gates (cont’d)Slide 18Waveform view of logic functionsChoosing different realizations of a functionWhich realization is best?Which is the best realization? (cont’d)Are all realizations equivalent?Implementing Boolean functionsCanonical formsSum-of-products canonical formsSum-of-products canonical form (cont’d)Product-of-sums canonical formProduct-of-sums canonical form (cont’d)S-o-P, P-o-S, and de Morgan’s theoremFour alternative two-level implementations of F = AB + CWaveforms for the four alternativesMapping between canonical formsIncompleteley specified functionsNotation for incompletely specified functionsSimplification of two-level combinational logicThe Uniting TheoremBoolean cubesMapping truth tables onto Boolean cubesThree variable exampleHigher dimensional cubesm-dimensional cubes in a n-dimensional Boolean spaceKarnaugh mapsKarnaugh maps (cont’d)Adjacencies in Karnaugh mapsKarnaugh map examplesMore Karnaugh map examplesKarnaugh map: 4-variable exampleKarnaugh maps: don’t caresKarnaugh maps: don’t cares (cont’d)Design example: two-bit comparatorDesign example: two-bit comparator (cont’d)Slide 53Design example: 2x2-bit multiplierDesign example: 2x2-bit multiplier (cont’d)Design example: BCD increment by 1Design example: BCD increment by 1 (cont’d)Definition of terms for two-level simplificationExamples to illustrate termsAlgorithm for two-level simplificationAlgorithm for two-level simplification (example)Combinational logic summaryCS 150 - Spring 2001 - Combinational Logic - 1Combinational logicLogic functions, truth tables, and switchesNOT, AND, OR, NAND, NOR, XOR, . . .Minimal setAxioms and theorems of Boolean algebraProofs by re-writingProofs by perfect inductionGate logicNetworks of Boolean functionsTime behaviorCanonical formsTwo-levelIncompletely specified functionsSimplificationBoolean cubes and Karnaugh mapsTwo-level simplificationCS 150 - Spring 2001 - Combinational Logic - 2X Y 16 possible functions (F0–F15)0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 10 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 11 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 11 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1XYFXYX nor Ynot (X or Y)X nand Ynot (X and Y)10not XX and YX or Ynot YX xor YX = YPossible logic functions of two variablesThere are 16 possible functions of 2 input variables:in general, there are 2**(2**n) functions of n inputsCS 150 - Spring 2001 - Combinational Logic - 3Cost of different logic functionsDifferent functions are easier or harder to implementEach has a cost associated with the number of switches needed0 (F0) and 1 (F15): require 0 switches, directly connect output to low/highX (F3) and Y (F5): require 0 switches, output is one of inputsX' (F12) and Y' (F10): require 2 switches for "inverter" or NOT-gateX nor Y (F4) and X nand Y (F14): require 4 switchesX or Y (F7) and X and Y (F1): require 6 switchesX = Y (F9) and X Y (F6): require 16 switchesBecause NOT, NOR, and NAND are the cheapest they are the functions we implement the most in practiceCS 150 - Spring 2001 - Combinational Logic - 4X Y X nand Y0 0 11 1 0X Y X nor Y0 0 11 1 0X nand Y not ( (not X) nor (not Y) ) X nor Y not ( (not X) nand (not Y) )Minimal set of functionsCan we implement all logic functions from NOT, NOR, and NAND?For example, implementing X and Yis the same as implementing not (X nand Y)In fact, we can do it with only NOR or only NANDNOT is just a NAND or a NOR with both inputs tied togetherand NAND and NOR are "duals", i.e., easy to implement one using the otherBut lets not move too fast . . . lets look at the mathematical foundation of logicCS 150 - Spring 2001 - Combinational Logic - 5An algebraic structureAn algebraic structure consists ofa set of elements Bbinary operations { + , • }and a unary operation { ' }such that the following axioms hold:1. set B contains at least two elements, a, b, such that a b2. closure: a + b is in B a • b is in B3. commutativity: a + b = b + a a • b = b • a4. associativity: a + (b + c) = (a + b) + c a • (b • c) = (a • b) • c5. identity: a + 0 = a a • 1 = a6. distributivity: a + (b • c) = (a + b) • (a + c) a • (b + c) = (a • b) + (a • c)7. complementarity: a + a' = 1 a • a' = 0CS 150 - Spring 2001 - Combinational Logic - 6Boolean algebraBoolean algebraB = {0, 1}+ is logical OR, • is logical AND' is logical NOTAll algebraic axioms holdCS 150 - Spring 2001 - Combinational Logic - 7X, Y are Boolean algebra variablesX Y X •KY0 0 00 1 01 0 01 1 1X Y X' Y' X •KY X' •KY' ( X •KY ) + ( X' •KY' )0 0 1 1 0 1 10 1 1 0 0 0 01 0 0 1 0 0 01 1 0 0 1 0 1( X •KY ) + ( X' •KY' ) X =KYX Y X' X' • Y0 0 1 00 1 1 11 0 0 01 1 0 0Boolean expression that is true when the variables X and Y have the same valueand false, otherwiseLogic functions and Boolean algebraAny logic function that can be expressed as a truth table can be written as an expression in Boolean algebra using the operators: ', +, and •CS 150 - Spring 2001 - Combinational Logic - 8Axioms and theorems of Boolean algebraIdentity1. X + 0 = X 1D. X • 1 = XNull2. X + 1 = 1 2D. X • 0 = 0Idempotency:3. X + X = X 3D. X • X = XInvolution:4. (X')' = XComplementarity:5. X + X' = 1 5D. X • X' = 0Commutativity:6. X + Y = Y + X 6D. X • Y = Y • XAssociativity:7. (X + Y) + Z = X + (Y + Z) 7D. (X • Y) • Z = X • (Y • Z)CS 150 - Spring 2001 - Combinational Logic - 9Axioms and theorems of Boolean algebra (cont’d)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') = XAbsorption:10. X + X • Y = X 10D. X • (X + Y) = X11. (X + Y') • Y = X • Y 11D. (X • Y') + Y = X + YFactoring:12. (X + Y) • (X' + Z) =
View Full Document
Unlocking...