K-MAP METHOD (KARNAUGH MAP)

The Karnaugh map (K-map for short), Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions. The Karnaugh map reduces the need for extensive calculations by taking advantage of humans' pattern-recognition capability, permitting the rapid identification and elimination of potential race hazards. 

In a Karnaugh map the boolean variables are transferred (generally from a truth table) and ordered according to the principles ofGray code in which only one variable changes in between squares. Once the table is generated and the output possibilities are transcribed, the data is arranged into the largest possible groups containing 2ⁿ cells (n=0,1,2,3...) and the minterm is generated through the axiom laws of boolean algebra.

Size of map

The size of the Karnaugh map with n Boolean variables is determined by 2ⁿ. The size of the group within a Karnaugh map with n Boolean variables and k number of terms in the resulting Boolean expression is determined by 2^nk. Common sized maps are of 2 variables which is a 2×2 map, 3 variables which is a 2×4 map, and 4 variables which is a 4×4 map.

2-variable k-map

3-variable k-map

4-variable k-map

Rules of Simplification

---

The Karnaugh map uses the following rules for the simplification of expressions by grouping together adjacent cells containing ones

• Groups may not include any cell containing a zero 
• Groups may be horizontal or vertical, but not diagonal. 
• Groups must contain 1, 2, 4, 8, or in general 2ⁿ cells.
  That is if n = 1, a group will contain two 1's since 2¹ = 2.
  If n = 2, a group will contain four 1's since 2² = 4. 
• Each group should be as large as possible. 
• Each cell containing a one must be in at least one group. 
• Groups may overlap. 
• Groups may wrap around the table. The leftmost cell in a row may be grouped with the rightmost cell and the top cell in a column may be grouped with the bottom cell.