How to simplify 10p3

5 Minimization of switching algebraic expressions


5.1 Objectives and ways of minimizing

The DNF or KNF of a Boolean function obtained from a truth table is usually not the shortest and simplest form, as the example "cube decoding" shows. Functions can often be simplified and in some cases variables can also be eliminated. The technical implementation of the simplified function then results in less effort than the 1: 1 implementation of the normal forms. For systematic simplification, the Boolean function must be available as DNF or KNF. There are several methods of simplification, two of which will be discussed here:
  • Application of the theorems
    Transform the given equations with the theorems for Boolean equations until a minimal form is achieved. The procedure is difficult even for equations with few unknowns (trial, intuitive procedure).
  • graphic process
    Appropriate representation of Boolean functions so that terms are clearly summarized and thereby simplified → systematic procedure clear and practical. The best known method are the Karnaugh-Veitch diagrams (KV diagram). They can be used for around four to five input variables. If there are more input variables, the process quickly becomes confusing (algorithmic processes then have an advantage).
  • algorithmic method according to Quine and McCluskey
    Successive merging of minterms or maxterms so that the terms are simplified. The best-known algorithm is the Quine-McCluskey method. The systematic procedure is not subject to any restriction on the number of variables. Algorithmic processes form the basis for the automatic minimization of Boolean functions using software (e.g. synthesis in ASIC design).
In all processes, only functions with one output variable can be simplified. Methods with which functions with several output variables can be optimized are mostly based on the above methods.

Measurand to determine the complexity of a switching function to be implemented is the Effort number AZ:

AZ = total number of all required gate inputs

The rule here is that the input variables are always available in inverted as well as in their own form.

The following example comes from the "cube decoder" from the previous chapter. The DNF version was for a:

a = (¬x3 ∧ x2 ∧ x1) ∨ (x3 ∧ ¬x2 ∧ ¬x1) ∨ (x3 ∧ ¬x2 ∧ x1) AZ = (3 + 3 + 3) + 3 = 12 and-gates or-gates The minimized The form was: a = (x1 * x2) + x3 AZ = 3 For all minimization methods, the reduction rule is applied (from the theorems), which is sometimes also called the "neighborhood rule" (in the case of minimization by means of the theorems, understandably, all theorems are more or less in use):
(A ∧ B) ∨ (A ∧ ¬B) = A
(A ∨ B) ∧ (A ∨ ¬B) = A

5.2 Minimization with the theorems

Transform the given equations with the theorems for Boolean equations until a minimal form is achieved. Mainly the o. A. Reduction rule and De Morgan's theorems are used. The procedure often requires trial and error and an intuitive approach and is usually only useful if the possibility of minimizing it is relatively obvious.

The procedure can be demonstrated using an example. The equation y = Σ (1,3,4,6,7) is given for three input variables (x3, x2, x1). The representation as DNF reads:

y = (¬x3 ∧ ¬x2 ∧ x1) d1 ∨ (¬x3 ∧ x2 ∧ x1) d3 ∨ (x3 ∧ ¬x2 ∧ ¬x1) d4 ∨ (x3 ∧ x2 ∧ ¬x1) d6 ∨ (x3 ∧ x2 ∧ x1 ) d7 The effort figure is: AZ = 5 * 3 + 5 = 20

The truncation rule can be applied to d1 and d3 because x2 occurs in negated and eigenform (and the other terms are identical):

(¬x3 ∧ ¬x2 ∧ x1) ∨ (¬x3 ∧ x2 ∧ x1) = (¬x3 ∧ x1) Likewise, d6 and d7 can be shortened, since x1 occurs negated and not negated: (x3 ∧ x2 ∧ ¬x1) ∨ (x3 ∧ x2 ∧ x1) = (x3 ∧ x2) In summary: y = (¬x3 ∧ x1) ∨ (x3 ∧ ¬x2 ∧ ¬x1) ∨ (x3 ∧ x2) The number of efforts is now: AZ = 2 + 3 + 2 + 3 = 10, so it is only half the size. This can also be seen well if you draw the circuit for both solutions:

Example 2: Simplify the disjunctive form

