11Elec 326 Karnaugh MapsKarnaugh MapsObjectivesThis section presents a technique for simplifying logical expressions. It will: Define Karnaugh and establish the correspondence between Karnaugh maps and truth tables and logical expressions. Show how to use Karnaugh maps to derive minimal sum-of-products and product-of-sums expressions.  Introduce the concept of "don't care" entries and show how to extend Karnaugh map techniques to include maps with don't care entries.Reading Assignment Sections 2.6 and 2.7 from the text2Elec 326 Karnaugh MapsKarnaugh Map DefinitionsA Karnaugh map is a two-dimensional truth-table. Unlike ordinary (i.e., one-dimensional) truth tables, however, certain logical network simplifications can be easily recognized from a Karnaugh map.Two-Variable MapsTruth Table001101010110AB ZABZType 1 Map0 11 0BZType 2 MapA01010 11 0Three-Variable MapsType 2 Map10111000010 00 11 11 0ZB,CACType 1 MapABZ0 1111000Truth Table000011110011001101010101ABC01101001Z23Elec 326 Karnaugh MapsFour-Variable MapsTruth Table0000000011111111000011110000111100110011001100110101010101010101ABCD0001011101111111ZType 2 MapZC,D00 01 101100011110A,B100 1 1 11 11 11 110ABCDZ10 00 1 1 11 11 11 110Type 1 Map00 04Elec 326 Karnaugh MapsThe interpretation of a type 1 map is that the rows or columns labeled with a variable correspond to region of the map where that variable has value 1. Numbering of Karnaugh Map Squares.A = 1regionC = 1regionD = 1regionB = 1regionABCDABCDABCDABCDZC,D00 01 101100011011A,B01324571213151489101160100011011ZB,CA01324756BZA010101 3235Elec 326 Karnaugh Maps Exercise: Plot the following expression on a Karnaugh map.Z = (A•B)⊕(C+D)ACBDZ = A•B•(C+D)' + (A•B)'•(C+D)= A•B•C'•D' + (A'+B')•(C+D)= A•B•C'•D' + A'•C + A'•D + B'•C + B'•D11111111110000006Elec 326 Karnaugh MapsMinimal Sum-Of-Products ExpressionsOrdering of Squares The important feature of the ordering of squares is that the squares are numbered so that the binary representations for the numbers of two adjacent squares differ in exactly one position. This is due to the use of a Gray code (one in which adjacent numbers differ in only one position) to label the edges of a type 2 map.The labels for the type 1 map must be chosen to guarantee this property. Note that squares at opposite ends of the same row or column also have this property (i.e., their associated numbers differ in exactly one position).47Elec 326 Karnaugh MapsMerging Adjacent Product TermsZ= m5 + m13= A'•B•C'•D + A•B•C'•D = (A'+A)•B•C'•D= 1•B•C'•D= B•C'•D ExampleABCDZ0 0 0 00 0 0 00 0 0 01 10 0A'BC'DABC'DZBC'DZBACDZ10 0 00 0 0000110 0 01A•B•C'A' • C • D8Elec 326 Karnaugh MapsFor k-variable maps, this reduction technique can also be applied to groupings of 4,8,16,...,2k rectangles all of whose binary numbers agree in (k-2),(k-3),(k-4),...,0 positions, respectively.Z= m5 + m7 + m13 + m15= A'•B•C'•D + A'•B•C•D + A•B•C'•D + A•B•C•D= (A'•C' + A'•C + A•C' + A•C) • (B•D)= (A'•(C' + C) + A•(C' + C)) • (B•D)= (A' + A) • (B•D)= B•DBACDZ10 000 0 0000 110 00159Elec 326 Karnaugh MapsBasic Karnaugh Map Groupings for Three-Variable Maps.BACZ311BACZ51111BACZ411 11BCZ611 11ABACZ111BACZ21110Elec 326 Karnaugh MapsBasic Karnaugh Map Groupings for Four-Variable Maps.DBACZ711BACDZ141 11 1BACD1 1Z8CD11ABZ9BACZ101 1DBACDZ111111BACZ121111DCDZ131 11 1AB611Elec 326 Karnaugh MapsBACDZ151111BACDZ1811111111BACD1Z161 1 1BACDZ171 11 11 11 1CDZ1911111111AB BAZ201 11 11 11 1CD12Elec 326 Karnaugh MapsRules for Grouping: The number of squares in a grouping is 2i for some i such that 1 ≤ i ≤ k. There are exactly k-i variables that have constant value for all squares in the grouping.Resulting Product Terms: If X is a variable that has value 0 in all of the squares in the grouping, then the literal X' is in the product term. If X is a variable that has value 1 in all of the squares in thegrouping, then the literal X is in the product term. If X is a variable that has value 0 for some squares in the grouping and value 1 for others, then neither X' nor X are in the product term.713Elec 326 Karnaugh Maps Invalid Karnaugh Map Groupings.BACDZ100 0000 1100111 11Violates Rule 1BACDZ111010 0011111111Violates Rule 2loop 1loop 214Elec 326 Karnaugh MapsIn order to minimize the resulting logical expression, the groupings should be selected as follows: Identify those groupings that are maximal in the sense that they are not contained in any other possible grouping. The product terms obtained from such groupings are called prime implicants.A distinguished 1-cell is a cell that is covered by only one prime implicant.An essential prime implicant is one that covers a distiquished 1-cell. Use the fewest possible number of maximal groupings needed to cover all of the squares marked with a 1.Examples:BACDZ1000110011111111#2#3#4#1815Elec 326 Karnaugh Mapsa. Z = A•B•D+A•B'•C'+A'•B•C'+A'•C•D+A'•B'•D'b. Z = B•D+A•B'•C'+A'•B•C'+A'•C•D+A'•B'•D'c. Z = B•D+A•B'•C'+A'•C'•D'+A'•B'•CBACDZ100011 001 11111 10BACDZ100011 001 11111 10BACDZ100011 001 11111 10#5#3 #2#4#1a. Non-minimalProduct Terms#1#2#3#4#5#1#2#3#4b. Non-minimal Selectionof Prime Implicantsc. MinimalGroupingBACW31 000110111111 111DBACDW31 000110111111 111a. W3 = C'D+AC'+BC+A'B'D'b. W3 = BD+AB+B'C'+A'CD'16Elec 326 Karnaugh MapsExercise: Derive minimal sum-of-products logical expressions from the following Karnaugh maps.ACBDACBD111111110000 0000111111110000 0000XYA•B + A'•B'•D' + A'•B'•C + B•C•D'X = A'•C' + A•C•D' + A•B•C + B•C'•D'Y =917Elec 326 Karnaugh MapsMinimal Product-Of-Sums ExpressionsMerging Adjacent Product Terms.ACZ00111 11B1Karnaugh MapA'B'C'AB'C'B'C'ZZOR-AND NetworksM3•M7 = (A+B'+C')•(A'+B'+C')= (A•A')+(B'+C')= 0 + (B'+C')= B' + C'18Elec 326 Karnaugh MapsRules for Grouping: Same as for sum-of-products, except that zero's are grouped instead of ones.Resulting Sum Terms: If variable X has value 0 for all squares in the group, then the literal X is in the sum term. If variable X has value 1 for all squares in the group, then the literal X' is in the sum term. If variable X has value 0 for some squares in the group and value 1 for the others, then that variable does not appear in the sum term.Prime