Unit 5: Karnaugh MapsEEC180A5.1 Minimum Forms of Switching Functions()()∑= 7,6,5,2,1,0,, mcbaFabcabccabbcacbacbaF+++++= '''''''''Find a minimum sum-of products expression for:F = a’b’ b’c bc’ ab++ +abcabccabbcacbacbaF+++++= '''''''''None of these terms can be eliminatedHowever, if we combine in a different way.F = a’b’ bc’ ac++Note: Use XY’ + XY = X5.2 Karnaugh MapsWe can represent a 1 and 2-input truth table as 1-D and 2-D cubeXY00011011FXF01XY + XY’ = XX’Y + X’Y’ = X’X’Y+XY = YX’Y’+XY’ = Y’5.2 Karnaugh MapsAllows for easy application of XY + XY’ = X5.2 Two-Variable Karnaugh MapsABAB5.2 Two-Variable Karnaugh MapsTwo Variable Karnaugh Map Example:• Minterms in adjacent squares on the map can be combined sincethey differ in only one variable (i.e. XY’ + XY = X)5.2 Three-Variable Karnaugh MapsFWe can represent a 3-input truth table as a 3-D cubeX Y Z5.2 Three-Variable Karnaugh MapsLocation of Minterms on a Three Variable Karnaugh MapTruth Table and resulting Karnaugh Map for Three-Variable Function5.2 Three-Variable Karnaugh Maps5.2 Three-Variable Karnaugh MapsLocation of Minterms on a Three Variable Karnaugh Map()()()∏∑== 7,6,4,2,05,3,1,, mcbaF5.2 Three-Variable Karnaugh Maps''' acbabcF++=Karnaugh Map for cb''a5.2 Three-Variable Karnaugh MapsKarnaugh Maps for Product Termsabcabc5.2 Three-Variable Karnaugh MapsSimplification of a Three-Variable Function()∑= 5,3,1mFcbcaF ''+=5.2 Three-Variable Karnaugh MapsSimplification of F’()∑= 5,3,1mF()∑= 7,6,4,2,0' mFabcF+=''F’5.2 Three-Variable Karnaugh MapsKarnaugh Maps which illustrate the Consensus Theorem5.2 Three-Variable Karnaugh MapsFunction with Two Minimum Forms5.3 Four-Variable Karnaugh MapsAdjacent squares should differ by only one variable5.3 Four-Variable Karnaugh MapsLocation of Minterms on a Four-Variable Karnaugh Map5.3 Four-Variable Karnaugh MapsSample 4-variable Karnaugh Map'' dbaacdF++=5.3 Four-Variable Karnaugh MapsSimplification of Four-Variable Functions()∑= 13,12,10,5,4,3,1mF''''' cdabdbabcF++=5.3 Four-Variable Karnaugh MapsSimplification of Incompletely Specified Function()( )∑∑+= 13,12,69,7,5,3,1 dmFdcdaF ''+=c’da’d5.3 Four-Variable Karnaugh MapsFinding Minimum Product of Sums from Karnaugh MapsyxzywwyzzxF ''''''+++=F’F1011100000101011wxyz00 011110000111100100011111010100wxyz00 01111000011110y’zwxz’w’xyxywwxzzyF ''''++=Using DeMorgan’s()()()''''' yxwzxwzyF+++++=5.4 Determination of Minimum ExpressionsImplicant – any single 1 or any group of 1’s which can be combined together on a map of the function F11 11111wxyz00 01111000011110wy’z’wy’zwxy’wx’y’wy’w’yz’w’x’yList of Implicants – wxy’, wx’y’, wy’z’, wy’z, wy’, w’x’y, w’yz’and all single 1’sPrime Implicant – an implicant which can not be combinedwith another term to eliminate a variable.11 11111wxyz00 0111100001111011 11111wxyz00 01111000011110wy’w’yz’w’x’yList of Prime Implicants: w’x’y, w’yz’, wy’5.4 Determination of Minimum ExpressionsImplicantsPrime ImplicantsFind the prime implicants:1111111111abcd00 011110000111105.4 Determination of Minimum ExpressionsFind the prime implicants:1111111111abcd00 011110000111101111111111abcd00 011110000110115.4 Determination of Minimum Expressions1111111111abcd00 011110000111101111111111abcd00 011110000110115.4 Determination of Minimum ExpressionsMinimum Solution might not utilize all prime implicants1 1Essential Prime Implicant –A prime implicant that contains a minterm that is coveredby only one prime implicant5.4 Determination of Minimum Expressions1111111 1abcd00 01111000011011- minterm covered by morethan 1 prime implicant- minterm covered byonly 1 prime implicantList of Essential Prime Implicants: bc’, ac bc’ac1 1To find minimum expression:5.4 Determination of Minimum Expressions1111111 1abcd00 01111000011011find simplestexpressionfor remaining1’sa’b’dF = a’b’d + bc’ + acbc’ac• Find all Prime Implicants• Determine Essential Prime Implicants• Find Simplest Expression for remaining uncovered 1’sFind Minimum Sum-of-Products Expression5.4 Determination of Minimum Expressions111111 1 1ABCD00 011110000111105.4 Determination of Minimum Expressions111111 1 1ABCD00 01111000011110111111 1 1ABCD00 01111000011110First find all Prime Implicants5.4 Determination of Minimum Expressions111111 1 1ABCD00 01111000011110Next find all essential Prime Implicants111111 1 1ABCD00 01111000011110- mintern covered byonly 1 prime implicantACDA’C’A’B’D’List of Essential Prime Implicants: A’C’, ACD, A’B’D’ Minimum Solution: F = A’C’ + ACD + A’B’D’ +