Class Note for ENGIN 112 at UMass(17)
Class Note for ENGIN 112 at UMass(17)
Popular in Course
Popular in Department
This 17 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 14 views.
Reviews for Class Note for ENGIN 112 at UMass(17)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
ENGIN 112 Intro to Electrical and Computer Engineering Lectu re 9 More Kamaugh Maps and Don t Cares quot ELECTRICAL 9 quot COMPUTER ENGINEERING umvsnswv or MASSACHUSETTS AMHERST ENGN11Z L9 Mm szzugh Maps Sememherzunna Overview Karnaugh maps with four inputs Same basic rules as three input Kmaps Understanding prime implicants Related to minterms Covering all implicants Using Don t Cares to simplify functions Don t care outputs are undefined Summarizing Karnaugh maps ENGN112 L9 More Karnaugh Maps September 22 2003 Karnaugh Maps for Four Input Functions Represent functions of 4 inputs with 16 minterms Use same rules developed for 3input functions Note bracketed sections shown in example yz y wx 0 O O 1 11 10 00 wxylz WxyZ wxyz Wxyz m0 m1 m3 m2 01 w39xy39z w xy z w xyz w xyz m4 m5 m7 m6 x 11 wxy z wxy z wxyz wxyz m12 m13 m15 77114 w 10 wxryZ wxryZ wxyz wxyzr m8 m9 mll m10 Z a b Fig 3 8 Four variable Map ENGN112 L9 More Karnaugh Maps September 22 2003 Karnaugh map 4variable example FABCD Zm023567810111415 F C A39BD B39D39 1JooL o 1 o o D N 1 1 1 1 C Q r 1 1 1 11 0000 B SoluTion 361 can be considered as a coordinaTe System ENGN112 L9 More Karnaugh Maps September 22 2003 Desi n examples A A A o o o 0 Z 0 o o o1 1 q 1 o o o D o o o D o 0 LAD 1 1 o 1 o o o o o o o C C C 1E o o o o o o o o B Kmap for LT Kmap for EQ Kmap for GT LT A39B39DA39CB39CD EQ A39B39C39D39 A39BC39D ABCD AB39CD39 GT BC39D39AC39ABD39 Can you draw The Tr39uTh Table for These examples ENGN112 L9 More Karnaugh Maps September 22 2003 Physical Implementation Step 1 Truth table ABCD Step 2 Kmap Step 3 Minimized sumof products Step 4 Physical implementation with gates EQ A 1000 0100 D 0010 C 0001 B Kmap for EQ ENGN112 L9 More Karnaugh Maps September 22 2003 Karnau h Maps Four variable maps CD AB 00 01 11 10 00 O O O T FAIBCIAICDIABC OlTT 0 r1 AB39C39D39ABC39AB39C 11 1 1 m39 FBC39CD39 AC AD39 10 1 0 i1 1 Need to make sure all 1 s are covered Try to minimize total product terms Design could be implemented using NANDs and NORs ENGN112 L9 More Karnaugh Maps September 22 2003 Karnaugh maps Don t cares In some cases outputs are undefined We don t care if the logic produces a 0 or a 1 This knowledge can be used to simplify functions AB A CD 00 O1 11 10 00 0 0 X 0 Treat X s like either 1 s or O s Very useful 01 1 1 X 1 D OK to leave some X s uncovered 111100 C 1Ooxoo T ENGN112 L9 More Karnaugh Maps September 22 2003 Karnaugh maps Don t cares fABCD Z m13579 d61213 without don39t cares f ABCDL 00000 ADCD 00011 00100 A AB 00111 01000 CD 01011 0110x OOooxo 01111 O111 x1 10000 D 10011 111100 10100 C P 10110 1Ooxoo 1100x 1101x T 11100 11110 ENGN112 L9 More Karnaugh Maps September 22 2003 Don t Care Conditions n sorne situations we don t care about the vaue of a function for certaIn combInatIons of the varIables these combinations may be impossible in certain contexts or the value of the function may not matter in when the combinations occur In such situations we say the function is incompletely specified and there are multiple completely specified logic functions that can be used in the deSIgn so we can select a function that gives the simplest circuit When constructing the terms in the simplification procedure we can choose to either cover or not cover the don t care conditions ENGN112 L9 More Karnaugh Maps September 22 2003 Map Simplification with Don t Cares CD AB 00 01 11 10 000 1 O O 01x X X 11 K1 1 i1 10x O 1 L1 1 J FA39C39DBAC Alternative covering D 00 01 11 10 AB 00 0 1 01x X 111 1 10x O ENGN112 L9 More Karnaugh Maps FA39B39C39DABC BCAC September 22 2003 Karnau h maps don t cares cont d fABCD 2 m13579 d61213 f AD B39C39D without don39t cares f with don39t cares AD C39D A 39 39 II by using don t care as a 1 O O X 0 a 2cube can be formed 1 1 X 1 rather than a 1cube to cover D this node 1 1 O O C don t cares can be treated as o x o o Is or Os 9 depending on which is more advantageous ENGN112 L9 More Karnaugh Maps September 22 2003 Definition of terms for twolevel simplification Implicant Single product term of the ONset terms that create a logic 1 Prime implicant Implicant that can39t be combined with another to form an implicant with fewer literals Essential prime implicant Prime implicant is essential if it alone covers a minterm in the Kmap Remember that all squares marked with 1 must be covered Objective Grow implicant into prime implicants minimize literals per term Cover the Kmap with as few prime implicants as possible minimize number of product terms ENGN112 L9 More Karnaugh Maps September 22 2003 Examples to illustrate terms O KX 11A 0 6 prime implicalm s I I I Tkl 1J0 DABDBCltACDABBCD 1 0 f1 1 essenTial C o 0 Egg minimum coverz AC BC39 A39B39D A 5pr39imeimplicanTs o o 11 o BDAB 39D 1 719 0 essenTial C 0 1 r1 1 minimum cover 4essenTia implicanTs O L O O ENGN112 L9 More Karnaugh Maps September 22 2003 Prime Implicants Any single 1 or group of ls in the Karnaugh map of a function F is an implicant of F A product term is called a prime implicant of F if it cannot be combined with another term to eliminate a variable Example 1 1 C 1 ENGN112 L9 More Karnaugh Maps If a function F is represented by this Karnaugh Map Which of the following terms are implicants of F and which ones are prime implicants of F a AC D lmpllcants b BD c A B C D d AC Prime llrnpllcanta e B C D September 22 2003 Essential Prime Implicants A product term is an essential prime implicant if there is a minterm that is only covered by that prime implicant The minimal sumof products form of F must include all the essential prime implicants of F CD C CD C AB 0 0 0 1 11 10 AB 0 0 0 1 11 10 00 1 I 1 00 01 1 1 01 B B 11 1 1 11 A A 10 1 1 10 D D a Essential prime implicants b Prime implicants CD B C BD and B D AD and AB Fig 3 11 Simplification Using Prime Implicants ENGN112 L9 More Karnaugh Maps September 22 2003 Summary Kmaps of four literals considered Larger examples exist Don t care conditions help minimize functions Output for don t cares are undefined Result of minimization is minimal sumofproducts Result contains prime implicants Essential prime implicants are required in the implementation ENGN112 L9 More Karnaugh Maps September 22 2003
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'