Logic Minimization and Karnaugh Maps |K maps

0
27
vlsi

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:

ABOUTPUT
001
011
100
111

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\B01
011
101

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\B01
011
101

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

Decimala2a1a0Q
00000
10010
20100
30111
41000
51011
61100
71111

K-map of above truth table:

a2\a1a000011011
00010
10110

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:

CABSUMCOUNT
00000
00110
01010
01101
10010
10101
11001
11111

K-map for full adder:

C\AB00011110
00010
10111