Digital Teaching AidKarnaugh Mapping - Lesson 4Lesson Plan*(introduction...)*IntroductionKarnaugh mapTruth table to Karnaugh map**Pairs, Quads, and Octets**Overlapping and Rolling

**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 mapGroups can overlap to get a simpler equation:

_{}Rolling the map

Ex:

Fig. 4-11: Karnaugh mapInstead 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:_{Simplification Procedure for Karnaugh mapsPair Reduction Rule : Remove the variable which changes its state from complemented to uncomplemented or vice versa.Pair removes one variable only.Quad Reduction Rule : Remove the two variables which change their states.A quad removes two variables.Octet Reduction Rule : Remove the three variables which changes their state.Octet removes three variables.Map Rolling : Map rolling means roll the map considering the map as if its left edges are touching the right edges and top edges are touching bottom edges.While marking the pairs quads and octet, map must be rolled.Overlapping Groups : Overlapping means same 1 can be encircled more than once. Overlapping always leads to simpler expressions.Redundant Group : It is a group whose all 1's are overlapped by other groups. Redundant groups must be removed. Removal of redundant group leads to much simpler expression. Ex. 1 : Represent the following boolean expression in a K-map and simplify.F = x'yz + x'yz' + xy'z' + xy'zSolution :The K-map is as follows :Hence the simplified expression isF = x'y + xy'Ex. 2 :Simplify the following boolean expression using K-map.F = a'bc + ab'c' + abc + abc'Solution :The K-map is as follows :Hence the simplified expression isF = bc + ac'}

## No comments:

## Post a Comment