(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: