Digital Engineering

Fall 2023

Lecture 04 – K-map Method

Instructor: Dr. Tarek Abdul Hamid
The Simplification Problem: Requirements

 Simplification of complex circuits, starting from their equivalent representation as

complex Boolean expressions, requires an understanding of cost.

 We will see that the typical goal is to arrive at Boolean expressions that:
 are expressible in SOP (or POS) form
 involve minimal numbers of literals
 involve a minimal number of gate application levels

 To help us understand how to accomplish circuit minimization, we will study one

powerful reduction technique:
 Karnaugh maps

2 Dr. Tarek Abdul Hamid Digital Engineering

Concepts of Cost

 We focus on two types of cost model.

 Minimum time of completion of circuit logic

 both SOP and POS circuit representations are two-level designs with
all the gates at each level performing in parallel with the same time
characteristics.

 Minimum cost of circuit construction

 very often it is possible, starting with the SOP or POS forms, to rewrite
a near-optimal cost form involving pure nand or nor gates only.

 This leads to four cost theorems.

3 Dr. Tarek Abdul Hamid Digital Engineering

Concepts of Cost
 Before stating the theorems we need some definitions of terms:

 Literal a variable or its complement (unique symbol)

 Implies F implies G, means that there does not exist a set

of N input literals such that both F=1 and G=0;
By contrast, if F=1 then G must be equal to 1.

 Subsumes A term T1 subsumes a term T2 if and only if (!)

all the literals in T2 are also found in T1.
If one term subsumes another in an expression,
then the subsuming term can always be deleted
with changing the function. In other words, if T1
subsumes T2 then T1 may be ignored because the
T2 terms account for logic.

4 Dr. Tarek Abdul Hamid Digital Engineering

Concepts of Cost

 … and some more definitions of terms:

 Implicant a product term is said to be an implicant of a

complete function if the product term implies
the function.

 Implicate a sum term is said to be an implicate of a

complete function if the sum term implies
the function.

5 Dr. Tarek Abdul Hamid Digital Engineering

Concepts of Cost
 … and some more definitions of terms:

 Prime Implicant an implicant is a prime implicant if it does not

subsume any other implicant with fewer literals.
This means that if any literal is removed from
the term, it no longer implies the function.

 Prime Implicate an implicate is a prime implicate if it does not

subsume any other implicate with fewer literals.
This means that if any literal is removed from
the term, it no longer implies the function.

Note the symmetry between the

definitions of implicant (product)
and implicate (sum).

6 Dr. Tarek Abdul Hamid Digital Engineering

Concepts of Cost

 Cost Theorem 1a.

When the cost, assigned by some criterion, for a minimal Boolean formula is such
that decreasing the number of literals in the disjunctive normal formula does not
increase the cost of the formula, there is at least one minimal disjunctive normal
formula that corresponds to a sum of prime implicants.

 Cost Theorem 2a.

For any cost criterion such that the cost of a formula does not increase when a
literal is removed, at least one minimal disjunctive normal formula describing a
function is an irredundant disjunctive normal formula (SOP).

7 Dr. Tarek Abdul Hamid Digital Engineering

Concepts of Cost

 Cost Theorem 1b.

When the cost, assigned by some criterion, for a minimal Boolean formula is such
that decreasing the number of literals in the conjunctive normal formula does not
increase the cost of the formula, there is at least one minimal conjunctive normal
formula that corresponds to a product of prime implicates.

 Cost Theorem 2b.

For any cost criterion such that the cost of a formula does not increase when a
literal is removed, at least one minimal conjunctive normal formula describing a
function is an irredundant conjunctive normal formula (POS).

 These theorems establish that implicates are dual to implicants.

8 Dr. Tarek Abdul Hamid Digital Engineering

Expression Simplification

 The algebraic techniques we have developed are too slow and uncertain to
apply in cases where the numbers of variables are large.

 To meet the needs of modern circuit analysis and design several methods have