y = (¬a ∧ b ∧ c) ∨ (a ∧ c) ∨ (a ∧ ¬b ∧ ¬c) Trick! First expand with: y = (¬a ∧ b ∧ c) ∨ (a ∧ b ∧ c) ∨ (a ∧ ¬b ∧ c) ∨ (a ∧ ¬b ∧ ¬c) = ((¬a ∨ a) ∧ b ∧ c) ∨ (a ∧ ¬b ∧ (c ∨ ¬c)) = (b ∧ c) ∨ (a ∧ ¬b) Example 3: Simplify DNF y = (¬a ∧ ¬b ∧ c) ∨ (¬ a ∧ b ∧ ¬c) ∨ (a ∧ ¬b ∧ ¬c) ∨ (a ∧ ¬b ∧ c) ∨ (a ∧ b ∧ ¬c) Rearranging (associative law) and "doubling" (expansion law) results in: y = (¬a ∧ ¬b ∧ c) ∨ (a ∧ ¬b ∧ c) ∨ (¬a ∧ b ∧ ¬c) ∨ (a ∧ b ∧ ¬c) ∨ (a ∧ b ∧ ¬c) ∨ (a ∧ ¬b ∧ ¬c) = ((a or ¬a) ∧ ¬b ∧ c) ∨ ((a or ¬a) ∧ b ∧ ¬c) ∨ ((b ∨ ¬b) ∧ a ∧ ¬c) = (¬b ∧ c) ∨ (b ∧ ¬c) ∨ (a ∧ ¬c) = ((a ∨ b) ∧ c) ∨ (¬b ∧ c) If EXOR is allowed in addition to AND and OR, the following alternative is possible possible: y = (b ⊕ c) ∨ (a ∧ ¬c) Example 4: Simplify CNF y = (a ∨ b ∨ c) ∧ (a ∨ ¬b ∨ ¬c) ∧ (¬a ∨ ¬b ∨ ¬c ) = (a ∨ b ∨ c) ∧ ((a ∧ ¬a) ∨ ¬b ∨ ¬c) = (a ∨ b ∨ c) ∧ (¬b ∨ ¬c) The examples already show that a simplification with the Theorems is relatively difficult, even with small expressions, because you don't always know s, which of the theorems should be applied, whether an extension leads to simplification in later steps and whether the result obtained is actually the minimal form.

5.3 Graphic minimization method according to Karnaugh-Veitch

A Karnaugh-Veitch diagram (KV diagram) is a multidimensional graphical representation of a function in which neighboring cells differ only with regard to one input variable (combinatorial neighborhood). Certain quantities of small squares labeled with "1" are bundled (fused) by contours, which can also penetrate one another. The particular benefit is that the merging usually results in simpler or shorter functional representations. The KV diagram is therefore very suitable for simplifying logic circuits with up to five input variables and one output variable. The truth table is divided into a rectangle with 2n Fields (n = number of input variables).

Terms:

So far the following have been introduced:
  • Minterm: full conjunction
  • Maxterm: full disjunction
  • Primterm: In the sense of the abbreviation rule, conjunction / disjunction that can no longer be minimized
