KARNAUGH MAP

The Karnaugh map also known as Veitch diagram or simply as K map is a two dimensional form of the truth table, drawn in such a way that the simplification of Boolean expression can be immediately be seen from the location of 1’s in the map. The map is a diagram made up of squares , each sqare represent one minterm or maxterm. 

Since any Boolean function can be expressed as a sum of minterms or product of maxterms of a TRUTH TABLE,  it follows then that a Boolean function is recognised  in the K-MAP graphically from the area enclosed by those squares whose minterms or maxterms are included in the function.

Karnaugh-map or K-map is the best tool for minimization of five or fewer variables functions for humans. K-maps are graphic and require pattern-matching which is one of human’s strongest abilities. Many believe that humans solve problems by creative pattern-matching.

• Karnaugh map => graphical representation of a truth table for a logic function.

• Each line in the truth table corresponds to a square in the Karnaugh map.

The size of the k-map is always equal to the total number of minterms.

• The Karnaugh map squares are labeled so that horizontally or vertically adjacent squares differ only in one variable. (Each square in the top row is considered to be adjacent to a corresponding square in the bottom row. Each square in the left most column is considered to be adjacent to a corresponding square in the right most column.)

K-map is a number of squares which are labeled using reflective gray code (each code is only 1 change from an adjacent code). For a given square, the user enters 0 or 1 corresponding to the function value at the inputs represented by the labels.

       GRAY CODE

        2 Variables  00 - 01         

                            10 - 11

        3 Variables  000 - 001 - 011 - 010    

                            100 - 101 - 111 - 110 

        4 Variables  0000 - 0001 - 0011 - 0010 

                            0100 - 0101 - 0111 - 0110

                            1100 - 1101 - 1111 - 1110

                            0100 - 0101 - 0111 - 0110

        5 Variables  00000 - 00001 - 00011 - 00010 - 00110 - 00111 - 00101 - 00100

                            01000 - 01001 - 01011 - 01010 - 01110 - 01111 - 01101 - 01100

                            11000 - 11001 - 11011 - 11010 - 11110 - 11111 - 11101 - 11100

                            10000 - 10001 - 10011 - 10010 - 10110 - 10111 - 10101 - 10100

CONSTRUCTION OF KMAP.   

NOTE : The 0s and 1s outside the boxes are the Literal Values  or the Values of a Variable.

Knowing the locations of all MINTERMS in a K-MAP is critical in understanding how to it.

A two variable Boolean function can be represented as follow

The above map shows boxes for the locations of  all Minterms for a 2 input variables A and B. These boxes should be filled up with the Function Values corresponding to the Minterms as expressed in the Truth Table.

We may present our K-Map differently, but as long as they can represent all the Minterms of of a Truth Table, then this is Valid and we can still arrived with the right simplified Function.

A 3-Variable K-Map.

Again here are different Valid ways to present the K-Map for 3 Variables ABC.

A 4-Variable K-Map.

Here is the K-MAP using the Minterms equivalent Decimal Values to label the boxes instead of theLiterals A,B,C, A', B', C'.

Here are K-map examples filled with the Function's Values of 0s and 1s  from a Truth Table (not shown)

for a 2, 3, and 4 Input Variables A,B,C,D:

From the Truth Table, we see that the Minterms A'B, AB' and  AB have all the Function equal to 1. Then in our K-Map we put a 1 to the corresponding boxes of these Minterms ( m1, m2 and m3 or  A'B, AB' and AB or  01, 10 and 11)      

Let us now use the K-MAP above to simplify  our  Function.  First from the Truth Table we get the Function X by getting the SOP of Minterms.  

                                X = m1 + m2 + m3 = A'B + AB' + AB

The from our K-MAP we can see that X = A + B

Note that we can also use the K-MAP to use the Maxterms and get the POS expression. Using above Truth Table.

Again, using the POS for Maxterms we consider 0 as the uncomplemented value of the literals and function.  Using Maxterm from the K-Map,  we can the function Y = A+B.

Another Example , with the following Truth Table.

Using the K-MAP above to derive the Function X, we get  X = AB' + A'B.  We can see that this is the

XOR function, where the output is 1 when inputs A and B are complement to each other. SO that means, from the K-MAP, we cannot make any more simplification, as it is not allowed to group any terms that are in Diagonal Position.

Using the POS of Maxterms, we get the function X = (A+B)(A'+B'), of course this will simplify to 

AB' + A'B.  SAme as the above.

HOW to get the Boolean Function from K-MAP

Consider the 3 variables function.

Minterm Karnaugh map and Maxterm Karnaugh map of the three variable Boolean function

Y = A'B'C' + A'BC' + AB'C' + ABC'                                   <--- SOP(Minterms)

Y = (A' + B' + C').(A' + B + C').(A + B' + C').(A + B +C')  <--- POS(Maxterms)

From the SOP K-Map, we get Y = B'C' + BC' or simply Y = C'

