Cover Image
close this bookDigital Teaching Aid (DED Philippinen, 86 p.)
close this folderKarnaugh Mapping - Lesson 4
Open this folder and view contentsLesson Plan
View the documentWorksheet No. 4

(introduction...)

Titel: Karnaugh Mapping

Objectives:

- Able to derive Karnaugh maps from a given truth table
- Know how to simplify Karnaugh maps

Time

Method

Topic

Way

Remark



* Review Lesson 3





* Introduction






- Karnaugh map





* Karnaugh mapping






- Truth table to Karnaugh map






- Two variable map






- Three variable map






- Four variable map






- Pairs, Quads, and Octets






- Overlapping groups






- Rolling the map





* Review exercise

WS

Worksheet No. 4


S: Speech
D Discussion
Q/A: Question/Answer
E: Exercise


B: Boardscript
P: Picture
Ex: Example
HO: Hands-On
WS: Worksheet
HT: Hand-Out


Introduction

Karnaugh Mapping

Simplify a Boolean equation

Ex:



is common in each term


Again factor to get


Simplify


Simplify



Karnaugh map

As you see, Boolean algebra can be used to create simpler circuits. But if you not quite familiar with Boolean theorems it is difficult to find the best simplification. Therefore Karnaugh mapping is the better alternative for simplification.

Truth table to Karnaugh map

The starting point for digital circuit design is usually the truth table which gives us the following information:

Under which input condition occurs a certain output condition.

Two variable map

Ex:


Fig. 4-1: Two variable Karnaugh map

The truth table outputs are translated into the Karnaugh map. Each position in the map represents a certain fundamental product.

Three variable map

Ex:


Fig. 4-2: Three variable Karnaugh map

Four variable map

Many digital systems process 4 bit numbers. For this reason, logic circuits are often designed to handle 4 input variables.

Ex:

(see Fig. 4-3)


Fig. 4-3: Four variable Karnaugh map

Pairs, Quads, and Octets

Pairs


Fig. 4-4: Four variable simplification

As you see in Fig. 4-4, only one variable goes from uncomplement to complement. Whenever this happens, you can eliminate the variable that changes form.

Proof:



X = A B C

Ex:


Fig. 4-5: Pairs

Whenever you see a pair first encircle it and then simplify to get the simplified Boolean expression:

Quad


Fig. 4-6: Quad

Quad: A group of 4 one's that are horizontally or vertically adjacent. End to end or in form of a square.

A quad eliminates two variables and their complements.

Proof:

(two pairs)


X = A B (C + C)



X = A B


Encircle the quad and step through the different one's in the quad and determine which two variables go from complement to uncomplement (or vs), these are the variables that drop out.

Ex:


Fig. 4-7: Quad

The variables B and D can be eliminated. So we get the following equation:

X = A C

Octet


Fig. 4-8: Octet

An octet eliminates three variables and their complements.

Proof:

(two quads)


X = A (C + C)



X = A


Karnaugh Simplifications

Process:

1. Draw the Karnaugh map
2. Look for octets and encircle them.
3. Look for quads and encircle them.
4. Look for pairs and encircle them.
5. Simplify and write down the equation.

Ex:


Fig. 4-9: Karnaugh map

Overlapping and Rolling

Overlapping groups

Ex:


Fig. 4-10: Karnaugh map

Groups can overlap to get a simpler equation:

Rolling the map

Ex:


Fig. 4-11: Karnaugh map

Instead of encircling two pairs:

We can roll the map and encircle a quad:


HO: Simplify the following map.

Solution:


HO: Simplify the following map.

Solution:

Worksheet No. 4

No. 1 Simplify the following Karnaugh maps and write down the Boolean equation for every map.


0

0

1

0

1

1

0

0


1

1

0

0

1

0

1

1


1

0

0

0

0

0

1

0


0

1

0

0

1

0

1

1

1

0

0

1

0

1

1

0


1

1

0

1

0

0

1

1

0

0

0

1

1

1

0

1

No. 2 Translate each output (v, w, x, y, z) into a Karnaugh map, do the simplification and write down the Boolean equation.

A

B

C

D

v

w

x

y

z

0

0

0

0

1

1

0

1

0

0

0

0

1

0

1

0

1

1

0

0

1

0

0

1

0

0

0

0

0

1

1

0

0

0

0

1

0

1

0

0

0

0

1

0

1

0

1

0

1

1

0

1

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

1

0

1

1

0

1

0

0

0

0

1

0

0

1

1

0

0

1

1

1

1

1

0

1

0

1

0

0

1

0

1

0

1

0

1

1

1

1

1

1

1

1

1

0

0

0

0

0

0

1

1

1

0

1

1

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

1

0

1

0

0

0