EE40 Lec 15 Logic Synthesis and Sequential Logic Circuits Prof. Nathan CheungSynthesis of Logic CircuitsLogic Synthesis Example: AdderSlide 4Logic Synthesis Example: AdderCreating a Better CircuitSlide 7Slide 8Slide 9NAND Gate ImplementationSlide 11SOP or POS ?Slide 13Slide 14Karnaugh MapsComments on Karnaugh MapsSlide 17Slide 184-Variables Example3-Variables Example: AdderMiscellaneous Examples4-Variable ExerciseExercise with “Don’t Cares”Sequential Logic CircuitsClock SignalsFlip-FlopsThe S-R (“Set”-“Reset”) Flip-FlopRealization of the S-R Flip-FlopXOR and NAND ImplementationExercise: Timing Diagram of SR flip-flopClocked S-R Flip-FlopThe D (“Delay”) Flip-FlopD Flip-Flop Example (Timing Diagram)RegistersSlide 36Slide 37Slide 38Conclusion (Logic Circuits)Slide 1EE40 Fall 2009 Prof. CheungEE40 Lec 15Logic Synthesis and Sequential Logic Circuits Prof. Nathan Cheung10/20/2009Reading: Hambley Chapters 7.4-7.6Karnaugh Maps: Read following before reading textbookhttp://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.htmlSlide 2EE40 Fall 2009 Prof. CheungSuppose 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 way is the “sum of products” (SOP) method:1) Write the sum of products expression based on the truth table for the logic function2) Implement this expression using standard logic gates.•An alternative way is the “product of sums” (POS) method.Synthesis of Logic CircuitsSlide 3EE40 Fall 2009 Prof. CheungLogic 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 1S1= carry, So=sumTruth Table of Adding Three Inputs : A, B, and CSlide 4EE40 Fall 2009 Prof. CheungSum-of-products method for S11) Find rows where S1 is 12) Write down each product of inputs which create a 1 (invert logic variables that are 0 in that row)1) Sum all of the products2) 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 CSlide 5EE40 Fall 2009 Prof. CheungLogic Synthesis Example: Adder ABCBCAABA B C + A B C + A B C + A B C SOP Logic CircuitABCCSlide 6EE40 Fall 2009 Prof. CheungCreating 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 relationsSlide 7EE40 Fall 2009 Prof. CheungCan we simplify this digital circuit further?Logic Synthesis Example: Adder ABCBCAABSOP SimplificationABCBABCA)CC(ABCBABCAABCCABCBABCASlide 8EE40 Fall 2009 Prof. CheungLogic Synthesis Example: AdderAdd in two inversions (signal stays the same)ABCBCAABSlide 9EE40 Fall 2009 Prof. CheungLogic Synthesis Example: AdderApply DeMorgan’s Theorem, i.e. “bubble pushing”ABCBCAABThis becomes a NANDXYZZYX Slide 10EE40 Fall 2009 Prof. CheungNAND 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.Slide 11EE40 Fall 2009 Prof. CheungProduct-of-sums method for S11) Find rows where S1 is 02) Write down each sum of inputs which create a 0 (invert logic variables that are 1 in that row)3) Product of the sums4) 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 1InputOutput)CBA( )CBA( )CBA( )CBA( )CBA)(CBA)(CBA)(CBA( Slide 12EE40 Fall 2009 Prof. CheungSOP or POS ?The Boolean Expression will appear shorter • If the Truth table has less 1’s, SOP•If the Truth Table has less 0’s, POS•After Minimization, both methods should give same results , unless there are “don’t care” rows in the Truth Table.Slide 13EE40 Fall 2009 Prof. CheungNotations of Hambley TextbookRow # A B C D0 0 0 0 11 0 0 1 02 0 1 0 13 0 1 1 04 1 0 0 05 1 0 1 06 1 1 0 17 1 1 1 1Sum of Products (SOP))7,6,2,0(mD Product of Sums (POS))5,4,3,1(MD Slide 14EE40 Fall 2009 Prof. CheungAnother Logic Synthesis Example: XORA B F0 0 00 1 11 0 11 1 0Sum of Products (SOP)BABAF )2,1(mF Product of Sums (POS))BA)(BA(F )3,0(MF Slide 15EE40 Fall 2009 Prof. CheungKarnaugh Maps2-variableKarnaugh Map3-variableKarnaugh Map4-variable Karnaugh Map* Arrows show example locations of logic PRODUCTSSlide 16EE40 Fall 2009 Prof. CheungComments on Karnaugh Maps•Required reading•http://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html•You may find more details there than the textbook.•As the number of variables increases (say >4) it becomes more difficult to see patterns, and computer methods start to become more attractive. •EE40 will focus only on 3 variables and 4 variables Karnaugh MapsSlide 17EE40 Fall 2009 Prof. CheungComments on Karnaugh MapsFor a 4-variables map1-cube: 1 square by itself ( logic product of 4 variables)2-cube: 2 squares that have a common edge ( logic product of 3 variables)8-cube: 8 squares with common edges ( logic product of 1 variable)4-cube: 4 squares with common edges ( logic product of 2 variables)Slide 18EE40 Fall 2009 Prof. CheungComments on Karnaugh Maps•In locating cubes on a Karnaugh map, the map should be considered to fold around from top to bottom, and from left to right.–Squares on the right-hand side are considered to be adjacent to those on the left-hand side.–Squares on the top of the map are considered to be adjacent to those on the bottom.–Example:The four squares in the map corners form a 4-cube1 11 1CD00 01 11 10AB00011110Slide 19EE40 Fall 2009 Prof. Cheung4-Variables Example•From Truth Table and Sum of Products F= m(1,3,4,5,7,10,12,13)•Converting the row numbers to binary yields 0001,0011, 0100 etc..•Place 1’s into the Karnaugh MapCBDADCBAF Slide 20EE40 Fall 2009 Prof. CheungA 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 1ABCBCACABS1 = AB + BC + ACSimplification of expression for S1:3-Variables Example: AdderBCSlide 21EE40 Fall 2009 Prof. CheungMiscellaneous ExamplesSlide 23EE40 Fall 2009 Prof. Cheung4-Variable
View Full Document
Unlocking...