Carnot Map

Carnot cube example

Karno Cube ( Karno map, Karno diagram ) is a graphical way of representing Boolean switching functions with the goal of visualizing and minimizing them conveniently, which simplifies complex logical functions of many variables and eliminates potential logical races ^[1] .

It is one of the equivalent ways of describing or defining logical functions along with a truth table or expressions of Boolean algebra . The transformation of the representation of a logical function defined in the form of a Carnot map into a truth table or into a Boolean formula and the inverse transformation are elementary in simplicity.

The convenience and visibility of such a representation of a logical function is due to the fact that logical terms, to which the operations of pairwise incomplete gluing and elementary absorption can be applied, are grouped in the Carnot map in the form of arrays of neighboring cells along the verticals and horizontals of logical units or zeros, which is immediately obvious to a person.

Carnot maps can be considered as a scan to the plane of an n- dimensional Boolean cube , and the dimension of this hypercube coincides with the number of variables of the represented function. Graphically, the Carnot map is depicted as a rectangle or square of cells, the number of which is equal to $2^{n}$ ${\ displaystyle 2 ^ {n}}$ $2 ^ {n}$ moreover, any two neighboring cells vertically or horizontally or, in other words, in the vicinity of von Neumann describe terms that differ only in one variable - with logical negation and without logical negation. Also adjacent are the first and last rows, the leftmost and rightmost columns of the table, so the Carnot table is actually a scan of the logical hypercube to the surface of the toroid . It is possible to construct a wide variety of maps for the same function, satisfying the condition: von Neumann's geometric cell neighborhood — a logical neighborhood of terms — that is, with a Hamming distance between the terms of neighboring cells equal to 1. Any of these tables is equally convenient for minimizing the function, but usually, the variables in the rows and columns in the Carnot map are ordered by the reflective Gray code because of the mnemonics and visualization.

History

Carnot maps were proposed in 1952 by Edward W. Veitch and improved in 1953 by Maurice Carnot , a physicist at Bell Labs , to simplify the design of digital systems .

Minimization Principles

The main method of minimizing the logical functions presented in the form of SDNF or SKNF is the operation of pairwise incomplete bonding and elementary absorption. The operation of pairwise gluing is carried out between two terms (members) containing the same variables, the occurrences of which (direct and inverse) coincide for all variables except one. In this case, all the variables except one can be put out of brackets, and the direct and inverse occurrences of one variable remaining in the brackets can be glued together. For example:

${\overline {X}}_{1}X_{2}X_{3}X_{4}\vee {\overline {X}}_{1}X_{2}{\overline {X}}_{3}X_{4}={\overline {X}}_{1}X_{2}X_{4}(X_{3}\vee {\overline {X}}_{3})={\overline {X}}_{1}X_{2}X_{4}\cdot 1={\overline {X}}_{1}X_{2}X_{4}.$ ${\ displaystyle {\ overline {X}} _ {1} X_ {2} X_ {3} X_ {4} \ vee {\ overline {X}} _ {1} X_ {2} {\ overline {X}} _ {3} X_ {4} = {\ overline {X}} _ {1} X_ {2} X_ {4} (X_ {3} \ vee {\ overline {X}} _ {3}) = {\ overline {X}} _ {1} X_ {2} X_ {4} \ cdot 1 = {\ overline {X}} _ {1} X_ {2} X_ {4}.}$

Similarly for CNF:

$({\overline {X}}_{1}\vee X_{2}\vee X_{3}\vee X_{4})({\overline {X}}_{1}\vee X_{2}\vee {\overline {X}}_{3}\vee X_{4})={\overline {X}}_{1}\vee X_{2}\vee X_{4}\vee X_{3}{\overline {X}}_{3}={\overline {X}}_{1}\vee X_{2}\vee X_{4}\vee 0={\overline {X}}_{1}\vee X_{2}\vee X_{4}.$ ${\ displaystyle ({\ overline {X}} _ {1} \ vee X_ {2} \ vee X_ {3} \ vee X_ {4}) ({\ overline {X}} _ {1} \ vee X_ { 2} \ vee {\ overline {X}} _ {3} \ vee X_ {4}) = {\ overline {X}} _ {1} \ vee X_ {2} \ vee X_ {4} \ vee X_ { 3} {\ overline {X}} _ {3} = {\ overline {X}} _ {1} \ vee X_ {2} \ vee X_ {4} \ vee 0 = {\ overline {X}} _ { 1} \ vee X_ {2} \ vee X_ {4}.}$