been developed that

 are somewhat scalable, and

 permit limited degrees of automation (ie. Programmability).

9 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps

 The use of mapping, or tableau-based, techniques were developed by Veitch and

modified by Karnaugh.

 We will determine these techniques by studying examples in order to establish the

rules for map manipulation.

10 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 1 variable map

x f(x)
0 f(0) Truth Table
1 f(1)

11 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 1 variable map
Literal
x f(x)
0 f(0) Truth Table
1 f(1)

Function Values
Binary Values

12 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 1 variable map
Literal
Literal x
x f(x) 0 1 Binary Values
0 f(0) Truth Table f(0) f(1) Function Values
1 f(1)

Function Values
Binary Values

13 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 1 variable map
x
x f(x) 0 1
0 f(0) Truth Table f(0) f(1)
1 f(1)

1x2 Karnaugh Map

14 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 2 variable map

x y f(x,y)
0 0 f(0,0)
0 1 f(0,1)
Truth Table
1 0 f(1,0)
1 1 f(1,1)

15 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 2 variable map

y
x y f(x,y) 0 1
0 0 f(0,0)
0 1 f(0,1) f(0,0) f(0,1)
Truth Table
1 0 f(1,0) 0
x
1 1 f(1,1) 1 f(1,0) f(1,1)

2x2 Karnaugh Map

16 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 3 variable map

yz
x y z f(x,y,z)
0 0 0 f(000) 00 01 11 10
0 0 1 f(001)
0 1 0 f(010) f(000) f(001) f(011) f(010)
0 1 1 f(011) 0
1 0 0 f(100) x
1 0 1 f(101) 1 f(100) f(101) f(111) f(110)
1 1 0 f(110)
1 1 1 f(111)

2x4 Karnaugh Map

17 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 3 variable map

yz
x y z Note
f(x) the way that
0 0 0 the column indices
f(000) 00 01 11 10
0 change by only 1
0 1 f(001)
0 bit at a time from
1 0 f(010)
left to right. f(000) f(001) f(011) f(010)
0 1 1 f(011) 0
1 0 0 f(100) x
1 0 1 f(101) 1 f(100) f(101) f(111) f(110)
1 1 0 f(110)
1 1 1 f(111)

2x4 Karnaugh Map

18 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 3 variable map

y
x y z f(x,y,z)
0 0 0 f(000) 00 01 11 10
0 0 1 f(001)
0 1 0 f(010) f(000) f(001) f(011) f(010)
0 1 1 Anf(011)
alternative 0
1 0 0labelling
f(100) scheme is x
1 0 1 based
f(101) on which 1 f(100) f(101) f(111) f(110)
1 1 0 literal
f(110)has value 1.
1 1 1 f(111)
z

2x4 Karnaugh Map

19 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 3 variable map

y
x y z f(x,y,z)
0 0 0 f(000) 00 01 11 10
0 0 1 f(001)
0 1 0 f(010) 0 1 3 2
0 1 1 f(011) 0
1 0 0 f(100) x
1 0 1 f(101) 1 4 5 7 6
1 1 0 f(110)
1 One final
1 1 f(111)
alternative labelling
z
scheme replaces
the function value
by the decimal 2x4 Karnaugh Map
minterm index
value.

20 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 4 variable map

