Karnaugh Map (K-map)
K-Map is a pictorial representation of the Boolean function. It is a systematic method of simplifying the Boolean expression. A K-Map is an arrangement of the adjacent cell , each cell representing the minterm or the maxterm of the SOP or the POS equations.
The number of adjacent cells in a K-Map depends on the number of input variables in an equation. The number of cell equals 2N where N is the number of input variables. Let us see how the minterm or the maxterms of the SOP or POS equations are represented.
Two variable K-Map
Table in figure-1 on the left is a truth table for two input variables. The output is shown in column marked ‘F’. m0, m1, m2, m3 are the four minterms (or the product terms )for high ‘1’ outputs.
Three Variable K-Map
Table on the left is a truth table for three input (x,y,z)and one output variables(F). The minterms are marked m0, m1, m2, m3 m4, m5, m6, m7 are the eight minterms (or the product terms )for high ‘1’ outputs. Note the naming of cells. Minterms in upper row is m0,m1,m3, m2 with binary value as 00, 01,11,10 and the lower row cell numbers being m4,m5, m7, m6.
Example: Show the representation of the minterms of a three variable majority function using a K-Map.
The table below shows the relationship for the input and output of the majority function
The K-map in figure shows the position of the minterms. Figure (c) is the K-map filled with the minterms values ‘1’ for the high outputs
Figure-4 below shows the K-map for four variables. There are 16 number of cells each marked for one minterm. Note down the position of the cells carefully. There cell numbering follow the unit distance /gray code pattern so that only one variable change as we move from any position to any next up or down or left or right of current cell. This method as we’ll see helps in simplification.
Simplification using K-Map
We can group adjacent ‘1’ in the following ways to reduce the number of variables in a Boolean or logical equation. The adjacent ‘1’ s can be grouped to form “pair”, “Quad” or “Octet” to reduce 1, 2 or 3 variable in an equation.
A pair can be formed by grouping two horizontal or two vertical ‘1’. A pair of ‘1’ reduces 1 variable.
Example: Simplify Y= x’yz + xy’z + xyz + xyz’
Solution: The equation has four minterms. We enter at the appropriate cell of 3 variable K-Map
We find that there are three pairs of 1’s marked in different colors. Each pair reduces 1 variable.
x from vertical pair; so it reduces to “yz”
y from 1st lower horizontal pair; which reduces to “xz”
z from lower 2nd pair; which reduces to “xy”
So the solution is :Y = yz + xz + xy
A quad is formed with four adjacent 1’s either horizontally, vertically or two 1’s horizontal and two 1’s vertically adjacent. A quad reduces two variable.
Y = x’y’z + x’yz + x’yz’ + xy’z’ + xy’z + xyz
The equation has six minterms. So, enter 1’s at appropriate positions in the K-Map
In figure (a), we see that a quad as shown in red color, is formed with four 1’s.
Overlapping the groups
As seen, two 1’s are still left ungrouped. We can combine the left over 1’s with adjacent groups. So, two pairs are also formed by combing the 1’s with the quad.
The pair is blue color and pair in green color overlapped with quad further give simplified minterms x’y and xy’
The complete solution thus is:
Y = z + x’y + xy’
An octet is a group of eight adjacent 1’s. An octet reduces three variable from a Boolean equation. Figure below shows a K-Map of a 4-variable K-Map.
As can be observed, the solution obtained by the octet in red color is z and the solution obtained by blue octet is x. Therefore, the complete solution of an SOP equation is Y = x + z
A redundant group is one whose all the 1’s have been consumed by other groups. So, there is no need to form such group. Whenever you see that all 1’s of a group have been exhausted, simply ignore that group.
In figure above the pair shown in red color is a redundant pair as its upper 1 is consumed by the pair in upper row and the lower 1 is consumed by the lower pair. Such pair can be just ignored.
The solution thus is:
y = x’z + xz’
Don’t Care Combinations:
There are many situations in which certain combination of inputs are of no consequences. For example while designing the BCD to seven segment decoder, the inputs combinations from 0-to-9 are valid combination, any other four bit value 1010, 1011, 1100, 1101, 1110 and 1111 are invalid input combinations. The don’t care terms in K-Map is written a ‘x’
The presence or absence of such input are f no important to us. We can therefor uses such combinations as don’t care combinations and assign a value ‘0’ or a ‘1’ as per our convenience.
If it helps in simplifying the SOP Boolean equation we can treat the don’t care term as a ‘1’ or make it as ‘0’. Similarly, for a POS if the don’t care helps in further simplification, we can treat it as ‘0’ or else make it as a ‘1’.
Let us take an example:
If we treat the value of don’t care as ‘1’, the K-Map reduces to Y = z + x’y
Find the minimal expression for Y = ∑m( 1,5,6,12,13,14) + d(2,4)
Find the minimal form of K-map
Simplify the following K-Map
Simplify the Boolean expression Y(A,B,C) = ∑m( 1,2,3,5,6,7)
When the Boolean function Y=∑m( 0,1,2,3) + d(4,5,6,7) is minimized, what does one get
The minimized logic expression corresponding to the K-Map given below is?
- A + B’C
- B + AC
- C + AB
The solution to the Boolean expression Y = ∑m( 0,2,4,6) + d(1,5)
What is the mimised logic expression corresponding to the following K-Map?
A relay is to operate with conditions that it should be ON when the input combinations are 0000, 0010, 0101, and 0111. The states 1000, 1001 and 1010 don’t occur. For rest of the status, relay should be OFF. The minimised boolean expression notifying the relationship is:
(a). BC + ACD
(b). B’D’ + A’BD
(c). BD + AC
(d). AB + CD