Karnaugh map

1. About Karnaugh Map

Previously, in the process of designing a logic circuit, the logic expression was simplified. This process is essential, but requires knowledge of various Boolean algebra laws and takes a considerable amount of time depending on the combination of variables. The Karnaugh map published by Maurice Karnaugh in 1953 is mainly used as a method to schematize this simplification process to make it simple and clear.
  This Karnaugh map is represented as a two-dimensional table, and simplification proceeds by arranging and tying identical terms of the input adjacent to each other. Simplification, which takes several minutes from fire algebra to necessary calculation, is powerful enough to finish in about 10 seconds if summarized in the Karnaugh map, but there is a limitation in that the input is limited to four in terms of two-dimensional expression. Let's look at the usage and examples of these Karnaugh maps. Let's look at the usage and examples of these Karnaugh maps.

 

2. 2-input Karnaugh map

The two-input Karnaugh map is not often used for the simple reason that the simplification of Boolean algebra is good, but it is good to approach when you want to understand the Karnaugh map.

 

 

To check the number of cases for the two inputs, write the inputs on the 2-axis, and all cells intersect in the coordinates. Since each input has two types of ‘0’ and ‘1’, it can be seen that the number of cases is 4 in the form of a 2×2 matrix. As with binary to decimal conversion, serial numbers of 0, 1, 2, 3 are assigned in the order of 00₂, 01₂, 10₂, 11₂ by combining the two inputs. Since each cell is in the form of a minterm, the notation of ‘m(serial number)’ is used.
  Next, looking at the characteristics, each cell has a complementary relationship with the adjacent cell for one input. That is, one of the inputs is removed by the logical sum of two adjacent minterms. By summing adjacent cells vertically, A’+A=1, and horizontally adding B’+B=1. Simplify using this characteristic.

 

Two inputs can be expressed on 1-axis, and the array is rotated like an animation so that m(1) and m(3) are adjacent. At the same time, the left and right ends, m(0) and m(2), are considered adjacent to each other as before. It is good to think of it as being rolled up into a single round object and connected end-to-end. Inputs are placed in the order of 00₂, 01₂, 11₂, 10₂ according to the arrangement of the minterm.

 

 

As above, the Karnaugh map for two inputs is expressed in two ways, but the final result should always be the same, and the detailed simplification order is as follows.

 

We know that each of the blanks in the matrix created in the Karnaugh map corresponds to a truth table or a minterm of Boolean algebra. Therefore, ‘1’ is written in the blank corresponding to the output, and even if several terms are overlapped in one cell, it is still ‘1’ according to the common identity law or the absorption law. If the result of Boolean algebra is not a minterm, write the number of minterm included. For example, if the output term in the 2-input Karnaugh map is A, it is A·B’＋A·B, so two ‘1’s are used. This corresponds to filling in all the fields A＝1 in the Karnaugh map. In addition, if the output contains don't care, write it as ‘X’, and blank spaces without output are automatically set to ‘0’, but there is no need to write it.
  As a result of the simplification, if the cell in which ‘1’ is written is adjacent, it is treated as a bundle and the matrix value of the corresponding axis is read. Since adjacent cells are simplified in a complementary relationship, they must be made in even numbers (2 or 4, etc.), and make it simple by making it as large as possible. When ‘X’ is present, it is included as an output when it is advantageous for simplification, and excluded when it is not. If there is a single '1' because it is not adjacent, write it as it is. For example, let’s summarize A’B’+A’·B+A·B’ on the Karnaugh map.

 

As in an animation, arrange three terms in an array of a 2-axis Karnaugh map, write ‘1’, group horizontally adjacent terms as A’ and vertically adjacent terms as B’. Since all ‘1’s are arranged in two sets, the simplification result is A’＋B’.

 

 

As in an animation, in a 1-axis Karnaugh map, write ‘1’ in each column corresponding to three terms and group adjacent terms together. At this time, it can be seen that the left end and the right end are adjacently tied. By reading the terms expressed in two groups, it can be seen that the simplification result is A’＋B’.

 

3. 3-input and 4-input Karnaugh maps

3-input and 4-input Karnaugh map are not used as a 1-axis type. If you think of it as a combination of the 1-axis type and the 2-axis type of the 2-input Karnaugh map, you can guess the shape.

 

 

 

