Unformatted text preview:

1Lecture 29, Slide 1EECS40, Fall 2003 Prof. KingLecture #29ANNOUNCEMENTS• 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 cancelledOUTLINE– Synthesis of logic circuits– Minimization of logic circuitsReading: Schwarz & Oldham pp. 403-411Lecture 29, Slide 2EECS40, Fall 2003 Prof. KingCombinational 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.2Lecture 29, Slide 3EECS40, Fall 2003 Prof. KingBoolean 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 lawsLecture 29, Slide 4EECS40, Fall 2003 Prof. KingBoolean Expression ExampleF = A•B•C + A•B•C + (C+D)•(D+E)F = C•(A+D+E) + D•E3Lecture 29, Slide 5EECS40, Fall 2003 Prof. KingLogical 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.Lecture 29, Slide 6EECS40, Fall 2003 Prof. KingLogical 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.4Lecture 29, Slide 7EECS40, Fall 2003 Prof. KingSuppose 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 CircuitsLecture 29, Slide 8EECS40, Fall 2003 Prof. KingS1using sum-of-products:1) Find where S1is 12) Write down each product of inputs which create a 13) Sum all of the products4) Draw the logic circuitLogic Synthesis Example: Adder011101000101101010111000S11010C1000A1100B1110S0Input 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 C5Lecture 29, Slide 9EECS40, Fall 2003 Prof. KingNAND Gate Implementation• De Morgan’s law tells us thatis the same as• By definition,is the same asÆ All sum-of-products expressions can be implemented with only NAND gates.Lecture 29, Slide 10EECS40, Fall 2003 Prof. KingCreating 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 relations6Lecture 29, Slide 11EECS40, Fall 2003 Prof. KingKarnaugh 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 Map0110A10BC00 01 11 103-variableKarnaugh Map4-variable Karnaugh MapCD00 01 11 10AB00011110Lecture 29, Slide 12EECS40, Fall 2003 Prof. King011101000101101010111000S11010C1000A1100B1110S0Input Output111010100010110100ABCBC AC AC ABS1= AB + BC + ACSimplification of expression for S1:Karnaugh Map


View Full Document

Berkeley ELENG 40 - Lecture Notes

Documents in this Course
Lecture 3

Lecture 3

73 pages

Lecture 1

Lecture 1

84 pages

Guide 4

Guide 4

8 pages

Diodes

Diodes

7 pages

Quiz

Quiz

9 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?