Sunday, 21 October 2012

Karnaugh Map by Eliza Joanne


The Karnaugh map or known as K-map is a simple method of minimizing Boolean expressions. K-map is a representation of the truth table in a grid-like manner.

Grouping 1’s in Karnaugh Map
  • The groups only contain 1 s, no zeros allowed.
  • There can only be adjacent grouping of cells only, no diagonal grouping.
  • The number of groups can only be a power of 2(2n, where n = 0, 1, 2, 3, 4,…).
  • The groups must be large as possible.
  • All 1 must belong to a group.
  • Overlapping of groups are allowed.
  • Wrap around is allowed.
  • There must be a few as possible groups.


In this case four variables are used, therefore the K-map has 16 outputs.

Sum-of-products (SOP)

Example 1: 
Let X = (A’B’C’D’) + (A’B’CD’) + (ABC’D’) + (ABC’D) + (AB’C’D’) + (AB’C’D)
     
                   
                  
Note
The labelling of 00, 01, 10, 11 is not in order. In the K-map 11 must be written before 10.

Following the rules as above:
Looking at the big box (4x4), AC’ does not change and from the wrap around A’B’D’ does not change. Hence, the simplification is AC’ + A’B’D’.

Example 2:
Let G = (A’B’C’D’) + (A’BC’D’) + (ABC’D’) + (AB’C’D’) + (AB’C’D)

                         
Following the rules as above:
Looking at the long box (1x4), C’D’ does not change and from the 2x2 box, AB’ does not change. Hence, the simplification is C’D’ + AB’C’.

 Product-of-sums (POS)

In a similar way as SOP, POS is simplified but using 0 instead of 1.
The rules of grouping 0 are the same as grouping 1. The changes are in grouping 0, no 1 can be included.

Example 1:
Let X = (A’B’C’D’) + (A’B’CD’) + (ABC’D’) + (ABC’D) + (AB’C’D’) + (AB’C’D)

Following the rules as above:
Looking at the 4x4 yellow box, AC does not change, from the green 4x4 box, A’D does not change and from the 1x4 box A’B’ does not change. Hence, the simplification is (A’+C’) x (A+D’) x (A+B).

Example 2:


Let H Let G = (A’B’C’D’) + (A’BC’D’) + (ABC’D’) + (AB’C’D’) + (AB’C’D)
                                                         

                                  

Following the rules as above:
Looking at the yellow 4x2 box, C does not change, from the green 4x4 box, BD does not change, and from the blue 4x4 box, A’D does not change. Hence, the simplification is C’ x (B’+D’) x (A+D’).
* With the known simplification the expression above can be found.





1 comment:

  1. thanks alot!! now I get the Karnaugh Map even better... no longer need to crack my head trying to understand it.

    ReplyDelete