Karnaugh map

The Karnaugh - Veitch - Diagram (or Karnaugh - Veitch - symmetry - diagram, the Karnaugh map or Karnaugh map ), short - KV diagram KVS diagram or K- chart (English Karnaugh map ) is used to clear presentation and simplification of Boolean functions in a minimal logical expression. It was designed in 1952 by Edward W. Veitch [vi ː tʃ ] and further developed in 1953 by Maurice Karnaugh [ kɑ ː ɹnɔ ː ] to its present form.

Properties

By means of a KV- diagram can be any disjunctive normal form ( DNF ) convert to a minimal disjunctive logical expression. The advantage over other methods is that the term generated (usually) is minimal. If the term is not to be minimal, a further simplification by applying the distributive law ( bracketing ) is possible. The conversion begins with the creation of a truth table, from which then the DNF is derived, which is then in turn converted directly into a KV diagram.

Since distinguish the neighboring fields associated minterms each in only one variable A by negation, is this (after factoring out the distributive law and application of A ∨ ¬ A = 1) from the term which describes the neighboring fields to be summarized eliminated. This rule is based reduction of the groups.

The inverse function is found by exchanging "1" and "0" in the KV- diagram.

A KV diagram is also useful to determine hazards and eliminate.

Filling out the KV diagram

Has a KV- map for n input variables 2n fields ( see example). The KV diagram is labeled with the variables at the edges. Here, each variable occurs in negated and non- negated form. The assignment of the variables on the individual fields can be carried out as desired, but it should be noted that horizontally and vertically adjacent fields may only differ in exactly one variable ( Gray code). Using the truth table of the function to be optimized is entered in each field a 1 if a minterm of the function exists, otherwise a 0 A minterm m of the function is deemed to exist if and only if

Where the vector of input variables. In disjunctive normal form, this applies to each of conjunction, provides 1, since then the Gesamtdisjunktion and thus also provides the function of 1.

KV- charts are useful for simplification of functions with a maximum of about 4-6 input variables; to 4 variables they are laid out.

Simplification

If there are fewer fields in the KV diagram with 1 being set to 0, just select the minterm method, otherwise the Maxterm method.

Minterm method

  • It tries its best to horizontally and vertically adjacent fields to summarize contains a 1 ( minterms ) to rectangular contiguous blocks ( packets ). As block size all powers of 2 are allowed (1, 2, 4, 8, 16, 32, ...). It all 1 fields must be recorded with blocks.
  • A block may be continued under certain circumstances on the right or bottom of the chart. This can be explained as follows: KV diagrams for three variables must be understood basically as a cylinder. The fields at left and right or up and down are thus adjacent. KV diagrams for four variables must be basically understood as a torus ( "donut - shape "); the four corners of the square drawn KV -diagram are adjacent. More complex neighborhood relations are valid for 5 or more variables. Since multidimensional structures are graphically difficult to handle, choose the representation in the plane, but then has to keep in mind the neighborhood relationships.
  • Of the identified blocks shall be selected so many that all 1- fields are covered. In many switching functions are all combined blocks, but it is not uncommon that there are alternatives. Then there is at the same large blocks free choice, otherwise the larger blocks are to be chosen, because they lead to the smaller (since more condensed ) terms.
  • The educated and selected blocks / pack one now transforms into of conjunction. Here are variables within a block occurring in negated and non- negated form, omitted.
  • This AND operations are combined by OR operations and result in a minimum disjunctive form.

Maxterm method

The Maxterm method differs from the minterm method only in the following points:

  • Zeros are grouped into packets instead of ones.
  • A packet of forms Disjunktionsterm ( OR links, instead of a Konjunktionsterms ).
  • The Disjunktionsterme be linked conjunctively ( with AND ).
  • The variables are also negated individually.

Ring -sum method

There is also the possibility of reading a so-called ring shape from a normal sum KV diagram. Here one has in principle the choice between the evaluation of ones or zeros. When evaluating the ones we group together the same to odd groups in the KV diagram mutually must not overlap. In evaluation of the zeros, however, it holds the same together to even-numbered groups, which may not overlap. In the event the evaluation of the terms are ones (comprising ANDed inputs ) then combined with the XOR, OR, and instead result in a minimal function. For evaluation of the zeros ( negated ) input variables with XOR instead of OR and these terms are then combined with AND. In both cases, the terms corresponding to the read from the KV diagram groups.

Do not care conditions

Often there are Boolean functions with truth tables, which need not be defined, a value of the output variable for each combination of input variables. They are called initial states Don't-Care -terms and is denoted by X, which can adapt to both the value of 1 and 0. This X - fields may be regarded as 0 or 1, to complete blocks of ones or zeros in the minterm or Maxterm method. A good example of this is the decoding of a binary coded decimal (BCD ). Here only play the numbers 0 to 9, a role that so-called pseudo tetrades may provide any result, so are Don't-Care -terms.

KV diagram with multiple outputs

