Berkeley ELENG 40 - Logic Synthesis and S C equential Logic ircuits

Unformatted text preview:

EE40 Lec 15Logic Synthesis and SCSequential Logic Circuits PfNh ChProf. Nathan Cheung10/20/2009Reading: Hambley Chapters 7.4-7.6KarnaughMaps: Read following before reading textbookSlide 1EE40 Fall 2009 Prof. CheungKarnaughMaps: Read following before reading textbookhttp://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.htmlSynthesis of Logic CircuitsSuppose 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 “fdt”(SOP) th d“sum of products”(SOP) method:1)Write the sum of products expression based on the )pptruth table for the logic function2) Implement this expression using standard logic gates.• An alternative way is the “product of sums” (POS) method.Slide 2EE40 Fall 2009 Prof. CheungLogic Synthesis Example: AdderSSABCS1S0S1= carry, So=sum0000000101Truth Table of Adding Three Inputs :0100101110Three Inputs : A, B, and C01110100011011011010Slide 3EE40 Fall 2009 Prof. Cheung11111Logic Synthesis Example: AdderSum-of-products method for S11)Find rows where S1is1ABCS1S0Input Output1)Find rows where S1is 12) Write down each product of inputs which create a1(invertABCS1S00000000101inputs which create a 1 (invert logic variables that are 0 in that row)00101010010111010001A B C A B C A B C A B C 1) Sum all of the products1011011010A B C + A B C + A B C + A B C Slide 4EE40 Fall 2009 Prof. Cheung2) Draw the logic circuit1101011111Logic Synthesis Example: Adder ABA B C + A B C + A B C + A B C SOP Logic CircuitBCASOP Logic CircuitBCAABCABSlide 5EE40 Fall 2009 Prof. CheungBCCreating a Better CircuitWhat makes a digital circuit better?•Fewer number of gatesFewer 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 Sto make aproducts expression for S1, to make a better circuit…–Use the Boolean algebra relationsUse the Boolean algebra relationsSlide 6EE40 Fall 2009 Prof. CheungLogic Synthesis Example: Adder AB)CC(ABCBABCAABCCABCBABCA+++=+++BCAABCBABCA)(++=BCAABSOP SimplificationCan we simplify this digital circuit further?Slide 7EE40 Fall 2009 Prof. CheungLogic Synthesis Example: AdderAdd in two inversions (signal stays theAB(signal stays the same)BCABCAABSlide 8EE40 Fall 2009 Prof. CheungLogic Synthesis Example: AdderABThis becomes a NANDBCABCAApply DeMorgan’s Theorem, i.e. “bubble hi ”ABpushing”XYZZYX=++Slide 9EE40 Fall 2009 Prof. CheungNAND Gate Implementation• De Morgan’s law tells us thatis the same as• By definition,is the same asSlide 10EE40 Fall 2009 Prof. CheungÆ All sum-of-products expressions can be implemented with only NAND gates.Logic Synthesis Example: AdderProduct-of-sums method for S11)Find rows where Sis0ABCS1S0InputOutput1)Find rows where S1is 02) Write down each sum of inputs which create a 0 (invert logic0000000101which create a 0 (invert logic variables that are 1 in that row)001010100101110)CBA(++)CBA(++0111010001)CBA(++)CBA(++)CBA( ++ )CBA( ++3) Product of the sums1011011010)CBA)(CBA)(CBA)(CBA( ++++++++Slide 11EE40 Fall 2009 Prof. Cheung4) Draw the logic circuit1101011111SOP or POS ?The Boolean Expression will appear shorter ppp• If the Truth table has less 1’s, SOP•If the Truth Table has less0’sPOS•If the Truth Table has less 0s, POS•After Minimization, both methods should give same results , unless there are “don’t care” rows in the Truth Table.Slide 12EE40 Fall 2009 Prof. CheungNotations of Hambley TextbookRow #ABCDSum of Products (SOP)Row #ABCD0 00011 001020101)7,6,2,0(mD Σ=201013 01104 1000),,,(Product of Sums (POS)5 10106 11017 1111())5,4,3,1(MDΠ=)5,4,3,1(MDΠSlide 13EE40 Fall 2009 Prof. CheungAnother Logic Synthesis Example: XORAB F00 0011Sum of Products (SOP))21(FΣProduct of Sums (POS))30(MFΠ01110 111 0BABAF+=)2,1(mFΣ=)BA)(BA(F++=)3,0(MFΠ=BABAF+=)BA)(BA(F++Slide 14EE40 Fall 2009 Prof. CheungKarnaugh Maps2-variableKarnaugh Map3-variableKarnaugh Map4-variable Karnaugh MapSlide 15EE40 Fall 2009 Prof. Cheung* Arrows show example locations of logic PRODUCTSComments on Karnaugh Maps• Required reading• http://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3 htmlL/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 methodsmore difficult to see patterns, and computer methods start to become more attractive. EE40 ill f l 3 i bl d 4 i bl•EE40 will focus only on 3 variables and 4 variables Karnaugh MapsSlide 16EE40 Fall 2009 Prof. CheungComments on Karnaugh MapsFor a 4-variables map1-cube: 1 square by itself(⇒ logic product of 4 variables)(gp )2-cube: 2 squares that have a common edge (⇒logic product of 3 variables)(⇒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)Slide 17EE40 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 sidethose on the lefthand side.– Squares on the top of the map are considered to be adjacent to those CDon the bottom.–Example:1 100 01 11 1000pThe four squares in the map corners form a 4-cubeAB0111Slide 18EE40 Fall 2009 Prof. Cheung11104-Variables ExampleFTthTbl dS fPdt•From Truth Table and Sum of ProductsF=Σ m(1,3,4,5,7,10,12,13)•Converting the row numbers to binary yields 0001 0011•Converting the row numbers to binary yields 0001,0011, 0100 etc..• Place 1’s into the Karnaugh MapgCBDADCBAF ++=Slide 19EE40 Fall 2009 Prof. CheungItOt t3-Variables Example: AdderABCS1S0InputOutputSimplification of expression for S1:B000000010100 01 11 10BC01001011100 00101 0111A011101000110110C1011011010BCACABS=AB+BC+ACSlide 20EE40 Fall 2009 Prof. Cheung11111S1= AB+ BC+ ACMiscellaneous ExamplesSlide 21EE40 Fall 2009 Prof. Cheung3-Variable ExerciseSlide 22EE40 Fall 2009 Prof. Cheung4-Variable ExerciseSlide 23EE40 Fall 2009 Prof. CheungExercise with “Don’t Cares”Slide 24EE40 Fall 2009 Prof. CheungSequential Logic Circuits• Sequential logic circuits that possess memory because their present output value depends on ill titlprevious as well as present input values.Slide 25EE40 Fall


View Full Document

Berkeley ELENG 40 - Logic Synthesis and S C equential Logic ircuits

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 Logic Synthesis and S C equential Logic ircuits
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 Logic Synthesis and S C equential Logic ircuits 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 Logic Synthesis and S C equential Logic ircuits 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?