LESSON 6.pdf

CS100P INTRODUCTION TO COMPUTER SYSTEMS LESSON 6 KARNAUGH MAP (K-MAP) GATE-LEVEL MINIMIZATION THE MAP METHOD ¡ The complexity of the digital logic gates that implement a Boolean function is directly related to the complexity of the algebraic expression from which the function is implemented....

CS100P INTRODUCTION TO COMPUTER SYSTEMS LESSON 6 KARNAUGH MAP (K-MAP) GATE-LEVEL MINIMIZATION THE MAP METHOD ¡ The complexity of the digital logic gates that implement a Boolean function is directly related to the complexity of the algebraic expression from which the function is implemented. ¡ The map method provides a simple, straightforward procedure for minimizing Boolean functions. This method may be regarded as a pictorial form of a truth table. The map method is also known as the Karnaugh map or K-map. ¡ A K-map is a diagram made up of squares, with each square representing one minterm of the function that is to be minimized. K-MAP  Two-Variable K-Map Example, Minimize the following equation: x’y + xy’+ xy Therefore: x’y + xy’+ xy = x + y THREE-VARIABLE K-MAP FOUR-VARIABLE K-MAP Rules of Grouping  Mapping the four p-terms yields a single group of four, which is B Mapping the four p-terms above yields a group of four.Visualize the group of four by rolling up the ends of the map to form a cylinder, then the cells are adjacent. We normally mark the group of four as above left. Out of the variables A, B, C, there is a common variable: C'. C' is a 0 over all four cells. Final result is C'. The six cells above from the unsimplified equation can be organized into two groups of four. These two groups should give us two p-terms in our simplified result of A' + C'. The above Boolean expression has seven product terms. They are mapped top to bottom and left to right on the K-map above. For example, the first P-term A'B'CD is first row 3rd cell, corresponding to map location A=0, B=0, C=1, D=1. The other product terms are placed in a similar manner. Encircling the largest groups possible, two groups of four are shown above. The dashed horizontal group corresponds the the simplified product term AB. The vertical group corresponds to Boolean CD. Since there are two groups, there will be two product terms in the Sum-Of-Products result of Out=AB+CD. The four cells above are a group of four because they all have the Boolean variables B' and D' in common. In other words, B=0 for the four cells, and D=0 for the four cells. The other variables (A, B) are 0 in some cases, 1 in other cases with respect to the four corner cells. Thus, these variables (A, B) are not involved with this group of four. This single group comes out of the map as one product term for the simplified result: Out=B'C' The above group of eight has one Boolean variable in common: B=0. Therefore, the one group of eight is covered by one p-term: B'. The original eight term Boolean expression simplifies to Out=B' The six product terms of four Boolean variables map in the usual manner above as single cells. The three Boolean variable terms (three each) map as cell pairs, which is shown above. Note that we are mapping p-terms into the K-map, not pulling them out at this point. For the simplification, we form two groups of eight. Cells in the corners are shared with both groups. This is fine. In fact, this leads to a better solution than forming a group of eight and a group of four without sharing any cells. Final Solution is Out=B'+D' Above, three of the cells form into a groups of two cells. A fourth cell cannot be combined with anything, which often happens in "real world" problems. In this case, the Boolean p-term ABCD is unchanged in the simplification process. Result: Out= B'C'D'+A'B'D'+ABCD Both results above have four product terms of three Boolean variable each. Both are equally valid minimal cost solutions. The difference in the final solution is due to how the cells are grouped as shown above. A minimal cost solution is a valid logic design with the minimum number of gates with the minimum number of inputs. Pick up three more cells in a group of four, center above. There are still two cells remaining. the minimal cost method to pick up those is to group them with neighboring cells as groups of four as at above right. The two solutions depend on whether the single remaining cell is grouped with the first or the second group of four as a group of two cells. That cell either comes out as either ABC' or ABD, your choice. Either way, this cell is covered by either Boolean product term. Final results are shown above. This (above) is a rare example of a four variable problem that can be reduced with Boolean algebra without a lot of work, assuming that you remember the theorems.