The possibility of absorption follows from the obvious equalities

$A\vee {\overline {A}}=1;A{\overline {A}}=0.$ ${\ displaystyle A \ vee {\ overline {A}} = 1; A {\ overline {A}} = 0.}$

Thus, the main task in minimizing SDNF and SKNF is the search for terms suitable for gluing with subsequent absorption, which for large forms can be quite a difficult task. Carnot cards provide a visual way to find such terms.

As you know, Boolean functions of N variables, presented in the form of SDNF or SKNF, can include 2 ^N different terms. All these terms make up some structure topologically equivalent to an N- dimensional cube, and any two terms connected by an edge are suitable for gluing and absorption.

The figure shows a simple truth table for a function of two variables, a 2-dimensional cube (square) corresponding to this table, as well as a 2-dimensional cube with the designation of the SDNF members and an equivalent table for grouping terms:

In the case of a function of three variables, you have to deal with a three-dimensional cube. It is more complicated and less obvious, but technically possible. As an example, the figure shows the truth table for the Boolean function of three variables and the corresponding cube.

As can be seen from the figure, for the three-dimensional case more complex configurations of terms are possible. For example, four terms belonging to one face of a cube are combined into one term with the absorption of two variables:

${\overline {X}}_{1}{\overline {X}}_{2}{\overline {X}}_{3}\vee X_{1}{\overline {X}}_{2}{\overline {X}}_{3}\vee {\overline {X}}_{1}{\overline {X}}_{2}X_{3}\vee X_{1}{\overline {X}}_{2}X_{3}=$ ${\ displaystyle {\ overline {X}} _ {1} {\ overline {X}} _ {2} {\ overline {X}} _ {3} \ vee X_ {1} {\ overline {X}} _ {2} {\ overline {X}} _ {3} \ vee {\ overline {X}} _ {1} {\ overline {X}} _ {2} X_ {3} \ vee X_ {1} {\ overline {X}} _ {2} X_ {3} =}$

$={\overline {X}}_{2}({\overline {X}}_{1}{\overline {X}}_{3}\vee {\overline {X}}_{1}X_{3}\vee X_{1}{\overline {X}}_{3}\vee X_{1}X_{3})={\overline {X}}_{2}({\overline {X}}_{1}\vee X_{1})({\overline {X}}_{3}\vee X_{3})={\overline {X}}_{2}$ ${\ displaystyle = {\ overline {X}} _ {2} ({\ overline {X}} _ {1} {\ overline {X}} _ {3} \ vee {\ overline {X}} _ {1 } X_ {3} \ vee X_ {1} {\ overline {X}} _ {3} \ vee X_ {1} X_ {3}) = {\ overline {X}} _ {2} ({\ overline { X}} _ {1} \ vee X_ {1}) ({\ overline {X}} _ {3} \ vee X_ {3}) = {\ overline {X}} _ {2}}$

In the general case, we can say that 2 ^K terms belonging to one K- dimensional face of a hypercube are glued into one term, and K variables are absorbed.

To simplify the work with Boolean functions of a large number of variables, the following convenient technique was proposed. The cube, which is a structure of terms, rotates on a plane, as shown in the figure. Thus, it becomes possible to represent Boolean functions with more than two variables in a flat table. It should be remembered that the order of the term codes in the table (00 01 11 10) does not correspond to the order of binary numbers, and the cells located in the extreme columns of the table are adjacent to each other.

Similarly, you can work with functions of more variables.

Carnot Card Procedure

The initial information for working with the Carnot map is the truth table of the minimized function. The truth table contains complete information about a logical function, setting its values on all possible 2 ^N sets of input variables X ₁ ... X _N. The Carnot map also contains 2 ^N cells, each of which is associated with a unique set of input variables X ₁ ... X _N. Thus, there is a one-to-one correspondence between the truth table and the Carnot map, and the Carnot map can be considered an appropriately formatted truth table.

In this section, as an example, we use the function of four variables defined by the truth table shown in Fig. 2a. The Carnot map for the same function is shown in Fig. 2b.

Fig. 2. An example of working with a Carnot card

Gluing Principles