w x y z f(w,x,y,z)
0 0 0 0 f(0000)
0 0 0 1 f(0001)
0 0 1 0 f(0010)
0 0 1 1 f(0011)
0 1 0 0 f(0100)
0 1 0 1 f(0101)
0 1 1 0 f(0110)
0 1 1 1 f(0111)
1 0 0 0 f(1000)
1 0 0 1 f(1001)
1 0 1 0 f(1010)
1 0 1 1 f(1011)
1 1 0 0 f(1100)
1 1 0 1 f(1101)
1 1 1 0 f(1110)
1 1 1 1 f(1111)
21 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 4 variable map yz
00 01 11 10
w x y z f(w,x,y,z)
f(0000) f(0001) f(0011) f(0010)
0 0 0 0 f(0000)
0 0 0 1 f(0001) 00
0 0 1 0 f(0010) f(0100) f(0101) f(0111) f(0110)
0 0 1 1 f(0011) 01
0 1 0 0 f(0100) wx
0 1 0 1 f(0101) 11 f(1100) f(1101) f(1111) f(1110)
0 1 1 0 f(0110)
0 1 1 1 f(0111) 10
1 0 0 0 f(1000)
f(1000) f(1001) f(1011) f(1010)
1 0 0 1 f(1001)
1 0 1 0 f(1010)
1 0 1 1 f(1011)
1 1 0 0 f(1100)
1 1 0 1 f(1101)
1 1 1 0 f(1110)
1 1 1 1 f(1111)
22 Digital Engineering
Dr. Tarek Abdul Hamid
Karnaugh Maps
 4 variable map yz
00 01 11 10
w x y z f(w,x,y,z)
0 0 0 0 f(0000) 0 1 3 2
0 0 0 1 f(0001) 00
0 0 1 0 f(0010)
0 0 1 1 f(0011) 01 4 5 7 6
0 1 0 0 f(0100) wx
0 1 0 1 f(0101) 11 12 13 15 14
0 1Note
1 0 the
f(0110)
way that
0 1both
1 1 the
f(0111)
row and 10
1 0column
0 0 f(1000)
indices 8 9 11 10
1 0change
0 1 f(1001)
by only 1
1 0bit
1 at
0 af(1010)
time.
1 0 1 1 f(1011)
1 1 0 0 f(1100)
1 1 0 1 f(1101)
1 1 1 0 f(1110)
1 1 1 1 f(1111)
23 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 4 variable map yz
00 01 11 10
w x y z f(w,x,y,z)
0 0 0 0 f(0000) 0 1 3 2
0 0 0 1 f(0001) 00
0 0 1 0 f(0010)
0 0 1 1 f(0011) 01 4 5 7 6
0 1 0 0 f(0100) wx
0 1 0 1 f(0101) 11 12 13 15 14
0 1Note
1 0 the
f(0110)
way that
0 1both
1 1 the
f(0111)
row and 10
1 0column
0 0 f(1000)
indices 8 9 11 10
1 0change
0 1 f(1001)
by only 1
1 0bit
1 at
0 af(1010)
time.
1 0 1 1 f(1011)
1 1 0 0 f(1100)
1 1 0 1 f(1101)
1 1 1 0 f(1110) This implies that two rows, or columns,
1 1 1 1 f(1111) whose indices differ by only 1 bit value, are
24 Dr. Tarek Abdul Hamid Digital Engineering
adjacent.
Karnaugh Maps
 4 variable map yz
00 01 11 10
w x y z f(w,x,y,z)
0 0 0 0 f(0000) 0 1 3 2
0 0 0 1 f(0001) 00
0 0 1 0 f(0010)
0 0 1 1 f(0011) 01 4 5 7 6
0 1 0 0 f(0100) wx
0 1 0 1 f(0101) 11 12 13 15 14
0 1Note
1 0 the
f(0110)
way that
0 1both
1 1 the
f(0111)
row and 10
1 0column
0 0 f(1000)
indices 8 9 11 10
1 0change
0 1 f(1001)
by only 1
1 0bit
1 at
0 af(1010)
time.
1 0 1 1 f(1011)
1 1 0 0 f(1100)
1 1 0 1 f(1101)
WRAP-AROUND!
1 1 1 0 f(1110) This implies that two rows, or columns,
1 1 1 1 f(1111) whose indices differ by only 1 bit value, are
25 Dr. Tarek Abdul Hamid Digital Engineering
adjacent.
Karnaugh Maps
 4 variable map y
