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 MapsCircuit MinimizationAlgebraic manipulations can be used to simplify Boolean expressionsAs we've seen, this process is not always easyKarnaugh maps (K-maps) provide an easy and visual technique for finding the minimum cost SOP (or POS) form for a Boolean expressionThis technique has limitations. i.e. works for # inputs < 7Not good for CAD tools, but good for teaching the idea of simplificationThe Combining PropertyRecall the combining propertyx y + x y' = x (y + y') = xExample:f = x1'x2'x3'+x1'x2x3'+x1x2'x3'+x1x2'x3 = m0 + m2 + m4 + m5Minterms 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 gatesHence, f = x1'x3' + x1x2'  still SOP but not canonicalVisualizing the Combining Propertyf(x1,x2) = m(0,1,3)Canonical SOP:f = x1'x2'+x1'x2+x1x2 = x1'x2'+x1'x2+x1x2+x1'x2 = x1'+x2A 2-variable Karnaugh map:x1 x2 F0 0 10 1 11 0 01 1 1 x2x10 10 1 11 0 1minimum form: f = x1'+x23 Variable Mapf(A,B,C) = m(1,2,6,7)Minimum SOP is f = A B + B C' + A' B' CCost = 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 bitK-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 m8m9m11m10Full-Adder Carry-OutCout(A,B,Cin) = m(3,5,6,7)Minimum SOP is Cout = A Cin + B Cin + A BCost = 4 + 9 = 13 B Cin A00 01 11 100 0 0 1 01 0 1 1 1More 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 SumS(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 0Sidebar: Gray CodesA binary Gray code is a binary sequence such that no two consecutive numbers differ by more that a single bitGray codes have many uses in CS2 bit Gray code: 00, 01, 11, 10Note that this is circular  10, 00 again differs in only 1 bitThese are called binary reflected Gray codes3 bit Gray code: 000, 001, 011, 010, 110, 111, 101, 100Constructing Gray CodesIf 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 ,1s0Example:00, 01, 11, 10 00, 01, 11, 10 followed by 10, 11, 01, 00 000, 001, 011, 010 followed by 110, 111, 101, 100Result is 000, 001, 011, 010, 110, 111, 101, 100The Formal Karnaugh Map Method1. Choose a 1 element2. Find all maximal groups of 1's adjacent to that elementNote: "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 boxThese boxes are essential!5. For all 1's not covered by the essential boxes, select the smallest number of other boxes that cover themIn case of a choice, select the largest box!4 Variable Mapsf(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 0Another 4 Variable Mapf(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' orf = 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!TerminologyAn 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 2A 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 ImplicantsAn essential prime implicant is a prime implicant that contains a 1 not included in any other prime implicantThe minimum Boolean expression must use this termA 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' + ACDDon’t Care ConditionsMany times there are incompletely specified conditionsValuations 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 instancesUse X as a value to indicate we don't care what happensDon't care situations are often called incompletely specified functionsExample Using Don't Caresf(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 1Karnaugh 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 elementNote 1: prime implicants are always a power of 2 in sizeNote 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 themExample: 7 Segment DisplayBinary Coded Decimal (BCD) input4 bit codes: 0000 (0) thru 1001 (9) allowed4 bit input code should operate lights of a 7 segment display: codes 1010 – 1111 never occur7 output signals – one for each lightaf bge cdWXYZ = 1001  af bgcdd = 1 is optional7 Segment Display Continued Y Z W X00 01 11 1000 1 0 1 101 0 1 1 X11 X X X