
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 2^{x} × 2^{y} where x and
y are nonzero integers in a Karnaugh map, irrespective of the num
ber of 1cells or 0cells it covers resuhs in one term. It was seen in
Section 9.7.4 that each group of 1cells resulted in a single product
terni and each group of 0cells 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 8cell map is plotted, if the expression represents a function of four variables, a 16cell 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 lcell grouping represents a product term which implies the function.

Consider the function
f (a, b, c) =abc + abc + ab c
This function can be represented using mnotation as
f(a, b, c) = Σm (0, 4, 5)
Let us plot this on a threevariable Karnaugh map containing 23 or 8cells 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) = ab +bc
Observe that the original function with three terms and five literals (a, c,a,b andc) has been reduced to two terms with three literals (a,b andc). The product terms ab andbc 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 nvariable Karnaugh map.


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.

Search for all subcubes of 1cells of size 2^{x} × 2^{y} = 2^{n}1. This means
in a four variable map of 16 cells, search for subcubes of eight 1cells as illustrated in Fig. 9.11 or in a three variable map of 8 cells search for subcubes of four 1cells. Such subcubes reduce the product terms in the groups to a onevariable 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.

The next step in the algorithm is to search for all subcubes of 1 cells of size 2^{x} × 2^{y} = 2^{n}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 1cells 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.

The next step is to search for all subcubes of 1 cells of size 2^{x} × 2^{y} = 2^{n}3 so that no subcube lies completely within a previously grouped subcube. This means, in a 4 variable 16cell map search for subcubes of two 1cells as illustrated in Fig. 9.9. Such subcubes result in three variable product terms as shown in Table 9.16.

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 lcells 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:9788131758366; Pages:341 + xxii) 
Follow Khannur 

Khannur's Company 

ISQT Process & Consulting Services Pvt. Ltd., Bangalore, INDIA

Khannur's Software Testing Forum 

STEPAUTO 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 