00 01 11 10
w x y z f(w,x,y,z)
0 0 0 0 f(0000) 0 1 3 2
0 0 0 1 f(0001) 00
0 0 1 0 f(0010)
0 0 1 1 f(0011) 01 4 5 7 6
0 1 0 0 f(0100) x
0 1 0 1 f(0101) 11 12 13 15 14
0 1 1 0 f(0110)
0 1 1 1 f(0111) w
10
1 0 0 0 f(1000) 8 9 11 10
1 0 0 1 f(1001)
1 0 1 0 f(1010)
1 0 1 1 f(1011) z
1 1 0 0 f(1100)
1 1 0 1 f(1101)
An alternative row/column
1 1 1 0 f(1110)
labelling, highlighting the
1 1 1 1 f(1111)
26 Dr. Tarek Abdul Hamid literal with value 1. Digital Engineering
Karnaugh Maps
 Case Study: 1 variable map
x
X F(X) 0 1
 Ex.
0 0 0 1
1 1

Place function
values (from the
defining function
truth table) in the
map positions.

27 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 1 variable map
x
0 1
0 1

Circle all 1 entries that, taken

together, form a subcube
(i.e. rectangular shape formed
from 1-boxes, without holes).

28 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 1 variable map
x
0 1
0 1

Circle all 1 entries that,

taken together, form a
subcube (i.e. rectangle).

DEFINITION:
When constructing SOP forms, a 2N -subcube is a rectangular region of a
Karnaugh map consisting of 2N adjacent cells, each containing the same
value 1 (or 0 for POS forms), and where N must be an integer greater or
equal to zero.
29 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 Case Study: 1 variable map
x
0 1
0 1

The entry 1 in the second

column corresponds to
the prime implicant x.

30 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 1 variable map
x
0 1
0 1

The entry 1 in the second

column corresponds to
the prime implicant x.

Recall that x is a prime implicant iff:

- x implies f(x) and,
- x does not subsume any other implicant:
Since, removing x from itself leaves nothing, then x is clearly prime.
31 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 Case Study: 1 variable map
x
0 1
0 1

Thus, the minimal

expression of the function
is:
F(x) = x

32 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 1 variable map - Complementation
x
X F(X)
0 1
0 1
1 0
1 0

The entry 1 in the first

column corresponds to
the prime implicant x’.

33 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 1 variable map - Complementation
x
X F(X)
0 1
0 1
1 0
1 0

The entry 1 in the first

column corresponds to
the prime implicant x’.
Thus, the minimal
expression of the function
is:
F(x) = x’

34 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 1 variable map - 2nd variation
x
X F(X)
0 1
0 1
1 1
1 1

Circle all 1 entries that,

taken together, form a
subcube (i.e. rectangle).

35 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 1 variable map - 2nd variation
x
X F(X)
0 1
0 1
1 1
1 1

We note that both x and x’ terms are

included in the rectangle. Their
individual “product” contributions
to the SOP expression must be
summed (or’ed):
x + x’
But, this reduces to 1.

36 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 1 variable map - 2nd variation
x
X F(X)
0 1
0 1
1 1
1 0

Thus, the minimal

expression of the function
is:
F(x) = 1

37 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 1 variable map - 2nd variation
x
X F(X)
0 1
0 1
1 1
1 0

Thus, the minimal

expression of the function
is:
f=1

In other words, when both 0 and 1 terms appear for a literal referenced
within the cells of a subcube, that literal is removed from the implicant
corresponding to that subcube, leaving a prime implicant.
38 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 3 variable map
yz
00 01 11 10

2x4 Karnaugh Map 0 1 1 0

0
x
1 1 0 1 0
X Y Z F(X,Y,Z)
0 0 0 0
0 0 1 1
0 1 0 0 Place function
values (from the
0 1 1 1 defining function
1 0 0 1 truth table) in the
1 0 1 0 map positions.

1 1 0 0
1
39 1 1 Dr. Tarek1Abdul Hamid Digital Engineering
Karnaugh Maps
 3 variable map
yz
00 01 11 10