New are now added:
  • Implicit: A function y is an implicant of a function z if: y = 1 → z = 1
    In the DNF of a function z, every full conjunction is an implicant of z.
  • Prime implicant (PI): Implicant that cannot be further minimized in the sense of the reduction rule. A block of 1 fields selected as large as possible in the KV diagram.
  • Core prime implicand: If a prime implicand contains at least one full conjunction that is not contained in any other prime implicand, one speaks of a core prime implicand (also called "essential PI). The minimal solution contains at least all essential PIs.
  • Redundant PI:Non-essential PI that are completely covered by core PI (i.e. are superfluous).
With the KV diagram, you can think of it as follows:

The KV diagram has the following features:

  • Graphical representation of the truth table (see above)
  • Square or rectangle that is divided into as many fields as full conjunctions / full disjunctions of the input variables are possible. Each field is 'addressable' through its full conjunction / full disjunction.
  • Half of all fields are assigned to each variable as the area of ​​validity.
  • Adjacent fields each differ in one variable → combinatorial neighborhood.

construction

  • A KV diagram for n input variables has 2n Fields
  • The KV diagram is labeled with the variables on the edges.
    • Each variable occurs in negated and non-negated form.
    • The assignment of the variables to the individual fields can be done in any way, however
    • horizontally and vertically adjacent fields may only differ in exactly one variable.
  • The individual fields are filled with the help of the truth table of the function to be optimized:
    • A 1 is entered if there is a minterm of the function,
    • otherwise a 0 is entered.

The KV diagrams are formed inductively by mirroring: To generate the KV diagram for n-dimensional functions, the KV diagram for (m – 1) -dimensional functions is doubled by mirroring. The new variable that is added has the value 0 in the old table and the value 1 in the new half of the new table.

The box numbers are the decimal numbers for the binary numbers (xn ... x0) in the "No." column of the respective truth table. So you can see that a KV diagram shows the content of the truth table in a different form.

Normally the designation of the negated variables is left out, so only X0, X1, x2 etc. are listed. In many publications, the range of the variable is also marked by a line parallel to the edge of the KV diagram, as the following example shows:

The KV diagrams are also axially symmetrical, so that KV diagrams that look different but are identical in content may result. The only important thing is the assignment of the fields to the respective input variables. The following figure shows an alternative to the arrangement above.

The most important thing is abolute care when filling out the KV diagram. Two examples with two input variables each:

As a rule, when minimizing a DNF, only the fields filled with "1" are labeled (Minterme), since - as will be shown below - only these fields can be used for simplification. In the next example, the KV diagram is filled based on the truth table (the field numbers are entered again for a better overview):

However, the switching function can also be assumed as the short form of DNF (or KNF). The KV diagram above could also be derived from the equation Y (x2, x1, x0) = Σ (2,3,6,7) emerge. If you have a template in which the decimal numbering is entered, as in the KV diagrams above, it is even much easier than with the truth table.

Graphic minimization with KV diagrams

KV diagrams from the disjunctive normal form (DNF) or from disjunctive forms

Two logical expressions that only differ in one variable can be combined into one term:
(x1 ∧ ¬x2) ∨ (x1 ∧ x2) = x1

Combinationally adjacent minter terms ("1" fields) in the KV diagram also only differ in one variable each and can therefore be combined to form a superordinate expression. Fewer input variables are required for the representation of the resulting implicit (by applying the abbreviation rule, the input variable, which is present both in eigenform and inverted, is always omitted). Two neighboring "pairs" can be combined again and so on. So there is a reduction by ...

  • 1 input variable: combine 2 adjacent fields
  • 2 input variables: combine 4 adjacent fields
  • 3 input variables: combine 8 adjacent fields
  • etc.
Therefore, as many fields as possible are always combined, which results in the shortest possible formulas (i.e. few variables) for the implicants. The procedure is then as follows:

In the first step the truth table is transferred to the KV diagram and in the second step rectangles are formed, e.g. B .:

In the third step, the simplified function equation is created, whereby a formula can be specified for each rectangle based on the coordinate designations. As already mentioned, there are variables which inverse and not inverse occur (in single form), omitted.

The following applies to the example in the picture above:

  • The variables B and ¬B appear together in the vertical rectangle and are therefore omitted:
    (A ∧ B) ∨ (A ∧ ¬B) = A ∨ (B ∧ ¬B) = A ∧ (1) = A
  • In the horizontal rectangle, A and ¬A appear together and are therefore omitted.
    (A ∧ B) ∨ (¬A ∧ B) = B ∧ (A ∨ ¬A) = B ∧ (1) = B
  • The simplified formula is: Y = A ∨ B

Rules for group formation

  • Adjacent fields in which a one is entered are combined into groups.
  • A group cannot contain any fields with zeros. (Often the zeros are not recorded and the fields are left blank. In this case, a group must not contain any empty fields.)
  • All ones must be grouped together.
  • Adjacent fields with ones are grouped together. (Fields that touch diagonally at the corners do not count as adjacent.
  • The groups must be as large as possible.
  • As few groups as possible have to be formed.
  • No group may be completely enclosed by another group.
  • The groups may only have a size that corresponds to a power of two (1, 2, 4, 8, 16, 32, 64).
  • The groups must be rectangular blocks.
  • The groups are allowed to overlap.
  • The groups are allowed to go over the edges. (In the case of KV diagrams with 3 variables, the right and left edges are adjacent, and in the case of KV tables with 4 variables, the top and bottom edge are also adjacent.)
  • Two groups cannot contain exactly the same ones. → The groups may overlap; if they overlap completely, the group (s) are superfluous.
  • The reduced formula is the result of an OR link between the individual "rectangular formulas".

Summary: One looks for a complete covering of the ones with the largest possible rectangular blocks.

Example: y = (¬a ∧ b ∧ c) ∨ (a ∧ c) ∨ (a ∧ ¬b ∧ ¬c)
To get the DNF, the middle term has to be expanded: (a ∧ c) = (a ∧ b ∧ c) ∨ (a ∧ ¬b ∧ c)

The four minterms are entered as "1" in the KV diagram:
¬a ∧ b ∧ c
a ∧ b ∧ c
a ∧ ¬b ∧ c
a ∧ ¬b ∧ ¬c

There are three prime implicants: (a ∧ c), (a ∧ ¬b) and (b ∧ c).

But since the red prime implicant (a ∧ c) is completely covered by the other two, it is no longer necessary and the final solution is:
y = (a ∧ ¬b) ∨ (b ∧ c)

So we remember:

  • All prime terms as well as the isolated "1" fields are disjunctively linked:
    minimized disjunctive form (MDF)
  • There can be several equivalent MDFs for one switching function

Example: Instead of a formula, a truth table is given. Based on this, the corresponding fields are first filled in with "1" and then the prime terms are determined:

The MDF is: Y = ¬X1 ∨ (¬X0 ∧ X2)

As already said, when combining adjacent fields, it is important to form blocks as large as possible. The larger the block, the easier the switching function. Each field filled with a "1" must be recorded. The following figure shows examples of combining mintermen in KV diagrams using blocks of two, four and eight:

The following example shows that not only can several equivalent MDFs be used, but also - if you are not careful - unfavorable combinations can result. The following figure shows two KV diagrams for the truth table next to it. The upper KV diagram requires five minterms and has 1 group of four, three groups of two and one group of ones.

The lower KV diagram (correctly) summarizes the green and purple groups of two over the edges to form another group of four (shown in red in the lower KV diagram).Likewise, the group of ones "over the edge" becomes a group of two (orange).

This then results in the MDF: Y = (¬X2 ∧ X3) ∨ (¬X1 ∧ X3) ∨ (¬X0 ∧ X1 ∧ ¬X3)

There are also special cases: Some functions have no core prime implicants. For other functions, no minter terms / max terms can be combined, so they cannot be minimized. The following figure shows a function without kernel prime implicants on the left and a function that cannot be minimized on the right:

KV diagrams from the conjunctive normal form (CNF) or from conjunctive forms

DNF and KNF are two completely equivalent ways of realizing a switching algebraic expression. Just like the DNF to the MDF, the KNF of the same switching function can be minimized to the minimized conjunctive form. Both minimized forms are equally equivalent in their logical truth content; but not in their minimization result.

In principle, the procedure is the same as for the disjunctive forms, only the Zeros considered instead of the ones. One looks for conjunctive terms (implicates) by considering maxterms and their possible summary:

  1. Summary of the largest possible blocks of zeros, with each block again 2k Fields must include
    → form the disjunctive minimal form for the inverse function ¬Y
    → prime implicates
  2. Selection of a minimal number of prime implicates (core prime implicates and further prime implicates).
    → minimal conjunctive form (MKF)
There is another special feature when reading the terms for the "0" blocks: In order to get the disjunctive sum term, the variables in which the block is linked are linked Not is disjunctive with each other. The "0" blocks denote the fields in which Y = 0 (i.e. ¬Y = 1). Hence the inversion.
→ Application of De-Morgan's rule results in the conjunctive minimal form of the original function Y.
But you can also, as in the following example, form minterms from the "0" groups and then invert this using DeMorgan.

The following example illustrates the procedure:

The minterms on the right are used to combine the fields into groups. In order to arrive at maxterms starting from this, DeMorgan's theorem has to be applied:

¬I1 = X3 ∨ X0
¬I2 = X3 ∨ ¬X2
¬I3 = X2 ∨ ¬X1 ∨ X0
¬I4 = ¬X2 ∨ X1 ∨ X0

So the overall result is:

Y = ¬I1 ∧ ¬I2 ∧ ¬I3 ∧ ¬I4
Y = (X3 ∨ X0) ∧ (X3 ∨ ¬X2) ∧ (X2 ∨ ¬X1 ∨ X0) ∧ (¬X2 ∨ X1 ∨ X0)

Another example:
The truth table has already been transferred to the KV diagram and the groups are already marked. This time the max terms should be determined directly from the KV diagram:


The following maxterms result:
¬X0 ∨ X2
¬X2 ∨ X3
¬X1 ∨ X2 ∨ ¬X3

The overall result is:
Y = (¬X0 ∨ X2) ∧ (¬X2 ∨ X3) ∧ (¬X1 ∨ X2 ∨ ¬X3)

Minimizing incompletely defined functions

If not all value combinations of the variables are always defined in a truth table ("any", "don't care"), then one speaks of an incompletely defined function. If such fields are available, they can be interpreted as "0" or "1" as desired, which offers more possibilities for optimization in the simplifications. Such "arbitrarily" selectable values ​​are also called Parameter terms or P terms. For favorable minimization results, P-terms can be integrated into groups (i.e. P = 1). Groups that only consist of P-terms are nonsense. So the following applies:
The undefined function values ​​(P terms) are entered as "X" in a truth table and in the KV diagram.

"X" terms can be viewed as either "0" or "1" in the KV diagram. This allows more optimal blocks to be formed.

The following example shows the use of the P-terms for grouping. Without using the P-terms, two groups of two and one group of ones would result. The resulting formula would then be: Y = (X1 ∧ ¬X2 ∧ ¬X3) ∨ (¬X0 ∧ X1 ∧ X2) ∨ (X0 ∧ ¬X1 ∧ ¬X2 ∧ X3). The effort figure is: AZ = 3 + 3 + 4 + 3 = 13.


Using the P-terms, we get:

Y = (X1 ∧ ¬X3) ∨ (X0 ∧ ¬X2) ∨ (X1 ∧ X2)

with AZ = 2 + 2 + 2 + 3 = 9

KV diagram for 5 variables

Below you can see the representation of the KV diagram for 5 variables. The following rules apply to "neighborhood relationships":
  1. As before: horizontally and vertically adjacent cells are considered to be adjacent and can be combined if necessary (do not forget the torus topology over the edge).
  2. Cells that are at reflection fall on the straight line g are also adjacent (e.g. 4 and 20 or 7 and 23).

Representation and generation of codes with KV diagrams

  • Each code word corresponds to a field in the KV diagram.
  • The characters represented by the corresponding code words are entered in the individual fields of the KV diagram.
  • Particularly suitable for the construction of one-step codes.
Example: Glixon Code

Enter a DF and expand it to DNF / KNF


Example: W (D, C, B, A) = (¬B ∧ A) ∨ (D ∧ C ∧ A)

DNF:

(¬D ∧ ¬C ∧ ¬B ∧ A) ∨ (¬D ∧ C ∧ ¬B ∧ A) ∨ (D ∧ ¬C ∧ ¬B ∧ A) ∨ (D ∧ C ∧ ¬B ∧ A) ∨ (D ∧ C ∧ ¬B ∧ A) ∨ (D ∧ C ∧ B ∧ A) The KNF can be "read out" in the same way.

Another effect is the knowledge that the specified DF is not minimal. The MDF is:
W (D, C, B, A) = (¬B ∧ A) ∨ (D ∧ A)

The graphic minimization with the help of a KV diagram can theoretically be carried out for any number of input variables. If there are five or more input variables, the analysis of the collectable fields becomes too complicated due to the increasingly complex neighborhood relationships. Therefore, KV diagrams are suitable for minimizing functions with up to five input variables.

5.4 Quine-McCluskey tabular procedure

Since the simplification of Boolean functions via the KV diagram is only possible by hand, the method presented here (named after the inventors) was developed using a computer to solve this problem. It is less clear than the KV diagram, but can be carried out automatically. The Quine and McCluskey method (QMC method) is also based on the reduction rule:
(A ∧ B) ∨ (A ∧ ¬B) = A
(A ∨ B) ∧ (A ∨ ¬B) = A

So it works on the same principle as the KV diagrams. Only those terms are considered for which the Boolean function results in "1". Such terms that differ in only one variable are grouped together. The starting point is usually the truth table of a function. In contrast to the KV diagrams, however, the following applies:

  • Use of tables instead of graphics
  • Suitable for any number of variables
  • Suitable for computer use, algorithmically writable
In this method, the minterms of the disjunctive normal form are systematically compared with one another in order to eliminate variables with the relationship (A ∨ ¬A) = 1. In order to find such relationships, the minter terms are combined in groups, which are ordered according to the number of "1" values ​​of the variables. To find simplifications, successive groups are compared with one another.

The computation of the disjunctive minimal form with the QMC method is carried out as follows:

  1. Draw up a table of all minterms
  2. Combine lines that differ only in one variable
  3. Continue merging lines until all prime implicants are found
  4. Creation of a new table of prime implicants
  5. Identification of the core primary implicants → add to the minimal form
  6. Add further prime implicants until all minterms are covered

First the table of all minterms is set up, in which the minterms are entered sorted according to groups, the groups being sorted according to the number of ones in ascending order. So

  • Group 1: All minterms with all zeros
  • Group 2: All minterms with 1 one
  • Group 3: All minterms with 2 ones
  • Group 4: All minterms with 3 ones
  • ...
  • Group n: All minterms with all ones
Now all terms of group m are compared with all terms of group m + 1. Do both terms differ? only in one variable, the two terms can be combined. The two terms are marked as "used" in the table and the term is entered in a second table, with the omitted variable being marked with "-". If a term could not be used, it forms a prime implicate for later processing (marked with "*").

The second table created in this way is handled in the same way and a third table is created and so on. The iteration ends when no more terms can be combined. When combining, it can happen that the same expressions arise several times. In such cases, all but one "duplicates" are deleted.

Now the list of the prime implicants takes place (all terms marked with "*"), from which a minimal form can be created. Often there are further simplifications by covering some terms.

Simplification of writing: For a simple tabular treatment one writes for a variable in a conjunction term:

1if the variable not inverted occurs,
0if the variable inverted occurs and
-if the variable no longer occurs.

example

The following Boolean function is given:
f (a, b, c) = Σ (0,2,4,5,6)
    1. Table or list: Group decimal a b c ok 1 0 0 0 0 x 2 2 0 1 0 x 4 1 0 0 x 3 5 1 0 1 x 6 1 1 0 x 2. Table or list: Group decimal a b c ok 1 0.2 0 - 0x 0.4 - 0 0 x 2 2.6 - 1 0 x 4.5 1 0 - P1 4.6 1 - 0x 3. Table or list: Group decimal a b c ok 1 0,2,4,6 - - 0 P2 1 0,4,2,6 - - 0
An "x" is entered in the "ok" column if the term was used for an entry in the following table. Otherwise it is a prime term (P1, P2).

The 1st list is filled from the DNF, the 2nd list is created by combining the terms from the 1st list and the 3rd list accordingly from the 2nd list:

  • 1st list → 2nd list:
    The comparison of all terms from group 1 with all terms from group 2 (0 with 2, 0 with 4) gives (0.2) and (0.4). The comparison of all terms of group 2 with group 3 gives (2,6), (4,5) and (4,6).
  • 2nd list → 3rd list:
    Remember: the "-" is treated like "0" or "1" and must also be in the same place for both terms. Here, too, only the terms that differ in only one variable are compared, i.e. (0.2) with (4.6) and (0.4) with (2.6). So there remains a prime implicant (4,5).
  • 3. List:
    No further summaries are possible. However, the two entries (0,2,4,6) and (0,4,2,6) represent the same full conjunctions → both times result in the same term "", so one line can be deleted.
  • The MDF results from the remaining terms P1 "" and P2 ": f (a, b, c) = (a ∧ ¬b) ∨ ¬c.

However, the case can also arise that the disjunctive form found according to the above scheme is not yet minimal. Under certain circumstances, further prime implicants can be deleted from the minimum sentence. This is possible if the minterms of a prime implicant are completely covered by the other prime implicants. Here is an example:

The function y = Σ (0,4,5,7) leads to the prime implicants according to the above procedure:
a ∧ c
a ∧ ¬b
¬b ∧ ¬c

These prime implicants are now compared to the minterms in a table:

PI 0 4 5 7 Minterme a ∧ c x x a ∧ ¬b x x ¬b ∧ ¬c x x One recognizes immediately that the middle prime implicant (a ∧ ¬b) can be omitted because its minterms are covered by the others (4 by the first, 5 by the third). This then results in MDF: y = (a ∧ c) ∨ (¬b ∧ ¬c). On the other hand, the other two prime implicants are necessary, since Minterm 0 is only covered by the first and Minterm 7 only by the third prime implicant.

When selecting the minimum theorem from the prime implicants, proceed as follows:

  1. Structure of the coverage matrix
    • the prime implicants are plotted in the rows
    • all minterms or their decimal numbers are entered in the columns
    • the intersection points are marked with "x" if the primary liqueur covers the corresponding minterm.
  2. Selection of the minimum rate
    Every occurring minterm (or its decimal number) must be covered by a prime implicant.
    • Search for all prime implicants in which there is only a single "x" in one of the columns → essential prime implicants or Core prime implicants.
    • Then mark which minterms are covered by the essential prime implicants and look for a minimal sentence → column elimination. Thinking aid: The "x" in a column can be viewed as an OR-linked.
    Subsequently, prime implicants that are no longer required can be eliminated → row elimination → a smaller matrix is ​​created.
If all columns are marked, the MDF results from the OR operation of all core primitives.

If this is not the case, the unmarked prime terms and the not yet used minter terms are entered in a second, smaller scheme. If this scheme contains lines without markings, these can also be omitted.

Furthermore, columns can be deleted if there are one or more other columns that have fewer markings than the column under consideration and these markings only appear in the same rows.

Through these steps, an even more simplified scheme arises, on the basis of which the most favorable selection from the remaining prime implicants can be made, taking into account the respective expenditure figures. It must be ensured that all minterms are recorded.

The MDF is formed by ORing the core primary implicants and the selected primary implicants.

Example: Given is the function Y = f (x1, x2, x3, x4) = Σ (0,4,6,11,12,13,14)

1. List:

Group decimal dual ok 1 0 0000 x 2 4 0 100 x 3 6 0 110 x 12 1100 x 4 11 1011 P1 13 1101 x 14 1110 x 2. List: Group decimal dual ok 1 0.4 0-00 P2 2 4.6 01-0 x 4.12 -100 x 3 6.14-110 x 12.13 110- P3 12.14 11-0 x 3. List: Group decimal dual ok 1 4,6,12,14 -1-0 P4 4,12,6,14 -1-0 → End of creating the coverage matrix:
(The core primary implicants are marked with "*" - just an "x" in the column.) Primimp. 0 4 6 11 12 13 14 Minterme P1 * P2 * x P3 x * P4 x x x * The following columns can be eliminated:
Gap covered by 4 0 and 6 12 6 and 13 14 6 The smaller matrix: Primimp. 0 6 11 13 Minterme P1 * P2 * P3 * P4 * Unfortunately, no prime implicant can be eliminated. It turns out the MDF as
Y = P1 ∨ P2 ∨ P3 ∨ P4 =
(x1 ∧ ¬x2 ∧ x3 ∧ x4) ∨ (¬x1 ∧ ¬x3 ∧ ¬x4) ∨ (x1 ∧ x2 ∧ ¬x3) ∨ (x2 ∧ ¬x4)

Example: Given is the function Y = f (x1, x2, x3, x4, x5) = Σ (2,4,5,6,10,12,13,14,18,22,26,30)

1. List:

Group decimal dual ok 1 2 00010 x 4 00 100 x 2 5 00 101 x 6 00 110 x 10 01 010 x 12 01 100 x 18 10010 x 3 13 01 101 x 14 01 110 x 22 10 110 x 26 11010 x 4 30 11 110 x 2. List: Group decimal dual ok 1 2.6 00-10 x 2.10 0-010 x 2.18 -0010 x 4.5 0010- x 4.6 001-0 x 4.12 0-100 x 2 5.13 0-101 x 6.14 0-110 x 6.22 -0110 x 10.14 01-10 x 10.26 -1010 x 12.13 0110- x 12.14 011-0 x 18.22 10-10 x 18.26 1-010 x 3 14.30 -1110 x 22.30 1-110 x 26.30 11-10 x 3. List: Group decimal dual ok 1 2,6,10,14 0-10 x 2,6,18,22 -0-10 x 2,10,18,26 --010 x 4,5,12,13 0-10- P1 4,6,12,14 0-1-0 P2 2 6,14,22,30 --110 x 10,14,26,30 -1-10 x 18,22,26,30 1--10 x 4. List: Group decimal dual ok 1 2,6,10,14 --- 10 P3 18,22,26,30 Setting up the coverage matrix: 2 4 5 6 10 12 13 14 18 22 26 30 P1 x * x * P2 x x x x P3 * x * x * * * * P1 is the core prime implicant (5, 13), as is P3 (2, 18 - 30). Columns 4, 12 and 13 can be eliminated (P1), as can columns 6, 10, 14, 18, 22, 26 and 30 (P3). The result is the reduced matrix: 2 5 P1 * P2 P3 * The line at P2 is empty → P2 can be omitted. The result is the MDF: Y = (¬x2 ∧ x3 ∧ ¬x5) ∨ (¬x1 ∧ x2).

Functions with any values, MKF

The procedure for minimizing incompletely defined functions is analogous to the treatment of fully defined functions. Here it is initially assumed that the function assumes the value "1" wherever it is not defined (any value, P-term). This allows as many terms as possible to be combined.

In the subsequent table of prime implicants, however, only the actual minterms of the function are taken into account. The P-terms must not be included in the table of prime implicants.

Similar to minimizing with the KV diagram, with the QMC method you can first determine the MDF of the inverse function and then obtain the MKF by negating it.

5.5 Supplements

Bundle of functions

So far, only cases have been considered in which input variables were linked to a single switching function. Often, however, several switching functions are formed from a group of input variables. For example, if a decoder is to be designed from 8-4-2-1-BCD to decimal, it has four inputs and ten outputs.

Circuits with multiple outputs will be Bundle of functions called. Each output is described by a Boolean function, so it can also be minimized in terms of circuitry if necessary.

In such cases, it is possible that certain partial links (groups, prime terms, core prime implicants) occur not only in one function, but also in several functions. Of course, such partial links do not have to be set up multiple times, but are implemented once and used multiple times.

These jointly usable links can be identified:

  • in the KV diagram by common groups and
  • in the QMC method by common terms.

Example: A bundle of two functions is given:
Y (x3, x2, x1, x0) = Σ (5,7,8,9,10,11,13,15)
Z (x3, x2, x1, x0) = Σ (0,1,5,6,7,8,9,13,14,15)

If you look at the KV diagrams for both functions, you immediately see a group (shown in blue) that both functions have in common: x0 ∧ x2. So we can formulate:

  • M = x0 ∧ x2
  • Y = (¬x2 ∧ x3) ∨ M
  • Z = (x1 ∧ x2) ∨ (¬x1 ∧ ¬x2) ∨ M

Example: A bundle of two functions is given:
Y (x3, x2, x1, x0) = Σ (2,3,6,7,10,11)
Z (x3, x2, x1, x0) = Σ (0,6,7) with the P-terms: 1,8,9

If you look at the KV diagrams for both functions, a summary of the four adjacent ones would be appropriate for Y (upper half of green + purple). However, if you consider both functions, you can depart from the single optimum at Y and thus gain a common term (purple). It then results:

  • M = x1 ∧ x2 ∧ ¬x3
  • Y = (x1 ∧ ¬x2) ∨ M
  • Z = (¬x1 ¬x2) ∨ M

Certain gate types do not exist

(or not wanted)
  1. Only NAND gate available:
    DF can only be implemented using NAND without additional effort: → NAND-NAND sequence
    Y = (x1 ∧ x2) ∨ (x3 ∧ x4) → ¬ [¬ (x1 ∧ x2) ∧ ¬ (x3 ∧ x4)]
  2. Only NOR gate available:
    KF can only be implemented with NOR without additional effort: → NOR-NOR sequence
    Y = (x1 ∨ x2) ∧ (x3 ∨ x4) → ¬ [¬ (x1 ∨ x2) ∨ ¬ (x3 ∨ x4)]

    5.6 exercises

    Exercises to minimize KV

    1. The switching function w (x2, x1, x0) always has the value 1 if two or more input variables have the value 1.
    1. Establish the truth table for w
    2. Enter the DNF of the switching function w
    3. Determine the MDF using the KV diagram
    4. Simplify this MDF even further using the logic theorems
    5. Sketch the logic diagram for the solutions according to c) and d)
    6. How do the solutions according to c) and d) differ in terms of effort?

    2. Minimize the following switching functions using the KV diagram:

    1. y (x2, x1, x0) = Σ (0,1,3,4,5,6)
    2. y (x3, x2, x1, x0) = Σ (0,1,2,3,5,7,8,9,10,11,12,15)

    3. The switching function is given

    y (x3, x2, x1, x0) = (x3 ∧ ¬x2) ∨ (¬x3 ∧ ¬x1) ∨ (¬x2 ∧ x0) ∨ (x1 ∧ x0)

    1. Enter the switching function in the KV diagram
    2. Use the KV diagram to check whether the given shape is minimal and, if necessary, indicate the MDF
    3. Enter the DNF like KNF in short notation

    4. A switching function of four variables assumes the value 1 for the minter terms k2, k4, k6, k12, k13, k14, k15. The input combinations of the terms k5, k9, k10 can never appear (P-terms).

    1. Enter the MDF of the function
    2. Also determine the MCF of the function

    5. The switching function is given

    y (x3, x2, x1, x0) = Σ (8,9,10,12,13,14)

    1. Determine the MDF of the function
    2. Also determine the MKF of this function
    3. Determine the form of the lower implementation effort and draw your logic diagram.

    solutions

    1st task
    1. w: lines 3,5,6,7: 1
    2. w = Σ (3,5,6,7)
    3. w = (x2 ∧ x1) ∨ (x2 ∧ x0) ∨ (x1 ∧ x0)
    4. w = [x1 ∧ (x2 ∨ x0)] (∨ x2 ∧ x0) or
      w = [x2 ∧ (x1 ∨ x0) ∨ (x1 ∧ x0) or
      w = [x0 ∧ (x1 ∨ x2) ∨ (x1 ∧ x2)
    5. to c: 3 x AND (2 inputs) in 1 x OR (3 inputs), 2 gate levels
      after d: 1 x OR fed into 1 x AND, parallel 1 x AND, both in 1 x OR, 3 gate levels
    6. after c: AZ = 9, after d: AZ = 8

    2nd task

    1. y = ¬x1 ∨ (x2 ∧ x0) ∨ (x2 ∧ x0)
    2. y = x2 ∨ (x3 ∧ x0) ∨ (x1 ∧ x0) ∨ (x3 ∧ ¬x1 ∧ ¬x0)

    3rd task

    1. -
    2. minimal form: y = (x3 ∧ ¬x1) ∨ (x1 ∧ x0) ∨ (x3 ∧ ¬x2)
    3. DNF: y = Σ (0,1,3,4,5,7,8,9,10,11,15)
      KNF: y = Π (2,6,12,13,14)

    4th task

    1. MDF: Y (x3, x2, x1, x0) = (x1 ∧ x0) ∨ (x3 ∧ x2) ∨ (x2 ∧ ¬x1)
    2. MKF: Y (x3, x2, x1, x0) = (x3 ∨ x2) ∧ (x3 ∨ ¬x0) ∧ (x2 ∨ x1) or
      Y (x3, x2, x1, x0) = (x2 ∨ ¬x0) ∧ (x3 ∨ ¬x0) ∧ (x2 ∨ x1)

    5th task

    1. MDF: Y (x3, x2, x1, x0) = (x3 ∧ ¬x1) ∨ (x3 ∧ ¬x0)
    2. MKF: Y (x3, x2, x1, x0) = x3 ∧ (¬x1 ∨ ¬x0)
    3. a: AZ = 6, b: AZ = 4

    QMC minimization exercises

    1. The following function Y is given:
    Y (x3, x2, x1, x0) = Σ (1,3,6,7,8,9,12,13,15)
    1. Identify an MDF using the QMC method
    2. Compare the results with the minimization in the KV diagram

    2. The function Z is given:
    Z (x3, x2, x1, x0) = Σ (0,2,4,8,9,13) with the P-terms 1,3,6,11,12 and 15

    1. Use the QMC method to determine an MDF of Z
    2. Now determine the MCF of Z by first applying the QMC method to the inverse function of Z and then negating the result
    3. Determine the MKF by now performing the QMC procedure with the maxterms.

    solution

    1st task
    1. Two equivalent MDF:
      Y = (x3 ∧ x2 ∧ x1) ∨ (x3 ∧ x1) ∨ (x3 ∧ x2 ∧ x0) ∨ (x2 ∧ x1)
      Y = (¬x3 ∧ x2 ∧ x1) ∨ (x3 ∧ ¬x1) ∨ (¬x3 ∧ ¬x2 ∧ x0) ∨ (x3 ∧ x2)
    2. Entering DNF in the KV diagram gives the same results

    2nd task

    1. MDF: Z = (¬x3 ∧ ¬x0) ∨ (x3 ∧ ¬x1)
    2. ¬Z = (¬x3 ∧ x0) ∨ (x3 ∧ x1) → Z = (x3 ∨ ¬x0) ∧ (¬x3 ∨ ¬x1)
    3. according to the information from the lecture:
      negated variable: → 1
      non-negated variable: → 0
      non-existent variable: → -
      results in identical tables as in b) and after corresponding "back translation" directly the MKF

    Exercises to minimize

    1. Determine the MDF of the following bundles of functions and pay attention to the possibility of multiple use when specifying the circuit to be implemented.
    1. y (x2, x1, x0) = (1,3,6,7), P-term: 0
      z (x2, x1, x0) = (0,2,6,7), P-term: 4
    2. y (x3, x2, x1, x0) = (4.11.15), P terms: 0, 1, 2, 6, 10
      z (x3, x2, x1, x0) = (0, 1, 4, 5, 11, 15), P-terms: 3.7

    2. Which logical structure is implemented by a NAND-NOR sequence (NOR combination of NAND operations)?

    3. The function w = (a ∧b) ∨ (c ∧ d) ∨ (e ∧ f) is to be realized:

    1. with AND gates and inverters
    2. with NAND gates
    3. with NAND gates with only 2 inputs

    solution

    1st task
    1. m = (x1 ∧ x2)
      y = (¬x2 ∧ x0) ∨ m
      z = ¬x0 ∨ m
    2. m = (x3 ∧ x1 ∧ x0)
      y = (¬x3 ∧ ¬x0) ∨ m
      z = (¬x3 ∧ ¬x1) ∨ m

    2nd task:
    AND-AND sequence = AND link

    3rd task:


    Copyright © Munich University of Applied Sciences, FK 04, Prof. Jürgen Plate
    Last updated: Feb 09, 2013