Minimization of combinational circuits, Carnot maps, circuit synthesis

In practical engineering work, logic synthesis is understood as the process of composing the eigenfunctions of a finite automaton operating according to a given algorithm. As a result of this work, algebraic expressions for the output and intermediate variables should be obtained, based on which circuits containing the minimum number of elements can be constructed. As a result of the synthesis, it is possible to obtain several equivalent variants of logical functions whose algebraic expressions comply with the principle of minimality of elements.

Rice. 1. Karnaugh map

The process of circuit synthesis is mainly reduced to the construction of truth tables or Carnot maps according to the given conditions for the appearance and disappearance of the output signals. The way of defining a logical function using truth tables is inconvenient for a large number of variables. It is much easier to define logical functions using Carnot maps.

A Karnaugh map is a quadrilateral divided into elementary squares, each of which corresponds to its own combination of values ​​of all input variables. The number of cells is equal to the number of all sets of input variables — 2n, where n is the number of input variables.

Input variable labels are written on the side and top of the map, and variable values ​​are written as a row (or column) of binary numbers above each map column (or on the side opposite each map row) and refer to the entire row or column ( see Figure 1). A sequence of binary numbers is written such that adjacent values ​​differ in only one variable.

For example, for one variable — 0.1. For two variables — 00, 01, 11, 10. For three variables — 000, 001, 011, 010, 110, 111, 101, 100. For four variables — 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000. Each square contains the value of the output variable that corresponds to the combination of input variables for that cell.

The Karnaugh map can be constructed from the verbal description of the algorithm, from the graphical diagram of the algorithm, as well as directly from the logical expressions of the function. In this case, a given logical expression must be reduced to the form of SDNF (perfect disjunctive normal form), which is understood as the form of a logical expression in the form of a disjunction of elementary unions with a complete set of input variables.

The logical expression contains the unions of single constituents only, therefore each set of variables in the unions must be assigned one in the corresponding cell of the Carnot map and zero in the other cells.

As an example of combinational chain minimization and synthesis, consider the operation of a simplified transportation system. In fig. 2 shows a conveyor system with a hopper, which consists of a conveyor 1 with a slip sensor (DNM), a feed container 4 with a top level sensor (LWD), a gate 3 and a reversing conveyor 2 with sensors for the presence of material on the belt (DNM1 and DNM2).

Rice. 2. Transportation system

Let's draw up a structural formula for turning on an alarm relay in the event of:

1) slippage of the conveyor 1 (signal from the BPS sensor);

2) overflow of storage tank 4 (signal from the DVU sensor);

3) when the shutter is on, there is no material on the reverse conveyor belt (no signals from the sensors for the presence of material (DNM1 and DNM2).

Let's label the elements of the input variables with letters:

• DNS signal — a1.

• TLD signal — a2.

• Gate limit switch signal — a3.

• DNM1 signal — a4.

• DNM2 signal — a5.

Thus we have five input variables and one output function R. The Carnot map will have 32 cells. The cells are filled based on the operating conditions of the alarm relay. Those cells in which the values ​​of the variables a1 and a2 by condition are equal to one are filled with ones, since the signal from these sensors must activate the alarm relay. Units are also placed in cells according to the third condition, ie. when the door is open, there is no material on the reversing conveyor.

To minimize the function in accordance with the previously stated properties of Carnot maps, we outline a number of units along contours, which are by definition adjacent cells. On the contour spanning the second and third rows of the map, all variables except a1 change their values.Therefore, the function of this loop will consist of only one variable a1.

Likewise, the second loop function spanning the third and fourth rows will consist of only the variable a2. The third loop function spanning the last column of the map will consist of the variables a3, a4, and a5 as the variables a1 and a2 in this loop change their values. Thus, the functions of the algebra of the logic of this system have the following form:

Rice. 3. Carnot map for transport scheme

Figure 3 shows the schematics for applying this FAL to relay contact elements and to logic elements.

Rice. 4. Schematic diagram of the alarm control of the transport system: a — relay - contact circuit; b — on logical elements

In addition to the Carnot map, there are other methods for minimizing the logic algebra function. In particular, there is a method to directly simplify the analytical expression of the function specified in SDNF.

In this form, you can find ingredients that differ by the value of a variable. Such pairs of components are also called adjacent, and in them the function, as in the Carnot map, does not depend on the variable that changes its value. Therefore, applying the pasting law, one can reduce the expression by one bond.

After doing such a transformation with all adjacent pairs, one can get rid of repeated unions by applying the law of idempotency. The resulting expression is called a shortened normal form (SNF), and the compounds included in the SNF are called implicits. If applying the generalized sticking law is acceptable for a function, then the function will be even smaller.After all the above transformations, the function is called a dead end.

Synthesis of logic block diagrams

In engineering practice, in order to improve equipment, it is often necessary to switch from relay-contactor schemes to contactless ones based on logic elements, optocouplers and thyristors. To make such a transition, the following technique can be used.

After analyzing the relay-contactor circuit, all signals operating in it are divided into input, output and intermediate and letter designations are introduced for them. Input signals include signals for the status of limit switches and limit switches, control buttons, universal switches (cam controllers), sensors that control technical parameters, etc.

Output signals control executive elements (magnetic starters, electromagnets, signaling devices). Intermediate signals occur when the intermediate elements are actuated. These include relays for various purposes, for example, time relays, machine shutdown relays, signal relays, operating mode selection relays, etc. The contacts of these relays, as a rule, are included in the circuits of the output or other intermediate elements. Intermediate signals are subdivided into non-feedback and feedback signals. The former have only input variables in their circuits, the latter have signals of input, intermediate and output variables.

Then the algebraic expressions of logical functions for the circuits of all output and intermediate elements are written. This is the most important point in the design of a contactless automatic control system.Logical algebra functions are compiled for all relays, contactors, electromagnets, signaling devices that are included in the control circuit of the relay-contactor version.

Relay-contactor devices in the power circuit of the equipment (thermal relays, overload relays, circuit breakers, etc.) are not described with logical functions, since these elements, in accordance with their functions, cannot be replaced with logical elements. If there are non-contact versions of these elements, they can be included in the logic circuit for controlling their output signals, which must be taken into account by the control algorithm.

Structural formulas obtained in normal forms can be used to construct a structural diagram of Boolean gates (AND, OR, NOT). In this case, one should be guided by the principle of a minimum of elements and cases of microcircuits of logic elements. To do this, you need to choose such a series of logical elements that it can fully realize at least all the structural functions of the algebra of logic. Often the "PROHIBITION", "IMPLICATION" logic is suitable for these purposes.

When constructing logic devices, they usually do not use a functionally complete system of logic elements that perform all basic logic operations. In practice, in order to reduce the nomenclature of elements, a system of elements is used that includes only two elements that perform the operations AND-NOT (Scheffer move) and OR-NOT (Pierce's arrow), or even only one of these elements. In addition, the number of inputs of these elements, as a rule, is indicated.Therefore, questions about the synthesis of logic devices in a given basis of logic elements are of great practical importance.