Combinational Logic (mostly review!)Possible Logic Functions of Two VariablesCost of Different Logic FunctionsMinimal Set of FunctionsLogic Functions and Boolean AlgebraSimple ExampleApply the Theorems to Simplify ExpressionsSlide 18Waveform View of Logic FunctionsChoosing Different Realizations of a FunctionWhich Realization is Best?Which is the Best Realization? (cont’d)Canonical FormsSum-of-Products Canonical FormsSum-of-Products Canonical Form (cont’d)Four Alternative Two-level Implementations of F = AB + CWaveforms for the Four AlternativesIncompletely Specified FunctionsNotation for Incompletely Specified FunctionsThe Uniting TheoremBoolean CubesSlide 39Mapping Truth Tables onto Boolean CubesThree Variable ExampleHigher Dimensional Cubesm-Dimensional Cubes in an 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: 2x2-bit MultiplierDesign Example: 2x2-bit Multiplier (cont’d)Basic Two-Level Logic Simplification AlgorithmEx: F=a’b’d’ + abd’ +a’bSlide 63Covering TableSolving the Covering Table“Dominated” Rows“Dominated” ColumnsAlgorithm (again)Slide 69Slide 70What can go wrong?What do we do about it?What do we mean by “usually”?Slide 74We See only a tiny fraction of circuitsExample: Prime GenerationCofactorsCofactors and PrimesExampleSimilar Fast Techniques to Generate RowsApproximate AlgorithmEspresso-II algorithm (approx)Espresso-II exampleEspresso-II presented here very simplifiedReturn to Exact MethodsEspresso-SignatureTwo-Level Synthesis SummaryImplementations of Two-level LogicTwo-level Logic Using NAND GatesTwo-level Logic Using NAND Gates (cont’d)Two-level Logic Using NOR GatesTwo-level Logic Using NOR Gates (cont’d)Combinational Logic SummaryCS 150 - Spring 2008 – Lec #3: Combinational Logic - 1Combinational Logic (mostly review!)Logic 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 functionsTwo-level minimizationCS 150 - Spring 2008 – Lec #3: 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 Variables16 possible functions of 2 input variables:2**(2**n) functions of n inputsCS 150 - Spring 2008 – Lec #3: Combinational Logic - 3Cost of Different Logic FunctionsSome are easier, others 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 2008 – Lec #3: 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 FunctionsImplement any logic functions from NOT, NOR, and NAND?For example, implementing X and Yis the same as implementing not (X nand Y)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 otherBased on the mathematical foundations of logic: Boolean AlgebraCS 150 - Spring 2008 – Lec #3: Combinational Logic - 7X, Y are Boolean algebra variablesX Y X •GY0 0 00 1 01 0 01 1 1X Y X' Y' X •GY X' •GY' ( X •GY ) + ( X' •GY' )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 •GY ) + ( X' •GY' ) X =GYX 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 2008 – Lec #3: Combinational Logic - 14Simple Example1-bit binary adderInputs: A, B, Carry-inOutputs: Sum, Carry-outABCinCoutSA B Cin S Cout0 0 0 0 0 1 0 1 0 0 1 11 0 0 1 0 1 1 1 0 1 1 1 0110100100010111Cout = A' B Cin + A B' Cin + A B Cin' + A B CinS = A' B' Cin + A' B Cin' + A B' Cin' + A B CinCS 150 - Spring 2008 – Lec #3: Combinational Logic - 15Apply the Theorems to Simplify ExpressionsTheorems of Boolean algebra can simplify Boolean expressionse.g., full adder's carry-out function (same rules apply to any function)Cout = 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 B Cin + A B' Cin + A B Cin' + A B Cin= (A' + A) B Cin + A B' Cin + A B Cin' + A B Cin= (1) B Cin + A B' Cin + A B Cin' + A B Cin= B Cin + A B' Cin + A B Cin' + A B Cin + A B Cin= B Cin + A B' Cin + A B Cin + A B Cin' + A B Cin= B Cin + A (B' + B) Cin + A B Cin' + A B Cin= B Cin + A (1) Cin + A B Cin' + A B Cin= B Cin + A Cin + A B (Cin' + Cin)= B Cin + A Cin + A B (1)= B Cin + A Cin + A BCS 150 - Spring 2008 – Lec #3: Combinational Logic - 18T1T2use of 3-input gateABCDT2T1ZABCDZFrom Boolean Expressions to Logic Gates (cont’d)More than one way to map expressions to gatese.g., Z = A' • B' • (C + D) = (A' • (B' • (C + D)))CS 150 - Spring 2008 – Lec #3: Combinational Logic - 19timechange in Y takes time to "propagate" through gatesWaveform View of Logic FunctionsJust a sideways truth tableBut note how edges don't line up exactlyIt takes time for a gate to switch its output!CS 150 - Spring 2008 – Lec #3: Combinational Logic - 20A B C Z0 0 0 00 0 1 10 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0Choosing Different
View Full Document
Unlocking...