X Y Z F(X,Y,Z) 0 1 1 0
0
0 0 0 0 x
0 0 1 1 1 1 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
•Circle all 1 entries that, taken together, form a
1 0 1 0 subcube (i.e. rectangle).
1 1 0 0 •Start with the largest subcubes, then proceed to
1 1 1 1 smaller subcubes
•Generally speaking, there will be more than one
independent subcube, each reflecting a different
prime implicant.
40 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 3 variable map y’ z’
yz
00 01 11 10

0 1 1 0
0
x
x 1 1 0 1 0

•For each subcube, write its algebraic expression

using the variable name (eg. x) if the box occurs
in the row/column for which the variable is 1 –
otherwise, if the box occurs in the row/column for
which the variable (eg. y,z) is 0, use the
complemented variable (ie. y’, z’).

41 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 3 variable map y’ z’
yz
Collecting 00 01 11 10
literals into a
product
0 1 1 0
gives: 0
xy’z’ x
x 1 1 0 1 0

1-subcubes are expressed using all

variable symbols

42 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
z y+y’=1
 3 variable map
yz
00 01 11 10

x’ 0 1 1 0
0
x
1 1 0 1 0

Circle all 1 entries that, taken

together, form a subcube (i.e.
rectangle). Generally speaking, there
will be more than one independent
subcube, each reflecting a different
prime implicant.

43 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
z y+y’=1
 3 variable map
yz
00 01 11 10
Collecting
literals into a x’ 0 1 1 0
product 0
gives: x
x’z 1 1 0 1 0

Circle all 1 entries that, taken

together, form a subcube (i.e.
rectangle). Generally speaking, there
will be more than one independent
subcube, each reflecting a different
prime implicant.

44 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 3 variable map y z
yz
00 01 11 10

0 1 1 0
0
x+x’ = 1 x
1 1 0 1 0

Circle all 1 entries that, taken

together, form a subcube (i.e.
rectangle). Generally speaking, there
will be more than one independent
subcube, each reflecting a different
prime implicant.

45 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 3 variable map y z
yz
00 01 11 10

0 1 1 0
0
x+x’ = 1 x
1 1 0 1 0

Collecting Circle all 1 entries that, taken

literals into a together, form a subcube (i.e.
product rectangle). Generally speaking, there
gives: will be more than one independent
yz subcube, each reflecting a different
prime implicant.

46 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 3 variable map
yz
00 01 11 10

0 1 1 0
0
Each subcube (rectangle)
x
corresponds to a prime
1 1 0 1 0
implicant term.

Gathering all terms in

SOP form,

f = xy’z’ + x’z + yz

47 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 3 variable map
yz
00 01 11 10
f = xy’z’ + x’z + yz
0 1 1 0
0
x
1 1 0 1 0

48 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 3 variable map
yz
00 01 11 10
f = xy’z’ + x’z + yz
0 1 1 0
0
x
1 1 0 1 0

Each subcube contains at least one 1-cell that can ONLY be

included within that subcube. Such 1-cells are called
essential 1-cells and their corresponding prime implicant is
called an essential prime implicant.
49 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 3 variable map
yz
00 01 11 10
f = xy’z’ + x’z + yz
0 1 1 0
0
x
1 1 0 1 0

xy’z’ ( xy’z’ )
Essential 1-cell (essential prime implicant).
Each subcube contains at least one 1-cell that can ONLY be
included within that subcube. Such 1-cells are called
essential 1-cells and their corresponding prime implicant is
called an essential prime implicant.
50 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 3 variable map
yz
00 01 11 10
f = xy’z’ + x’z + yz
0 1 1 0
0
x
1 1 0 1 0

x’y’z ( x’z )
Essential 1-cell (essential prime implicant).
Each subcube contains at least one 1-cell that can ONLY be
included within that subcube. Such 1-cells are called
essential 1-cells and their corresponding prime implicant is
called an essential prime implicant.
51 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 3 variable map
yz
00 01 11 10
f = xy’z’ + x’z + yz
0 1 1 0
0
x
1 1 0 1 0

