Unit 8 - Karnaugh Mapping

Digital Electronic Systems Unit 8
Simplification of Logic Circuits using Karnaugh Mapping

A Karnaugh map provides a systematic method for simplifying a Boolean expression to
produce the simplest SOP form possible. Like a truth table, it presents all possible values of
input variables and the resulting output for each.
A Karnaugh map is composed of adjacent cells. Each cell represents one particular
combination of variable values. The total number of possible combinations of n variables is
2n. Therefore, there are 2n cells in the Karnaugh map, which is the same as the number of
rows in the corresponding truth table.
Shown below are the truth tables and the corresponding Karnaugh maps for two variables A
and B, for three variables A, B and C and for four variables A,B,C and D.
2-Variable Karnaugh Map
2-Variable Truth Table
Input
A
0
0
1
1
Input
B
0
1
0
1
B (0)
(1)
(0) A
m0
m1
(1) A
m2
m3
Minterms
m0= A.B
m1= A.B
m2= A.B
m3= A.B
Input Input Input

Minterms
A
B
C
0
0
0
m0= A.B.C
0
0
1
m1= A.B.C
0
1
0
m2= A.B.C
0
1
1
m3= A.B.C
1
0
0
m4= A.B.C
1
0
1
m5= A.B.C
1
1
0
m6= A.B.C
1
1
1
m7= A.B.C
00
m0
m1
01
m2
m3
11
m6
m7
10
m4
m5
AB

Input Input Input Input
A
B
C
D
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
Minterms
AB
m0= A.B.C .D
m1= A.B.C .D
m2= A.B.C .D
m3= A.B.C .D
m4= A.B.C .D
m5= A.B.C.D
m6= A.B.C.D
m7= A.B.C.D
m8= A.B.C.D
m9= A.B.C.D
m10= A.B.C.D
m11= A.B.C.D
m12= A.B.C.D
m13= A.B.C.D
m14= A.B.C.D
m15= A.B.C.D
CD
00
01
11
10
00
m0
m1
m3
m2
01
m4
m5
m7
m6
11
m12
m13
m15
m14
10
m8
m9
m11
m10
The cells in the Karnaugh map are arranged so that there is only a single variable change
between the minterms in adjacent cells.
For example, for a four variable function (with inputs A, B, C and D), m 0 and m1 are adjacent.
This is because the only change between A.B.C.D and A.B.C.D is D replaced by D.
In a similar fashion, m5 and m13 are adjacent A.B.C.D and A.B.C.D . Note that m12 and
m14 are also adjacent A.B.C.D and A.B.C.D .
It can be concluded that each cell in a Karnaugh map is adjacent to cells that are immediately
next to it on any of its four sides. Cells on the top row are adjacent to the corresponding cells
on the bottom row and cells in the left-most column are adjacent to the corresponding cells on
the right-most column (This is called wrap-around). However a cell is not adjacent to the
cells that diagonally touch any of its corners.
Once a Boolean expression is in the SOP form it can be plotted by placing 1s in the cells
corresponding to the minterms that make up the function.
Now draw a Karnaugh Map for the Boolean Functions of Ex. 1 to Ex. 5.
Grouping the cells

