Topic 2 Subtopic 4: Karnaugh Map

Karnaugh map is a two-dimensional truth-table. Unlike ordinary (i.e., one-dimensional) truth tables, however, certain logical network simplifications can be easily recognized from a Karnaugh map. The Karnaugh map or K-Map provides a simple and straight-forward method of minimizing Boolean expression.

Here are the examples of two ,three,and four variables K-Map.

 




In this case, the four input variables can be combined in 16 different ways, so the truth table has 16 rows, and the K-Map has 16 positions. Therefore, the K-Map is arranged in a 4x4 grid.

The diagram below illustrates the correspondence between the Karnaugh map and the truth table for the general case of a two variable problem.


There are two input values, A and B, and four minterms, a,b,c,d, which represent all of the possible input combinations for the function.

Example:



The values around the edge of the map can be thought of as coordinates. So as an example, the square on the top right hand corner of the map in the above diagram has coordinates A=1 and B=0. This square corresponds to the row in the truth table where A=1 and B=0 and F=1.
*Note that the value in the F column represents a particular function to which the Karnaugh map corresponds.

   

      Rules for K-Maps

1. Each cell with a 1 must be included in at least one group.

2. Try to form the largest possible groups.

3. Try to end up with as few groups as possible.

4. Groups may be in sizes that are powers of 2: 

     2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 16, …

5. Groups may be square or rectangular only (including wraparound at the grid edges). 

     No diagonals or zig-zags can be used to form a group.

6. The larger a group is, the more redundant inputs there are:

   i. A group of 1 has no redundant inputs.

   ii. A group of 2 has 1 redundant input.

   iii. A group of 4 has 2 redundant inputs.

   iv. A group of 8 has 3 redundant inputs.

   v. A group of 16 has 4 redundant inputs.

Addition:

•  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.
  
• There should be as few groups as possible, as long as this does not contradict any of the previous rules. 

Building Logic Equation

A circuit built with several gates,that is 3 input and 3 output.



L1 will light up if at least one switch is on,L2 will light up if at least two switches are on and L3 will light up if all three switches are on.

From the truth table,

L1=S1+S2+S3
L3=S1.S2.S3

while L2 can be deriving that L2 is true if at least 2 switches are true.It is in sum-of-products form.
L2=(S1'.S2.S3)+（S1.S2'.S3）+(S1.S2.S3')+(S1.S2.S3) or represent into product-of-sums,
L2=((S1'.S2.S3)+(S1.S2'.S3)+(S1.S2.S3')+(S1.S2.S3))'

Goh Menning              B031210149