Application of Karnaugh Map in Digital Circuits

In digital circuits, the Karnaugh map is a method of representing logic functions with minimum term grids. It uses graphics to represent the logical relationship between input variables and functions. It uses geometric proximity to vividly represent the logical proximity between the various minimum terms that make up the logic function. Beginners often think that the Karnaugh map is just a tool for simplifying logic functions in digital circuit analysis and design. In fact, the flexible use of the Karnaugh map can greatly simplify the analysis and design process of logic circuits and solve some difficult problems. The following introduces several flexible uses of the Karnaugh map in addition to simplification.

1 Application of Karnaugh Map

1.1 Using the Karnaugh map structure to help remember Gray code

Gray code is a commonly used unweighted BCD code, in which only one binary digit is different between two adjacent codes. It is often used in analog quantity conversion. When a small change in analog quantity may cause a change in digital quantity, Gray code only changes one bit. This is more reliable than other codes that change two or more bits at the same time, which can reduce the possibility of errors and improve the anti-interference ability of the circuit. It is a typical reliability code. This code system is widely used in numerical control devices. However, due to the uniqueness of this encoding, it is difficult to remember in practical applications. After research and discussion, we have observed that using Karnaugh maps to take values ​​according to certain rules can be used to realize the memory of Gray code. This unique way of memory can help students remember the code conveniently and easily and apply it in practice.

Select the four-variable Karnaugh map and set: G3G2G1G0 as the input variables of the four-bit Gray code. Set the variables G3G2 as the high bit and G1GO as the low bit. Draw the four-variable Karnaugh map. From the four-variable Karnaugh map, we can see that if the four variables in the Karnaugh map take values ​​in the order shown by the arrows, the order of the value changes is exactly the encoding table of the four-bit Gray code, as shown in the Karnaugh map representation of Gray code in Figure 1. The decimal numbers from 0 to 15, the corresponding input codes of the four-bit Gray code are 0000-0001-0011-1001-1000 respectively, as shown in Table 1, the encoding table of Gray code.

1.2 Application of Karnaugh Map in Competition and Adventure of Combinational Logic Circuits

Competition hazard is a unique phenomenon in digital circuits. Different gate circuits have different delay times. Input signals are transmitted through different paths. The time they arrive at the output end may be earlier or later, and the state changes may be earlier or later, resulting in time differences. This phenomenon of time differences in state changes is called "competition". If the result of competition is that the logical relationship of the steady-state output is temporarily destroyed and an unnecessary spike pulse appears, this phenomenon is called "hazard". Hazards may cause temporary or permanent logic errors in the circuit.

When designing logic circuits, we must discover and identify the possibility of competition hazards and take active and effective measures to eliminate them. There are many ways to judge and eliminate competition hazards. The simplest and most intuitive method is to use the Karnaugh map.

The general steps for using the Karnaugh map to determine whether a combinational logic circuit has a race hazard are: first draw the Karnaugh map of the circuit's logic function, then draw the Karnaugh cycles corresponding to all the product terms in the expression on the function Karnaugh map. If there are tangent Karnaugh cycles in the graph, then the logic circuit has a race hazard as shown in Figure 2. The so-called tangent Karnaugh cycles mean that there are adjacent minimum terms between two Karnaugh cycles that are not included in the same Karnaugh cycle.

If there are tangent Karnaugh circles in the Karnaugh map of a logic function, there is a race hazard in the logic circuit; then, as long as the tangent Karnaugh circles are eliminated from the function's Karnaugh map, the race hazard phenomenon can be eliminated. On the Karnaugh map, add a circle (one item) that intersects with the two tangent Karnaugh circles to destroy the individual tangency of the Karnaugh circles. After adding this circle, the logic function has an additional redundant item. The addition of the redundant item does not change the logic value of the original logic function, but the addition of the redundant item can effectively eliminate the hazard.

For example, in the Karnaugh map shown in Figure 3, there are two places where Karnaugh circles are tangent, so the logic function F = ABC + ABD + AD represented by it has hazards. Two Karnaugh circles (dashed circles) can be added to destroy its tangency, that is, to add two redundant items BCD and ACD. After eliminating the competition hazard, the expression of the logic function is as follows:

It can be seen that using Karnaugh maps to judge and eliminate competition hazards in digital circuits is simple, intuitive and easy to operate.

1.3 Using Karnaugh maps to perform logical operations on two logical functions