The 1s on a Karnaugh map are grouped according to the following rules by enclosing those
adjacent cells containing 1s. The goal is to maximise the size of the groups and to minimise
the number of groups.
(1) Cells may be combined in groups of 1s, 2s, 4s, 8s 16s, i.e. in groups of 2n.
(2) Cells may combine horizontally and vertically, but NOT diagonally. Each cell in
the group must be adjacent to one or more cells in that same group.
(3) As many maximum-sized groups as possible should be formed, until all cells
containing 1s are included in at least one group.
(4) Each 1 on the map should be contained in at least one group. The 1s already in a
group can be included in another group as long as the overlapping groups include
the 1s that are not common.
Now group the cells on the Karnaugh maps of Ex. 1 to Ex. 5.
Simplifying the Boolean expression
This is very easy to do once the cells have been grouped.
(1) Each group of 1s that appears in the table creates a minimised product term. Variables that
occur both uncomplemented and complemented within the group have been eliminated
for that product term.
(2) The final expression is composed of all the product groupings ORed together. This
produces the minimum SOP form.
Now write down the minimised product terms of the functions of Ex. 1 to Ex. 5.
Ex 1: Minimise the following function using Karnaugh Mapping. Verify your result using
F1 X.Y X.Y X.Y
Boolean Algebra.
F2 A.B A.B
Boolean Algebra.
F3 A.B.C A.B.C A.B.C
Boolean Algebra.
Boolean Algebra.
F4 A.B.C .D A.B.C .D A.B.C .D A.B.C .D A.B.C .D A.B.C .D
A.B.C .D A.B.C .D A.B.C .D A.B.C .D A.B.C .D
Boolean Algebra.
F5 A.B.C.D A.B.C .D A.B.C.D A.B.C.D A.B.C .D

A.B.C .D A.B.C.D A.B.C.D
Dont Care combinations

In certain cases, some combinations of the inputs can never occur, or if they do it does not
matter what function the output is. This may allow us to further minimise the Boolean
function. However, great care should be taken when using this as part of the minimisation
process. When grouping the 1s, the Xs can be treated as 1s to make a larger grouping, or as
0s if they cannot be used to advantage. Remember, the larger the grouping, the simpler the
resulting Boolean expression.
Ex 6:
F A.B.C .D A.B.C .D A.B.C .D A.B.C .D A.B.C .D
Karnaugh Map
Truth Table
Input Input Input Input Minterms
A
B
C
D
0
0
0
0
m0
0
0
0
1
m1
0
0
1
0
m2
0
0
1
1
m3
0
1
0
0
m4
0
1
0
1
m5
0
1
1
0
m6
0
1
1
1
m7
1
0
0
0
m8
1
0
0
1
m9
1
0
1
0
m10
1
0
1
1
m11
1
1
0
0
m12
1
1
0
1
m13
1
1
1
0
m14
1
1
1
1
m15
Output
F
0
0
0
0
0
0
1
0
1
0
1
0
1
0
1
0
AB
CD
00
01
11
10
00
01
11
10
B.C.D
A.D
F A.D B.C.D
Now say that this function had some dont care states denoted by X. The resulting Boolean
function can be minimised further.
Karnaugh Map
Truth Table
Input Input Input Input Minterms
A
B
C
D
0
0
0
0
m0
0
0
0
1
m1
0
0
1
0
m2
0
0
1
1
m3
0
1
0
0
m4
0
1
0
1
m5
0
1
1
0
m6
0
1
1
1
m7
1
0
0
0
m8
1
0
0
1
m9
1
0
1
0
m10
1
0
1
1
m11
1
1
0
0
m12
1
1
0
1
m13
1
1
1
0
m14
1
1
1
1
m15
Output
F
X
0
X
0
X
0
1
0
1
0
1
0
1
0
1
0
AB
CD
00
01
11
10
00
01
11
10
It can be seen that the output function has been reduced to contain just one variable. The
output function is
F D
Further Exercises
Minimise the following Boolean expressions using Karnaugh Mapping:
Ex. 7:
F A.B.C A.B.C A.B.C A.B.C
Ex. 8:
F A.B.C A.B.C A.B.C A.B.C A.B.C A.B.C
Ex. 9:
Ex. 10:
F A.B.C .D A.B.C.D A.B.C.D A.B.C.D A.B.C .D A.B.C .D

A.B.C .D A.B.C.D
F A.B.C .D A.B.C .D A.B.C .D A.B.C .D A.B.C .D A.B.C .D
A.B.C .D A.B.C .D A.B.C .D A.B.C .D A.B.C .D
Ex. 11: F A.B.C.D A.B.C.D