Since the overall simplification method is the same as the 2-input Karnaugh map, binary numbers are assigned to each axis according to the number of inputs, the truth table or logical expression term is written as '1', adjacent cells are grouped in even units, and the matrix of the grouped cells is read.
  As an example, let’s summarize ∑d(0, 13)＋A’·B’·C’·D＋A’·B’·C＋A’·B·C＋A·B’·C as a 4-input logic expression with unrelated terms added. (The d(serial number) is the first letter of ‘don’t care’ and means ‘don’t care’.)

 

 

Write don’t care terms as ‘X’ at positions m(0) and m(13), and find other terms in order and write them as ‘1’. When tying adjacent cells with ‘1’, if they are grouped in a 2×2 form, all 2×1 or 1×2 included here will be absorbed, so group them as large as possible. In the case of m(0), which is don’t care, it is included because it can be made into a larger group by including, and in case of m(13), the terms only increase and are excluded because they are not bundled with adjacent cells. As a result, they are grouped into 4×1, 2×2, and 2×2 forms, and are organized into A’·B’＋A’·C＋B’·C.

 

4. 5-input Karnaugh map(basic type)

Karnaugh map uses 3-axis from 5 inputs, which is difficult to express on paper or screen. It is common to think of stacking 2 layers (5 inputs) and 4 layers (6 inputs) in the direction of the height axis while applying 4 inputs as it is to the horizontal and vertical axes, and arranging them sideways for convenience.

 

 

As with the above-mentioned 2 inputs, 3 inputs, and 4 inputs, the output terms are written in the blanks and arranged by even numbers in the adjacent horizontal and vertical height directions, and then the matrix is ​​read.

 

 

Only for 5-input Karnaugh map, it is combined by dividing one cell as shown in the figure, here ∑d(0, 1, 17, 21)＋A’·B·C·E＋A·C·D·E＋A’B’CD’E＋A’B’CDE＋A’BC’DE is summarized.

 

 

As a result of the simplification, it can be seen that the don’t care term does not affect the simplification and is A’CE＋CDE＋A’BDE.

 

In the case of a 6-input Karnaugh map, it is thought that 4 matrices of 4×4 are stacked in the same way as the 5-input. 5 In the method of input, the amount is increased, but the method is the same, so it is omitted.

 

5. 6-input Karnaugh map(modified type)

Originally, Maurice Karnaugh schematized the logic in his paper by assigning two inputs to each axis. That is, a 4-input in a 2-axis plane and a 6-input Karnaugh map in a 3-axis solid are the maximum. As time goes on, a simplified method for more inputs is found based on the Karnaugh map, and the key is the gray code.
  Since gray codes have the characteristic of changing only one digit when they are arranged in order, there is always a complementary relationship between consecutive numbers. In the case of 4 inputs, the order of 2 inputs for each axis in the plane is 00₂, 01₂, 11₂, 10₂, which coincides with the order of gray codes. In addition to this, if 3 inputs are expressed on one axis, the order of 000₂, 001₂, 011₂, 010₂, 110₂, 111₂, 101₂, 100₂ can be predicted. Applying this to the 6-input Karnaugh map is as follows.

 

 

The part where the simplification is cut between adjacent cells is eliminated by the application of the gray code, but the part where the simplification occurs between the non-adjacent cells should be identified in the simplifying process. In this Karnaugh map, ∑d(9, 15, 27, 43, 45, 47, 57, 61)＋A’·B·C·D·F＋A’·B·C·D’·E’·F＋A’·B’·C·D’·E·F＋A·B·C·D’·E·F＋A·B·C·D·E·F is as follows.

 

 

As shown in the figure, simplification is possible, but it is difficult because it is not intuitive. (The simplifying process is omitted.)

 

6. Conclusion

Applying the Karnaugh map to the simplification of logical expressions makes it unnecessary to know the law of simplification of Boolean algebra, but it is advantageous depending on the situation to be able to use both. Actually, Karnaugh map also has a dedicated calculator, so you should find it on the internet and use it. For reference, there is also a method of applying the maxterm to the Karnaugh map, but it is omitted because it is relatively unreasonable to use.