Karnaugh MapsSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Multiple Output ProblemsSlide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Karnaugh MapsCircuit MinimizationAlgebraic manipulations can be used to simplify Boolean expressionsAs we've seen, this process is not always easyKarnaugh maps (K-maps) provide an easy and visual technique for finding the minimum cost SOP (or POS) form for a Boolean expressionThis technique has limitations. i.e. works for # inputs < 7Not good for CAD tools, but good for teaching the idea of simplificationThe Combining PropertyRecall the combining propertyx y + x y' = x (y + y') = xExample:f = x1'x2'x3'+x1'x2x3'+x1x2'x3'+x1x2'x3 = m0 + m2 + m4 + m5Minterms m0 and m2 differ in only one variable (x2)m0 and m2 can be combined to get x1'x3'Reduced fan in and reduced number of gatesHence, f = x1'x3' + x1x2' still SOP but not canonicalVisualizing the Combining Propertyf(x1,x2) = m(0,1,3)Canonical SOP:f = x1'x2'+x1'x2+x1x2 = x1'x2'+x1'x2+x1x2+x1'x2 = x1'+x2A 2-variable Karnaugh map:x1 x2 F0 0 10 1 11 0 01 1 1 x2x10 10 1 11 0 1minimum form: f = x1'+x23 Variable Mapf(A,B,C) = m(1,2,6,7)Minimum SOP is f = A B + B C' + A' B' CCost = gates + fan-in = 4 + (7+3) = 14 B C A00 01 11 100 0 1 0 11 0 0 1 1Gray Code: any two consecutive numbers differ in only a single bitK-maps in Various Sizes B C A00 01 11 100 m0m1m3m21 m4m5m7m6 BA0 10 m0m11 m2m3 C D A B00 01 11 1000 m0m1m3m201 m4m5m7m611 m12m13m15m1410 m8m9m11m10Full-Adder Carry-OutCout(A,B,Cin) = m(3,5,6,7)Minimum SOP is Cout = A Cin + B Cin + A BCost = 4 + 9 = 13 B Cin A00 01 11 100 0 0 1 01 0 1 1 1More 3 Variable Maps B C A00 01 11 100 0 0 1 11 1 1 0 0 B C A00 01 11 100 1 1 1 11 0 0 1 1 A' B + A B' (A B) A' + Bf = f =And Even More 3 Variable Maps B C A00 01 11 100 0 1 1 01 1 0 0 1 B C A00 01 11 100 1 0 0 11 1 0 1 1 A' C + A C' (A C) C' + A Bf = f =Full-Adder SumS(A,B,Cin) = m(1,2,4,7)Minimum is S = A B' Cin' + A' B' Cin + A B Cin + A'B Cin'Can't reduce anything and stay in SOP form! B Cin A00 01 11 100 0 1 0 11 1 0 1 0Sidebar: Gray CodesA binary Gray code is a binary sequence such that no two consecutive numbers differ by more that a single bitGray codes have many uses in CS2 bit Gray code: 00, 01, 11, 10Note that this is circular 10, 00 again differs in only 1 bitThese are called binary reflected Gray codes3 bit Gray code: 000, 001, 011, 010, 110, 111, 101, 100Constructing Gray CodesIf s0, s1, s2, …, s2n is a n bit Gray code, then we can construct an n+1 bit Gray code as follows:0s0, 0s1, 0s2, …, 0s2n, 1s2n, 1s2n-1, 1s2n-2, …, 1s1 ,1s0Example:00, 01, 11, 10 00, 01, 11, 10 followed by 10, 11, 01, 00 000, 001, 011, 010 followed by 110, 111, 101, 100Result is 000, 001, 011, 010, 110, 111, 101, 100The Formal Karnaugh Map Method1. Choose a 1 element2. Find all maximal groups of 1's adjacent to that elementNote: "box" must be a power of 2 in size3. Repeat steps 1-2 for all 1 elements4. Select all boxes for which a 1 is “covered” by only that boxThese boxes are essential!5. For all 1's not covered by the essential boxes, select the smallest number of other boxes that cover themIn case of a choice, select the largest box!4 Variable Mapsf(A,B,C,D) = m(0,1,2,3,6,8,9,11,13,14)f = A C' D + B C D' + B' C ' + B' D + A'B' C D A B00 01 11 1000 1 1 1 101 0 0 0 111 0 1 0 110 1 1 1 0Another 4 Variable Mapf(A,B,C,D) = m(0,1,2,5,6,7,8,9,10,13,15)f = B D + A' B C + B' D' + B' C' orf = B D + A' B C + B' D' + C' D (there are 2 more) C D A B00 01 11 1000 1 1 0 101 0 1 1 111 0 1 1 010 1 1 0 1These are not essential!TerminologyAn implicant is a product term in an SOP expression (or a sum term in POS expression)Implicants are always rectangular in shape and the # of 1's covered is a power of 2A prime implicant is an implicant that is not fully contained in some other larger implicant B C A00 01 11 100 1 1 1 11 0 0 1 1red implicant (but not prime)many more are not shownblue prime implicants (only two)Essential Prime ImplicantsAn essential prime implicant is a prime implicant that contains a 1 not included in any other prime implicantThe minimum Boolean expression must use this termA cover is a collection of implicants that accounts for all valuations in which the function is “on” (e.g. 1)Find the Essential Prime Implicants C D A B00 01 11 1000 1 0 0 101 1 1 1 111 1 0 1 010 1 0 1 1 C D A B00 01 11 1000 1 0 0 101 1 1 1 111 1 0 1 010 1 0 1 1essential prime implicantsf = C'D' + A'B + B'D' + ACDDon’t Care ConditionsMany times there are incompletely specified conditionsValuations that can never occur, or for which we “don’t care what the device does”Modeling such a device requires us to specify don’t care conditions in those instancesUse X as a value to indicate we don't care what happensDon't care situations are often called incompletely specified functionsExample Using Don't Caresf(A,B,C,D) = m(1,5,8,9,10) + d(3,7,11,15)f = A B' + A' D C D A B00 01 11 1000 0 1 X 001 0 1 X 011 0 0 X 010 1 1 X 1Karnaugh Map Method Restated1. Choose an element from the “on” set2. Find all maximal groups (prime implicants) of “on” elements and X elements adjacent to that elementNote 1: prime implicants are always a power of 2 in sizeNote 2: do not feel compelled to include X’s – use them only when they provide a larger implicant3. Repeat steps 1-2 for all elements in the “on” set4. Select all essential prime implicants5. For all elements of the “on” set not covered by the essential prime implicants, select the smallest number of prime implicants that cover themExample: 7 Segment DisplayBinary Coded Decimal (BCD) input4 bit codes: 0000 (0) thru 1001 (9) allowed4 bit input code should operate lights of a 7 segment display: codes 1010 – 1111 never occur7 output signals – one for each lightaf bge cdWXYZ = 1001 af bgcdd = 1 is optional7 Segment Display Continued Y Z W X00 01 11 1000 1 0 1 101 0 1 1 X11 X X X
View Full Document