Arunkumar Khannur's Software Testing Knowledge Center
   
 

9.9 Karnaugh Maps


Boolean functions can be diagrammatically represented by means of Karnaugh maps. A n variable function has 24 or 8 rows in the truth table and a 4 variable function has 24 of 16 rows in the truth table describing the function. A n variable function would have 2n rows in its truth table. A Karnaugh map is so drawn such that each row of the table corresponds to a cell in the map. A 1 is placed in a cell corresponding to a row for which the function evaluates to 1 and 0 is placed in the cells corresponding to rows for which the function evaluates to 0.

The cells are so arranged that physically adjacent cells are also logically adjacent. Two terms are logically adjacent if they differ only in one literal. For example, a-b c is adjacent to abc. -a-b c and a-b-c, a compliment b is adjacent to ab and -a b, abcd is adjacent to -abcd. abcd, abcd and abcd compliment. Observe that a two variable term is logically adjacent to 2 terms, a three variablc term is logically adjacent to 3 terms and an n variable term is logically adjacent to n terms. On the map. a cell corresponding to a n variable term would be logically adjacent to n other cells.

9.9.1 One and Two Variable Maps

A one variable map relates to function of one variable, for example. f (a) = -a This function describes an inverter. The truth table is shown in Table 9.10


This table can be diagrammatically represented in a Karnaugh map as shown in fig. 9.3 with 21 or 2 cells.

Fig. 9.3 Karnaugh map of (a) a one variable function (b) f(a) -a

Observe that the physically adjacent cells vary only in one variable (a and a) and hence are logically adjacent.

A two variable map relates to a function of two variables. Example fa, b) = ab + ab. The truth table for the function is shown in Table 9.11.


Observe that cell corresponding to f(0, 0),-a-b is adjacent to -a b and a-b.

9.9.2 Three and Four Variable Maps

A three variable map relates to a function of three variables, for example,
f (a, b, c)=-a bc + a-b-c + ab-c + abc. The truth table for this function is shown in Table 9.12.


The three variable map is constructed on a cylinder such that the left hand and right hand edges of the map touch each other. We can ensure that all cells, including those at the left and right extremes are logically and physically adjacent to three other cells.

The Karnaugh map for the three variable function is shown in Fig.9.5 with 23 or 8 cells.


Imagine folding the three variable map over a cylinder with edge WX in contact truth edge YZ as shown in Fig. 9.5(c).
This assures that
Cell 0 is adjacent to cells 1, 4 and 2
Cell 4 is adjacent to cells 0, 5 and 6
Cell 2 is adjacent to cells 3, 6 and 0
Cell 6 is adjacent to cclls 2 , 7 and 4

The cell numbers have been so-arranged that physically adjacent cells are also logically adjecent. Cell 0 (-a-b-c ) and cell 2(-a-b-c ) different only in one literal ‘b’
A four variable map relates to a function of four variables, for example, f (a, b,c,d) = Σm (0, 3, 5, 11, 12, 14, 15). The truth table for this function is shown in Table 9.13.


The cells in the four variable Karnaugh map are so arranged that physically adjacent cells are also logically adjacent. Imagine that the map is rolled horizontally so that edge WY is in contract with edge. XZ and that the map is rolled vertically so that edge WX is in contact with edge YZ. The Karnaugh map for a four variable function is shown in Fig. 9.6 with 24 or 16 cells.

It is easy to sec that
Cell 0 is adjacent to cells 1,4, 2 and 8
Cell 8 is adjacent to cells 12,9, 10 and 0
Cell 3 is adjacent to cells 1, 7, 2 and 11
and so on.
Observe that physically adjacent cells are also logically adjacent in the sense that they vary in only one literal.

 
 
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