Page 40 - Computer science 868 Class 12
P. 40

1.12 INTRODUCTION TO KARNAUGH MAPS
              We have already learnt how to simplify a Boolean expression using Boolean laws. A Boolean expression can also be
              simplified graphically using the K-map method. The K-map (Karnaugh map) is a graphical method of simplifying a
                                                                  n
              Boolean expression in which a rectangle or square grid of 2  (where n represents the number of Boolean variables that
              constitute the expression) is drawn in a definite pattern.

              K-map is a representation of the information derived from a truth table of a Boolean function in a rectangular array of
              cells.

              In this class, we shall discuss a K-map of 3 and 4 variables. As any Boolean expression is represented in two forms
              namely SOP (Sum of Product) and POS (Product of Sum), the K-map also has two forms based on the type of expression.
              The individual grid of the map is filled with 0 or 1 and accordingly, grouping is made.
              The following steps are taken to minimise a Boolean expression using a Karnaugh Map.


              1.12.1 Drawing a K-map
              Considering a Boolean expression of three variables F(A, B, C), two rightmost terms B and C are written at the top and
              the leftmost A is written to the left in such a way that at a time only one variable changes its sign. Each box represents
              a minterm (for SOP) and a maxterm (for POS). The number associated with each box is its corresponding cardinal
                            3
              number. Total 2 , i.e., 8 boxes are used to represent the terms.
              The three-variable SOP K-map both in algebraic form and in binary from or grey code is illustrated below.

                              B'.C'   B'.C    B.C     B.C'           B.C
                        A'   A'.B'.C'  A'.B'.C  A'.B.C  A'.B.C'    A       0 0     0 1     1 1     10
                               0       1       3       2
                        A    A.B'.C'  A.B'.C  A.B.C  A.B.C'        0       0       1        3       2
                               4       5       7       6           1       4       5        7       6
              The three-variable POS K-map both in algebraic and binary forms is illustrated below.

                              B+C     B+C'    B'+C'    B'+C          B+C
                        A    A+B+C   A+B+C'  A+B'+C'  A+B'+C       A       0 0     0 1     1 1     1 0
                               0       1        3       2
                        A'   A'+B+C  A'+B+C'  A'+B'+C'  A'+B'+C    0       0       1        3       2
                               4       5        7       6          1       4       5        7       6
                                                                                  4
              Similarly, a four-variable truth table of F(A, B, C, D) can be represented with 2 , i.e., 16 grids cell. Considering a Boolean
              expression F(A, B, C, D), the first two variables are written to the left, while the last two variables are written at the
              top in such a way that a single variable is either complemented or uncomplemented. The minterms or maxterms along
              with their cardinal numbers are shown in the diagram below.

              The four-variable SOP K-map in algebraic and grey code form is illustrated below.
                              C'.D'    C'.D      C.D     C.D'
                       A'.B' A'.B'.C'.D' A'.B'.C'.D A'.B'.C.D A'.B'.C.D'
                               0        1        3        2             C.D
                       A'.B  A'.B.C'.D' A'.B.C'.D  A'.B.C.D  A'.B.C.D'  A.B   0 0     0 1     1 1     1 0
                               4        5        7        6           0 0     0        1       3       2
                       A.B  A.B.C'.D'  A.B.C'.D  A.B.C.D  A.B.C.D'
                               12       13       15       14          0 1     4        5       7       6
                       A.B'  A.B'.C'.D' A.B'.C'.D  A.B'.C.D  A.B'.C.D'  1 1   12      13      15      14
                               8        9        11       10          1 0     8        9      11      10



                3838  Touchpad Computer Science-XII
   35   36   37   38   39   40   41   42   43   44   45