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:
The 0s and 1s outside the boxes are the Literal Values and the ones in the inside of the boxes are the Function values taken from the TRUTH TABLE.
HOW TO SET UP K-MAP
The Karnaugh map also known as K map is a two dimensional form of the truth table. So it is necessary that we have a complete Truth Table before we can construct the corresponding K-MAP.
Consider the Truth Table below and construct the corresponding K-MAP.
From the Truth Table, we see that the Minterms A'B and AB have both the Function equal to 1. Then in our K-Map we put a 1 to the corresponding boxes of these Minterms ( m1 and m3 or A'B and AB or 01 and 11)
Getting the Minterms from the Truth Table we get the function X = A'B + AB
From K-Map, we can visually see that it is simple occupying the squares where B=1.
Which means that the function can simply be X = B.
Going back to the original function X = A'B + AB, we can simplify it to X = B.
Consider anotherTruth Table below and construct the corresponding K-MAP.
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.
A small DC generator coupled to the bicycle tire outputs a voltage proportional to speed. It drives a tachometer board which limits the voltage at the high end of speed where all lamps light. No further increase in speed can increase the voltage beyond this level. This is crucial because the downstream A to D (Analog to Digital) converter puts out a 3-bit code, ABC, 23or 8-codes, but we only have five lamps. A is the most significant bit, C the least significant bit.
The lamp logic needs to respond to the six codes out of the A to D. For ABC=000, no motion, no lamps light. For the five codes (001 to 101) lamps L1, L1&L2, L1&L2&L3, up to all lamps will light, as speed, voltage, and the A to D code (ABC) increases. We do not care about the response to input codes (110, 111) because these codes will never come out of the A to D due to the limiting in the tachometer block. We need to design five logic circuits to drive the five lamps.
TRUTH TABLE
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.