KARNAUGH MAP METHOD–2 Variable K-map and 3 Variable K-map

BOOLEAN EXPRESSION SIMPLIFICATION

SIMPLIFICATION METHODS

1.USING BOOLEAN THEOREMS

2. KARNAUGH MAP METHOD

3.QUINE Mc CLUSKY METHOD

NEED FOR SIMPLIFICATION

F = x’y’z +x’yz +xy’ ------- Eqn 1

= x’z (y + y’) + xy’

= x’z +xy’ ------- Eqn 2

Compare Eqn 1 and Eqn 2

Eqn 1 requires two 3 input AND gates, one 2 input AND gate and an OR gate with 3 inputs

Eqn 2 requires two 2 input AND gates and an OR gate with 2 inputs

Simplified expression requires lesser number of gates and lesser number of inputs. It is preferable since it requires less wires and less components

SIMPLIFICATION USING BOOLEAN THEOREMS

DISADVANTAGES

1.Time consuming process

2.Need better understanding of laws and theorems

3.Lack of specific rules to predict each succeeding step in reduction process.

KARNAUGH MAP METHOD

• Karnaugh Map, invented by Maurice Karnaugh of Bell Labs in 1953, also known as K-map, is a diagrammatic method for logic minimization

• Pictorial form of truth table showing the relationship between inputs & outputs

• More efficient than Boolean algebra

• K-map is a diagram made up of squares. Each square represents a minterm or maxterm of the logic function

• K-map identifies the group of minterms which contains redundant variables of the form x + x’ = 1 and then it can be eliminated.

TWO - VARIABLE K-MAP

• For a 2-variable function, there are 4 minterms.

Therefore, the K-map for a 2- variable function has 4 squares:

In each square, the minterm is either 0 or 1

depending on the value of the function at that r

Construction of 2-variable K-map

• To construct a K-map for a 2-variable function, a logic 1 is entered into the square where the corresponding minterm exists. A logic 0 is entered otherwise (or the square is left blank)

• (ex) f = A’B + AB’

• f is true when AB = 01 or 10

• f = Σ(1, 2)

Construction of K-map from Truth Table

• A K-map can be created directly from a truth table

• Each square of the K-map corresponds to one row of the truth table

• A logic 1 is entered when the function is 1

• A logic 0 is entered when the function is 0

For example

3-variable K-map

• A 3-variable logic function has 8 minterms and its truth table has 8 rows

• Hence, a 3-variable K-map has 8 squares

Logic Minimization with K-Map

• Consider a logic function with m2 and m6

• i.e. f = Σ(2, 6)

• m2 is a’bc’ and m6 is abc’

• f = m2 + m6 = a’bc’ + abc’ = bc’(a’ + a) = bc’

• The 2 minterms have a common factor bc’ In the K-map, if we group these 2 adjacent minterms, we can reduce 1 variable

TRUTH TABLE TO MAP

Example of looping pairs of adjacent 1s PAIRS

Example of looping pairs of adjacent 1s QUADS

Example of looping pairs of adjacent 1s OCTETS

PROCEDURE

• Construct the K map, place 1s as indicated in the truth table.

• Check for octets (group of eight 1s)

• If octets not available check for quads (four adjacent 1s)

• Loop 1s that are adjacent to only one other 1 and encircle such pairs.

• Loop 1s that are not adjacent to any other 1s.

• 1s which are already present in a group can be included in new group to group the other 1s.

• Form the sum of all product terms generated by each loop.