**K-Maps**

It is always possible to write down a correct logic expression simply by forming an OR of the AND of all input variables for which the output is true (Q=1). However, for an arbitrary truth table, such a procedure could produce a very lengthy and cumbersome expression that might be needlessly inefficient to implement with gates.

There are several methods for simplification of Boolean logic expressions. The process usually called “logic minimization” and the goal is to form a result that is efficient. Two methods we will discuss are algebraic minimization and karnaugh maps. For every complicated problem, the former method can be done using simple analysis programs. Karnaugh maps are also limited to problems up to 4 binary inputs.

Example of simple arbitrary truth table:

A | B | OUTPUT |

0 | 0 | 1 |

0 | 1 | 1 |

1 | 0 | 0 |

1 | 1 | 1 |

**There are two overall strategies:**

1.Write down an expression directly from the truth table.Use Boolean algebra ,if desired to simplify.

2.Use karnaugh mapping.This is only applicable if there are inputs<=4.

In our example above,we can use two different ways of writing down a result directly from truth table.We can write down all TRUE terms and OR the result.This gives

Q=A’B’+A’B+AB

While correct, without further simplification this expression would involve 3-2 input AND gates,2 INVERTERS, and 1-3 input OR gate.

Alternatively,one can write an expression for all of the FALSE states of the truth table.This is simpler in this case:

Q’=AB’->Q=(AB’)’=A’+B

Where the step results form eq3.Presumably, the two expressions can be found to be equivalent to some algebra. Certainly, the 2 nd is simpler and involves only an inverter and one 2-input OR gate.

Finally, one can try a K-map solution. The first step is to write out the truth table in the form below, with the input states the headings of the rows and columns of the table, and corresponding outputs, as shown below

** K-map of truth table:**

A\B | 0 | 1 |

0 | 1 | 1 |

1 | 0 | 1 |

The steps/rules are as follows:

1.Form the 2-dimensional truth table as above.Combine 2 inputs in a “gray code” way-see 2nd example below.

2.Form groups of 1’s and cricle them;the groups are rectangular and must have sides of length 2^n * 2^,where m,n are integers 0,1,2.

3.The groups can overlap

4.Write down an expression of the inputs of each group.

5.OR together these expressions,that’s it.

6.Groups can wrap accross the table edges.

7.As before,one can alternatively form groups of 0’s to give solution for Q’.

8.The bigger the groups one can form groups,the better (simpler)the result.

9.There are usually many alternative solutions,all equivalent,some bettter than others depending upon what one is trying to optimize.

Here is one way of doing it:

A\B | 0 | 1 |

0 | 1 | 1 |

1 | 0 | 1 |

The two groups we have drawn are A’ and B.So the solution is:

Q=A’+B

## K-map Example 2

Let’s use this is to determine which 3-bit numbers are prime.We assume that 0,1,2 are not primes.We will let our input number have digits aa2a1a0.Here is the truth table.

Here is the corresponding K-map solution.

Note that where two inputs are combined in a row or column that their progression follows gray code,that is only one bit changes at a time.The solution shown above is:

Q=a1a0+a2a0=a0(a1+a2)

**3-digit prime finder**

Decimal | a2 | a1 | a0 | Q |

0 | 0 | 0 | 0 | 0 |

1 | 0 | 0 | 1 | 0 |

2 | 0 | 1 | 0 | 0 |

3 | 0 | 1 | 1 | 1 |

4 | 1 | 0 | 0 | 0 |

5 | 1 | 0 | 1 | 1 |

6 | 1 | 1 | 0 | 0 |

7 | 1 | 1 | 1 | 1 |

K-map of above truth table:

a2\a1a0 | 00 | 01 | 10 | 11 |

0 | 0 | 0 | 1 | 0 |

1 | 0 | 1 | 1 | 0 |

## K-map Example 3: Full Adder

In this example we will outline how to build a digital full adder.It is called “full” because it will include a “carry-in” bit and a “carry-out” bit.The carry bits will allow a succession of 1-bit full adders to be used to add binary numbers of arbitrary length.(A half adder includes only one carry bit.)

The scheme for the full adder is outlined in above picture.Imagine that we are adding two n-bit binary numbers.Let the inputs are A,B,the carry is C.The truth table for full adder is given below:

C | A | B | SUM | COUNT |

0 | 0 | 0 | 0 | 0 |

0 | 0 | 1 | 1 | 0 |

0 | 1 | 0 | 1 | 0 |

0 | 1 | 1 | 0 | 1 |

1 | 0 | 0 | 1 | 0 |

1 | 0 | 1 | 0 | 1 |

1 | 1 | 0 | 0 | 1 |

1 | 1 | 1 | 1 | 1 |

**K-map for full adder:**

C\AB | 00 | 01 | 11 | 10 |

0 | 0 | 0 | 1 | 0 |

1 | 0 | 1 | 1 | 1 |