(i.e. they never occur) as follows
A.B.C .D
and there are six disallowed combinations
A.B.C .D, A.B.C .D, A.B.C .D, A.B.C .D, A.B.C .D and A.B.C .D.
Ex. 12:
F A.B.C .D A.B.C .D A.B.C .D A.B.C .D A.B.C .D A.B.C .D

A.B.C .D A.B.C .D A.B.C .D
Ex. 13: The function of Ex. 12, in which minterms m10 to m15 are not allowed.
Ex. 14:
F A.B.C A.B.C A.B.C A.B.C
Ex. 15: F A.C B B. B C

Ex. 16:
Ex. 17:
Ex. 18:
F A.B.C A.B.C A.B.C

F B.C .D A.B.C .D A.B.C .D A.B.C .D A.B.C .D A.B.C .D
A.B.C .D A.B.C .D A.B.C .D
F A.B A.B.C A.B.C
Ex. 19: F A B.C

Ex. 20:
F A.B.C.D A.C.D B.C.D A.B.C.D
Ex. 21:
F A.B A.B.C.D C.D B.C.D A.B.C .D
Ex. 22: F C .
Ex. 23:
[ A.B.(C D).B ( A D).B]
F B.( A.C . A.D.C . A.D.C ) ( A B C D )
Ex. 24: F A. B.D B.C.D BC.D A B C D

Ex. 25:
F A.( B D C BD ) CB ( AD. A D )
Building Functions using NAND gates only

Building an Inverter using a NAND gate
To build a NAND inverter, connect the inputs of a 2-input NAND gate together.
A. A A (Rule 7)
This may also be verified using a truth table. When both inputs are the same, that is A=B,
then the 01 and 10 conditions dont exist.
INPUT A
0
0
1
1
INPUT B
0
1
0
1
A.B
1
1
1
0
Building an AND gate using NAND gates

To build an AND gate using NAND gates, simply attach a NAND inverter to the output of a
NAND gate.
A
A.B
A.B A.B (Rule 9)
Building an OR gate using NAND gates

To build an OR gate using NAND gates, one of De Morgans Theorems must be applied in
conjunction with rule 9.
A.B A B
A.B A B
A B
A.B
A B
B
A.B
B
A B
B
A.B
B
A B
Building a NOR gate using NAND gates

To build a NOR gate using NAND gates, simply attach a NAND inverter to the output of the
OR gate built using NAND gates.
Building Functions using NOR gates only

Building an Inverter using a NOR gate
To build a NOR inverter, connect the inputs of a 2-input NOR gate together.
A A A (Rule 5)
This may also be verified using a truth table. When both inputs are the same, that is A=B,
then the 01 and 10 conditions dont exist.
INPUT A
0
0
1
1
INPUT B
0
1
0
1
A B
1
0
0
0
Building an OR gate using NOR gates

To build an OR gate using NOR gates, simply attach a NOR inverter to the output of an OR
gate.
A
A B
A B A B (Rule 9)
Building an AND gate using NOR gates

To build an AND gate using NOR gates, one of De Morgans Theorems must be applied in
conjunction with rule 9.
A B A.B
A B A.B
A.B
A B
A B
A.B
B
A.B
B
A B
B
A B
Building a NAND gate using NOR gates

To build a NAND gate using NOR gates, simply attach a NOR inverter to the output of the
AND gate built using NOR gates.
10
Ex. 26: Implement the minimised expression

(a) NAND gates only
(b) NOR gates only
Solution to Ex 26
26(a) Implement the function
F A.B C.D A.C
F A.B C.D A.C
using
using NAND gates only
To build a function using NAND gates only

Reduce the function to its minimised Sum of Products format.
Apply rule 9 A A to the whole function.
Apply De Morgans Theorem A B A.B .
The function is in its minimised sum of products format. Therefore

