Boolean Algebra and Computer LogicMinimizationKarnaugh MapExample: Karnaugh MapKarnaugh MapsSlide 6Slide 7Slide 8Slide 9Using the Karnaugh MapUsing Karnaugh MapsExample: Using Karnaugh MapsSlide 13Slide 14Quine-McCluskey ProcedureExample: Quine-McCluskey ProcedureSlide 17Slide 18Slide 19Slide 20Slide 21Boolean Algebra and Computer LogicMathematical Structures for Computer ScienceChapter 7Copyright © 2006 W.H. Freeman & Co. MSCS Slides Boolean Logic and Computer LogicSection 7.3 Minimization 2MinimizationTo design a logic network for the function, the ideal would be to have a procedure that chooses the simplest Boolean expression from the equivalence class.At any rate, it would be ideal to minimize the total number of connections that must be made and the total number of logic elements used. To discuss minimization procedures, many factors may influence the economics of the situation. If a network is to be built only once, the time spent on minimization is costlier than building the network. But if the network is to be mass-produced, then the cost of minimization time may be worthwhile.Section 7.3 Minimization 3Karnaugh MapIn the canonical sum-of-products form for a truth function, we are interested in values of the input variables that produce outputs of 1. The Karnaugh map records the 1s of the function in an array that forces products of inputs differing by only one factor to be adjacent. The array form for a two-variable function is given in the figure below. Notice that the square corresponding to x1x2, the upper left-hand square, is adjacent to squares x1x2 and x1x2, which differ in one factor from x1x2. However, it is not adjacent to the x1x2 square, which differs in two factors from x1x2.Section 7.3 Minimization 4Example: Karnaugh MapThe truth function of Table 7.10 as seen here is represented by the Karnaugh map of the figure below. At once we can observe 1s in two adjacent squares, so there are two terms in the canonical sum-of-products form differing by one variable; again from the map, we see that the variable that changes is x1. It can be eliminated. We conclude that the function can be represented by x2. Indeed, the canonical sum-of-products form for the function is x1x2 + x1x2, which, by our basic reduction rule, reduces to x2. However, we did not have to write the canonical form  we only had to look at the map.Section 7.3 Minimization 5Karnaugh MapsMaps for three and four variables.The array forms for functions of three and four variables are shown in the figure below. In these arrays, adjacent squares also differ by only one variable. However, in Figure (a), the leftmost and rightmost squares in a row also differ by one variable, so we consider them adjacent. (They would in fact be adjacent if one wrapped the map around a cylinder and glued the left and right edges together.)Section 7.3 Minimization 6Karnaugh MapsIn Figure (b), the leftmost and rightmost squares in a row are adjacent (differ by exactly one variable), and also the top and bottom squares in a column are adjacent. In three-variable maps, when two adjacent squares are marked with 1, one variable can be eliminated; when four adjacent squares are marked with 1 (either in a single row or arranged in a square), two variables can be eliminated.Section 7.3 Minimization 7Karnaugh MapsIn the map in the figure below, the squares that combine for a reduction are shown as a block. These four adjacent squares reduce to x3 (eliminate the changing variables x1 and x2). The reduction uses our basic reduction rule more than once: x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 = x1x3 (x2 + x2) + x1x3 (x2 + x2) = x1x3 + x1x3 = x3 (x1 + x1) = x3Section 7.3 Minimization 8Karnaugh MapsIn four-variable maps, when two adjacent squares are marked with 1, one variable can be eliminated; when four adjacent squares are marked with 1, two variables can be eliminated; when eight adjacent squares are marked with 1, three variables can be eliminated.Figure (a) illustrates some instances of two adjacent marked squares.Section 7.3 Minimization 9Karnaugh MapsFigure (b) illustrates some instances of four adjacent marked squares, and Figure (c) shows instances of eight.(b)(c)Section 7.3 Minimization 10Using the Karnaugh MapHow do we find a minimal sum-of-products form from a Karnaugh map (or from a truth function or a canonical sum-of-products form)? We must use every marked square of the map, and we want to include every marked square in the largest combination of marked squares possible since doing so will reduce the expression as much as possible. However, we cannot begin by simply looking for the largest blocks of marked squares on the map.Section 7.3 Minimization 11Using Karnaugh MapsSteps for using Karnaugh Maps are listed in the table as seen here:Section 7.3 Minimization 12Example: Using Karnaugh MapsFigure (a) shows the only square that cannot be combined into a larger block. In Figure (b), shows the unique two-square block for the x1x2x3 square and the unique two-square block for the x1x2x3 square. All marked squares are covered. The minimal sum-of-products expression is: x1x2x3 + x2x3 + x1x2Formally, the last two terms are obtained by expanding x1x2x3 into x1x2x3 + x1x2x3 and then combining it with each of its neighbors.Section 7.3 Minimization 13Example: Using Karnaugh MapsFigure (a) shows the unique two-square and four-square blocks. The remaining two unused marked squares can be assigned to two-square blocks in two different ways, as shown in Figures (b) and (c). Assigning them together to a single two-square block is more efficient since it produces a sum-of-products form with three terms rather than four. The minimal sum-of-products expression is:x1x3 + x1x2x3 + x2x3x4Section 7.3 Minimization 14Example: Using Karnaugh MapsMap of Figure (a) shows two unique four-square blocks determined by the squares with * have been chosen. In Figure (b), the remaining unmarked squares, for which there was a choice of blocks, are combined into blocks as efficiently as possible. The resulting sum-of-products form is:x1x3 + x1x3 + x3x4 + x1x2 + x1x2x4 Yet in Figure (c), choosing a different four-square block at the top leads to a simpler sum-of-products form: x2x3 + x1x3 + x3x4 + x1x2x4Section 7.3