Week 11bCombinational Logic CircuitsBoolean Algebra RelationsBoolean Expression ExampleLogical Sufficiency of NAND GatesLogical Sufficiency of NOR GatesSynthesis of Logic CircuitsPowerPoint PresentationLogic Synthesis Example: AdderNAND Gate ImplementationCreating a Better CircuitKarnaugh MapsKarnaugh Map ExampleFurther Comments on Karnaugh MapsSlide 15Slide 16Slide 17Slide 18Week 11b, Slide 1EECS42, Fall 2005 Prof. WhiteWeek 11bOUTLINE– Synthesis of logic circuits– Minimization of logic circuitsReading: Hambley Ch. 7 through 7.6Week 11b, Slide 2EECS42, Fall 2005 Prof. WhiteCombinational Logic Circuits•Logic gates combine several logic-variable inputs to produce a logic-variable output.•Combinational logic circuits are “memoryless” because their output value at a given instant depends only on the input values at that instant.•Next time, we will study sequential logic circuits that possess memory because their present output value depends on previous as well as present input values.Week 11b, Slide 3EECS42, Fall 2005 Prof. WhiteBoolean Algebra RelationsA•A = AA•A = 0A•1 = AA•0 = 0A•B = B•AA•(B•C) = (A•B)•CA+A = AA+A = 1A+1 = 1A+0 = AA+B = B+AA+(B+C) = (A+B)+CA•(B+C) = A•B + A•CA•B = A + BA•B = A + BDe Morgan’s lawsWeek 11b, Slide 4EECS42, Fall 2005 Prof. WhiteBoolean Expression ExampleF = A•B•C + A•B•C + (C+D)•(D+E)F = C•(A+D+E) + D•EWeek 11b, Slide 5EECS42, Fall 2005 Prof. WhiteLogical Sufficiency of NAND Gates•If the inputs to a NAND gate are tied together, an inverter results•From De Morgan’s laws, the OR operation can be realized by inverting the input variables and combining the results in a NAND gate.•Since the basic logic functions (AND, OR, and NOT) can be realized by using only NAND gates, NAND gates are sufficient to realize any combinational logic function.Week 11b, Slide 6EECS42, Fall 2005 Prof. WhiteLogical Sufficiency of NOR Gates•Show how to realize the AND, OR, and NOT functions using only NOR gates•Since the basic logic functions (AND, OR, and NOT) can be realized by using only NOR gates, NOR gates are sufficient to realize any combinational logic function.Week 11b, Slide 7EECS42, Fall 2005 Prof. WhiteSuppose we are given a truth table for a logic function.Is there a method to implement the logic function using basic logic gates?Answer: There are lots of ways, but one simple way is the “sum of products” implementation method:1) Write the sum of products expression based on the truth table for the logic function2) Implement this expression using standard logic gates.•We may not get the most efficient implementation this way, but we can simplify the circuit afterwards…Synthesis of Logic CircuitsWeek 11b, Slide 8EECS42, Fall 2005 Prof. WhiteExample: the half adder and the full adderA BCarrySumAn+1 Bn+1Cn+1Sn+1CnSnAnBnCn-1Week 11b, Slide 9EECS42, Fall 2005 Prof. WhiteS1 using sum-of-products:1) Find where S1 is 12) Write down each product of inputs which create a 13) Sum all of the products4) Draw the logic circuitLogic Synthesis Example: AdderA B C S1S00 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1Input OutputA B C A B C A B C A B C A B C + A B C + A B C + A B C A B C A B C A B CWeek 11b, Slide 10EECS42, Fall 2005 Prof. WhiteNAND Gate Implementation•De Morgan’s law tells us that is the same as•By definition, is the same as All sum-of-products expressions can be implemented with only NAND gates.Week 11b, Slide 11EECS42, Fall 2005 Prof. WhiteCreating a Better CircuitWhat makes a digital circuit better?•Fewer number of gates•Fewer inputs on each gate–multi-input gates are slower•Let’s see how we can simplify the sum-of-products expression for S1, to make a better circuit…–Use the Boolean algebra relationsWeek 11b, Slide 12EECS42, Fall 2005 Prof. WhiteKarnaugh Maps•Graphical approach to minimizing the number of terms in a logic expression:1. Map the truth table into a Karnaugh map (see below)2. For each 1, circle the biggest block that includes that 13. Write the product that corresponds to that block.4. Sum all of the productsAB2-variableKarnaugh Map0 110A10BC00 01 11 103-variableKarnaugh Map4-variable Karnaugh MapCD00 01 11 10AB00011110Week 11b, Slide 13EECS42, Fall 2005 Prof. WhiteA B C S1S00 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1Input Output00 01 11 100 0 0 1 01 0 1 1 1ABCBC AC AC ABS1 = AB + BC + ACSimplification of expression for S1:Karnaugh Map ExampleWeek 11b, Slide 14EECS42, Fall 2005 Prof. WhiteFurther Comments on Karnaugh Maps•The algebraic manipulations needed to simplify a given expression are not always obvious. Karnaugh maps make it easier to minimize the number of terms in a logic expression.Week 11b, Slide 15EECS42, Fall 2005 Prof. WhiteHomework Assignment 9 -- LogicWorksThis 40-point assignment is to simulate one stage of a full adder using the LogicWorks program available on Windows machines in 199 Cory. Use your EE43 account log-in and password, or use this temporary log-in: ee42-temp pwd: Go Bears 005Print out your circuit and the timing diagram and hand them inThursday April 21 in the usual homework box. To help the grader, put “bus bars” with A and B and their complements on your circuit as shown on the next page here.There’s a LogicWorks manual/tutorial on those machines. Note: on your display be sure “show Window’s contents while dragging” is disabled. Your GSI has floppies you can use to store your work (temp account won’t allow machine storage). You can print your work on the printer in 199 Cory. If theControl bar doesn’t appear when you launch LogicWorks, on the Main toolbarat the top of the screen, click on Tools and then on Simulate.Week 11b, Slide 16EECS42, Fall 2005 Prof. WhiteW. G. OldhamEECS 40 Fall 2001 Lecture 2Copyright Regents of University of CaliforniaA B CABCA B CFABCABCABCABCExample of general purpose circuit to implement the truth table of Table 22.4. (This solution is NOT minimized.)Two sets of “bus bars” on left provide variables and theircomplements for whatever you connect on the right side.Homework 9 -- continuedWeek 11b, Slide 17EECS42, Fall 2005 Prof. WhiteHomework 9 -- concludeda. Draw and run your circuit as derived from the sum-of-productsexpressions for your sum and carry outputs using whatever gatesyou require. b. Then try to simplify those expressions using Boolean algebra.c. Then simply if
View Full Document
Unlocking...