xyz ( yz )
Essential 1-cell (essential prime implicant).
Each subcube contains at least one 1-cell that can ONLY be
included within that subcube. Such 1-cells are called
essential 1-cells and their corresponding prime implicant is
called an essential prime implicant.
52 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 3 variable map - 2nd variation
yz
00 01 11 10

1 1 1 1
0
x
1 1 0 0 1

53 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 3 variable map - 2nd variation
yz
00 01 11 10

1 1 1 1
0
x
1 1 0 0 1

Circle all 1 entries that,

taken together, form a
subcube (i.e. rectangle) of
the largest size, but
containing 2N squares (for
Dr. Tarek Abdul Hamid all possible N).
54 Digital Engineering
Karnaugh Maps
 3 variable map - 2nd variation
yz
00 01 11 10

1 1 1 1
0
x
1 1 0 0 1

Circle all 1 entries that,

taken together, form a
subcube (i.e. rectangle) of
the largest size, but
containing 2N squares (for
all possible N).
55 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 3 variable map - 2nd variation
yz
00 01 11 10

1 1 1 1
The “wrap-around” 0
technique. x
1 1 0 0 1

Circle all 1 entries that,

taken together, form a
subcube (i.e. rectangle) of
the largest size, but
containing 2N squares (for
all possible N).
56 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 3 variable map - 2nd variation
yz
00 01 11 10

1 1 1 1
0
x’[yz + y’z + yz’ + y’z’] x
= x’[(y+y’)z + (y+y’)z’] 1 1 0 0 1
= x’[z+z’]
= x’

x’y’z’+x’yz’+xy’z’+xyz’
= x’(y’+y)z’ +x(y’+y)z’ Circle all 1 entries that,
= (x’+x)(y’+y)z’ taken together, form a
= z’ subcube (i.e. rectangle) of
the largest size, but
containing 2N squares (for
Dr. Tarek Abdul Hamid
all possible N).
57 Digital Engineering
Karnaugh Maps
 3 variable map - 2nd variation
yz
00 01 11 10

1 1 1 1
0
x
1 1 0 0 1

Collecting
literals into a
product Circle all 1 entries that,
gives: taken together, form a
x’ + z’ subcube (i.e. rectangle) of
the largest size, but
containing 2N squares (for
all possible N).
58 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 Case Study: 4 variable map

yz
00 01 11 10

1 0 0 1
00

01 1 1 0 0
Place function
wx values in the map
11 1 1 1 0 positions.

10
1 0 1 1

59 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 4 variable map

yz Identify 2N
00 01 11 10 subcubes by
decreasing
1 0 0 1 N=4,3,2,1,0; using
00 wraparound.

01 1 1 0 0
wx
11 1 1 1 0

10
1 0 1 1

60 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 4 variable map
Identify 2N
subcubes by
yz
decreasing
00 01 11 10 N=4,3,2,1,0; using
wraparound.
1 0 0 1
00
1 1 0 0 There are no subcubes
01
of sizes:
wx
24 =16 or 23 = 8.
11 1 1 1 0

10
1 0 1 1

61 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 4 variable map
Identify 2N
yz subcubes by
00 01 11 10 decreasing
N=4,3,2,1,0; using
1 0 0 1 wraparound.
00

01 1 1 0 0
Subcubes of size:
wx 22 =4.
11 1 1 1 0

10
1 0 1 1

62 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 4 variable map
Identify 2N
yz subcubes by
00 01 11 10 decreasing
N=4,3,2,1,0; using
1 0 0 1 wraparound.
00

01 1 1 0 0
Subcubes of size:
wx 22 =4.
11 1 1 1 0

10
1 0 1 1

63 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 4 variable map
Identify 2N
yz subcubes by
00 01 11 10 decreasing
N=4,3,2,1,0; using
1 0 0 1 wraparound.
00

01 1 1 0 0
wx
Subcubes of size:
11 1 1 1 0
21 =2.
10
1 0 1 1

