DLD Lecture No 15 Prime and Essential Implicants, Five Variable Map.pptx

4r5

1. Digital Logic and Design Lecture No 15 : Prime and Essential Prime Implicants Five Variable Karnaugh Map 1

2. Another Example Four adjacent corners can be combined to form the two literal term x ’ z ’ . Four adjacent squares can be combined to form the two literal term x ’ y. The remaining 1 is combined with a single adjacent 1 to obtain the three literal term w ’ y ’ z ’ . F = x ’ z ’ + x ’ y + w ’ y ’ z ’ 2

3. Another Example F=A ’ BC ’ +A ’ CD ’ +ABC+AB ’ C ’ D ’ +ABC ’ +AB ’ C F=BC ’ + CD ’ + AC+ AD ’ AB 1 1 00 01 00 01 CD 1 1 11 10 1 1 1 11 10 1 1 1 1 3

4. Another Example F(A,B,C,D) =  m(0,3,5,8,9,10,11,12,13,14,15 ) F = A + B’C’D’ + BC’D + B’CD 4

5. Working With Maxterms At times, we may be required to work with maxterms. The previous process actually worked with minterms. Remember that the numbers used for minterms are the opposites of the numbers used for maxterms: F(w, x, y, z) = ∑(0, 1, 2, 8, 9, 10, 11), uses minterms F(w, x, y, z) = ∏(3, 4, 5, 6, 7, 12, 13, 14, 15), uses maxterms If you are given minterms, fill in 1 ’ s for the minterms and then fill the remaining cells with 0 ’ s If you are given maxterms, fill in 0 ’ s for the maxterms and then fill the remaining cells with 1 ’ s For SOP simplification, solve the map for the 1 ’ s For POS simplification, solve the map for the 0 ’ s to get complemented function. Taking the complement of this complemented function we obtain function in POS form 5

6. Example 3-5 F( w,x,y,z ) =  ( 0,1,2,4,5,6,8,9,12,13,14) Sol: 1 is marked in each minterm that represents the function Find the possible adjacent squares and mark them with rectangles We combine eight adjacent squares to get a single literal term y’ The top two 1 ’ s on the right are combined with the top two 1,son the left to give the term w ’ z ’ We combine the single square left on right with three adjecent squares that are already used to give the term xz ’ The logical sum of these three terms gives: F = y ’ + w ’ z ’ + xz ’ Correction in the book: Add 1 in the square 6

7. Example 3-6 F = A ’ B ’ C ’ +B ’ CD ’ +A ’ BCD ’ +AB ’ C ’ Sol: Each of three literal term in map is represented by two squares and four literal term in map is represented by one square We combine the 1’s in the four corners to give the term B’D’ The two left hand 1 ’ s in the top row are combined with two 1 ’ s in the bottom row to give the term B ’ C ’ The remaining 1 ’ s may be combined in the two-square area to give the term A ’ CD ’ The logical sum of these three terms gives: F = B’D’ + B ’ C ’ + A ’ CD ’ 7

8. Overview of Karnaugh Map Karnaugh Map? Made up of squares Each square represent one minterm The variables in squares change in gray code Each variable covers an area in the squares Grouping of Squares Rules? Every cell containing a 1 must be included at least once. The largest possible “ power of 2 rectangle ” must be enclosed. The 1 ’ s must be enclosed in the smallest possible number of rectangles Mapping of Functions into the Karnaugh Map Function expressed in sum of products or sum of minterms Function expressed in product of sums or product of maxterms? Convert it to sum of minterms or sum of products form 8

9. Five Variable Map 9

10. Five-Variable Map A five-variable map holds thirty-two minterms for five variables. We use two four variable map with one of the variables distinguishing between the two. Each square in the first map is adjacent to the corresponding square in the second map (i.e. 4 and 20 are adjacent). It is just like placing one map on the top of the other. 10

11. 5-Variable Map Patterns 11

12. 5-Variable Map Patterns The number of adjacent squares that may be combined always represent a number that is a power of 2 such as 1, 2, 4, 8, 16, and 32. One square represents one minterm with five literals. Two adjacent squares represents a term of four literals. Four adjacent squares represents a term of three literals. Eight adjacent squares represents a term of two literals. Sixteen adjacent squares represents a term of one literal. Thirty-two adjacent squares represents the entire map and produces a function that is always equal to 1. 12

13. Alternative Five Variable Map 13

14. Minimization Example (5-Variable Map) Example 3-7 Simplify the Boolean function F(V,W,X,Y,Z) = Σ (0,2,4,6,9,13,21,23,25,29,31) F = v ’ w ’ z ’ + wy ’ z + vxz v’w’z’ wy’z vxz 14

15. Your Turn Simplify the following function in Sum of Products form 15

16. Product of Sums Minimization By definition, all the squares in a map that are not marked with a 1 represent the complement of the function. If we mark the empty squares with 0s and then combine the zeros into valid adjacent squares, we obtain a simplified expression of the complement of the function i.e., F ’ The complement of F’ [as (F’)’ = F] by DeMorgan ’ s theorem (by taking the dual and complementing each literal, section 2-4), gives us the product of sums form 16

17. POS Minimization Example F ’ = w ’ x + yz + xz + xy F = (F ’ ) ’ =( w ’ x + yz + xz + xy ) ’ = ( w + x ’ )( y ’ + z ’ )( x ’ + z ’ )( x ’ + y ’ ) w’x xz yz xy 17

18. Example 3-8 F = Σ (0,1,2,5,8,9,10) Simplify the function in S um Of Products (SOP) Product Of Sums (POS) Sol: The squares marked with 1 ’ s represents minterms and are combined to form simplified function in sum of products (SOP). F=B ’ D ’ +B ’ C ’ +A ’ C ’ D If the squares marked with 0’s are are combined we obtain the simplified complemented function F’=AB+CD+BD’ Applying DeMorgan ’ s theorem we obtain the simplified function in product of sum form (POS) F=(A ’ +B ’ )(C ’ +D ’ )(B ’ +D) 18

19. SOP Gate Implementation F 1 = B ’ D ’ + B ’ C ’ + A ’ C ’ D 19

20. POS Gate Implementation F 2 = (A ’ + B ’ )(C ’ + D ’ )(B ’ + D) 20

21. SOP and POS Gate Implementation 21

22. Function Comparison 22

23. Working With Maxterms At times, we may be required to work with maxterms. The previous process actually worked with minterms. Remember that the numbers used for minterms are the opposites of the numbers used for maxterms: F(w, x, y, z) = ∑(0, 1, 2, 8, 9, 10, 11), uses minterms F(w, x, y, z) = ∏(3, 4, 5, 6, 7, 12, 13, 14, 15), uses maxterms If you are given minterms, fill in 1 ’ s for the minterms and then fill the remaining cells with 0 ’ s If you are given maxterms, fill in 0 ’ s for the maxterms and then fill the remaining cells with 1 ’ s For SOP simplification, solve the map for the 1 ’ s For POS simplification, solve the map for the 0 ’ s to get complemented function. Taking the complement of this complemented function we obtain function in POS form 23

24. The End 24