F A.B C .D A.C
A.B C .D A.C
A.B.C .D. A.C
B
C
D
A
26(b) Implement the function
F A.B C .D A.C
using NOR gates only
To build a function using NOR gates only

Reduce the function to its minimised Sum of Products format.
Apply rule 9 A A to each product term (minterm).
Apply De Morgans Theorem A.B A B .
The function is in its minimised sum of products format. Therefore

F A.B C.D A.C
A.B C.D A.C
A BC D AC
A B C D AC
11

A
C
F
Alternatively, the logic diagram for the minimised function can be built using AND, OR and
NOT gates and the NAND (or NOR) equivalents of each gate can be substituted. Removal of
superfluous inverter pairs will result in the same circuits as obtained above. However, the
gate substitution method takes significantly longer to implement.
Further Exercises
Ex. 27: Minimise the following Boolean Expression using Boolean algebra:
F C.
[ A.B.(C D).B (A D).B]
Implement in the minimised form (a) using NAND gates only; and (b) using NOR gates only.
F B.( A.C . A.D.C . A.D.C ) ( A B C D )
F A. B.D B.C.D BC.D A B C D

F A.( B D C BD ) CB ( AD. A D )
12

Unit 8 - Karnaugh Mapping

Uploaded by

Copyright:

Available Formats

Unit 8 - Karnaugh Mapping

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit 8 - Karnaugh Mapping

Uploaded by

Copyright:

Available Formats

Digital Electronic Systems Unit 8

Simplification of Logic Circuits using Karnaugh Mapping

2-Variable Karnaugh Map

2-Variable Truth Table

3-Variable Truth Table

3-Variable Karnaugh Map

Input Input Input

Digital Electronic Systems Unit 8

4-Variable Truth Table

4-Variable Karnaugh Map

Digital Electronic Systems Unit 8

Grouping the cells

F5 A.B.C.D A.B.C .D A.B.C.D A.B.C.D A.B.C .D

Digital Electronic Systems Unit 8

Dont Care combinations

Digital Electronic Systems Unit 8

F A.B.C A.B.C A.B.C A.B.C

F A.B.C A.B.C A.B.C A.B.C A.B.C A.B.C

F A.B.C .D A.B.C.D A.B.C.D A.B.C.D A.B.C .D A.B.C .D

Ex. 11: F A.B.C.D A.B.C.D

and there are six disallowed combinations

F A.B.C .D A.B.C .D A.B.C .D A.B.C .D A.B.C .D A.B.C .D

Digital Electronic Systems Unit 8

F A.B.C A.B.C A.B.C A.B.C

Ex. 15: F A.C B B. B C

F A.B.C A.B.C A.B.C

F A.B A.B.C A.B.C

Ex. 19: F A B.C

F A.B.C.D A.C.D B.C.D A.B.C.D

F A.B A.B.C.D C.D B.C.D A.B.C .D

[ A.B.(C D).B ( A D).B]

F B.( A.C . A.D.C . A.D.C ) ( A B C D )

Ex. 24: F A. B.D B.C.D BC.D A B C D

Digital Electronic Systems Unit 8

Building Functions using NAND gates only

Building an AND gate using NAND gates

A.B A.B (Rule 9)

Building an OR gate using NAND gates

Digital Electronic Systems Unit 8

Building a NOR gate using NAND gates

Digital Electronic Systems Unit 8

Building Functions using NOR gates only

Building an OR gate using NOR gates

Building an AND gate using NOR gates

Digital Electronic Systems Unit 8

Building a NAND gate using NOR gates

Digital Electronic Systems Unit 8

Ex. 26: Implement the minimised expression

F A.B C.D A.C

F A.B C.D A.C

using NAND gates only

To build a function using NAND gates only

The function is in its minimised sum of products format. Therefore

26(b) Implement the function

using NOR gates only

To build a function using NOR gates only

The function is in its minimised sum of products format. Therefore

Digital Electronic Systems Unit 8