EE40 Lec 15 Logic Synthesis and Sequential Logic Circuits Prof Nathan Cheung 10 20 2009 Reading Hambley Chapters 7 4 7 6 Karnaugh Maps Read following before reading textbook http www facstaff bucknell edu mastascu eLessonsHTML Logic Logic3 html EE40 Fall 2009 Slide 1 Prof Cheung Synthesis of Logic Circuits Suppose 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 function 2 Implement this expression using standard logic gates An alternative way is the product of sums POS method EE40 Fall 2009 Slide 2 Prof Cheung Logic Synthesis Example Adder S1 carry So sum Truth Table of Adding Three Inputs A B and C EE40 Fall 2009 Slide 3 A B C S1 S0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 1 0 1 0 0 1 Prof Cheung Logic Synthesis Example Adder Output Sum of products method for S1 C S1 S0 1 Find rows where S1 is 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 1 0 1 0 0 1 Input A B 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 EE40 Fall 2009 2 Write down each product of inputs which create a 1 invert logic variables that are 0 in that row ABC ABC ABC ABC 1 Sum all of the products ABC ABC ABC ABC 2 Draw the logic circuit Slide 4 Prof Cheung Logic Synthesis Example Adder ABC ABC ABC ABC A A C B C SOP Logic Circuit B C A B A B C EE40 Fall 2009 Slide 5 Prof Cheung Creating a Better Circuit What 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 ofproducts expression for S1 to make a better circuit Use the Boolean algebra relations EE40 Fall 2009 Slide 6 Prof Cheung Logic Synthesis Example Adder ABC AB C AB C ABC A B C ABC AB C AB C C ABC AB C AB A C B A B SOP Simplification Can we simplify this digital circuit further EE40 Fall 2009 Slide 7 Prof Cheung Logic Synthesis Example Adder A B Add in two inversions signal stays the same B C A C A B EE40 Fall 2009 Slide 8 Prof Cheung Logic Synthesis Example Adder A B This becomes a NAND B C A C A B Apply DeMorgan s Theorem i e bubble pushing X Y Z XYZ EE40 Fall 2009 Slide 9 Prof Cheung NAND 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 EE40 Fall 2009 Slide 10 Prof Cheung Logic Synthesis Example Adder Output Input A B C S1 S0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 1 0 1 0 0 1 EE40 Fall 2009 Product of sums method for S1 1 Find rows where S1 is 0 2 Write down each sum of inputs which create a 0 invert logic variables that are 1 in that row A B C A B C A B C A B C 3 Product of the sums A B C A B C A B C A B C 4 Draw the logic circuit Slide 11 Prof Cheung SOP 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 EE40 Fall 2009 Slide 12 Prof Cheung Notations of Hambley Textbook Sum of Products SOP D m 0 2 6 7 Product of Sums POS D M 1 3 4 5 EE40 Fall 2009 Slide 13 Row 0 1 2 3 4 5 6 7 A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 Prof Cheung D 1 0 1 0 0 0 1 1 Another Logic Synthesis Example XOR Sum of Products SOP F m 1 2 F AB A B EE40 Fall 2009 A B F 0 0 0 0 1 1 1 0 1 1 1 0 Slide 14 Product of Sums POS F M 0 3 F A B A B Prof Cheung Karnaugh Maps 2 variable Karnaugh Map 3 variable Karnaugh Map 4 variable Karnaugh Map Arrows show example locations of logic PRODUCTS EE40 Fall 2009 Slide 15 Prof Cheung Comments on Karnaugh Maps Required reading http www facstaff bucknell edu mastascu eLessonsHTM L 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 Maps EE40 Fall 2009 Slide 16 Prof Cheung Comments on Karnaugh Maps For a 4 variables map 1 cube 1 square by itself logic product of 4 variables 2 cube 2 squares that have a common edge logic product of 3 variables 4 cube 4 squares with common edges logic product of 2 variables 8 cube 8 squares with common edges logic product of 1 variable EE40 Fall 2009 Slide 17 Prof Cheung Comments 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 CD considered to be adjacent to those 00 01 11 10 on the bottom 1 00 1 Example The four squares in the map corners form a 4 cube AB 01 11 10 1 EE40 Fall 2009 Slide 18 1 Prof Cheung 4 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 Map F A B C D AD B C EE40 Fall 2009 Slide 19 Prof Cheung 3 Variables Example Adder Input Output Simplification of expression for S1 A B C S1 S0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 EE40 Fall 2009 0 1 0 1 0 1 0 1 0 …
View Full Document
Unlocking...