Page 43 - Computer science 868 Class 12
P. 43

1.13 FORMATION OF GROUPS BY OVERLAPPING
                 One or more minterms or maxterms may be included in multiple groups in a K-map. This is due to the unavailability
                 of other consecutive terms or with the intent of forming the maximum combinations of the groups. For making the
                 maximum combinations of the groups, they can be overlapped with other groups. A few examples are given below to
                 support this fact.

                 Example 5: Minimise a Boolean expression F(A, B, C) = π(0, 1, 2, 3, 4, 5)
                 Solution: First, draw a POS K-map with A at the left and B, C at the top.   Quad 1: M , M , M , M 3
                                                                                                        2
                                                                                                    1
                                                                                                 0
                                                                                        M  = A+B+C
                                                                                          0
                 Then fill 0 in the grids mentioned and 1 in the remaining boxes.       M  = A+B+C'
                                                                                          1
                                          B+C    B+C'    B'+C'    B'+C                  M  = A+B'+C
                                                                                          2
                                                                                          3
                                    A    0 0     0 1     0 3      0 2                   M  = A+B'+C'
                                                                                        Literals B and C are in both forms.
                                   A'    0 4     0 5     1 7      1 6                   Hence, M .M .M .M  = A
                                                                                                   1
                                                                                                         3
                                                                                                      2
                                                                                                0
                 A quad can be formed either with M +M +M +M  or with M +M +M +M .      Quad 2: M , M , M , M 5
                                                                                                    1
                                                                                                 0
                                                                                                        4
                                                   0
                                                       1
                                                          4
                                                                                2
                                                                                    3
                                                                             1
                                                              5
                                                                         0
                 Then M +M  can form a pair in the former case and M +M  can form a pair   M  = A+B+C
                                                                                          0
                           3
                        2
                                                                      5
                                                                  4
                 in  later  case.  But  a  pair  eliminates  only  1  variable  and  a  quad  removes  2   M  = A+B+C'
                                                                                          1
                                                                                        M  = A'+B+C
                                                                                          4
                 variables. The purpose of minimisation is to eliminate maximum variables,   M  = A'+B+C'
                                                                                          5
                 hence overlapping quad is considered and not pairs.                    Literals A and C are in both forms.
                                                                                        Hence, M .M .M .M  = B
                                                                                                   1
                                                                                                      4
                                                                                                         5
                                                                                                0
                 Example 6: Given F(P, Q, R, S) = Σ(4, 5, 8, 9, 10, 11, 12, 13, 14, 15)       Thus, the reduced POS expression = A.B
                 Reduce the above expression by using a four-variable Karnaugh’s Map.
                 Solution:
                                         R'.S'    R'.S    R.S     R.S'     Octet 1: m +m +m +m +m +m +m +m  = P
                                                                                                               15
                                                                                                           14
                                                                                          10
                                                                                                   12
                                                                                               11
                                                                                                       13
                                                                                       9
                                                                                    8
                                  P'.Q'  0 0     0 1     0 3      0 2      Quad 1: m +m +m +m  = Q.R'
                                                                                    4
                                                                                       5
                                                                                          12
                                                                                              13
                                  P'.Q   1 4     1 5     0 7      0 6      [Here overlapping  quad  m +m +m +m  is  preferred
                                                                                                            13
                                                                                                        12
                                                                                                     5
                                                                                                  4
                                   P.Q    1    12   1    13   1    15   1    14  over pair m +m  as it eliminates 2 variables.]
                                                                                        5
                                                                                     4
                                   P.Q'  1 8     1 9      1    11   1    10  Thus, the reduced SOP expression: P+Q.R'
                     1.14 GROUPING BY MAP ROLLING
                 If we fold a K-map horizontally or vertically, then the edges intersect and a formation of a pair, a quad or an octet is
                 made. A few formations of the pairs, the quads and the octets are illustrated below.
                                                                                0       1        3       2
                                        0       1       3       2             4         5        7       6
                                        4       5       7       6              12      13       15   14
                                                                                8       9       11      10
                                        0       1       3       2               0       1        3       2
                                     4          5       7       6               4       5        7       6
                                       12      13      15    14                12      13       15      14
                                        8       9      11      10               8       9       11      10
                                                                                                                        41
                                                                                                      Boolean Algebra   41
   38   39   40   41   42   43   44   45   46   47   48