64 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 4 variable map
Identify 2N
yz subcubes by
00 01 11 10 decreasing
N=4,3,2,1,0; using
wraparound.
1 0 0 1
00

01 1 1 0 0
wx
Subcubes of size:
11 1 1 1 0
21 =2.
10
1 0 1 1

65 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 4 variable map
Identify 2N
yz subcubes by
00 01 11 10 decreasing
N=4,3,2,1,0; using
1 0 0 1 wraparound.
00

01 1 1 0 0
wx No more subcubes!
11 1 1 1 0

10
1 0 1 1

66 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 4 variable map
Identify 2N
yz subcubes by
00 01 11 10 decreasing
N=4,3,2,1,0; using
1 0 0 1 wraparound.
00

01 1 1 0 0
wx
11 1 1 1 0

10
1 0 1 1 Now to identify the
prime implicants:

y’z’ + xy’ + x’z’ + wxz + wx’y

67 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 Case Study: 4 variable map

yz Identify 2N
00 01 11 10 subcubes by
decreasing
1 0 0 1 N=4,3,2,1,0; using
00 wraparound.

01 1 1 0 0
wx
11 1 1 1 0

10
1 0 1 1 Now to identify the
prime implicants:

xy’ + x’z’ + wxz + wx’y

68 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 Case Study: 4 variable map

yz Identify 2N
subcubes by
00 01 11 10
decreasing
N=4,3,2,1,0; using
1 0 0 1 wraparound.
00

01 1 1 0 0
wx
11 1 1 1 0

10
1 0 1 1 Now to identify the
prime implicants:

xy’ + x’z’ + wxz + wx’y

69 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 Case Study: 4 variable map

yz Identify 2N
subcubes by
00 01 11 10
decreasing
N=4,3,2,1,0; using
1 0 0 1 wraparound.
00

01 1 1 0 0
wx
11 1 1 1 0

10
1 0 1 1 Now to identify the
prime implicants:

xy’ + x’z’ + wxz + wx’y

70 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 Case Study: 4 variable map

yz Identify 2N
00 01 11 10 subcubes by
decreasing
N=4,3,2,1,0; using
1 0 0 1 wraparound.
00

01 1 1 0 0
wx
11 1 1 1 0

10
1 0 1 1 Now to identify the
prime implicants:

xy’ + x’z’ + wxz + wx’y

71 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 Case Study: 4 variable map

Identify 2N
yz
subcubes by
00 01 11 10 decreasing
N=4,3,2,1,0; using
1 0 0 1 wraparound.
00

01 1 1 0 0
wx
11 1 1 1 0

10
1 0 1 1 Now to identify the
prime implicants:

f(w,x,y,z) = xy’ + x’z’ + wxz + wx’y

72 Dr. Tarek Abdul Hamid Digital Engineering
Karnaugh Maps
 Using the procedure of identifying the largest possible subcubes in the
Karnaugh map first, then dealing with smaller sized subcubes, we arrive
at minimal representations of SOP (POS) expressions for the function.

 These expressions may not be unique, however.

73 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps
 Case Study: 4 variable map

yz
00 01 11 10
Previously, we had
presented this
1 0 0 1
example.
00

01 1 1 0 0
wx
11 1 1 1 0

10
1 0 1 1

f(w,x,y,z) = xy’ + x’z’Digital

+ wxz + wx’y
74 Dr. Tarek Abdul Hamid Engineering
Karnaugh Maps
 Case Study: 4 variable map

yz
00 01 11 10
Consider these
1 0 0 1 subcubes ...
00

01 1 1 0 0
wx
11 1 1 1 0

10
1 0 1 1

f(w,x,y,z) = xy’ + x’z’Digital

+ wxz + wx’y
75 Dr. Tarek Abdul Hamid Engineering
Karnaugh Maps
 Case Study: 4 variable map

yz
00 01 11 10
Now, choose the other,
alternative subcube
1 0 0 1 containing these 1-
00 cells …
…thereby, minimizing
01 1 1 0 0 the number of
wx subcubes, hence the
11 1 1 1 0 number of product
terms in the function.
10
1 0 1 1