The gluing of the cells of the Carnot map can be done in units (if you need to get DNF ) or by zeros (if you need CNF ).
You can only glue together rectangular areas with the number of units (zeros) 2 ⁿ , where n is an integer, while it is recommended to take the maximum of the possible values of n. In some situations, a unit or zero is formed in the layout that cannot be glued to any area. In this case, the unit sticks together "with itself." For Carnot maps with more than four variables, more complex areas can be obtained, which will be discussed in the following sections.
The area to be glued should contain only ones (zeros).
The extreme cells of each horizontal and each vertical also border each other (topologically, the Carnot map for four variables is a torus) and can be combined into rectangles. A consequence of this rule is the adjacency of all four corner cells of the Carnot map for N = 4. If there are units (zeros) in all four corner cells, they can be combined into a square, as shown in Fig. 2c.
All units (zeros) must fall into any region.
From the point of view of minimization of DNF ( CNF ), the number of regions should be as small as possible (each region is a term), and the number of cells in the region should be as large as possible (the more cells in the region, the fewer variables the term contains. Term in size 2 ⁿ cells contains N - n variables).
One cell of the Carnot map can enter several areas at once. This follows from the obvious property of Boolean functions: the repetition of an existing term (factor) does not affect the function:

$A\vee A=A;A\cdot A=A.$ ${\ displaystyle A \ vee A = A; A \ cdot A = A.}$

Unlike SDNF (SKNF), DNF (CNF) are not unique. There are several possible DNFs (CNFs) equivalent to each other, which correspond to different methods of covering the Karno map with rectangular regions.

Description

A Carnot map can be built for any number of variables, however it is convenient to work with the number of variables no more than five. In fact, the Carnot Map is a truth table presented in the form of a matrix in 2-dimensional form.

Each cell of this map corresponds to one row in the classical truth table and is indicated by a row of variables with and without inversions. For example, suppose in a truth table for a function 4 variables $x_{1},x_{2},x_{3},x_{4},$ ${\ displaystyle x_ {1}, x_ {2}, x_ {3}, x_ {4},}$ one of the lines is: 0 1 1 0 | 1, then the cell in the Carnot map corresponding to this row will have a name ${\overline {x}}_{1},x_{2},x_{3},{\overline {x}}_{4}$ ${\ displaystyle {\ overline {x}} _ {1}, x_ {2}, x_ {3}, {\ overline {x}} _ {4}}$ and 1. is indicated in this cell. The indication of the cell names in the Carnot map is usually done by an additional line at the top and an additional column to the left.

It is significant that in the Carnot map, neighboring cells necessarily have neighboring codes, in the sense of the Hamming distance , that is, the Hamming distance between neighboring cells is 1, and they differ only in state - with or without inversion, of one and only one of the variables. Neighboring cells are cells adjacent to each other by the side, also cells of the leftmost and rightmost columns and cells of the first and last rows are considered neighboring cells. Thus, a Carnot map on a plane is topologically equivalent to a torus surface in three-dimensional space, or a hypertorus in a space with a dimension 1 greater than the dimension of the corresponding multidimensional Carnot map.

Since the permutation of variables in a logical function does not change the function itself, that is, for example, $F(x_{1},x_{2},x_{3},x_{4})=F(x_{4},x_{2},x_{3},x_{1})$ ${\ displaystyle F (x_ {1}, x_ {2}, x_ {3}, x_ {4}) = F (x_ {4}, x_ {2}, x_ {3}, x_ {1})}$ or, what’s the same thing - rearranging the columns of variables in the truth table does not change the function, there are several options for displaying the truth table on the Carnot map while preserving the “neighborhood” of the cells. But practically the most often Carnot map is filled, using the increasing Gray code to indicate rows and columns. This approach guarantees the generation of a Carnot map with the avoidance of subjective errors.

When filling in the card at the intersection of a row and a column, the corresponding value from the truth table is put down - 0 or 1. After the card is full, they begin to minimize it.

If it is necessary to obtain the minimum DNF , then in the Map we consider only those cells that contain units, if CNF is needed, then we consider those cells that contain zeros. Minimization itself is carried out according to the following rules (for example, DNF).

