4 ways of minimization based on the method of sampling, the method of Quine-McCluskey, on the basis of minimizing diagrams for the function of 2, 3, 4 variables (Veitch diagrams)

Annotation: In this lecture, minimization methods are presented on the basis of the trial method, the Quine-MacClasky method, on the basis of minimizing diagrams for a function of 2, 3, 4 variables (Veitch diagrams).

Consider an arbitrary DNF. If you throw away any work in it, then the remaining expression will take a zero value on those sets as the original form, since only then all the members .

However, if the discarded product (implicant) was converted to one, and the function took a single value on this single set, then the remaining expression may no longer take a single value on this set. This means that the implicant was not redundant. If, by checking, it is established that the remaining expression turns into one, the implicant is redundant, and it can be discarded.

Example 1 :

Let it be given

1. Drop the term x ₁ x ₂ :

   

   x ₁ x ₂ = 1 => x ₁ = 0, x ₂ = 0

   

   Because then x ₁ x ₂ cannot be excluded

2. Drop the term x ₁ x ₃ :

   

     x 

   _one

     x 

   ₃

     = 1 => x 

   _one

     = 1, x 

   ₃

     = 1 

   1 => x ₁ x ₃ cannot be excluded.
3. Drop the term x ₂ x ₃ :

   

   x ₂ x ₃ = 1 => x ₂ = 0, x ₃ = 1

   => x ₂ x ₃ - member extra.

If the verification shows that several implicants at the same time are superfluous, then they cannot be simultaneously excluded from the expression DNF. This can be done only alternately .

Example 2 :

1. we will test 1 member: x ₁ x ₃ x ₄ = 1; x ₁ = 0; x ₃ = 1; x ₄ = 1

   Those. the term x ₁ x ₃ x ₄ cannot be excluded.
2. test 2 member: x ₂ x ₃ x ₄ = 1; x ₂ = 0; x ₃ = x ₄ = 1

   Those. member x ₂ x ₃ x _{4 is} superfluous.
3. test 3 member: x ₁ x ₂ x ₄ ; x ₁ = 1; x ₂ = 0 x ₄ = 1

   Those. member x ₁ x ₂ x _{4 is} superfluous.
4. test 4 member: x ₁ x ₂ x ₃ ; x ₁ = 1; x ₂ = x ₃ = 0

   I.e. member x ₁ x ₂ x _{3 is} superfluous.
5. test 5 member: x ₂ x ₃ x ₄ ; x ₂ = x ₃ = x ₄ = 0

   I.e. The term x ₂ x ₃ x _{4 is} not superfluous.

Exclude at the same time members 2, 3, 4

Let us check the values ​​of f simultaneously on those sets in which all the dropped members turn into one.

those. it is evident that in the totality of this can not be done

Eliminate the term x ₂ x ₃ x ₄ , we get:

Let us check if those terms in the expression are superfluous members that turned out to be superfluous in the original expression, i.e.: x ₁ x ₂ x ₄ and x ₁ x ₂ x ₃ .

1. check x ₁ x ₂ x ₄ :

   x ₁ = 1; x ₂ = 0; x ₄ = 1

   those. member x ₁ x ₂ x _{4 is} not superfluous
2. check x ₁ x ₂ x ₃ :

   x ₁ = 1; x ₂ = x ₃ = 0

   i.e. member x ₁ x ₂ x _{3 is} superfluous,

therefore - deadlock form.

Checking then, starting with the exclusion of the third member, we obtain another dead-end form. Then choose the minimum of them.

The disadvantage of the method lies in the fact that with a large number of members it becomes cumbersome, because it is associated with the enumeration of various options. The machine implementation of this method is therefore complex. When automating the search for minimal forms, the method is practically not used.

Quine's method - Mac Klasky

The main disadvantage of Quine's method is that when searching for simple implicants it is necessary to make pair-wise comparisons at the beginning of all the constituent units, then obtained as a result of gluing the works.

In order to simplify this procedure, Mac-Klasky proposed an algorithm whose essence boils down to the following:

1. The concept of a digital equivalent for each work is introduced according to the following rule: a certain product is assigned a digital equivalent using the numbers 0 and 1 and - (dash). The variable included in the product in the direct form is set to correspond to one (1), in the inverse - zero (0), the absence of a variable is indicated by a dash;
2. in any work, the variables are arranged only in one order, namely, in ascending indices;
3. Only those works in which the dashes are located respectively, the number of zeros (or ones) differs by one and they are also arranged accordingly, are subject to gluing.

Example :

The product x ₁ x ₂ x ₄ for a function depending on five variables must be assigned to the following numeric set: x ₁ x ₂ x ₄ : 11-0-

We present a graphic representation of the simple implicant search process for the function presented in the following SDNF:

we write the expression of the function in the form of a disjunction of digital equivalents:

In the graphic method of finding simple implicants, at first all digital sets are divided into groups and these groups are arranged in the following order: first there is a group of digital equivalents containing only zeros (there can be one such set), then a group with sets containing one unit, then two and so on By comparing sets of neighboring groups, the possibility of gluing is established, the necessary mark is made and the result of gluing is written. The process continues until glueing is possible. All non-glued sets, as well as the final results of gluing, give simple implicants. Decoding received digital equivalents is obvious.

For our example, it looks like this:

So, simple implicants:

10-0 and -101, i.e.

Implicant matrix method

To search for the minimal form of a function, the method of implicant matrices is used. The essence of the method is as follows: an implicant matrix is ​​composed, the columns of which are referred to as the constituents of the unit, and the rows - as simple implicants. Then there is a minimal coverage of all constituents of the unit with the simplest implicants. At the same time, such a minimal set of simple implicants is searched for, which together cover all the constituents of the unit of the original function. The fact of coverage is marked in the matrix cell by the symbol * (asterisk) in the case when the implicant covers the corresponding constituent (is its own part). Of all the simple implicants, only those that select only the constituents of the unit (in the matrix column only one symbol of coverage) are selected first, then the search is performed.

Example :

It is clear from the matrix that implicants n (covers the constituent F), implicant r (covers the constituent D) will necessarily enter the minimal form of the function. The same is true of implicants p. As for the rest, you need to choose the minimum set.

So:

Those. This function has two equally minimal forms.

Note : an important circumstance complicating the minimization of functions is the presence of enumeration of various options when searching for optimal coverage.

Minimizing charts

This method of graphic minimization was outlined by Carnot, who introduced special cards. These cards allow for a function that depends on a small number of arguments (up to five to six) to find the results of all possible gluing. Maps were subsequently improved by Weitch, and the method itself is sometimes referred to as the minimization method using Weitch diagrams.

Consider the essence of the method for functions depending on 2, 3 and 4 variables.

Functions of 2 variables

A diagram is a matrix whose columns and rows are assigned the meaning of variables entering the function in direct or inverse form.

In the cells of the matrix put the product, formed from the letters, which are called the rows and columns of the matrix.

We draw attention to the fact that this matrix immediately indicates a possible gluing of products that are included in the expression of the function.

So all the works, located in the adjacent vertical and horizontal cells, are subject to gluing together.

• xy sticks to xy and xy;
• xy sticks to xy and xy;
• xy sticks to xy and xy;
• xy sticks to xy and xy;

Moreover, the same diagram gives the result of gluing: it is the name of either a row or a column. When minimizing by this method, the function diagram of 2 variables is filled in according to the following rule: if a product enters the PDNF function, then a unit is put in the corresponding cell of the diagram, and zero - otherwise. If there are at least two adjacent units in the diagram, this means that the two works are glued together, and the result of gluing is the product (in this case, of one letter), the name of which is the given row or column.

Example :

Select neighboring units in the diagram, and the result of gluing gives the minimum form of the function:

Note that the result of gluing is the result of covering the constituents of the original function with simple implicants. In this case, the variables that named the rows and columns of the chart.

Functions of 3 variables

To minimize the functions depending on the three variables, the following diagram is used:

From the diagram it is clear that all works located in adjacent cells, as well as in cells located at the edges of the diagram, are subject to gluing together. The result of gluing is a piece containing one letter less. It is also seen that further gluing is possible, however, already between works located in a mutually perpendicular direction.

Consider, for example, the left half of the diagram:

We glue in pairs the works in rows:

Now we see that it is possible to make further gluing together, but works in the columns of the matrix:

As you can see, the result of gluing is the product x ₂ . It is this variable that covers all four constituents of the unit of the PDNF function.

A similar statement is true for the constituents located in the rows and columns of the diagram along the edges of the table.

Thus, when searching for the minimum form, it is necessary to consider the left edge of the table glued to the right. It is said that, for clarity, it is possible to conditionally present this diagram as applied to the surface of a cylinder.

Example :

We see that two units corresponding to the constituents x ₁ x ₂ x ₃ and x ₁ x ₂ x ₃ are covered by the product x ₁ x ₂ .

Functions of 4 variables

For functions of 4 variables, the following diagrams are used:

Everything that has been said about functions of 2, 3 variables is also true in this case. But this diagram has an additional feature: when searching for the minimal form of a function, it is necessary to consider the right edge with the left and the top with the bottom edge glued together.

It is said that for convenience it is advisable to consider this diagram written on the surface of the torus.

Example :

Make a diagram:

Note that based on the property of the diagram, four units standing in the corner cells of the diagram correspond to the constituents that are glued together.

So, we give a formalized description of the method.

DefinitionThe correct configuration of the rank K is the set of ones (zeros), forming a rectangle with an area of ​​2 ^k .

To minimize the function depending on n arguments, the correct configurations are searched for, first n-1 rank, then n-2 rank, etc.

Next, the covering of the found correct configurations is determined by the joint projection of the corresponding rows and columns, which highlights the given correct configuration.

Fig. 4.1. Determining the correct configurations

C - the correct configuration

A, B, D - configuration projections

A * B - the result of gluing

Properties of Veitch diagrams

With the help of the Veitch diagrams one can find:

1. minimum form according to SKNF
2. minimum form according to the DNF and CNF functions
3. all equally minimal forms
4. minimal form of incompletely defined functions.

Let f (x ₁ x ₂ x ₃ ) be defined not in the form of the SDNF, but in the DNF:

Fill in the appropriate chart:

Because , the units are placed in the corresponding cells of the diagram.

Therefore:

The advantage of the method: simplicity and clarity for a small number of arguments.

Disadvantages: the inapplicability of the method for a large number of arguments (> 6) due to the complexity of the diagrams and loss of visibility.