If a digital circuit has multiple outputs, the truth table thus has multiple result columns, a private KV diagram must be created for each output.

For example, a 1-of- n decoder the adjacent truth table and its 4 outputs the four adjacent 4 KV diagrams.

Another example of a plurality of outputs is a 2 2 bit comparator. He has four input variables and three output variables. The number of A is composed of 2 bits ( and ) and the number B is composed of 2 bits (and). Depending on whether the " A B ", the three outputs ( X, Y, Z ) is a 1 or 0.

The corresponding truth table is right. The pictures 5-2 to 5-4 show the 3 KV diagrams for the three outputs.

Normal Forms

Usually groups for the ones to be formed ( Figure 6-2 ). The ones derived from the disjunctive normal form ( DNF ). But there is also the possibility to make matches of the zeros ( the zeros are not separately shown in Figure 6-1 and the following, but still present). The zeros represent the Conjunctive Normal Form (CNF ).

The DNF is: ¬ AB ¬ C ¬ D ∨ ¬ ¬ AB CD ABCD ∨ ∨ ¬ AB ¬ C ∨ ¬ D ¬ AB CD ABCD ∨.

The KNF is: (A ∨ B ∨ C ∨ D) ∧ (A ∨ B ∨ C ∨ ¬ D) ∧ (A ∨ B ∨ ¬ C ∨ D) ∧ (A ∨ B ∨ ¬ C ∨ ¬ D) ∧ (A ∨ ¬ B ∨ ¬ C ∨ D) ∧ ( ¬ A ∨ B ∨ C ∨ D) ∧ ( ¬ A ∨ B ∨ C ∨ ¬ D) ∧ ( ¬ A ∨ B ∨ ¬ C ∨ D) ∧ ( ¬ A ∨ B ∨ ¬ C ∨ ¬ D) ∧ ( ¬ A ∨ ¬ B ∨ ¬ C ∨ D).

The DNF is read from the table by each line is written to the output value of "one". The input variables for the zero is indicated, are taken in negated form. All the terms for the row (in this example 6 lines ) are connected by "∨ ".

For the KNF, all rows are written out with the output value " zero ", where input variables for a "one" is to be taken in negated form. All the terms for the row (in this example 10 lines) are connected by "∧", the literals themselves are connected by "∨ ".

