2.5 KARNAUGH MAP (K-MAP)
- A Boolean expression may have many different forms.
- WiththeuseofK-map,thecomplexityofreducingexpressionbecomeseasyandBooleanexpression
obtained is simplified. - K-map also be said as pictorial form of truth table.
- K-map is alternative way of simplifying logic circuits.
- Instead of using Boolean algebra simplification techniques, you can transfer logic values from a
Boolean statement or a truth table into a Karnaugh map(k-map) - Tool for representing Boolean functions of up to six variables.
- K-maps are tables of rows and columns with entries represent 1’s or 0’s of SOP and POS
representations. - K-mapcellsarearrangedsuchthatadjacentcellscorrespondtotruthrowsthatdifferinonlyonebit position
(logical adjacency) - K-Map are often used to simplify logic problems with up to 6variables
- No. of Cells = 2n
, where n is a number of variables. - The Karnaugh map is completed by entering a ‘1’ (or ‘0’) in each of the appropriate cells.
- Within the map, adjacent cells containing 1’s (or 0’s) are grouped together in twos, fours, or eights and so on.
2.5.1 2 variables k-map
- For 2 variable k-map, there are 22 = 4 input combinations.
- If A & B are two variables then;
SOP Min terms A’B’ (m0, 00) ; A’B (m1, 01) ; AB’ (m2, 10) ; AB (m3, 11) POS Max terms A + B (M0, 00) ; A + B’ (M1, 01) ; A’ + B (M2, 10) ; A’ + B’ (M3, 11)
- Mapping of SOP Expression: B B’ B A 0 1 B B’ B A 0 1 A’0 A1 A’0 A1 1 in a cell indicates that the min term is included in Boolean expression. For e.g. if F = ∑m(0,2,3), then 1 is put in cell no. 0,2,3 as shown below. B B’ B A 0 1
Example 1: Map for a 2-input OR gate. A’0 A1 A’B’ 0 A’B 1 AB’ 2 AB 3 m0 0 m1 1 m2 2 m3 3 1 0 0 1 1 1 2 3
Example 2: Map for a 2-input EX-OR gate. F = A’B’ + AB
- Map following SOP expressions:
Example 1: F = AB B B’ B A 0 1
Example 2: F = AB’ + A’B +A’B’ A’0 A1 B B’ B A 0 1 A’0 A1 0 0 0 1 0 1 2 3 1 0 1 1 1 0 2 3
Example 3: F = m0 + m1 B B’ B A 0 1
- Map following POS expressions: A’0 A1 B B B’ A 0 1 A0 A’1 B B B’ A 0 1 A0 A’1
0 in a cell indicates that the maxterm is included in Boolean expression. For e.g. if F = Π M(0,2,3), then 0 is put in cell no. 0,2,3 as shown below. B B’ B A 0 1 A’0 A1 1 0 1 1 0 0 2 3 A+B 0 A+B’ 1 A’+B 2 A’+B’ 3 M0 0 M1 1 M2 2 M3 3 0 0 1 1 0 0 2 3
Example 1: F = M0·M1·M2 B B B’ A 0 1 A 0 A’ 1
Example 2: F = ΠM(1,3)
- Reduce following SOP expressions: A 0 A’ 1
Example 1: F = m0 + m1 B B’ B A 0 1 A’ 0 1 A 1
Example 2: F = A’B’ + AB’ F = A’ B B’ B A 0 1 A’0 A1 0 0 1 1 1 2 0 3 F = B’ 3 0 2 0 0 1 1 0 0 0 1 0 1 2 3 1 0 0 1 1 0 2 3
Example 3: F = Σ(1,3) B B’ B A 0 1 A’0 A1 0 1 1 0 0 1 2 3 F = B
Example 4: F = m2 + m3 B B’ B A 0 1 A’0 A1 0 0 0 1 1 1 2 3 F = A
Example 5: F = ∑m(0,1,2,3) B B’ B A 0 1 A’0 A1 2 3 F = 1 1 1 1 1 0 1 Example 1: F = (A+B) (A’+B) (A+B’) B B B’ A 0 1 A0 A’1 1 2 F = AB Example 2: F = M3·M1·M2 B B B’ A 0 1 A 0 A’ 1 1 2 F = A’B’ Example 4: m2 + m3 F = m2 + m3 = Π(0,1) B B B’ A 0 1 A0 A’1 F = A 0 0 1 0 1 0 0 3 1 2 1 0 1 0 0 3 0 0 3 0 3 variablesk-map Reduce following SOPexpression: For 3 variables, in SOP form there are 8 combinations asfollow; For the case of 3 variables, we form a map consisting of 2 EXAMPLE 1: F = A’B’C’ + ABC + A’BC’ For 3 variables, in SOP form there are 8 combinations asfollow; A’B’C ’ (m0, 000) A’B’C (m1, 001) A’BC’ (m2, 010) A’BC (m3, 011) AB’C’ (m4, 100) A’BC’ (m5, 101) A’B’C (m6, 110) ABC (m7, 111) we form a map consisting of 23=8 cells as shown inFigure EXAMPLE 1: F = A’B’C’ + ABC + A’BC’ F = A’B’C + ABC + A’BC’ EXAMPLE 2: F = Σ(1,6,7) F = A’B’C’ + AB EXAMPLE 3: F = A’B’C’ + ABC’ + AB’C’ + A’BC F = B’C’ + AC’ + A’BC EXAMPLE 4: F = Σm(0,1,2,4,5,6) F = B’ + C’ EXAMPLE 5: F = m3 + m4 +m6 +m7 F = BC + AC’ EXAMPLE 6: F = Σm(3,7,1,6,0,2,5,4)
(Pending)
(Pending – Post MCQ)