Digital Logic Design
Karnaugh map
Karnaugh map
• The Karnaugh map (K-map) is a tool for
simplifying combinational logic with 3 or 4
variables. For 3 variables, 8 cells are required
(23).
• The map shown is for three ABC ABC
variables labeled A, B, and C.
ABC ABC
Each cell represents one
possible product term. ABC ABC
• Each cell differs from an ABC ABC
adjacent cell by only one
variable.
Minimizing Boolean Equation with Karnaugh
Map
Gray
First we must write the Boolean code
equation in a SOP, then place each C
0 1
AB
term on a map.
00
Cells are usually labeled using 0’s
and 1’s to represent the variable and 01
its complement. 11
Ones are read as the true variable
10
and zeros are read as the
complemented variable.
Gray code
Decimal Binary Gray code
0 0000 0000
• Gray code is an unweighted 1 0001 0001
2 0010 0011
code that has a single bit 3 0011 0010
change between one code 4 0100 0110
5 0101 0111
word and the next in a 6 0110 0101
sequence. 7 0111 0100
8 1000 1100
• Gray code is used to avoid 9 1001 1101
problems in systems where an 10 1010 1111
11 1011 1110
error can occur if more than 12 1100 1010
one bit changes at a time. 13 1101 1011
14 1110 1001
15 1111 1000
Alternatively, cells can be labeled with the variable
letters. This makes it simple to read, but it takes more
time preparing the map.
CC CC
Read the terms for the AB
AB ABC ABC
yellow cells.
AB
AB ABC
ABC ABC
AB
The cells are ABC and ABC. AB ABC ABC
AB
AB ABC ABC
ABC
Two variable Map
Two variable X and Y can form four AND
combination, which are:
Y
0 1
X
0 XY XY
1 XY XY
Three variable Map
Three variable A, B and C can form eight SUM
terms, which are:
Four variable Map
Four variable A, B , C and D can form sixteen
combinations. These can put on the Karnaugh map as:
Cell Adjacency
The cell arrangement in K-map allows only
single variable changes between adjacent cells
Mapping of a standard SOP expression
(3-variable case)
Example
Example
Example
Mapping of a non-standard SOP expression
(3-variable case)
We expand the terms by including all
combinations of the missing variables
Karnaugh Map Simplification
of SOP Expressions
K-maps can simplify combinational logic by grouping
cells and eliminating variables that change.
Group the 1’s on the map and read the minimum logic.
CC 00 11
AB
AB
11 1. Group the 1’s into two overlapping
00
00
B changes groups as indicated.
across this 01
01 11 11 2. Read each group by eliminating any
boundary variable that changes across a
11
11
boundary.
10
10 C changes 3. The vertical group is read AC.
across this 4. The horizontal group is read AB.
boundary
X = AC +AB
Karnaugh Map Simplification
of SOP Expressions
Group the 1’s on the map and read the minimum logic.
C changes across
outer boundary
CD
AB
00 01 11 10 1. Group the 1’s into two separate
00 1 1 groups as indicated.
B changes 2. Read each group by eliminating
01 1 1 any variable that changes across a
11 1 1
boundary.
B changes 3. The upper (yellow) group is read as
10 1 1 AD.
C changes
4. The lower (green) group is read
as AD.
X
X = AD +AD
Karnaugh Map Simplification
of SOP Expressions
Step-1: Develop appropriate map structure according to
the number of inputs for a given expression.
Step-2: Map all the terms within the given SOP
expression.
Step-3: Group the 1’s within the map.
Step-4: Determine the minimum SOP expression for the
map.
Grouping the 1’s within the map
Step-1: Group must contain either 1, 2, 4 , 8 or 16 cells,
which are all powers of two.
Step-2: Each cell in a group must be adjacent to one or
more cell in that group.
Step-3: Include largest possible numbers of 1s in a
group.
Step-4: Each 1 on the map must be included in at least
one group.
Determine the minimum SOP expression for
the map
Step-1: Each group of cells containing 1s creates one
product term composed of all variables that occur in only
one form (either uncomplemented or complemented
within the group.
Step-2: Variables that occur both uncomplemented and
complemented within the group are eliminated.
Example
Group the 1’s in each of the Karnaugh maps
Example
Group the 1’s in each of the Karnaugh maps
Example
Group the 1’s in each of the Karnaugh maps
Example
Group the 1’s in each of the Karnaugh maps
Example
Group the 1’s in each of the Karnaugh maps
Example
Example
Example
Example
Mapping Directly from a Truth-table
Self
training:
Find the
Simplified
expression
“Don’t Care” Conditions
For example in BCD
Are not allowed so they will never occur
Karnaugh Map Simplification of POS
Expressions
Step-1: Determine binary value of each sum term
in the standard POS expression. This is the
binary value that makes the term equal to 0.
Step-2: As each term is evaluated, place a 0
on the Karnaugh map in the corresponding
cell.
Example
Example
Example
Remember
A simplified Boolean equation uses fewest gates
possible to implement a given expression
37
Thank you for your attention
Any question?
References
1. T. Floyd, “Digital Fundamental”, 10th Ed., USA:
PrenticeHall, 2008
2. R.J. Tocci, “Digital Systems: Principles and
Applications”, 10th Ed., USA: Prentice-Hall, 2006
3. W. Kleitz, “Digital Electronics: A Practical
Approach”, 8th Ed., USA: Prentice-Hall, 2007
4. Begnell and Donovan, “Digital Electronics”, 5th
Ed., USA: Delmar Thomson Learning, 2006