First, the logic functions F1 and F2 are represented in the same Karnaugh map. For the sake of distinction, the l that appears in function F1 is filled in the upper left corner of the small square of the Karnaugh map, and the l that appears in the other function F2 is filled in the lower left corner of the small square of the Karnaugh map.

The following uses several common logical operations as examples to illustrate.

1) Find the OR operation F1+F2 of two logical functions Y1 and Y2

According to the characteristics of the OR operation, when performing the OR operation, just draw all the l's that appear in the Y1 and Y2 Karnaugh maps into encircles, and then write the expression based on the Karnaugh map.

2) Find the AND operation of two logic functions Fl and F2: Fl·F2

According to the characteristics of AND operation, when performing AND operation, just draw the repeated l in the Karnaugh map of F1 and F2 into a circle, and then write the expression according to the Karnaugh map.

3) Find the XOR operation of two logic functions F1 and F2: F1+F2

According to the characteristics of XOR operation, when calculating XOR operation, just draw the non-repeating l in the Fl and F2 Karnaugh maps into a bracket, and then write the expression according to the Karnaugh map.

Example: Given two logic functions F1(A, B, C) = ∑m(0, 1, 3) and F2(A, B, C) = ∑m(0, 4, 5, 7), try using the Karnaugh map to find F1+F2; Fl·F2 and Fl+F2 respectively.

untie:

1) The logic functions Fl and F2 are represented in the same Karnaugh map, the 1 that appears in the function is filled in the upper left corner of the small square of the Karnaugh map, and the l that appears in the function F2 is filled in the lower left corner of the small square of the Karnaugh map, as shown in Figure 4;

2) When finding Fl+F2, draw all l appearing in the Fl and F2 Karnaugh maps into the encirclement, as shown in Figure 5;

3) When calculating F1·F2, draw the repeated 1s in the Karnaugh maps of F1 and F2 into encircles, as shown in Figure 6;

4) When calculating F1+F2, draw the non-repeating 1 in the Karnaugh map of F1 and F2 into the encirclement, as shown in Figure 7;

5) Write the function expression according to Figures 5, 6, and 7:

1.4 Using Dimensionality-Reduced Karnaugh Maps to Simplify Multivariable Functions

In the Karnaugh map, we usually use "0", "1" and the irrelevant term "d" (or "×") as the unit values ​​in the Karnaugh map. The variables of the function are all used as the variables of the Karnaugh map. Generally speaking, the dimension of the Karnaugh map is the number of variables of the function. If some variables are also used as unit values ​​in the map, the dimension of the resulting Karnaugh map will be reduced. Such a Karnaugh map is called a reduced-dimensional Karnaugh map. When using medium-scale integrated circuits, especially when using data selectors to implement functions, it is very useful to use reduced-dimensional Karnaugh maps to simplify multi-variable functions. The principle of reduced-dimensional Karnaugh map simplification will not be repeated here.

For example, the logic function F(A, B, C, D)=∑m(0, 3, 5, 6, 9, 10, 12, 15) if the 8-to-1 data selector 74LSl5l is selected to implement the combinational logic function, since the 8-to-1 data selector has 3 address variables, the logic function is reduced to a three-dimensional Karnaugh map and compared with the Karnaugh map of the 8-to-1 data selector containing Di (see Figure 8). It is easy to obtain the relationship between the data selector input signal and the logic function variable: let A2=A, A1=B, A0=C, then Do="D3"=D5=D6=D, Dl=D2=D4=D7=D, draw a logic diagram, as shown in Figure 9.

If a 4-to-1 data selector is used to implement the logic function, the 3D Karnaugh map can be further reduced to a 2D Karnaugh map and then compared with the 4-to-1 data selector containing Di's Karnaugh map (see Figure 11) to obtain the relationship between the data selector input signal and the logic function variable: A1=A, A0=B, D0=D3=CD+CD=C+D, D1=D2=CD+CD=C+D

The implementation of the logic function using a 4-to-1 data selector is shown in Figure 10.

2 Conclusion

From the above examples, we can see that the use of Karnaugh maps is not limited to the simplification of logic functions. It can be widely used in memorizing or designing related codes, judgments in competitive adventures, data selectors to implement logical operations of combinational logic functions and logic functions, etc. A deep understanding of the connotation of the Karnaugh map and its skillful application can achieve unexpected results and bring great convenience to the analysis and synthesis of digital logic circuits.