Boole

The Karnaugh Map Simplification Method

Definition of Binary Logic

Binary logic consists of binary variables and logic operations. The variables are described by letters such as A, B, C, x, y, z, etc., with each variable having two distinct possible values: 1 (true) and 0 (false). There are three basic logical operations: AND, OR, and NOT.

AND: This operation is represented by a dot or by the absence of an operator.

For example, x.y = z or xy = z is read "x AND y is equal to z".

OR: This operation is represented by a plus sign. For example, x + y = z is read

"x OR y is equal to z".

NOT: This operation is represented by a prime (sometimes by a bar).

For example, x' = z is read "not x is equal to z".

For each combination of the values x and y, there is a value ofz specified by the definition of the logical operation. Since each value in a binary system can have two distinct values, the number of possible combinations of such a sytem is equal to 2ⁿ, where n represents the number of variables that describe the system.

Truth Table

A truth table is a table of all possible combinations (minterms) of the variables showing the relation between the values that the variables may take and the result of the operation. For example, the truth table for the operations AND and OR with variables x and y are obtained by listing all possible values that the variables may have when combined in pairs. The results of each operation for each combination is then listed in a separate row.

Truth Tables of Logical Operations

Karnaugh Map Concept

The Karnaugh map (K map) allows you to simplify logic functions in a straightforward manner by providing a more useful graphic display of logic functions than truth tables.
A map has one square corresponding to each row of a truth table. Since a minterm corresponds to a row, then each minterm corresponds to one square.
A one is entered into a square if the function is true for the minterm the square represents.
A zero is entered if the function is false.
In a design process values can be directly entered into a K map. This is an alternative to using a truth table.

The K map is based on the concept of adjacent states. Two states are adjacent if they differ in the value of only one variable (variable x is in one state and x' is in the other state).
This concept is important because of the algebraic combination of two adjacent states results in the elimination of one variable.
The concept of adjacent states requires that any horizontal or vertical move from any square to any adjacent square changes only one bit in the number (Gray code) forcing the numbers in the
K map squares to be out of sequence.

K Map for functions of two variables

K Map for functions of three variables

K Map for functions of four variables

A direct consequence of the minterms repartition, based on the Gray code, in the K map is a symmetrical effect with respect to the medians of the map equivalent to a mirror effect with respect to the parallel sides of the map.

Simplification Process Using the Karnaugh Map

The basis of boolean function simplification with the K map is done by regrouping the maximum number of minterms in adjacent states. The number of adjacent states that can be combined has to be a power of 2.

One can observe that in a binary system of n variables:

A combination of 1 adjacent state represents a term made of n variables.
A combination of 2 ajdacent states represents a term of (n-1) variables.
A combination of 4 ajdacent states represents a term of (n-2) variables.
A combination of 2ⁿ ajdacent states represents a term of (n-n) variable and means that the entire map has been regrouped and that the function is Unity.

The above observation can be summarized as follows:
The combination of 2^xadjacent states, where n represents the number of variables describing the binary system and x is smaller than n, corresponds to a term formed of (n-x) variables.

To illustrate what we have seen up to know, let us take a look at a concrete application.
Assume that we want to symplify a system described by three variables whose function is the following:

F(A,B,C) = ABC' + A'BC' + AB'C + B'C'

The first step involved is the mapping of the function, where a '1' is put in states corresponding to each term of the F(A,B,C) functions.
The second step involves the regrouping of adjacent states.

The simplification processus is completed once all the minterms have been covered.

Keep in mind that the ultime goal is to minimize the final number of terms in the final expression of the function and to avoid redundancy of some terms that have already been regrouped.

In the following example we will see that the above processus is not always evident and that there may not be a unique way of simplifying a boolean expression.

As one can see from the above example, simplification may not be as straightforward as it may appear mostly when several combination options satisfy the simplification criteria are possible.

How can one be sure of getting an optimized simplification and avoid any unecessary redundancy of minterms already covered by other terms?

Let us introduce at this level two new terms:

Prime Implicant
Essential Prime Implicant

A Prime Implicant a product term obtained by combining all possible maximum numbers of adjacent squares in the K map: All the product terms in the simplified expression of a boolean function are Prime Implicants.

If a minterm in a square is covered by only one prime implicant, that prime implicant is said to be Essential .

Thus, to simplify a boolean expression using the K map one has to determine the essential prime implicants plus any other prime implicants that are needed to regroup the minterms that have not yet been regrouped.

The Karnaugh map is a very efficient and important tool in analyzing digital systems, but it has its own limitations; beyond five variables it becomes geometrically complex and looses its simplicity and efficiency.