f(w,x,y,z) = xy’ + x’z’Digital

+ wyz + wx’y
76 Dr. Tarek Abdul Hamid Engineering
Karnaugh Maps
 Case Study: 4 variable map

f(w,x,y,z) = xy’ + x’z’ + wxz + wx’y

yz
00 01 11 10
f(w,x,y,z) = xy’ + x’z’ + wyz
1 0 0 1
00
1 1 0 0 Both solutions are
01
equivalent, but the
wx second one is
11 1 1 1 0 minimal.

10
1 0 1 1

77 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps - POS

 The Karnaugh mapping technique can also be applied to prime implicate

(POS) forms.

78 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps - POS
 The Karnaugh mapping technique can also be applied to prime implicate
(POS) forms.

 Instead of grouping 1-cells, we group 0-cells.

79 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps - POS
 The Karnaugh mapping technique can also be applied to prime implicate
(POS) forms.

 Instead of grouping 1-cells, we group 0-cells.

 For each subcube of 0-cells we assign a sum expression, removing all

literals whose row/column indices are both 0 and 1, and listing the literal
itself for index label 0, or its complement for index label 1.
 Review this point with respect to algebraic representations
 Note the duality relationships

80 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps - POS
 Case Study: 4 variable map

yz
00 01 11 10

1 0 0 1
00

01 1 1 0 0
wx
11 1 1 1 0

10
1 0 1 1

81 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps - POS
 Case Study: 4 variable map

Identify 2N
yz
subcubes by
00 01 11 10 decreasing
N=4,3,2,1,0; using
1 0 0 1 wraparound.
00

01 1 1 0 0
No subcubes of
wx sizes 16, 8 or 4.
11 1 1 1 0

10
1 0 1 1

82 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps - POS
 Case Study: 4 variable map

Identify 2N
yz subcubes by
00 01 11 10 decreasing
N=4,3,2,1,0; using
1 0 0 1 wraparound.
00

01 1 1 0 0
Subcubes of size 2.
wx
11 1 1 1 0

10
1 0 1 1

83 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps - POS
 Case Study: 4 variable map

yz Identify 2N
subcubes by
00 01 11 10
decreasing
N=4,3,2,1,0; using
1 0 0 1 wraparound.
00

01 1 1 0 0
wx
11 1 1 1 0 Note the
essential 0-cells
10 that denote
1 0 1 1 essential prime
implicates.

84 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps - POS
 Case Study: 4 variable map
Identify 2N
subcubes by
yz decreasing
00 01 11 10 N=4,3,2,1,0; using
wraparound.
1 0 0 1
00

01 1 1 0 0 This subcube contains

wx 0-cells that may be
11 1 1 1 0 associated with other
subcube choices, hence
10 they are not essential
1 0 1 1 0-cells.
This choice minimizes
the number of subcubes.

85 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps - POS
 Case Study: 4 variable map

Identify 2N
yz subcubes by
00 01 11 10 decreasing
N=4,3,2,1,0; using
1 0 0 1 wraparound.
00

01 1 1 0 0
Note there are no
wx smaller subcubes.
11 1 1 1 0 The subcube choices
reflect a minimal POS
10 expression.
1 0 1 1

86 Dr. Tarek Abdul Hamid Digital Engineering

Karnaugh Maps - POS
 Case Study: 4 variable map
Identify 2N
yz subcubes by
00 01 11 10 decreasing
N=4,3,2,1,0; using
1 0 0 1 wraparound.
00

01 1 1 0 0 Note there are no

wx smaller subcubes.
11 1 1 1 0 The subcube choices
reflect a minimal POS
10 expression.
1 0 1 1

87 Dr. Tarek Abdul Hamid f(w,x,y,z) = (x+y+z’)(x’+y’+z)(w+y’+z’)

Digital Engineering