From the POS K-MAP, we get Y = (B' + C').(B + C') = B'B + B'C' + BC' + C'C'  = C'

This actually means that we can group all the 4 cells to get the simplified form of the Boolean Expression,

The Group of 4 cells represent the Literal C' from the K-MAP.

HOW TO USE K-MAP TO MINIMIZE BOOLEAN FUNCTION

Example: Use K-map to minimize F(A,B,C) = A'.B'.C  + A'.B.C  + A.B'.C + A.B.C

Solution:

1. Use a truth table to identify all the Min-terms.

2. Fill in the K-map:

a. Select the K-Map that matches the number of variables in your function.

b. Draw the K-map (remember the labels are reflective Gray Code)

c. Enter the value of the function for the corresponding min-term.

     Other Valid ways to Draw K-MAP.  (remember the labels are reflective Gray Code)

3. The next step is to group as many neighboring ones as possible. Cells with one variable is      

     complemented are referred to as neighboring cells:

a. Grouping adjacent min-terms (boxes) is applying the Adjacency theorem graphically.

     In an n-variable k-map, each square is adjacent to exactly n other squares.

b. The goal is to get as large a grouping of 1s as possible 

    (Must form a full rectangle – cannot group diagonally)

• Only adjacent squares can be combined

• All 1’s must be covered

• Covering rectangles must be of size 1,2,4,8, … 2n

4. For each identified group, look to see which variable has a unique value. In this case, 

                            F(A,B,C) = C 

    since F’s value is not dependent on the value of A and B.

Using other K-MAP for Booelan SImplification.

All other K-MAPS will also yield to F = C.

To easily Simplify a Boolean expression using a K-Map, we should be able to detect immediately Adjacent Squares that we can Validly combined.    Below shows the 

GUIDE LINES in Forming groups of 1s in K-MAP.

1. Each square containing a 1 must be considered at least once, although it can be considered as often      as needed.

2. The objective should be to account for all the marked squares in the minimum number of groups.

3. The number of squares in a group must always be a power of 2, i.e. groups of 1,2, 4, 8, 16, squares.

4. Each group should be as large as possible, which means that a square should not be accounted for by      itself if it can be accounted for by a group of two squares; a group of two squares should not be made      if the involved squares can be included in a group of four squares and so on.

EXAMPLE of K-MAP with 4 Variables 

USING MINTERMS

USING MAXTERMS

Get the Simplified SOP and POS Function from the KMAP Below:

*** Get the Simplified Boolean Function for the K-Map below.

Get the K-Map from the TRUTH TABLES below and the simplified

Boolean Function from the derived K-Map.

IMPLICANTS:  K-map related definitions

 An Implicant is the product term where the function is evaluated to 1 or complemented to 0. An

Implicant implies the term of the function is 1 or complemented to 0. Each square with a 1 for the

function is called an implicant (p). If the complement of the function is being discussed, then 0’s

are called implicants (r).

Note: To find the complement of F, apply the same rules to 0 entries in the K-map instead of 1.

 A Prime Implicant of a function is a rectangular (each side is powers of 2) group of product

terms that is not completely contained in a single larger implicant.

 An Essential Prime Implicant of a function is a product term that provides the only coverage for

a given min-term and must be used in the set of product terms to express a given function in

minimum form. •If a minterm is covered by exactly one prime implicant then this prime implicant is called an essential prime implicant

 An Optional Prime Implicant of a function is a product term that provides an alternate covering

for a given Min-term and may be used in the set of product terms to express a function in a

minimum form. Some functions can be represented in a minimum form in more than one way

because of optional prime implicants.

 A Redundant Prime Implicant or Nonessential Prime Implicant of a function is a product term

that represents a square that is completely covered by other essential or optional prime

Get the Simplified SOP Function from the K-MAP Below 

a) Without using don't cares  b) using the don't cares.

Example Application (Don't Care)

The electronics class of Lightning State College has been asked to build the lamp logic for a stationary bicycle exhibit at the local science museum. As a rider increases his pedaling speed, lamps will light on a bar graph display. No lamps will light for no motion. As speed increases, the lower lamp, L1 lights, then L1 and L2, then, L1, L2, and L3, until all lamps light at the highest speed. Once all the lamps illuminate, no further increase in speed will have any effect on the display.

K-MAP

IMPLEMENTATION: Logic Circuit

5 Variable K-MAP

The Function above from the 5-variable K-map is 

F = X2X4 + X2'X3'X4' + X1'X2X3 + X1X2'X3X5 

6 Variable K-MAP

EXAMPLE: 5 Variable KMAP.  F(ABCDE)

EXAMPLE: 6 Variable KMAP.  Z(ABCDEF)

MORE EXAMPLES:

Determination of simplified Boolean function in SOP and POS form in Karnaugh Map 

USING SOP (MInterms)

USING POS (Maxterms)

5 and 6 VARIABLES

USEFUL ALGORITHMS for K-MAP.

5 Important Points in SImplifying Functions Using K-MAP.

EXAMPLE:

To begin our simplification, we first plot the fuction on the KMAP as follows.