Karnaugh -map

Karnaugh Map
 Based on its history, the founder of the K-MAP is
Maurice Karnaugh during the year 1953.
Karnaugh Map
 Graphical technique of simplifying Boolean
expression containing 2, 3, 4, and 5 variables
 Contains all the possible values of input variables and
their corresponding output values - 2D truth tables .
 Values are stored in cells of the array
 Number of cells is similar to the total number of
variable input combinations
 For example, if the number of variables is three, the
number of cells is 23=8, and if the number of variables
is four, the number of cells is 24
 Contd..
 In general, the number of cells in the K-map is
determined by the number of input variables and is
mathematically expressed as 2n, where the number of
input variables is n.
 Further, each cell within a K-map has a definite place-
value which is obtained by using an encoding
technique known as Gray code.
 The specialty of this code is the fact that the adjacent
code values differ only by a single bit. That is, if the
given code-word is 01, then the previous and the next
code-words can be 11 or 00, in any order, but cannot
be 10 in any case
2 – Variable K-Map
 A two variable has four input combinations, hence it
has 4 squares one for each term.
3 – Variable K-Map
 A three variable has 8 input combinations, hence it
has 8 squares one for each term
Contd..
4 – Variable K-Map
 A three variable has 8 input combinations, hence it
has 8 squares one for each term
Contd..
Rules for simplification
 Following rules for the simplification of expressions
by grouping together adjacent cells containing ones.
No zeros allowed.
No diagonals.
Only power of 2 number of cells in each group.
Groups should be as large as possible.
Every one must be in at least one group.
Overlapping allowed.
Wrap around allowed.
Fewest number of groups possible.
Cell adjacency
 The cells in a karnaugh map
are arranged so that there is
only a single-variable change
between adjacent cells.
 Adjacency is defined by a
single variable change.
 Cells with values that differ by
more than one variable are not
adjacent.
Rule-1
 Groups may not include any cell containing a zero
Rule - 2
 Groups may be horizontal or vertical, but not
diagonal.
Rule - 3
 Groups must contain 1, 2, 4, 8, or in general
2n cells.
if n = 1, a group will contain two 1's since 21 = 2.
If n = 2, a group will contain four 1's since 22 = 4.
Rule - 4
 Each cell containing a one must be in at least one
group.
Rule- 5
 Each group should be as large as possible
 Group the number of ones in the decreasing order.
First, we have to try to make the group of eight, then
for four, after that two and lastly for 1
Rule - 6
 Groups may overlap.
Rule - 7
 Groups may wrap around the table. The leftmost
cell in a row may be grouped with the rightmost
cell and the top cell in a column may be grouped
with the bottom cell.
Rule - 8
 There should be as less number of groups as
possible, as long as this does not contradict any
of the previous rules.
Rule - 9
 Don’t care conditions are to be considered only if they
aid in increasing the group-size (else neglected).
Obtain Boolean Expression for Each
Group
 Express each group in terms of input variables by
looking at the common variables seen in cell-labelling.
 There are two groups
 Group 1 - groups with two number of ‘ones’
 Group 2 - groups with only one ‘ones’
 Contd..
 All the ‘ones’ in the Group 1 of the K-map are present
in the row for which A = 0. Thus they contain the
variable A̅.
 Further these two ‘ones’ are present in adjacent
columns which have only B term in common as
indicated by the pink arrow in the figure.
 Hence the next term is B. This yields the product term
corresponding to this group as A̅B.

Group 1 = A̅B
 Contd..
 Similarly the ‘one’ in the Group 2 of the K-map is
present in the row for which A = 1.
 Further the variables corresponding to its column are
B̅C̅. Thus one gets the overall product-term for this
group as AB̅C̅.

Group 2 = AB̅C
Steps to solve
 Define the given expression in its canonical form.
 Enter 1 to each product-term into the K-map cell and
fill the remaining cells with zeros.
 Forming the groups by considering the rules
mentioned above.
 Obtain Boolean Expression for Each Group
 Obtain Boolean Expression for the Output by adding
each group Boolean Expression.
Example-1
 Step : 1 : Enter 1 to each product-term into the K-map
cell and fill the remaining cells with zeros
 Contd..
 Step: 2 Forming the groups by considering the rules
and obtain the Boolean expression.
Example : 2
Example : 2
Example : 3
Example : 3
 https://youtu.be/iJ9cFDoXajw
Video on Logic
https://youtu.be/6HTN3IDi2Fw
minimization
https://youtu.be/VY9J3qYbky4
using K-map
https://youtu.be/SyTGG2TeJJw
https://youtu.be/ygm25sqqepg
https://docs.google.com/document/d/1Af7TfeK9p
Activity on
TdcLmSWehNYaq73zsR6rMoZvE2vVPeu2T4/edi
Karnaugh Map
t