What is it and what is Karnaugh’s map for?

Question

The question is just this: What is and what is this map of Karnaugh?

I do not want to know everything about it, a short definition and a small example is enough.

Answer 1

It is difficult to summarize much because there are many concepts that need to be mastered to properly understand Karnaugh’s map. Below I will try to simplify to the maximum without leaving important details out.

Summary

• The Karnaugh map is a systematic method for simplifying logical expressions;
• Can be used to simplify logic circuits, abbreviate boolean expressions, convert expressions of different formats, among others;
• It is directly related to the Truth Table so knowing it is trivial;
• Grouping 1 on the map will generate an output in the sum format of products;
• Grouping 0 on the map will generate an output in the sum product format;
• Always choose to group the most present value in the map;
• Groups should always be formed in power size of 2, as large as possible;
• Groups shall consist only of adjacent values;
• All values must belong to at least one group;

Introducing

The map of Karnaugh - sometimes called diagram - is a technique for simplification of boolean expressions, arising basically to counteract the simplification techniques through Boolean algebra, which are exhaustive, require in-depth knowledge of all rules and very easy to err on; in turn, simplification through the Karnaugh map is a systematic method by following all its steps to obtain the result.

It is a concept very related to the truth table, as it is customary, in practice, to elaborate the Karnaugh map from the truth table, given the ease that this brings the solution and the ease of constructing the truth table apart from any boolean expression.

What is and what serves a "truth table"?

The result of the Karnaugh map, when executed correctly, will always be the simplest expression in the sum product or sum product formats, depending on how the map is solved, both non-canonical.

Applying

The Karnaugh map can be used to simplify any boolean expression, ie when you are developing a logical circuit you can first do itlo work, without worrying too much about numbers of logical gates used and then apply Karnaugh’s map to the system and reduce its circuit to the maximum, thus decreasing, project cost, response delay and electric power consumed. Another possible application is the reduction of logical operations performed by ULA to verify an expression in your code. If you have a if with an overly complex expression, you can use Karnaugh’s map to simplify it.

Construction and Resolution

Karnaugh’s map works very well for logic expressions with 2 to 5 variables. Above this, the resolution of the map becomes too exhaustive and generally makes its use unfeasible. As an example for the answer, we will always consider the letters A to E as the variables of the logic expression and S as the output value.

To construct the map for an expression with n variables, it will be necessary to construct a table with 2^n cells, in the following format:

1. To n = 2, create a table with 2 rows and 2 columns;
2. To n = 3, create a table with 2 rows and 4 columns;
3. To n = 4, create a table with 4 rows and 4 columns;
4. To n = 5, create a table with 4 rows and 8 columns;

Realize that to n > 2 it will be necessary to create entry groupings. In the first map, the values of A are placed in line and the values of B and column; in the second map, the values of the combination AB are placed in line and the values of B in column; in the third map, the values of the combination AB are placed in line and the values of the combination CD in column; in the fourth map, the values of the combination ABC are placed in line and the values of the combination DE in column. The combinations that will be placed in row or column does not matter much, but it is a matter of life or death you correctly position the values. These should always follow the order of Gray, that is, each row or column value should only vary in one bit for adjacent rows or columns. Note that in the second map, the combination AB is positioned in sequence 00, 01, 11 and 10, because if it were in the natural order, 00, 01, 10 and 11, between the values 01 and 10 there would be the change of two bits and this is not allowed. This is actually the essence of Karnaugh’s map. This process would be the equivalent of you positioning side by side the terms with most variables in common in Boolean algebra, thus simplifying the process.

Each cell in the Karnaugh map refers to a truth table cell and must be filled as such. Once the map has been filled in, it must be checked whether there are more zeroes or ones, because in order to obtain the most simplified form of the final expression, the values must always be considered in greater quantity. If there are more than zeros, you will group them and get an answer in the formed sum of products; already if there are more zeros than one, you will group them and get an answer in the form of sums product. Even, another application of the Karnaugh map is the conversion between the sum format of products to the sum of sums, or vice versa. The grouping should always be done considering power quantities of 2, obtaining the largest possible groups. The only rule for grouping, besides the size being power of 2, is that the values of the group should be adjacent to each other in the row or column, considering the table as a cylinder, that is, the first line is considered adjacent to the last, as the first column is adjacent to the last. Once the grouping is done, each group will generate an operand of the result and this operand will be defined according to the variables that maintain its value within the respective group. This will be clearer in the example.

Example

For a practical example, let’s consider that the program will calculate a mathematical process in 4 different ways in parallel, returning the result when at least three processes have been completed with the same value, or when two of them have finished, and one of them is process A. That is, if all ABCD processes end, if BCD end or if AB, AC or AD end, the program must return the result.

The canonical logic expression for this verification would be:

S = (A.B.C.D) + (~A.B.C.D) + (A.B.C.~D) + (A.B.~C.D) + (A.~B.C.D) + (A.B.~C.~D) + (A.~B.C.~D) + (A.~B.~C.~D)

This requires the realization of 41 logical operations. Imagine writing a if with all this? But by mounting the truth table, we have:

| A | B | C | D | S |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | -> B.C.D
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | -> A.D
| 1 | 0 | 1 | 0 | 1 | -> A.C
| 1 | 0 | 1 | 1 | 1 | -> A.C.D
| 1 | 1 | 0 | 0 | 1 | -> A.B
| 1 | 1 | 0 | 1 | 1 | -> A.B.D
| 1 | 1 | 1 | 0 | 1 | -> A.B.C
| 1 | 1 | 1 | 1 | 1 | -> A.B.C.D

When you build Karnaugh’s map, you get something like:

We have the same amount of zeros and ones on the map, so it will be indifferent which group. By way of example, I will make the two ways.

Groups of 1

First, we will solve the map by grouping the ones together to get the answer in sum of products. The possible groups are:

Remember that all values must be grouped and that the same value can be part of several groups. In this way, analyzing each group, we have:

• Blue: variables A and B have the same value throughout the group, so the generated operand will be A.B;
• Red: variables A and D have the same value throughout the group, so the generated operand will be A.D;
• Black: variables A and C have the same value throughout the group, so the generated operand will be A.C;
• Green: variables B, C and D have the same value in any group, then the generated operand will be B.C.D;

Therefore, the simplified expression will be:

S = (A.B) + (A.C) + (A.D) + (B.C.D)

That will require only 8 logical operations, against the 41 initials.

Groups of 0

The same can be done by grouping zeros:

Thus remaining:

• Blue: variables A and B have the same value throughout the group, so the generated operand will be A+B;
• Red: variables A and C have the same value throughout the group, so the generated operand will be A+C;
• Black: variables A and D have the same value throughout the group, so the generated operand will be A+D;
• Green: variables B, C and D have the same value throughout the group, so the generated operand will be B+D;

Therefore, the simplified expression will be:

S = (A+B).(A+C).(A+D).(B+C+D)

Which will also require only 8 logical operations.