Karnaugh Map

1. KARNAUGH MAPKARNAUGH MAP
Presented By:Presented By:
Syed Absar KarimSyed Absar Karim
(EP076268)(EP076268)

2. IntroductionIntroduction
The Karnaugh map (also known as The Karnaugh map (also known as
a a Veitch diagram)Veitch diagram) was invented was invented
in 1953 by Maurice Karnaugh, a in 1953 by Maurice Karnaugh, a
telecommunications engineer at telecommunications engineer at
Bell Labs. It is a graphical way of Bell Labs. It is a graphical way of
minimizing Boolean expressions. minimizing Boolean expressions.
An expression’s truth table is An expression’s truth table is
drawn as a matrix in such a way drawn as a matrix in such a way
that each row and each column of that each row and each column of
the matrix puts minterms that the matrix puts minterms that
differ in the value of a single differ in the value of a single
variable adjacent to each other. variable adjacent to each other.
Then, by grouping adjacent cells of Then, by grouping adjacent cells of
the matrix, you can identify the matrix, you can identify
product terms that eliminate all product terms that eliminate all
complemented literals, resulting in complemented literals, resulting in
a minimized version of the a minimized version of the
expression.expression.

3. PropertiesProperties
Normally, extensive calculations Normally, extensive calculations
are required to obtain the are required to obtain the
minimal expression of a Boolean minimal expression of a Boolean
function, but one can use a function, but one can use a
Karnaugh map instead. Karnaugh map instead.
A Karnaugh map may have any A Karnaugh map may have any
number of variables, but usually number of variables, but usually
works best when there are only works best when there are only
a few a few - - between 2 and 6 for between 2 and 6 for
exampleexample. .
Each square in a Karnaugh map Each square in a Karnaugh map
corresponds to a minterm (and corresponds to a minterm (and
maxterm). The picture to the maxterm). The picture to the
right shows the location of each right shows the location of each
minterm on the map. minterm on the map.

4. Size of MapSize of Map
In a Karnaugh map with In a Karnaugh map with nn variables, a Boolean term mentioning variables, a Boolean term mentioning
kk of them will have a corresponding rectangle of area 2 of them will have a corresponding rectangle of area 2nn − − kk. .
Common sized maps are of 2 variables which is a 2x2 map; 3 Common sized maps are of 2 variables which is a 2x2 map; 3
variables which is a 2x4 map; and 4 variables which is a 4x4 variables which is a 2x4 map; and 4 variables which is a 4x4
map map
For problems involving more than six variables, solving the For problems involving more than six variables, solving the
Boolean expressions is more preferred than the Karnaugh map. Boolean expressions is more preferred than the Karnaugh map.

6. SOP & POSSOP & POS
A Karnaugh map can also be drawn for 0’s as well as 1’sA Karnaugh map can also be drawn for 0’s as well as 1’s
The SOP (Sum of Product) expression refers to drawing of a Karnaugh The SOP (Sum of Product) expression refers to drawing of a Karnaugh
map in which high values (1’s) are plotted. The simplified equation map in which high values (1’s) are plotted. The simplified equation
comes in SOP form such as (A.B)+(B.C)comes in SOP form such as (A.B)+(B.C)
The POS (Product of Sum) expression represents the low (0) values in The POS (Product of Sum) expression represents the low (0) values in
the Karnaugh Map. The simplified equation comes in POS form like the Karnaugh Map. The simplified equation comes in POS form like
(A+B).(C+D)(A+B).(C+D)
Pairs, Quads & Octets
A group of two adjacent 1’s in the Veitch Diagram is known as Pair.
The quad is a group of four 1’s that are end to end, or in the form of a
square. Two variables and their compliments drop out of the Boolean
equation in the quad.
An octet is a group of eight adjacent 1’s. an octet always eliminates
three variables and their complements

7. Don't caresDon't cares
Karnaugh maps also allow easy Karnaugh maps also allow easy
minimizations of functions minimizations of functions
whose truth tables include whose truth tables include
""don't caredon't care" " conditions conditions

They are usually indicated on They are usually indicated on
the map with a hyphenthe map with a hyphen//dashdash//X X
in place of the numberin place of the number. .
The value can be a The value can be a ""0,0," "" "1,1," " or or
the hyphenthe hyphen//dashdash//X depending X depending
on if one can use the on if one can use the ""00" " or or ""11" "
to simplify the Karnaugh Map to simplify the Karnaugh Map
moremore. .

8. Thank YouThank You
References:References:
Digital Fundamentals (Floyd)Digital Fundamentals (Floyd)
Digital Computer Electronics (Malvino Brown)Digital Computer Electronics (Malvino Brown)
Wikipedia, The free EncyclopediaWikipedia, The free Encyclopedia