Lecture 29 ANNOUNCEMENTS Lab project Bring a check 50 payable to UC Regents to lab this week in order to receive your Tutebot kit You will receive this back when you return the kit Extra credit will be awarded if you endow your Tutebot with additional intelligence Prof King s office hour tomorrow 11 6 is cancelled OUTLINE Synthesis of logic circuits Minimization of logic circuits Reading Schwarz Oldham pp 403 411 EECS40 Fall 2003 Lecture 29 Slide 1 Prof King Combinational 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 EECS40 Fall 2003 Lecture 29 Slide 2 Prof King 1 Boolean Algebra Relations A A A A A 0 A 1 A A 0 0 A B B A A B C A B C A A A A A 1 A 1 1 A 0 A A B B A A B C A B C A B C A B A C A B A B A B A B EECS40 Fall 2003 De Morgan s laws Lecture 29 Slide 3 Prof King Boolean Expression Example F A B C A B C C D D E F C A D E D E EECS40 Fall 2003 Lecture 29 Slide 4 Prof King 2 Logical 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 EECS40 Fall 2003 Lecture 29 Slide 5 Prof King Logical 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 EECS40 Fall 2003 Lecture 29 Slide 6 Prof King 3 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 simple way is the sum of products implementation 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 We may not get the most efficient implementation this way but we can simplify the circuit afterwards EECS40 Fall 2003 Lecture 29 Slide 7 Prof King Logic Synthesis Example Adder Input A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 Output C S1 S0 0 0 0 1 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 1 EECS40 Fall 2003 S1 using sum of products 1 Find where S1 is 1 2 Write down each product of inputs which create a 1 ABC ABC ABC ABC 3 Sum all of the products ABC ABC ABC ABC 4 Draw the logic circuit Lecture 29 Slide 8 Prof King 4 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 EECS40 Fall 2003 Lecture 29 Slide 9 Prof King 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 EECS40 Fall 2003 Lecture 29 Slide 10 Prof King 5 Karnaugh Maps Graphical approach to minimizing the number of terms in a logic expression 1 2 3 4 Map the truth table into a Karnaugh map see below For each 1 circle the biggest block that includes that 1 Write the product that corresponds to that block Sum all of the products 4 variable Karnaugh Map 2 variable Karnaugh Map 3 variable Karnaugh Map B 0 1 BC 00 01 11 10 A 0 A 1 CD 00 01 11 10 00 AB 0 1 EECS40 Fall 2003 01 11 10 Lecture 29 Slide 11 Prof King Karnaugh Map Example Input A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 Output C 0 1 0 1 0 1 0 1 EECS40 Fall 2003 S1 0 0 0 1 0 1 1 1 S0 0 1 1 0 1 0 0 1 Simplification of expression for S1 BC A 0 00 01 11 10 0 0 1 0 1 0 BC 1 AC 1 AC 1 AB S1 AB BC AC Lecture 29 Slide 12 Prof King 6
View Full Document
Unlocking...