Combine adjacent cells containing units into a region so that one region contains $2^{n}$ ${\ displaystyle 2 ^ {n}}$ ( $n$ ${\ displaystyle n}$ integer = 0 ... $\infty$ ${\ displaystyle \ infty}$ ) cells (remember that the extreme rows and columns are adjacent to each other), in the area there should not be cells containing zeros;
The area should be located symmetrically to the axis (s) (axes are located every four cells);
Non-adjacent regions located symmetrically to the axis (s) can be combined into one;
The area should be as large as possible, and the number of areas as small as possible;
Areas may intersect;
Several coating options are possible.

Next, we take the first area and look at which variables do not change within this area, we write out the conjunction of these variables; if the unchanging variable is zero, we put an inversion on it. We take the next area, do the same as for the first, etc. for all areas. The conjunctions of regions are joined by a disjunction .
For example (for Maps on 2 variables):

{\overline {X_{1}}}\ {\overline {X_{2}}}

{\ displaystyle {\ overline {X_ {1}}} \ {\ overline {X_ {2}}}}

{\overline {X_{1}}}\ X_{2}

{\ displaystyle {\ overline {X_ {1}}} \ X_ {2}}

X_{1}\ X_{2}\

{\ displaystyle X_ {1} \ X_ {2} \}

X_{1}\ {\overline {X_{2}}}

{\ displaystyle X_ {1} \ {\ overline {X_ {2}}}}

{\overline {X_{2}}}

{\ displaystyle {\ overline {X_ {2}}}}

{\overline {X_{1}}}

{\ displaystyle {\ overline {X_ {1}}}}

{X_{2}}\

{\ displaystyle {X_ {2}} \}

{X_{1}}\

{\ displaystyle {X_ {1}} \}

S_{1}\vee S_{2}=

{\ displaystyle S_ {1} \ vee S_ {2} =}

S_{1}\vee S_{2}=

{\ displaystyle S_ {1} \ vee S_ {2} =}

S_{1}\vee S_{2}=

{\ displaystyle S_ {1} \ vee S_ {2} =}

S_{1}\vee S_{2}=

{\ displaystyle S_ {1} \ vee S_ {2} =}

S_{1}\vee S_{2}=

{\ displaystyle S_ {1} \ vee S_ {2} =}

S_{1}\vee S_{2}=

{\ displaystyle S_ {1} \ vee S_ {2} =}

=X_{1}X_{2}\vee

{\ displaystyle = X_ {1} X_ {2} \ vee}

=X_{1}{\overline {X_{2}}}\vee

{\ displaystyle = X_ {1} {\ overline {X_ {2}}} \ vee}

=X_{2}\vee X_{1}

{\ displaystyle = X_ {2} \ vee X_ {1}}

=X_{1}\vee {\overline {X_{2}}}

{\ displaystyle = X_ {1} \ vee {\ overline {X_ {2}}}}

={\overline {X_{1}}}\vee {\overline {X_{2}}}

{\ displaystyle = {\ overline {X_ {1}}} \ vee {\ overline {X_ {2}}}}

=X_{2}\vee {\overline {X_{1}}}

{\ displaystyle = X_ {2} \ vee {\ overline {X_ {1}}}}

\vee {\overline {X_{1}}}\ {\overline {X_{2}}}

{\ displaystyle \ vee {\ overline {X_ {1}}} \ {\ overline {X_ {2}}}}

\vee {\overline {X_{1}}}X_{2}

{\ displaystyle \ vee {\ overline {X_ {1}}} X_ {2}}

For CNF, everything is the same, only we consider cells with zeros, unchanging variables within the same area are combined into disjunctions (we put inversions over single variables), and we combine disjunctions of regions into a conjunction. This minimization is considered complete. So, for the Carnot Map in fig. 1, the expression in DNF format will look like:

$f(X_{1},X_{2},X_{3},X_{4})=S_{1}\vee S_{2}\vee S_{3}={\overline {X_{1}}}\ {\overline {X_{4}}}\vee X_{1}\ X_{2}\ X_{4}\vee {\overline {X_{4}}}{\overline {X_{2}}}$ ${\ displaystyle f (X_ {1}, X_ {2}, X_ {3}, X_ {4}) = S_ {1} \ vee S_ {2} \ vee S_ {3} = {\ overline {X_ {1 }}} \ {\ overline {X_ {4}}} \ vee X_ {1} \ X_ {2} \ X_ {4} \ vee {\ overline {X_ {4}}} {\ overline {X_ {2} }}}$

In CNF format:

$f(X_{1},X_{2},X_{3},X_{4})=S_{1}S_{2}S_{3}=(X_{1}\vee {\overline {X_{4}}})(X_{2}\vee {\overline {X_{4}}})({\overline {X_{1}}}\vee {\overline {X_{2}}}\vee X_{4})$ ${\ displaystyle f (X_ {1}, X_ {2}, X_ {3}, X_ {4}) = S_ {1} S_ {2} S_ {3} = (X_ {1} \ vee {\ overline { X_ {4}}}) (X_ {2} \ vee {\ overline {X_ {4}}}) ({\ overline {X_ {1}}} \ vee {\ overline {X_ {2}}} \ vee X_ {4})}$

You can also go from DNF to CNF and vice versa using the Laws of de Morgan .

Examples

Example 1

Kolya’s boy has a mom, dad, grandfather and grandmother. Kolya will go for a walk on the street if and only if at least two relatives allow him.
For brevity, we denote the relatives of Kolya through the letters:
mom - x1
dad - x2
grandfather - x3

grandmother - x4

We agree to denote the consent of relatives as unity, disagreement as zero. The ability to go for a walk is denoted by the letter f, Kolya goes for a walk - f = 1, Kolya does not go for a walk - f = 0.
Let's make a truth table:

Let's redraw the truth table in a 2-dimensional view:

We rearrange the rows and columns in it according to the Gray code (the last and penultimate columns are interchanged). Received Carnot Card:

Fill it with values from the truth table (the first row does not correspond to the truth table, since f = 0 and there is no permission to walk):

Minimize in accordance with the rules:

1. All areas contain 2 ^ n cells;
2. Since the Carnot Map has four variables, the axes are located at the borders of the Map and are not visible (for more details see the example of a Map with 5 variables );
3. Since the Carnot Map has four variables, all areas of the symmetrical axes are adjacent to each other (for more details see the example of a Map with 5 variables );
4. Areas S3, S4, S5, S6 are as large as possible;
5. All areas intersect (optional);
6. In this case, there is only one rational option.

$f(X1,X2,X3,X4)=S1\vee S2\vee S3\vee S4\vee S5\vee S6=$ ${\ displaystyle f (X1, X2, X3, X4) = S1 \ vee S2 \ vee S3 \ vee S4 \ vee S5 \ vee S6 =}$

$=X3X4\ \vee \ X1X2\ \vee \ X2X4\ \vee \ X1X4\ \vee \ X1X3\ \vee \ X2X3$ ${\ displaystyle = X3X4 \ \ vee \ X1X2 \ \ vee \ X2X4 \ \ vee \ X1X4 \ \ vee \ X1X3 \ \ vee \ X2X3}$

Now, using the obtained minimum DNF, we can construct a logical circuit :

Due to the lack of a six-input OR element that implements the disjunction function, it was necessary to cascade five- and two-input elements (D7, D8).

Make up min. CNF:

$f(X1,X2,X3,X4)=(S1)\ (S2)\ (S3)\ (S4)=$ ${\ displaystyle f (X1, X2, X3, X4) = (S1) \ (S2) \ (S3) \ (S4) =}$

$=(X1\vee X2\vee X3)(X1\vee X3\vee X4)(X2\vee X3\vee X4)(X1\vee X2\vee X4)$ ${\ displaystyle = (X1 \ vee X2 \ vee X3) (X1 \ vee X3 \ vee X4) (X2 \ vee X3 \ vee X4) (X1 \ vee X2 \ vee X4)}$

Notes

↑ Carnot maps. Lecture on Youtube .

Links

Using Karnaugh maps in practical applications , Designing a traffic light control scheme.

Software

Karnaugh Minimizer , Commercial Windows application (often does not work correctly, for example, for this equation: 0,1,5,8,10,13).
Logic Minimizer , a commercial Windows application, but can be made to run on Unix.
Kmap minimizer Online application (Flash).
GKMap , free software at SourceForge.net .
Karnaugh Map Minimizer , free (but often incorrectly working) software at SourceForge.net .
Gorgeous Karnaugh , the commercial Gorgeous Karnaugh software for minimizing on Carnot cards.

Literature

R. Tokheim Basics of Digital Electronics - M .: Mir, 1988. - 392 p. (Chapter 4, pages 88–95)

[1] Carnot maps. Lecture on Youtube .