Arunkumar Khannur's Software Testing Knowledge Center
   
 

9.10 Use of Karnaugh Maps to Minimize Boolean Expressions Representing Complete Functions


Grouping Is or 0s into subcells of specific sizes led to both reduction in the number of terms as well as number of variables. These concepts can be effectively used in the simplification of Boolean expressions.

9.10.1 Prime Impllcants and Karnaugh Maps

We have already seen that each grouping of size 2x × 2y where x and y are non-zero integers in a Karnaugh map, irrespective of the num- ber of 1-cells or 0-cells it covers resuhs in one term. It was seen in Section 9.7.4 that each group of 1-cells resulted in a single product terni and each group of 0-cells resulted in a single sum term.

For simplification of Boolean expressions using Karnaugh maps, the mintcrms are plotted m the map of size depending on the number of variables namely, if the Boolean expression represents a ‘function of three variables, an 8-cell map is plotted, if the expression represents a function of four variables, a 16-cell map is plotted and soon. Using laws of Boolean Algebra the given expression can be brought to its equivalent minterm canonical form if it is not already in such a form Each product term resulting from a l-cell grouping represents a product term which implies the function.

Consider the function
f (a, b, c) =-a-b-c + a-b-c + a-b c
This function can be represented using m-notation as
f(a, b, c) = Σm (0, 4, 5)
Let us plot this on a three-variable Karnaugh map containing 23 or 8-cells as shown in Fig. 9.15


Ignore subcubes which are entirely contained in bigger subcubes. This leaves us with ubcubes (iv) and (v) which together entirely imply the function.

There fore f(a, b, c) = a-b +-b-c
Observe that the original function with three terms and five literals (a, c,-a,-b and-c) has been reduced to two terms with three literals (a,-b and-c). The product terms a-b and-b-c are the prime implicants of this function. If a variable is further dropped from one of these terms the remaining term will no longer imply the function. In the two level implementation of a SOP expression if the number of node inputs is the minimality criterion, the original expression has a cost of 6 and the minimized form has a cost of 4, where the cost is computed as the sum of the number of literals and the number of terms with more than one literal.

This method of considering subcubes of all possible sizes may prove tedious for more complex expressions. An algorithmic procedure can be laid down to guide the groupings in a Karnaugh map. The algorithm proceeds as follows.
Consider a n-variable Karnaugh map.

  1. Check if all the 2n enter are Is. This means that in a four variable map check if all the 16 cells have a i entry. If yes, the only prime implicant of the function is 1. If no, proceed to the next step.
  2. Search for all subcubes of 1-cells of size 2x × 2y = 2n-1. This means in a four variable map of 16 cells, search for subcubes of eight 1-cells as illustrated in Fig. 9.11 or in a three variable map of 8 cells search for subcubes of four 1-cells. Such subcubes reduce the product terms in the groups to a one-variable term as shown in Table 9.18. These subgroups reduce the grouped minterms to a single variable term which is a prime implicant because no two different subcubes can result in the same single term. This can be easily verified.
  3. The next step in the algorithm is to search for all subcubes of 1 cells of size 2x × 2y = 2n-2, so that no subcube is completely within another previously grouped subcube. This means, in a 4 variable 16 cell map search for subcubes of four 1-cells as illustrated in Fig. 9.10. Such subcubes reduce the product terms in the groups to two variable terms as shown in Table 9.17. These terms are also prime implicants.
  4. The next step is to search for all subcubes of 1 cells of size 2x × 2y = 2n-3 so that no subcube lies completely within a previously grouped subcube. This means, in a 4 variable 16-cell map search for subcubes of two 1-cells as illustrated in Fig. 9.9. Such subcubes result in three variable product terms as shown in Table 9.16.
  5. This process is continued until each 1 -cell in the map is grouped into atleast one subcube keeping track that no subcube should be completely contained within another subcube.

These steps can be written in the form of a flow chart as shown in Fig. 9.16.


Observe that subcube (ii) is a valid subcube according to the algorithm but even without subcube (ii) all the l-cells would have been covered and hence the term bc is not required.

there fore f =-a b + a c
This can be verified by the truth table in Table 9.25.




 
 
Khannur's Book
Arunkumar Khannur, Software Testing - Techniques and Applications, Published by Pearson Publications, 2011 (ISBN:978-81-317-5836-6; Pages:341 + xxii)
Follow Khannur
         
Khannur's Company
ISQT Process & Consulting Services Pvt. Ltd., Bangalore, INDIA
Khannur's Software Testing Forum
STEP-AUTO Forum
 Contact Khannur
ISQT Process & Consulting Services Pvt. Ltd.
#732, 1st Floor, 12th Main,
3rd Block, Rajajinagar,
Bangalore - 560010, INDIA
Phone: +91 80 23012511
URL: www.isqtinternational.com
Email: khannur@isqtinternational.com
Skype: arun.isqt