Error in Figure 6-2: The minimal polynomial is: B ( D ∨ ¬ C) [ Since the two red boxes can be extended upwards towards a four - box, allowing more literals eliminated and the final minimal polynomial of length 4 (BD B ∨ ¬ C) is formed. Is important to note here that this indeed relevant two indexes are used several times, but this allows both, as is necessary to form the minimal.

Compact notation

A compact notation for a KV diagram ( Figure 7-1 ) shows the following example:

F = Σ (0, 3, 6, 7, 10, 11, 12, 14, 15 )

Starting (more precisely: Indexing - starting at frame 0 ) of a continuous numbering of fields, as shown in Figure 7-2, the numbers of the fields are listed in which a one is entered.

Regularities in reducing

By combining a group of size 2n is the logical expression reduces to n variables. This is irrespective of what kind of situation or form the group or if it reaches beyond the edges. This is also independent of whether it is a 2x2, 2x4, 4x4 or 4x4x4 KV diagram.

  • A group of eight (23 ) is reduced by 3 variables ( n = 3) - 9-1.
  • A group of four (22 ) is reduced by 2 variables ( n = 2) - Figure 9-2 and 9-3.
  • A group of two (21 ) is reduced by one variable ( n = 1) - Figure 9-4 and 9-5.
  • A One group ( 20) is reduced to zero variables ( n = 0) - Figure 9-6.

Rules for group formation

  • Adjacent fields in the a one is entered, are grouped together.
  • A group can not contain fields with zeros. ( The zeros are often not written, leaving the fields blank. In this case, a group must not contain any blank spaces. )
  • All ones must be grouped together.
  • Adjacent fields with ones are grouped together. ( Fields that touch at the corners, diagonal, do not count as adjacent. )
  • The groups must be as large as possible.
  • It must be formed so few groups as possible.
  • The groups may only have sizes that correspond to powers of two (1, 2, 4, 8, 16, 32, 64 ... ).
  • The groups must be rectangular blocks.
  • The groups may overlap.
  • The groups are allowed to pass over the edges.
  • Two groups may not comprise exactly the same ones.
  • There may be no group be completely enclosed by another group.

Summary: Man looking for a complete coverage of the ones with the largest possible rectangular blocks.

KV- tables for 2 and 4 variables

Who often works with the KV diagram, a method to be able to fill out a KV- chart quickly wishes.

This is shown in the above arrangement for the four input variables A, B, C and D obtained by the following arrangement:

  • Figure 3: Illustrates the logical values ​​of 16 fields; if you line by line the DNF transfers from a truth table in the KV diagram, then the entry is made in the order of red numbers
  • Figure 4: The red numbers facilitate the row-wise allocation of the truth table for the individual fields; the order depends on the specific labeling of the KV- diagram; the numbering is a way to simplify extensive use of Karnaugh maps

In this case, each field is assigned its value. At 4 signals, these are 16 entries:

0000 = 0 0001 = 1 0010 = 2, ..., 1110 = 14 1111 = 15

In this way the KV diagram can be completed very quickly. It is shown next to the above arrangements but also variations of the arrangement of the input variables A, B, C and D are possible. This other divisions of the values ​​in the matrix result.

Venn diagram

The Karnaugh - Veitch - diagram is a modified, abstract form of the quantity chart ( Venn diagram ).

Figures 1 to 4 show a Venn diagram and equivalent diagram of CT.

  • 2 variables

Figure 2: Venn diagram

  • 4 variables

Figure 4: Venn diagram

Figures 5 to 8 show once again the individual subsets, from which the Venn diagram composed in Figure 4.

  • 4 variables

Figure 6: subset in the Venn diagram

Figure 7: subset in the Venn diagram

Figure 8: subset in the Venn diagram

Illustration by hyper - unit cube

Boolean functions with n variables can be graphically illustrate by means of unit cubes of dimension n. Cubes of arbitrary dimension is also called hypercube. Since Karnaugh diagrams are a special form of representation for Boolean functions itself, it is not surprising that a clearer connection can be established between Hyper- unit cubes and Karnaugh diagrams. And although they meet Karnaugh diagrams for n variables biunique the Hyper- unit cubes of dimension n The corner coordinates of the hypercube correspond to the dual numbers of the fields in the Karnaugh map.

Figure 3-2 shows the unit cube for 3 variables. This corresponds to a 2x4 KV diagram. The KV- diagram in Figure 3-3 is shown in Figure 3-4 marked accordingly (green level). The node ( vertex or circles ) on the Hyper- unit cube corresponding to each field in the KV diagram. The transitions (neighborhood of the fields ) are represented by the edges of the cube. While hiking on the edge produces a Gray code. On each edge changes exactly 1 bit. An essential property is that the Gray codes for two adjacent numbers by only 1 digit in binary code ie 1 bit differ ( Hamming distance ).

The KV- chart has so many neighborhoods, such as the cube has edges. Figure 3-5 shows a flat view of the hyper - unit cube. Without internal structure of the transient change can be the cube in any direction " invert ", as shown in the animation in Figure 3-9. This explains why there are KV- map with various arrangements of the variables ( edge inscription). They were virtually " turned inside out " like a cube.

For the KV- chart with two variables (2x2 box ) results in a simpler hyper - cube unit ( Figure 3-6 ). When one variable is the "cube" trivial ( Figure 3-7 ). With increasing variables, the number of edges increases but exponentially. Thus there are four variables ( Figure 3-8 ) already 32 edges.

Enhancements of symmetry chart for more than 4 input variables

A disadvantage of the original version of the KV diagram is that it is not suitable for more than four input variables. To work with any number of input variables, the generalized form of the chart of symmetry may be used.

In this method, the formation of a combined diagram is characterized said n input variables that CT diagram is mirrored with n- 1 input variables and thus doubled. Hence the term " symmetry diagram ". The emerging half of the KV diagram then corresponds to the newly added input variable in non- negated form, while the existing half of the input variable is in negated form.

By reflection symmetry of a graph with n input variables can be created with an n 1 input variables in this way, so that the number of input variables is not limited even in two dimensions.

Also the formation of groups of contiguous, rectangular blocks in the conventional KV diagram is explained on the mirror:

Every conceivable group of fields in an KV- graph with n input variables, which represents a minterm or Maxterm can be generated by mirroring and / or maintaining a group in the KV- graph with n- 1 input variables. For example, the minterm ¬ AB (in the drawing, red) generated by the fact that

  • At the first mirroring the original group not mitgespiegelt ( but retained),
  • Mitgespiegelt the group at the second mirror and do not preserve the existing fields and
  • Mitgespiegelt the group at the third mirror and the existing fields are maintained simultaneously.

The condition that several fields can form a group, therefore, is not that it is contiguous rectangular blocks, but whether it is possible to generate a corresponding group by mirroring and maintaining. In Karnaugh maps with up to 4 input variables but this condition leads to the same groups as the rule that it must be in the groups of contiguous rectangles. However, this is from 5 input variables no longer the case, as can be seen from the following example with six input variables.

The blue marked block is not a valid block ( the one minterm represents ) that although all the rules were met for a block formation in a conventional KV diagram. The red-marked group of fields corresponding to the minterm AB ¬ ¬ D; thus it is a valid group. This is clearly not a contiguous block.

The application of the method for more than four input variables is, however, difficult as the application with a maximum of 4 input variables because non-contiguous groups of ones not apparent to the user as easy as contiguous rectangles of ones.

Glitch Gray-Code Clause (logic) Minimal polynomial (linear algebra) Two-element Boolean algebra Carnot cycle
459046
de