Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung
Nächste Überarbeitung
Vorhergehende Überarbeitung
introduction_to_digital_systems:combinatorial_logic [2021/10/17 16:17]
tfischer
introduction_to_digital_systems:combinatorial_logic [2023/11/21 07:15] (aktuell)
mexleadmin
Zeile 1: Zeile 1:
-====== 3. Combinatorical Logic ======+====== 3 Combinatorial Logic ======
  
 <callout  title="introductional example"> <callout  title="introductional example">
Zeile 8: Zeile 8:
 </well></WRAP> </well></WRAP>
  
-The combinatorial logic shown in <impref pic1> enables to output distinct logic values for eacht logic input. When you change the ''input nibble'' you can see that the the correct number appears on the 7-segment-display. By clicking onto the bits of the input nibble, you can change the number. +The combinatorial logic shown in <imgref pic1> enables to output of distinct logic values for each logic input. When you change the ''input nibble''you can see that the correct number appears on the 7-segment display. By clicking on the bits of the input, you can change the number. 
  
 Tasks: Tasks:
   - Which output $Y_0$ ... $Y_6$ is generated from the input nibble ''1000''? Which from ''1001''?   - Which output $Y_0$ ... $Y_6$ is generated from the input nibble ''1000''? Which from ''1001''?
-  - Is the output only depending on the input? Is there a dependance on the histroy?+  - Is the output only depending on the input? Is there a dependence on history?
 </callout> </callout>
  
  
-===== 3.1 Combinatorical Circuit =====+===== 3.1 Combinatorial Circuits =====
  
-Up to now, we looked onto simple logic circuits. Thes are relatively easy to analyze and synthesize (=develop). The main question in this chapter is: how can we set up and optimize logic circuits?+Up to now, we looked at simple logic circuits. These are relatively easy to analyze and synthesize (=develop). The main question in this chapter is: how can we set up and optimize logic circuits?
  
-In the following we have a look onto combinatorical circuits. These are generally logic circuits with +In the followingwe have a look at combinatorial circuits. These are generally logic circuits with 
     * $n$ inputs $X_0$, $X_1$, ... $X_{n-1}$      * $n$ inputs $X_0$, $X_1$, ... $X_{n-1}$ 
     * $m$ outputs $Y_0$, $Y_1$, ... $Y_{m-1}$      * $m$ outputs $Y_0$, $Y_1$, ... $Y_{m-1}$ 
   * no "memory", that is: a given set of input bits results in a distinct output   * no "memory", that is: a given set of input bits results in a distinct output
-They can be description by+They can be described by
     * truth table     * truth table
     * boolean formula     * boolean formula
     * hardware description language      * hardware description language 
-The ladder one is not in the focus of this course. +The ladder one is not the focus of this course. 
  
 The applications range: The applications range:
   * (simple) half/full adder   * (simple) half/full adder
   * [[http://www.falstad.com/circuit/e-digcompare.html|digital comparator]]s (logic circuit to compare 2 values)   * [[http://www.falstad.com/circuit/e-digcompare.html|digital comparator]]s (logic circuit to compare 2 values)
-  * Multiplexer / demultiplexer+  * Multiplexer/demultiplexer
   * Arithmetic logic units in microcontrollers and processors   * Arithmetic logic units in microcontrollers and processors
   * much more   * much more
Zeile 39: Zeile 39:
 ==== 3.1.1 Example ==== ==== 3.1.1 Example ====
  
-In order to understand the synthesis of combinatoric logic we will follow a step-by-step example for this chapter.+To understand the synthesis of combinatoric logic we will follow a step-by-step example for this chapter.
  
-Imagine you are working for a company called "mechatronics and robotics". One costumer wants to have an intelligent switch as input device connected to a microcontroller for controlling an oven. For this project "Therm-o-Safety" he needs a combinatoric logic:+Imagine you are working for a company called "mechatronics and Robotics". One customer wants to have an intelligent switch as an input device connected to a microcontroller for controlling an oven. For this project "Therm-o-Safety" he needs a combinatoric logic:
   * The intelligent switch has 4 user selectable positions: $1$, $2$, $3$, $4$   * The intelligent switch has 4 user selectable positions: $1$, $2$, $3$, $4$
-  * Additionally there are 2 non-selectable positions for the case of failure.  +  * Additionally there are 2 non-selectable positions in the case of failure.  
-  * The output $Y=1$ will activate temperature monitoring. +  * The output $Y=1$ will activate temperature monitoring. 
-  * The temperature monitoring has to be active for $3$ and $4$ and in case of a major failure. A major failure is for examplewhen the switch position is unclear. In this case the input of the combinatorial circuit is "ON".+  * The temperature monitoring has to be active for $3$ and $4$ in case of a major failure. A major failure is for example when the switch position is unclear. In this casethe input of the combinatorial circuit is "ON".
   * There are no other cases of inputs.   * There are no other cases of inputs.
  
-This requirements are put into a truth table:+These requirements are put into a truth table:
 <WRAP center> <WRAP center>
 <imgcaption pic01 | Therm-o-Safety truth table> <imgcaption pic01 | Therm-o-Safety truth table>
 </imgcaption> </imgcaption>
-{{drawio>ToStruthtable1}}+{{drawio>ToStruthtable1.svg}}
 </WRAP> </WRAP>
  
-<imgref pic01> shows one implementation of this requirements. The inputs ''001'' ... ''011'' represent the inputs $1$...$4$. The cases of failure are coded with ''110'' and ''111''. \\ +<imgref pic01> shows one implementation of these requirements. The inputs ''001'' ... ''011'' represent the inputs $1$...$4$. The cases of failure are coded with ''110'' and ''111''. \\ 
-The output $Y$ is activated as requested. For the two combinations ''000'' and ''101'' there is no output value defined. Depending on the requierements for a project these shall either better be ''0'' or ''1'' or the output of these does not matter. We had this "does not matter" before: the technical term is "I don't care", and it is written as a ''-'' or a ''x''+The output $Y$ is activated as requested. For the two combinations ''000'' and ''101'' there is no output value defined. Depending on the requirements for a project these shall either better be ''0'' or ''1'' or the output of these does not matter. We had this "does not matter" before: the technical term is "I don't care", and it is written as a ''-'' or a ''x''
  
-By this, we have done the first step in order to syntesize the requested logic.+By this, we have done the first step to synthesize the requested logic.
  
-==== 3.1.2 Sum of Products ====+==== 3.1.2 Sum-of-Products ====
  
-Now, we want to investigate some of the input combinations (= lines in the truth table). At first, we have a look onto the input combination ''011'', where the output has to be $Y=1$. +Now, we want to investigate some of the input combinations (= lines in the truth table). At first, we have a look at the input combination ''011'', where the output has to be $Y=1$. 
  
 If this input combination would be the only one for the output of $Y=1$, the following could be stated: \\  If this input combination would be the only one for the output of $Y=1$, the following could be stated: \\ 
Zeile 68: Zeile 68:
 "$Y=1$ (only) when the $X_0$ is $1$ AND $X_1$ is $1$ AND $X_2$ is not $1$ " "$Y=1$ (only) when the $X_0$ is $1$ AND $X_1$ is $1$ AND $X_2$ is not $1$ "
  
-This statement is similar to $X_0 \cdot X_1 \cdot \overline{X_2}$. The used conjuntion resuts only in $1$when all inputs are $1$. The negation of $X_2$ takes account of the fact, that $X_2$ has to be $0$. +This statement is similar to $X_0 \cdot X_1 \cdot \overline{X_2}$. The used conjunction results only in $1$ when all inputs are $1$.  
 +The negation of $X_2$ takes account of the fact, that $X_2$ has to be $0$. 
  
 <WRAP center> <WRAP center>
 <imgcaption pic02 | Therm-o-Safety truth table - first analysis> <imgcaption pic02 | Therm-o-Safety truth table - first analysis>
 </imgcaption> </imgcaption>
-{{drawio>ToStruthtable2}}+{{drawio>ToStruthtable2.svg}}
 </WRAP> </WRAP>
  
-<imgref pic02> shows the boolean expression for ths combination. In <imgref pic03>, this boolean expression is converted into a struction with logic gates. +<imgref pic02> shows the boolean expression for this combination. In <imgref pic03>, this boolean expression is converted into a structure with logic gates. 
  
 <WRAP><well> <WRAP><well>
Zeile 83: Zeile 84:
 </well></WRAP> </well></WRAP>
  
-With the same idea in mind, we can have a look for the other combinations resulting in $Y=1$. These are the combinations ''100'' and ''111'':  +With the same idea in mind, we can have a look at the other combinations resulting in $Y=1$. These are the combinations ''100'' and ''111'':  
-  * For ''100'' The statement would be: "$Y=1$ (only) when the $X_0$ is $0$ AND $X_1$ is $0$ AND $X_2$ is $1$"Similary to the combination above this leads to: $\overline{X_0} \cdot \overline{X_1} \cdot {X_2}$.+  * For ''100'' The statement would be: "$Y=1$ (only) when the $X_0$ is $0$ AND $X_1$ is $0$ AND $X_2$ is $1$"Similarly to the combination above this leads to: $\overline{X_0} \cdot \overline{X_1} \cdot {X_2}$.
   * For ''111'', the boolean expression is ${X_0} \cdot {X_1} \cdot {X_2}$.   * For ''111'', the boolean expression is ${X_0} \cdot {X_1} \cdot {X_2}$.
  
Zeile 91: Zeile 92:
  
   * Each row in a truth table (=one distinct combination) can be represented by a **minterm** or **maxterm**   * Each row in a truth table (=one distinct combination) can be represented by a **minterm** or **maxterm**
-  * A **minterm** is the conjunction (AND'ing) of all inputs, where unter certain instances a negation have to be used +  * A **minterm** is the conjunction (AND'ing) of all inputs, where under certain instances a negation has to be used 
-  * In a minterm an input variable with ''0'' has to be negated, in order to use it as an input for the AND. \\ e.g. $X_0 = 0$ AND $X_1 = 1$$ \quad \rightarrow \quad \overline{X_0} \cdot X_1$ +  * In a minterm an input variable with ''0'' has to be negated, to use it as an input for the AND. \\ e.g. $X_0 = 0$ AND $X_1 = 1$$ \quad \rightarrow \quad \overline{X_0} \cdot X_1$ 
-  * A minterm results in output of ''1''+  * A minterm results in an output of ''1''
  
 </WRAP></WRAP></panel> </WRAP></WRAP></panel>
Zeile 99: Zeile 100:
  
 <WRAP center> <WRAP center>
-<imgcaption pic04 | Therm-o-Safety truth table - sum of products>+<imgcaption pic04 | Therm-o-Safety truth table - the sum-of-products>
 </imgcaption> </imgcaption>
-{{drawio>ToStruthtable3}}+{{drawio>ToStruthtable3.svg}}
 </WRAP> </WRAP>
  
Zeile 111: Zeile 112:
 </well></WRAP> </well></WRAP>
  
-For the final step we have to combine the single results for the minterms. The output has to be $1$ when at least one of the minterms is $1$. Therefore, the minterms have to be connected disjunctive: +For the final stepwe have to combine the single results for the minterms. The output has to be $1$ when at least one of the minterms is $1$. Therefore, the minterms have to be connected disjunctive: 
  
 \begin{align*} \begin{align*}
Zeile 118: Zeile 119:
 \end{align*} \end{align*}
  
-This leads to the logic circuit shown in <imgref pic06>. Here, you can input the different combinations by clicking onto the bits of the input nibble. +This leads to the logic circuit shown in <imgref pic06>. Here, you can input the different combinations by clicking on the bits of the input nibble. 
  
 <WRAP><well> <WRAP><well>
Zeile 128: Zeile 129:
 <panel type="danger" title="Note!"> <WRAP group><WRAP column 7%>{{fa>exclamation?32}}</WRAP><WRAP column 80%> <panel type="danger" title="Note!"> <WRAP group><WRAP column 7%>{{fa>exclamation?32}}</WRAP><WRAP column 80%>
  
-  * The disjunction of the minterms is called **sum of products**, **SoP**, **disjunctive normal form** or **DNF**.+  * The disjunction of the minterms is called **sum-of-products**, **SoP**, **disjunctive normal form** or **DNF**.
   * When all inputs are used in each of the minterms the normal form is called **full disjunctive normal form**   * When all inputs are used in each of the minterms the normal form is called **full disjunctive normal form**
-  * When snytesizing a logic circuit by sum of products, all 'don't care' terms outputing $0$. +  * When synthesizing a logic circuit by the sum-of-products, all 'don't care' terms output $0$. 
  
 </WRAP></WRAP></panel> </WRAP></WRAP></panel>
  </WRAP>  </WRAP>
  
-We have seen, that the sum of products is one tool to derive a logic circuit based on a truth table. Alternatively it is also possible to insert an intermediate step, where the logic formula is simplified.+We have seen, that the sum-of-products is one tool to derive a logic circuit based on a truth table. Alternativelyit is also possible to insert an intermediate step, where the logic formula is simplified.
  
 In the following one possible optimization is shown: In the following one possible optimization is shown:
Zeile 149: Zeile 150:
 </WRAP> </WRAP>
  
-==== 3.1.3 Product of Sums ====+==== 3.1.3 Product-of-Sums ====
  
-In the sub-chapter before we had a look onto the combinations which generates an output of $Y=1$ by means of the AND operator. Now we are investigating the combinations with $Y=0$. Therefore, we need an operator, which results in $0$ for only on distinct combination.+In the sub-chapter before we had a look at the combinations which generate an output of $Y=1$ using the AND operator. Now we are investigating the combinations with $Y=0$. Therefore, we need an operator, which results in $0$ for only one distinct combination.
  
 The first combination to look for is ''001''. The first combination to look for is ''001''.
 If this input combination would be the only one for the output of $Y=0$, the following could be stated: \\  If this input combination would be the only one for the output of $Y=0$, the following could be stated: \\ 
-"$Y=0$ (only) when the $X_0$ is $1$ AND $X_1$ is $0$ AND $X_2$ is $0$ ". \\ With having the duality in mind (see cpt. [[boolean_algebra#The Set of Rules]]) the opposite is also true: \\ +"$Y=0$ (only) when the $X_0$ is $1$ AND $X_1$ is $0$ AND $X_2$ is $0$ ". \\ With having the duality in mind (see chapter [[boolean_algebra#The Set of Rules]]) the opposite is also true: \\ 
 "$Y=1$ when $X_0$ is $0$ OR $X_1$ is $1$ OR $X_2$ is $1$ " "$Y=1$ when $X_0$ is $0$ OR $X_1$ is $1$ OR $X_2$ is $1$ "
  
-This is the same like: $\overline{X_0} + X_1 + X_2$ \\ The booleand operator we need hiere is the OR-operator.+This is the same as: $\overline{X_0} + X_1 + X_2$ \\ The boolean operator we need here is the OR-operator.
  
-Simmilarly, the combinations ''010'' und ''110'' can be transformed. Keep in mind, that this time we are looking for a formula with results in $0$ only for the given one distinct combination.+Similarly, the combinations ''010'' and ''110'' can be transformed. Keep in mind, that this time we are looking for a formula with results in $0$ only for the given one distinct combination.
  
 <WRAP column 100%> <panel type="danger" title="Note!"> <WRAP group><WRAP column 7%>{{fa>exclamation?32}}</WRAP><WRAP column 80%> <WRAP column 100%> <panel type="danger" title="Note!"> <WRAP group><WRAP column 7%>{{fa>exclamation?32}}</WRAP><WRAP column 80%>
  
-  * A **maxterm** is the disjunction (OR'ing) of all inputs, where unter certain instances a negation have to be used. +  * A **maxterm** is the disjunction (OR'ing) of all inputs, where under certain instances a negation has to be used. 
-  * In a maxterm an input variable with ''1'' has to be negated, in order to use it as an input for the OR. +  * In a maxterm an input variable with ''1'' has to be negated, to use it as an input for the OR. 
-  * A maxterm results in output of ''0''+  * A maxterm results in an output of ''0''
  
 </WRAP></WRAP></panel> </WRAP> </WRAP></WRAP></panel> </WRAP>
Zeile 175: Zeile 176:
 <imgcaption pic07 | Therm-o-Safety truth table> <imgcaption pic07 | Therm-o-Safety truth table>
 </imgcaption> </imgcaption>
-{{drawio>SoTtruthtable1}}+{{drawio>SoTtruthtable1.svg}}
 </WRAP> </WRAP>
  
-The formulas of <imgref pic07> can again be transformed into gate circiuts (<imgref pic08>). Here, only for the inputs '001', '010', '110' one of the outputs $Y'$, $Y''$ or $Y'''$ is $0$. +The formulas of <imgref pic07> can again be transformed into gate circuits (<imgref pic08>). Here, only for the inputs ''001'', ''010'', ''110'' one of the outputs $Y'$, $Y''$ or $Y'''$ is $0$. 
  
 <WRAP><well> <WRAP><well>
Zeile 185: Zeile 186:
 </well></WRAP> </well></WRAP>
  
-When these intermediate outputs $Y'$, $Y''$, $Y'''$ are used as an input for an AND-gate the resultin output will get $0$ when at least one of the intermediate outputs are $0$. This results in another way to synthesize the Therm-o-Safety (see <imgref pic09>)+When these intermediate outputs $Y'$, $Y''$, and $Y'''$ are used as an input for an AND-gate the resulting output will get $0$ when at least one of the intermediate outputs is $0$. This results in another way to synthesize the Therm-o-Safety (see <imgref pic09>)
  
 <WRAP><well> <WRAP><well>
Zeile 192: Zeile 193:
 </well></WRAP> </well></WRAP>
  
-Also the products of sum can be simplified:+Alsothe product-of-sum can be simplified:
  
 \begin{align*} \begin{align*}
Zeile 200: Zeile 201:
 \end{align*} \end{align*}
  
-This result $Y$ by the sum of products is different compared to the result in product of sums: +This result from $Y$ by the sum-of-products is different compared to the result in product-of-sums: 
-  * product of sums: $Y = (\overline{X_0} \cdot \overline{X_1} \cdot {X_2})  +  (X_0 \cdot X_1)$  +  * product-of-sums: $Y = (\overline{X_0} \cdot \overline{X_1} \cdot {X_2})  +  (X_0 \cdot X_1)$  
-  * sum of products: $Y = (\overline{X_0} + X_1 + X_2) \cdot (\overline{X_0} + \overline{X_1})$+  * sum-of-products: $Y = (\overline{X_0} + X_1 + X_2) \cdot (\overline{X_0} + \overline{X_1})$
  
-In this case these resuls cannot be transformed into each other with the means of boolean rules. +In this casethese results cannot be transformed into each other with the means of boolean rules. 
  
 <WRAP column 100%> <panel type="danger" title="Note!"> <WRAP group><WRAP column 7%>{{fa>exclamation?32}}</WRAP><WRAP column 80%> <WRAP column 100%> <panel type="danger" title="Note!"> <WRAP group><WRAP column 7%>{{fa>exclamation?32}}</WRAP><WRAP column 80%>
  
-  * The disjunction of the maxterms is called **products of sum**, **PoS**, **conjunctive normal form** or **CNF**.+  * The disjunction of the maxterms is called **products-of-sum**, **PoS**, **conjunctive normal form** or **CNF**.
   * When all inputs are used in each of the minterms the normal form is called **full conjunctive normal form**   * When all inputs are used in each of the minterms the normal form is called **full conjunctive normal form**
-  * When snytesizing a logic circuit by sum of procucts, all 'don't careterms outputing $1$ +  * When synthesizing a logic circuit by the sum-of-products, all "don't careterms outputting $1$ 
-  * The products of sum is the DeMorgan dual of the sum of products **__if__** there are no don't care terms. Otherwise the resuls cannot be transformed into each other with the means of boolean rules. +  * The products-of-sum is the DeMorgan dual of the sum-of-products **__if__** there are no don't care terms. Otherwisethe results cannot be transformed into each other with the means of boolean rules. 
  
 </WRAP></WRAP></panel> </WRAP> </WRAP></WRAP></panel> </WRAP>
Zeile 219: Zeile 220:
 ==== 3.2.1 Introduction with the two dimensional Map ==== ==== 3.2.1 Introduction with the two dimensional Map ====
  
-For a simple introduction we take one step back and look onto a simple example. The formula $Y(X_1, X_0) = X_0 \cdot X_1$ combines two variables. Therefore, it has two dimensions. +For a simple introductionwe take one step back and look at a simple example. The formula $Y(X_1, X_0) = X_0 \cdot X_1$ combines two variables. Therefore, it has two dimensions. 
-In <imgref pic13> (a) the truth table of this is shown. The most left column shows the decimal interpretation of the binary numeral given by $X_1$, $X_0$ (e.g. $(X_1=1, X_0=0) \rightarrow 10_2=2_{10}$).+In <imgref pic13> (a) the truth table of this is shown. The leftmost column shows the decimal interpretation of the binary numeral given by $X_1$, $X_0$ (e.g. $(X_1=1, X_0=0) \rightarrow 10_2=2_{10}$).
  
-The given logic expression can also be interpreted in in a coordinate system, with the following conditions: +The given logic expression can also be interpreted in a coordinate system, with the following conditions: 
-  * There are be only two coordinates on each axis possible: ''0'' and ''1''.  +  * There are only two coordinates on each axis possible: ''0'' and ''1''.  
-  * There are as much axis as variables given in the logic: For the example we have two variables $X_0$ and $X_0$. These are spanning a two dimensional system.+  * There are as many axes as variables given in the logic: For the examplewe have two variables $X_0$ and $X_0$. These are spanning a two-dimensional system.
   * On the possible positions, the results $Y$ have to be shown.   * On the possible positions, the results $Y$ have to be shown.
  
-In the following pictures of this representation the values are shown as:+In the following pictures of this representationthe values are shown:
   * green dot, when the result is ''1''   * green dot, when the result is ''1''
   * red dot, when the result is ''0''   * red dot, when the result is ''0''
   * grey dot, when the result is ''don't care''    * grey dot, when the result is ''don't care'' 
  
-For the given example the coordinate system shows four possible positions: This are the edges of a square (<imgref pic13> (b)). +For the given example the coordinate system shows four possible positions: These are the edges of a square (<imgref pic13> (b)). 
  
 We will in the future write this as in <imgref pic13> (c). This diagram is also called **{{wp>karnaugh map}}** (often called k-map or KV map). We will in the future write this as in <imgref pic13> (c). This diagram is also called **{{wp>karnaugh map}}** (often called k-map or KV map).
-In the shown Karnaugh map the coordinate $X_0$ is shown vertically and $X_1$ horizontally. Similar to the coordinate system the upper left cell is for $X_1=0$ and $X_0=0$. The upper right cell is for  $X_1=1$ and $X_0=0$, the lower right one for $X_1=1$ and $X_0=1$. In each cell the result $Y(X_1,X_0)$ is shown as large number - similar to the color code in the coordinate system. The small number is the decimal representation of the number given by $X_1$ and $X_0$. This index is often __not__ explicitly shown in the Karnaugh map, but simplifies the fill-in of the map and helps for the start.+In the shown Karnaugh map the coordinate $X_0$ is shown vertically and $X_1$ horizontally. Similar to the coordinate system the upper left cell is for $X_1=0$ and $X_0=0$. The upper right cell is for  $X_1=1$ and $X_0=0$, and the lower right one is for $X_1=1$ and $X_0=1$. In each cell the result $Y(X_1, X_0)$ is shown as large number - similar to the color code in the coordinate system. The small number is the decimal representation of the number given by $X_1$ and $X_0$. This index is often __not__ explicitly shown in the Karnaugh map, but simplifies the fill-in of the map and helps for the start.
  
 <WRAP center> <WRAP center>
 <imgcaption pic13 | two dimensional Karnaugh map> <imgcaption pic13 | two dimensional Karnaugh map>
 </imgcaption> </imgcaption>
-{{drawio>multicube2}}+{{drawio>multicube2.svg}}
 </WRAP> </WRAP>
  
-The karnaugh map will help us in the following to find simplifications of more complex logic expressions.+The Karnaugh map will help us in the following to find simplifications of more complex logic expressions.
  
-==== 3.2.2 The three dimensional Karnaugh Map ====+==== 3.2.2 The three-dimensional Karnaugh Map ====
  
-In this subchapter we will have a look onto our example of the therm-o-safety. For this example we found two possible gate logics which can produce the required output. We have also seen, that optimizing the terms (i.e. the min- or maxterms) is often possible. But we do not know how we can find the optimum implementation.+In this subchapterwe will have a look at our example of thermo--safety. For this examplewe found two possible gate logic which can produce the required output. We have also seen, that optimizing the terms (i.e. the min- or maxterms) is often possible. However we do not know how we can find the optimum implementation.
  
-For this, we try to interpret the inputs of our example again as dimensions in a multidimensional space. The three input variables $X_0$, $X_1$, $X_2$ span a 3-dimensional space. The point ''000'' is the origin of this space. The three combinations ''001'', ''010'', ''100'' are onto the $X_0$-, $X_1$-, and $X_2$-axis, respectively (see <imgref pic10> (a)). The other combinations can be reached by adding these axis values together (see <imgref pic10> (b)+(c)). This is similar to the situation of a two dimensional or three dimensional vector. Three inputs result in this representation in the edges of a cube.+For this, we try to interpret the inputs of our example again as dimensions in a multidimensional space. The three input variables $X_0$, $X_1$, $X_2$ span a 3-dimensional space. The point ''000'' is the origin of this space. The three combinations ''001'', ''010'', ''100'' are onto the $X_0$-, $X_1$-, and $X_2$-axis, respectively (see <imgref pic10> (a)). The other combinations can be reached by adding these axis values together (see <imgref pic10> (b)+(c)). This is similar to the situation of a two-dimensional or three-dimensional vector. Three inputs result in this representation in the edges of a cube.
  
 In the <imgref pic10> (d) the situation $X_0=1$, $X_1=1$, $X_2=0$ is shown.  In the <imgref pic10> (d) the situation $X_0=1$, $X_1=1$, $X_2=0$ is shown. 
Zeile 256: Zeile 257:
 <imgcaption pic10 | 3 dimensional cube represetation> <imgcaption pic10 | 3 dimensional cube represetation>
 </imgcaption> </imgcaption>
-{{drawio>multicube0}}+{{drawio>multicube0.svg}}
 </WRAP> </WRAP>
  
-There is also an alternative way to look onto this representation:+There is also an alternative way to look at this representation:
   * The formula $Y=1$ (independent from inputs $X_0...X_{n-1}$) lead to all positions are ''1''   * The formula $Y=1$ (independent from inputs $X_0...X_{n-1}$) lead to all positions are ''1''
-  * A single input equal ''1'' ( $Y:\, X_0=1$, independent from all other inputs, i.e. all others are ''don't care''lead in the three dimansional example to the edges of a side surface of the cube. \\ In out example $\color{violet}{X_1=1}$ lead to the situation shown in <imgref pic11> (a). When investigating the shown green dots ''0**__1__**0'', ''0**__1__**1'', ''1**__1__**0'', ''1**__1__**1'' it is visible that the middle value (= the value for $X_1$) is the same.  \\ Generally: A single input equal ''1'' (independent from all other inputs) lead to a structure one dimension smaller than the number of inputs (In our example: 3 inputs $\rightarrow$ two dimensional structure = surface). +  * A single input equal ''1'' ( $Y:\, X_0=1$, independent from all other inputs, i.e. all others are ''don't care''leads in the three-dimensional example to the edges of a side surface of the cube. \\ In out example $\color{violet}{X_1=1}$ lead to the situation shown in <imgref pic11> (a). When investigating the shown green dots ''0**__1__**0'', ''0**__1__**1'', ''1**__1__**0'', ''1**__1__**1'' it is visible that the middle value (= the value for $X_1$) is the same.  \\ Generally: A single input equal ''1'' (independent from all other inputs) leads to a structure one dimension smaller than the number of inputs (In our example: 3 inputs $\rightarrow$ two-dimensional structure = surface). 
-  * Multiple given inputs equal ''1'' lead to smaller structures correspondingly. In our example: $\color{blue}{X_0=1}$ and $\color{violet}{X_1=1}$ ($=\color{blue}{X_0}\cdot \color{violet}{X_1}$) result in the two edges on a corner of the cube (<imgref pic11> (b)). For this coordinates (''0**__11__**'', ''1**__11__**'') the last two values are the same.+  * Multiple given inputs equal ''1'' lead to smaller structures correspondingly. In our example: $\color{blue}{X_0=1}$ and $\color{violet}{X_1=1}$ ($=\color{blue}{X_0}\cdot \color{violet}{X_1}$) result in the two edges on a corner of the cube (<imgref pic11> (b)). For these coordinates (''0**__11__**'', ''1**__11__**'') the last two values are the same.
   * A minterm (=''1'' as an output) in our example is given by the intersection of all surfaces for the individual dimensions. In our example:$\color{blue}{X_0=1}$ and $\color{violet}{X_1=1}$ and $\color{brown}{X_2=0}$ ($=\color{blue}{X_0}\cdot \color{violet}{X_1}\cdot \color{brown}{\overline{X_2} }$) result in the two edges on a corner of the cube (<imgref pic11> (c))   * A minterm (=''1'' as an output) in our example is given by the intersection of all surfaces for the individual dimensions. In our example:$\color{blue}{X_0=1}$ and $\color{violet}{X_1=1}$ and $\color{brown}{X_2=0}$ ($=\color{blue}{X_0}\cdot \color{violet}{X_1}\cdot \color{brown}{\overline{X_2} }$) result in the two edges on a corner of the cube (<imgref pic11> (c))
  
  
-On the right side of <imgref pic11> also the truth table is shown. There, the combinations for each side surfaces of the cube is marked with the corresponding color. +On the right side of <imgref pic11> also the truth table is shown. There, the combinations for each side surface of the cube are marked with the corresponding color. 
  
 <WRAP center> <WRAP center>
-<imgcaption pic11 | examples in 3 dimensional cube represetation>+<imgcaption pic11 | examples in 3-dimensional cube represetation>
 </imgcaption> </imgcaption>
-{{drawio>multicube01}}+{{drawio>multicube01.svg}}
 </WRAP> </WRAP>
  
-With this representation in mind, we can simplify other representations much more simplier. \\+With this representation in mind, we can simplify other representations much more simply. \\
 One example for this would be to represent the formula: $Y= X_0 \cdot X_1 \cdot \overline{X_2} + X_2 \cdot X_1 + X_0 \cdot X_1 $. By drawing this into the cube one will see that it represents only a side surface of the cube. It can be simplified into $Y=X_1$. One example for this would be to represent the formula: $Y= X_0 \cdot X_1 \cdot \overline{X_2} + X_2 \cdot X_1 + X_0 \cdot X_1 $. By drawing this into the cube one will see that it represents only a side surface of the cube. It can be simplified into $Y=X_1$.
  
-We can also try to interpret our Therm-o-Safety truth table. The <imgref pic12> shows the corresponding cube. The problem here is, that it is a bit unhandy to reduce a three dimansional cube onto a flat monitor or paper. It will also get more stressfull for higher dimensions.+We can also try to interpret our Therm-o-Safety truth table. The <imgref pic12> shows the corresponding cube. The problem here is, that it is a bit unhandy to reduce a three-dimensional cube onto a flat monitor or paper. It will also get more stressful for higher dimensions.
  
 <WRAP center> <WRAP center>
 <imgcaption pic12 | Therm-o-Safety in multi-dimensional space> <imgcaption pic12 | Therm-o-Safety in multi-dimensional space>
 </imgcaption> </imgcaption>
-{{drawio>multicube1}}+{{drawio>multicube1.svg}}
 </WRAP> </WRAP>
  
 Therefore, we try to find a better way to sketch the coordinates, before we simplify our Therm-o-Safety.  Therefore, we try to find a better way to sketch the coordinates, before we simplify our Therm-o-Safety. 
-For the three dimensional Karnaugh map it is a good idea "unwrap" the cube. This can be done as shown in <imgref pic14>+For the three-dimensional Karnaugh mapit is a good idea to "unwrap" the cube. This can be done as shown in <imgref pic14>
  
 <WRAP center> <WRAP center>
-<imgcaption pic14 | flattening the 3 dimensional cube represetation>+<imgcaption pic14 | flattening the 3-dimensional cube represetation>
 </imgcaption> </imgcaption>
-{{drawio>kmap3D}}+{{drawio>kmap3D.svg}}
 </WRAP> </WRAP>
  
  
-Out of the flattened cube we can derive the three dimensional Karnaugh map (see <imgref pic15>). Generally, there are different ways to show the Karnaugh map. +Out of the flattened cubewe can derive the three-dimensional Karnaugh map (see <imgref pic15>). Generally, there are different ways to show the Karnaugh map. 
-  - One way is to show the variable names of the dimensions in the corner. Be aware, that the order of the numbers in horizontal direction is ''0,0'', ''0,1'', ''1,1'', ''1,0'' and not in ascending order!  +  - One way is to show the variable names of the dimensions in the corner. Be aware, that the order of the numbers in the horizontal direction is ''0,0'', ''0,1'', ''1,1'', ''1,0'' and not in ascending order!  
-  - In other ways the columns / rows related to the dimension are marked with lines. In this represenation only the ''TRUE'' (=''1'') position of the coordinate is highlighted.+  - In other waysthe columns/rows related to the dimension are marked with lines. In this representation, only the ''TRUE'' (=''1'') position of the coordinate is highlighted.
 In <imgref pic15> the dimensions are additionally marked with colors.  In <imgref pic15> the dimensions are additionally marked with colors. 
  
-In the following chapters mainly the visualisation shown in <imgref pic15> (b) is used. +In the following chapters mainly the visualization shown in <imgref pic15> (b) is used. 
  
 <WRAP center> <WRAP center>
-<imgcaption pic15 | different representation of the three dimensional Karnaugh map I>+<imgcaption pic15 | different representation of the three-dimensional Karnaugh map I>
 </imgcaption> </imgcaption>
-{{drawio>kmap3D2}}+{{drawio>kmap3D2.svg}}
 </WRAP> </WRAP>
  
-With this representation we can now try to read out the logic terms for the Therm-o-Safety from its Karnaugh map. <imgref pic18> shows the neighbouring combinations: +With this representationwe can now try to read out the logic terms for the Therm-o-Safety from its Karnaugh map. <imgref pic18> shows the neighboring combinations: 
-  * In light brown the group (''011'' + ''111'') resp. position 3 and position 7 is shown. This can be simplified into $X_0 \cdot X_1$ +  * In light brown the group (''011'' + ''111'') resp. position 3 and position 7 are shown. This can be simplified into $X_0 \cdot X_1$ 
-  * In light blue the group  (''101'' + ''111'') resp. position 5 and position 7 is shown. This can be simplified into $X_0 \cdot X_2$. This group seems not to be needed, since ''111'' is already in the light brown group. +  * In light blue the group  (''101'' + ''111'') resp. position 5 and position 7 are shown. This can be simplified into $X_0 \cdot X_2$. This group seems not to be needed, since ''111'' is already in the light brown group. 
-  * In light violet the group  (''000'' + ''100'') resp. position 0 and position 4 is shown. This can be simplified into $\overline{X_0} \cdot \overline{X_1}$ +  * In light violet the group  (''000'' + ''100'') resp. position 0 and position 4 are shown. This can be simplified into $\overline{X_0} \cdot \overline{X_1}$ 
  
-The first two groups are also neighbouring cells in the Karnaugh map. For the last one we have to keep in mind, that we had to cut the surface of the cube in order to flatten it.  +The first two groups are also neighboring cells in the Karnaugh map. For the last onewe have to keep in mind, that we had to cut the surface of the cube to flatten it.  
-Therefore, this cells are also neighbouringThese leads to the conclusion, that the borders of the Karnaugh map are connected to the opposite borders!+Therefore, these cells are also neighboringThis leads to the conclusion, that the borders of the Karnaugh map are connected to opposite borders!
  
-For our example the result would be: (light brown the group) + (light violet the group) $= X_0 \cdot X_1 + \overline{X_0} \cdot \overline{X_1}$+For our examplethe result would be: (light brown the group) + (light violet the group) $= X_0 \cdot X_1 + \overline{X_0} \cdot \overline{X_1}$
  
 <WRAP center> <WRAP center>
-<imgcaption pic18 | simplification of the three dimensional Karnaugh map>+<imgcaption pic18 | simplification of the three-dimensional Karnaugh map>
 </imgcaption> </imgcaption>
-{{drawio>kmap3D4}}+{{drawio>kmap3D4.svg}}
 </WRAP> </WRAP>
  
-We also have to remember, that there are multiple permutations to show exacly the same logic assignment. This can be interpreted as other ways to unwrap the cube. The <imgref pic17> shows the variant from before at (a). In image (b) the coordinates are mixed ($X_0 \rightarrow X_1$, $X_1 \rightarrow X_2$, $X_2 \rightarrow X_0$). In the image (c) the position of the origin is not on the upper left corner anymore. \\  +We also have to remember, that there are multiple permutations to show exactly the same logic assignment. This can be interpreted as other ways to unwrap the cube. The <imgref pic17> shows the variant from before at (a). In the image (b) the coordinates are mixed ($X_0 \rightarrow X_1$, $X_1 \rightarrow X_2$, $X_2 \rightarrow X_0$). In image (c) the position of the origin is not in the upper left corner anymore. \\  
-Independent from the permutation, the grouped cells are always neighbouring each other. +Independent of the permutation, the grouped cells are always neighboring each other. 
  
 <WRAP center> <WRAP center>
-<imgcaption pic17 | different representation of the three dimensional Karnaugh map II>+<imgcaption pic17 | different representation of the three-dimensional Karnaugh map II>
 </imgcaption> </imgcaption>
-{{drawio>kmap3D3}}+{{drawio>kmap3D3.svg}}
 </WRAP> </WRAP>
  
Zeile 336: Zeile 337:
 <WRAP column 100%> <panel type="danger" title="Note!"> <WRAP group><WRAP column 7%>{{fa>exclamation?32}}</WRAP><WRAP column 80%> <WRAP column 100%> <panel type="danger" title="Note!"> <WRAP group><WRAP column 7%>{{fa>exclamation?32}}</WRAP><WRAP column 80%>
  
-  * The Karnaugh map is an alternative way to represent a logic relation. +  * The Karnaugh map is an alternative way to represent a logical relation. 
-  * There are possible grouping in order to simplify the logic.+  * There are possible groups to simplify the logic.
   * We need to take care of whether a group is needed or not. (will be done in chapter 3.3)   * We need to take care of whether a group is needed or not. (will be done in chapter 3.3)
  
 </WRAP></WRAP></panel> </WRAP> </WRAP></WRAP></panel> </WRAP>
  
-==== 3.2.3 Four Dimensional Karnaugh Map ====+==== 3.2.3 Four-Dimensional Karnaugh Map ====
  
-For the four dimensional Karnaugh map the situation becomes in the classical coordinate system more complicated. The respective object would be a four-dimensional hypercube (see <imgref pic16>). This is hard to print in a two dimensional layout like on a website or on a page. +For the four-dimensional Karnaugh mapthe situation becomes more complicated in the classical coordinate system.  
-Here, a four dimensional Karnaugh map might be a good representation.+The respective object would be a four-dimensional hypercube (see <imgref pic16>). This is hard to print in a two-dimensional layout like on a website or a page. 
 +Here, a four-dimensional Karnaugh map might be a good representation.
  
 <WRAP center> <WRAP center>
-<imgcaption pic16 | four dimensional hypercube>+<imgcaption pic16 | four-dimensional hypercube>
 </imgcaption> </imgcaption>
-{{drawio>kmap4D1}}+{{drawio>kmap4D1.svg}}
 </WRAP> </WRAP>
  
-In order to create a four dimensional Karnaugh map, we look at first how the two and three dimensional Karnaugh map can be derived. The <imgref pic19> (a) shows, that the two dimensional Karnaugh map can be created from a one dimensional one by folding the table on the x-axis and adding $10_2$ to all values. The additional line is marked with the new dimension $X_1$. +To create a four-dimensional Karnaugh map, we look at first how the two and three-dimensional Karnaugh maps can be derived. The <imgref pic19> (a) shows, that the two-dimensional Karnaugh map can be created from a one-dimensional one by folding the table on the x-axis and adding $10_2$ to all values. The additional line is marked with the new dimension $X_1$. 
  
-The three dimensional one is created by folding the table on the __y-axis__ and adding $100_2$ to all values. The additional line is marked with the new dimension $X_2$ (<imgref pic19> (b) ). Be aware, that the $X_0$ marking now has to be extended - it is also folded to the right.+The three-dimensional one is created by folding the table on the __y-axis__ and adding $100_2$ to all values. The additional line is marked with the new dimension $X_2$ (<imgref pic19> (b) ). Be aware, that the $X_0$ marking now has to be extended - it is also folded to the right.
  
-The four dimensional one is created by folding the table again on the __x-axis__ and adding $100_2$ to all values. The additional line is marked with the new dimension $X_2$ (<imgref pic19> (c) ). +The four-dimensional one is created by folding the table again on the __x-axis__ and adding $100_2$ to all values. The additional line is marked with the new dimension $X_2$ (<imgref pic19> (c) ). 
  
-By this we can visually derive the four dimensional Karnaough map. +By thiswe can visually derive the four-dimensional Karnaough map. 
  
 <WRAP center> <WRAP center>
 <imgcaption pic19 | four dimensional Karnaugh map> <imgcaption pic19 | four dimensional Karnaugh map>
 </imgcaption> </imgcaption>
-{{drawio>kmap4D3}}+{{drawio>kmap4D3.svg}}
 </WRAP> </WRAP>
  
-Again, there are alternative ways to show the Karnaugh map. To get the index of each cell one can easily add up the values of the dimension $X_0 ... X_3$. This is shown on an example in <imgref pic20>+Again, there are alternative ways to show the Karnaugh map. To get the index of each cell one can easily add up the values of the dimension $X_0 ... X_3$. This is shown in an example in <imgref pic20>
  
  
 <WRAP center> <WRAP center>
-<imgcaption pic20 | different representations of a four dimensional Karnaugh map>+<imgcaption pic20 | different representations of a four-dimensional Karnaugh map>
 </imgcaption> </imgcaption>
-{{drawio>kmap4D4}}+{{drawio>kmap4D4.svg}}
 </WRAP> </WRAP>
  
-For getting used to the four dimensional Karnaugh map, we expand our Therm-o-Safety: Instead of four user selectable levels for oven, the version 2.0 will have seven. The temperature monitoring ($Y=1$) has to be active starting with level $4$. Additionally, the Therm-o-Safety 2.0 has three non-selectable positions for the case of failure, where the last one needs active temperature monitoring. Some of the combinations (''0000'', ''1000'', ''1001'', ''1010'', ''1011'', ''1100'') are not needed. +To get used to the four-dimensional Karnaugh map, we expand our Therm-o-Safety: Instead of four user-selectable levels for the oven, version 2.0 will have seven. The temperature monitoring ($Y=1$) has to be active starting with level $4$. Additionally, the Therm-o-Safety 2.0 has three non-selectable positions for the case of failure, where the last one needs active temperature monitoring. Some of the combinations (''0000'', ''1000'', ''1001'', ''1010'', ''1011'', ''1100'') are not needed. 
  
 The truth table of the new Therm-o-Safety 2.0 is shown in <imgref pic16> The truth table of the new Therm-o-Safety 2.0 is shown in <imgref pic16>
Zeile 383: Zeile 385:
 <imgcaption pic21 | truth table of Therm-o-Safety 2.0> <imgcaption pic21 | truth table of Therm-o-Safety 2.0>
 </imgcaption> </imgcaption>
-{{drawio>kmap4D2}}+{{drawio>kmap4D2.svg}}
 </WRAP> </WRAP>
  
Zeile 391: Zeile 393:
 <imgcaption pic22 | Karnaugh map of Therm-o-Safety 2.0> <imgcaption pic22 | Karnaugh map of Therm-o-Safety 2.0>
 </imgcaption> </imgcaption>
-{{drawio>kmap4D5}}+{{drawio>kmap4D5.svg}}
 </WRAP> </WRAP>
  
 === Disjunctive Form === === Disjunctive Form ===
  
-The Karnaugh map can now be used to either get the disjunctive form (= sum of products) when looking onto the groups of $1$s, or the conjunctive form (= product of sums) out of the groups of $0$s. We will at first look onto the disjunctive form. There are multiple way to group the minterms. One is shown here:+The Karnaugh map can now be used to either get the disjunctive form (= sum-of-products) when looking at the groups of $1$s, or the conjunctive form (= product-of-sums) out of the groups of $0$s.  
 +We will first look at the disjunctive form. There are multiple ways to group the minterms. One is shown here:
  
 <WRAP center> <WRAP center>
 <imgcaption pic23 | Disjunctive solution of Therm-o-Safety 2.0> <imgcaption pic23 | Disjunctive solution of Therm-o-Safety 2.0>
 </imgcaption> </imgcaption>
-{{drawio>kmap4D6}}+{{drawio>kmap4D6.svg}}
 </WRAP> </WRAP>
  
-The group $I$ in <imgref pic23> can be expandedsince there are don't care states nearby:  +The group $I$ in <imgref pic23> can be expanded since there are don't care states nearby:  
  
 <WRAP center> <WRAP center>
 <imgcaption pic24 | optimized disjunctive solution of Therm-o-Safety 2.0> <imgcaption pic24 | optimized disjunctive solution of Therm-o-Safety 2.0>
 </imgcaption> </imgcaption>
-{{drawio>kmap4D7}}+{{drawio>kmap4D7.svg}}
 </WRAP> </WRAP>
  
-This can be transformed back into a formula. We can derive the boolean terms from the Karnaugh map with the folloring steps (see <imgref pic26>): +This can be transformed back into a formula. We can derive the boolean terms from the Karnaugh map with the following steps (see <imgref pic26>): 
-  - Investigate each single group individually.  +  - Investigate every single group individually.  
-  - For the sum of products each group has to be the product (AND-combination) of the inputs / coordinates. +  - For the sum-of-productseach group has to be the product (AND-combination) of the inputs/coordinates. 
-  - Then the formula can be derived as the sum of products...+  - Then the formula can be derived as the sum-of-products...
    
 <WRAP center> <WRAP center>
 <imgcaption pic26 | Interpretation of the formula> <imgcaption pic26 | Interpretation of the formula>
 </imgcaption> </imgcaption>
-{{drawio>kmap4D9}}+{{drawio>kmap4D9.svg}}
 </WRAP> </WRAP>
  
-The given groups are created as a product as following:+The given groups are created as a product as follows:
   * group $I$: all of this minterms are in the columns of $\color{green}{X_3}$. They are also all in the columns of $\color{blue}{X_1}$ and in the rows of $X_0$. This leads to  $X_0 \cdot \color{green}{X_3} \cdot \color{blue}{X_1}$   * group $I$: all of this minterms are in the columns of $\color{green}{X_3}$. They are also all in the columns of $\color{blue}{X_1}$ and in the rows of $X_0$. This leads to  $X_0 \cdot \color{green}{X_3} \cdot \color{blue}{X_1}$
   * group $II$: all of this minterms are in the columns of $\color{green}{\overline{X_3}}$. They are also all in the rows of $\color{magenta}{X_2}$. This leads to  $\color{green}{\overline{X_3}} \cdot \color{magenta}{X_2}$   * group $II$: all of this minterms are in the columns of $\color{green}{\overline{X_3}}$. They are also all in the rows of $\color{magenta}{X_2}$. This leads to  $\color{green}{\overline{X_3}} \cdot \color{magenta}{X_2}$
  
-Out of this groups we can get the full formula by disjunctive combination:+Out of these groupswe can get the full formula by disjunctive combination:
 \begin{align*} \begin{align*}
 Y &= X_0 \cdot \color{green}{X_3} \cdot \color{blue}{X_1} + \color{green}{\overline{X_3}} \cdot \color{magenta}{X_2} Y &= X_0 \cdot \color{green}{X_3} \cdot \color{blue}{X_1} + \color{green}{\overline{X_3}} \cdot \color{magenta}{X_2}
Zeile 434: Zeile 437:
 === Conjunctive Form === === Conjunctive Form ===
  
-Similarily we look onto the conjunctive form. Here we have to find groups of $0$s. One way of grouping the maxterms is shown here:+Similarly, we look at the conjunctive form. Here we have to find groups of $0$s. One way of grouping the maxterms is shown here:
  
 <WRAP center> <WRAP center>
Zeile 450: Zeile 453:
 </WRAP> </WRAP>
  
-Also here, we can derive the boolean terms from the Karnaugh map with the folloring steps (see <imgref pic27>): +Also here, we can derive the boolean terms from the Karnaugh map with the following steps (see <imgref pic27>): 
-  - Investigate each single group individually.  +  - Investigate every single group individually.  
-  - For the products of sum each group has to be the sum (OR-combination) of the inputs / coordinates. \\ Be aware, that for the OR-combination we get the groups of $0$s as "rest" of not marked cells!  +  - For the product-of-sumeach group has to be the sum (OR-combination) of the inputs/coordinates. \\ Be aware, that for the OR-combination we get the groups of $0$s as the "rest" of not-marked cells!  
-  - In the end the formula can again be derived, now as the product of sums.+  - In the endthe formula can again be derived, now as the product-of-sums.
  
 <WRAP center> <WRAP center>
 <imgcaption pic27 | Interpretation of the formula> <imgcaption pic27 | Interpretation of the formula>
 </imgcaption> </imgcaption>
-{{drawio>kmap4D10}}+{{drawio>kmap4D10.svg}}
 </WRAP> </WRAP>
  
Zeile 476: Zeile 479:
 ==== 3.2.4 Rules for the Karnaugh map ==== ==== 3.2.4 Rules for the Karnaugh map ====
  
-We saw, that with the Karnaugh map we can analyze logic combinations much better. But to use this tool right we have first to look onto some definitions.+We saw, that with the Karnaugh mapwe can analyze logic combinations much better. But to use this tool right we have first to look at some definitions.
  
 === Allowed Groups === === Allowed Groups ===
  
-As we have seen, the groups in the Karnaugh map are created by the combination of the inputs. By this only distinct groups are allowed. These can only have $2^{n-1}$ cells for $n$ inputs (= dimensions).+As we have seen, the groups in the Karnaugh map are created by the combination of the inputs. By thisonly distinct groups are allowed. These can only have $2^{n-1}$ cells for $n$ inputs (= dimensions).
  
-For a four dimensional Karnaugh map only the following groups are possible:+For a four-dimensional Karnaugh map only the following groups are possible:
   * groups of 1: Derived from 4 inputs, e.g. $X_3 \cdot \overline{X_2} \cdot \overline{X_1} \cdot \overline{X_0}$     * groups of 1: Derived from 4 inputs, e.g. $X_3 \cdot \overline{X_2} \cdot \overline{X_1} \cdot \overline{X_0}$  
   * groups of 2: Derived from 3 inputs, e.g. $ \overline{X_3} \cdot {X_1} \cdot \overline{X_0}$     * groups of 2: Derived from 3 inputs, e.g. $ \overline{X_3} \cdot {X_1} \cdot \overline{X_0}$  
   * groups of 4: Derived from 2 inputs, e.g. ${X_2} \cdot {X_0}$     * groups of 4: Derived from 2 inputs, e.g. ${X_2} \cdot {X_0}$  
-  * groups of 8: Derived from 1 inputs, e.g. $\overline{X_1} $  +  * groups of 8: Derived from 1 input , e.g. $\overline{X_1} $  
  
 <WRAP center> <WRAP center>
-<imgcaption pic29 | allowed groups in a four dimensional Karnaugh map>+<imgcaption pic29 | allowed groups in a four-dimensional Karnaugh map>
 </imgcaption> </imgcaption>
-{{drawio>kmapallowedgroups}}+{{drawio>kmapallowedgroups.svg}}
 </WRAP> </WRAP>
  
-Keep in mind, that not all groups of 2, 4 or 8 cells are allowed. In <imgref pic30> some not allowed groups are shown+Keep in mind, that not all groups of 2, 4or 8 cells are allowed. In <imgref pic30> some not allowed groups are shown
  
 <WRAP center> <WRAP center>
 <imgcaption pic30 | examples for not allowed groups> <imgcaption pic30 | examples for not allowed groups>
 </imgcaption> </imgcaption>
-{{drawio>kmapnotallowedgroups}}+{{drawio>kmapnotallowedgroups.svg}}
 </WRAP> </WRAP>
  
 === Necessary and Important Groups === === Necessary and Important Groups ===
  
-In the sub-chapter before the creation of the groups was done rather intuitively. This shall be explained more structured here. His needs some more definitions.+The sub-chapter before the creation of the groups was done rather intuitively. This shall be explained more structured here. This needs some more definitions.
  
 <callout icon="fa fa-exclamation" color="red" title="Note!"> <callout icon="fa fa-exclamation" color="red" title="Note!">
Zeile 512: Zeile 515:
   * **core prime implicant** (CPI) is a prime implicant, containing at least one term, which is not covered with any other prime implicant.   * **core prime implicant** (CPI) is a prime implicant, containing at least one term, which is not covered with any other prime implicant.
  
-The (non core) prime implicant additionally are separated into:+The (non-core) prime implicant additionally are separated into:
   * **Redundant prime implicants**: These are prime implicants, which are fully contained in a disjunction of multiple core prime implicants.   * **Redundant prime implicants**: These are prime implicants, which are fully contained in a disjunction of multiple core prime implicants.
   * **Selective prime implicants**: These are prime implicants, which are neither core prime implicants nor redundant prime implicants.   * **Selective prime implicants**: These are prime implicants, which are neither core prime implicants nor redundant prime implicants.
Zeile 518: Zeile 521:
 </callout> </callout>
  
-<imgref pic31> depicts the different implicants on one example.+<imgref pic31> depicts the different implicants in one example.
  
 <WRAP center> <WRAP center>
Zeile 526: Zeile 529:
 </WRAP> </WRAP>
  
-In order to get all the necessary implicants the following has to be considered:+To get all the necessary implicants the following has to be considered:
   * **All core prime implicant** are needed. They contain terms, which are not covered anywhere else.   * **All core prime implicant** are needed. They contain terms, which are not covered anywhere else.
-  * **No redundant prime implicant** is needed. They are covered by core primte implicants+  * **No redundant prime implicant** is needed. They are covered by core prime implicants
   * **Selective prime implicant** need to be investigated. Some of them are necessary, depending on the solution (see <imgref pic32>)   * **Selective prime implicant** need to be investigated. Some of them are necessary, depending on the solution (see <imgref pic32>)
  
Zeile 534: Zeile 537:
 <imgcaption pic32 | selective prime implicants> <imgcaption pic32 | selective prime implicants>
 </imgcaption> </imgcaption>
-{{drawio>kmapspi}}+{{drawio>kmapspi.svg}}
 </WRAP> </WRAP>
  
 === higher dimensional Karnaugh Maps === === higher dimensional Karnaugh Maps ===
  
-For highe dimensional Karnaugh maps the implicants look more am more unintuitive (see <imgref pic33>). +For higher dimensional Karnaugh maps the implicants look more am more unintuitive (see <imgref pic33>). 
-The Karnaugh map is in our coruse used to understand the different types of implicants (there will be only three and four dimensional maps in the exam).+The Karnaugh map is in our course used to understand the different types of implicants (there will be only three and four-dimensional maps in the exam).
  
 <WRAP center> <WRAP center>
 <imgcaption pic33 | five dimensional Karnaugh map> <imgcaption pic33 | five dimensional Karnaugh map>
 </imgcaption> </imgcaption>
-{{drawio>kmap5D}}+{{drawio>kmap5D.svg}}
 </WRAP> </WRAP>
  
-When solving higher dimensional boolean problems the [[https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/qmc/index.html|Quine–McCluskey algorithm]] or a [[https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer|heuristic approach, like the ESPRESSO algorithm]] can be used. Languages like the Hardware Description Language (HDL) often come with implemented optimizer in the development enviroment.+When solving higher dimensional boolean problems the [[https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/qmc/index.html|Quine–McCluskey algorithm]] or a [[https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer|heuristic approach, like the ESPRESSO algorithm]] can be used. Languages like the Hardware Description Language (HDL) often come with implemented optimizers in the development environment.
  
 ---- ----
 +==== Exercises ====
 +
 +<callout>
 +Tipp: You can check your answer yourself.
 +  * Online: [[https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/normalform/index.html|Normalforms]] and [[https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/karnaughmap/index.html|K-map]]
 +  * in the [[https://wiki.mexle.org/introduction_to_digital_systems/tools|Tool digital]]: via 
 +    * ''Analysis >> Synthesis'' 
 +    * filling the truth table 
 +    * change the variable names by right click on the name
 +    * ''Kmap >> Kmap''
 +
 +</callout>
  
 <panel type="info" title="Exercise 3.1.1 CNF, DNF, Optimization"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> <panel type="info" title="Exercise 3.1.1 CNF, DNF, Optimization"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%>
  
 The following truth table is given. The following truth table is given.
-  - Write down the DNF for the function table  
-  - Minimize the DNF step by step, stating the used boolean rules  
-  - Write down the CNF for the function table  
-  - Minimize the CNF step by step, stating the used boolean rules  
-  - Show, that the minimized DNF can be converted into the CNF (duality principle) 
-  - Create a Karnaugh map and mark the smallest number of largest prime implicants. Derive the minimized DNF and CNF from the map. 
  
 <WRAP center> <WRAP center>
 <imgcaption pic50 | Exercise 3.1.1 CNF, DNF, Optimization> <imgcaption pic50 | Exercise 3.1.1 CNF, DNF, Optimization>
 </imgcaption> </imgcaption>
-{{drawio>Exer311}}+{{drawio>Exer311.svg}}
 </WRAP> </WRAP>
 +
 +1. Write down the DNF for the function table. \\ <button size="xs" type="link" collapse="Solution_3_1_1_1_Final_result">{{icon>eye}} Result </button><collapse id="Solution_3_1_1_1_Final_result" collapsed="true">
 +For the DNF, one has to only use the following lines to get the minterms:
 +{{drawio>Exer311_res1.svg}}
 +</collapse> 
 +
 +2. Minimize the DNF step by step, starting with the used boolean rules \\ <button size="xs" type="link" collapse="Solution_3_1_1_2_Solution_Path">{{icon>eye}} Solution steps </button><collapse id="Solution_3_1_1_2_Solution_Path" collapsed="true">
 +\begin{align*}
 +Y &= \overline{X2}\cdot \overline{X1} \cdot X0 + \color{blue}{{X2}\cdot \overline{X1} \cdot X0} + {X2}\cdot {X1} \cdot X0                                          && | \color{blue}{\text{ Idempotence: Double the second term}} \\
 +  &= \overline{X2}\cdot \overline{X1} \cdot X0 + {X2}\cdot \overline{X1} \cdot X0 + {X2}\cdot \overline{X1} \cdot X0 + {X2}\cdot {X1} \cdot X0 \quad &&  \\
 +  &= \overline{X2}\cdot \color{blue}{\overline{X1} \cdot X0} + {X2}\cdot \color{blue}{\overline{X1} \cdot X0} + {X2}\cdot \color{violet}{\overline{X1} \cdot X0} + {X2}\cdot  \color{violet}{{X1} \cdot X0} \quad && |  \color{blue}{\text{Distributive Law }} \color{violet}{\text{(twice)}} \\
 +  &= (\overline{X2}+ X2) \cdot \overline{X1} \cdot X0 + (\overline{X1}+ X1) \cdot {X2} \cdot X0                                                      &&  \\
 +  &= \color{blue}{(\overline{X2}+ X2)} \cdot \overline{X1} \cdot X0 + \color{violet}{(\overline{X1}+ X1)} \cdot {X2} \cdot X0                        && | \color{blue}{\text{ Complementary Element + Neutral Element }} \color{violet}{\text{(twice)}}\\
 +  &= \overline{X1} \cdot X0 +  {X2} \cdot X0                                                                                                         && | \color{blue}{\text{ Distributive Law}} \\
 +  &= (\overline{X1} +  {X2}) \cdot X0                                                                                                                && \\
 +\end{align*}
 +</collapse>
 +
 +<button size="xs" type="link" collapse="Solution_3_1_1_2_Final_result">{{icon>eye}} Result </button><collapse id="Solution_3_1_1_2_Final_result" collapsed="true">
 +The final result is 
 +\begin{align*}
 +Y = (\overline{X1} +  {X2}) \cdot X0
 +\end{align*}
 +</collapse> 
 +
 +3. Write down the CNF for the function table \\ <button size="xs" type="link" collapse="Solution_3_1_1_3_Final_result">{{icon>eye}} Result </button><collapse id="Solution_3_1_1_3_Final_result" collapsed="true">
 +For the CNF, one has to only use the following lines to get the maxterms:
 +{{drawio>Exer311_res2.svg}}
 +</collapse> 
 +
 +4. Minimize the CNF step by step, starting with the used boolean rules \\
 +<button size="xs" type="link" collapse="Solution_3_1_1_4_Solution_Path">{{icon>eye}} Solution steps</button><collapse id="Solution_3_1_1_4_Solution_Path" collapsed="true">
 +
 +\begin{align*}
 +Y &= (X2 + X1 + X0)_{\color{blue}{I}} \cdot \color{blue}{(X2 + \overline{X1} + X0)}_{\color{blue}{II}} &&\cdot (X2 + \overline{X1} + \overline{X0})_{\color{blue}{III}} \cdot (\overline{X2} + X1 + X0)_{\color{blue}{IV}} &&\cdot (\overline{X2} + \overline{X1} + X0)_{\color{blue}{V}}                                          && | \color{blue}{\text{ Idempotence: Double the second term (II)}} \\
 +  &= (X2 + X1 + X0)_{\color{blue}{I}} \cdot (X2 + \overline{X1} + X0)_{\color{blue}{II}}               &&\cdot (X2 + \overline{X1} + \overline{X0})_{\color{blue}{III}} \cdot (\overline{X2} + X1 + X0)_{\color{blue}{IV}} &&\cdot (\overline{X2} + \overline{X1} + X0)_{\color{blue}{V}} \cdot (X2 + \overline{X1} + X0)_{\color{blue}{II}} &&| \text{Commutative Law: rearrange the terms} \\
 +  &= (X2 + X1 + X0)_{\color{blue}{I}} \cdot (\overline{X2} + X1 + X0)_{\color{blue}{IV}}               &&\cdot (X2 + \overline{X1} + X0)_{\color{blue}{II}} \cdot (X2 + \overline{X1} + \overline{X0})_{\color{blue}{III}} &&\cdot (\overline{X2} + \overline{X1} + X0)_{\color{blue}{V}} \cdot (X2 + \overline{X1} + X0)_{\color{blue}{II}}\\
 +  &= (X2 + \color{blue}{X1 + X0})_{\hphantom{I}} \cdot (\overline{X2} + \color{blue}{X1 + X0})_{\hphantom{IV}} &&\cdot (\color{violet}{X2 + \overline{X1}} + X0)_{\hphantom{II}} \cdot (\color{violet}{X2 + \overline{X1}} + \overline{X0})_{\hphantom{III}} &&\cdot (\overline{X2} + \color{green}{\overline{X1} + X0})_{\hphantom{V}} \cdot (X2 + \color{green}{\overline{X1} + X0})_{\hphantom{II}} &&| \color{blue}{\text{Distributive Law (}} \color{violet}{\text{three }} \color{green}{\text{times}} \color{black}{\text{)}} \\
 +  &= (X1 + X0) \cdot (X2 + \overline{X2}) &&\cdot (X2 + \overline{X1}) \cdot (X0 + \overline{X0}) &&\cdot (\overline{X2} + X2) \cdot (\overline{X1} + X0) \\
 +  &= (X1 + X0) \cdot \color{blue}{(X2 + \overline{X2})} &&\cdot (X2 + \overline{X1}) \cdot \color{violet}{(X0 + \overline{X0})} &&\cdot \color{green}{(\overline{X2} + X2)} \cdot (\overline{X1} + X0) &&| \color{blue}{\text{ Complementary Element + Neutral Element (}} \color{violet}{\text{three }} \color{green}{\text{times}} \color{black}{\text{)}} \\
 +  & (X1 + X0) \cdot  (X2 + \overline{X1}) \cdot  (\overline{X1} + X0) \\
 +  & (\color{blue}{X1} + X0) \cdot  (X2 + \overline{X1}) \cdot  (\color{blue}{\overline{X1}} + X0) && && &&| \color{blue}{\text{Distributive Law}}\\
 +  & (X1 + \overline{X1}) \cdot X0 \cdot  (X2 + \overline{X1}) \\
 +  & \color{blue}{(X1 + \overline{X1})} \cdot X0 \cdot  (X2 + \overline{X1}) && && &&| \color{blue}{\text{Complementary Element + Neutral Element}}\\
 +  & X0 \cdot  (X2 + \overline{X1}) \\
 +  \end{align*}
 +</collapse>
 +
 +<button size="xs" type="link" collapse="Solution_3_1_1_4_Final_result">{{icon>eye}} Result </button><collapse id="Solution_3_1_1_4_Final_result" collapsed="true">
 +The final result is 
 +\begin{align*}
 +Y = (\overline{X1} +  {X2}) \cdot X0
 +\end{align*}
 +</collapse> 
 +
 +5. Show, that the un-minimized DNF can be converted into the un-minimized CNF (duality principle) \\ <button size="xs" type="link" collapse="Solution_3_1_1_5_path">{{icon>eye}} Solution Steps</button><collapse id="Solution_3_1_1_5_path" collapsed="true">
 +
 +The distributive law ($a\cdot(b+c)=a\cdot b + a \cdot c$) can be generalized - similar to the conventional algebra:
 +\begin{align*}
 +(a+b)\cdot(c+d) = a\cdot c + a \cdot d + b\cdot c + b\cdot d
 +\end{align*}
 +
 +This also works for the dual situation:
 +\begin{align*}
 +(a\cdot b)+(c \cdot d) = (a + c) \cdot  (a + d) \cdot  (b + c) \cdot  (b + d)
 +\end{align*}
 +
 +This can be applied to the DNF:
 +\begin{align*}
 +Y &= \overline{X2}\cdot \overline{X1} \cdot X0 + \color{blue}{{X2}\cdot \overline{X1} \cdot X0} + {X2}\cdot {X1} \cdot X0 
 +\end{align*}
 +
 +</collapse> 
 +
 +6. Create a Karnaugh map and mark the smallest number of the largest prime implicants. Derive the minimized DNF and CNF from the map. \\ <button size="xs" type="link" collapse="Solution_3_1_1_6_Final_result">{{icon>eye}} Result </button><collapse id="Solution_3_1_1_6_Final_result" collapsed="true">
 +{{drawio>Exer311_res6.svg}}
 +</collapse> 
  
 </WRAP></WRAP></panel> </WRAP></WRAP></panel>
Zeile 573: Zeile 659:
 <panel type="info" title="Exercise 3.1.2 Implementation of a BCD-to-7-Segment Decoder"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> <panel type="info" title="Exercise 3.1.2 Implementation of a BCD-to-7-Segment Decoder"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%>
  
-A full BCD-to-7-Segment Decoder with positive logic shell be developed +A full BCD-to-7-Segment Decoder with positive logic shell be developed 
-As a base the following truth table shall be used.+As a basethe following truth table shall be used.
   - Write down the DNF and CNF for the function table and the outputs a...g. Use the don't care states wisely.   - Write down the DNF and CNF for the function table and the outputs a...g. Use the don't care states wisely.
   - Optimize the functions by the use of 7 Karnaugh maps.    - Optimize the functions by the use of 7 Karnaugh maps. 
   - Show, that the minimized DNF can be converted into the CNF (duality principle)   - Show, that the minimized DNF can be converted into the CNF (duality principle)
-  - Create a Karnaugh map and mark the smallest number of largest prime implicants. Derive the minimized DNF and CNF from the map. Mark the smallest number of largest prime implicants. \\ Write down the derived, smallest formula based on CNF and DNF. +  - Create a Karnaugh map and mark the smallest number of the largest prime implicants. Derive the minimized DNF and CNF from the map. Mark the smallest number of the largest prime implicants. \\ Write down the derived, smallest formula based on CNF and DNF. 
-  - Check the expressions with the programm "Digital"+  - Check the expressions with the program "Digital"
     - Use at first only the DNF and CNF.      - Use at first only the DNF and CNF. 
     - After this, use the minimized DNF and the minimized DNF     - After this, use the minimized DNF and the minimized DNF
-    - Check whether a 7-Segment-Display works foine with the created logic +    - Check whether a 7-Segment-Display works fine with the created logic
- +
  
  
Zeile 590: Zeile 674:
 <imgcaption pic51 | Exercise 3.1.2 Implementation of a BCD-to-7-Segment Decoder> <imgcaption pic51 | Exercise 3.1.2 Implementation of a BCD-to-7-Segment Decoder>
 </imgcaption> </imgcaption>
-{{drawio>Exer312}}+{{drawio>Exer312.svg}}
 </WRAP> </WRAP>
  
Zeile 596: Zeile 680:
  
  
-<panel type="info" title="Exercise 3.1.Further Questions"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%>+<panel type="info" title="Exercise 3.1.Further Questions"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%>
  
-Use the [[https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/karnaughmap/index.html|interactive example]] and activate "Hide result" plus the push of the "Random example" button in order to get an individual test for a minterm optimization via a Karnaugh map.+  * Write a random allocation of $0$s and $1$s to the variations of inputs. Write the min- and maxterms 
 +  * Compare the results with the output given [[https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/normalform/index.html|here]] (the output $y$ can be changed by clicking onto the grey cells) 
 +  * Use the [[https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/karnaughmap/index.html|interactive example]] and activate "Hide result" plus the push of the "Random example" button to get an individual test for a minterm optimization via a Karnaugh map.
      
 </WRAP></WRAP></panel> </WRAP></WRAP></panel>
- 
-<panel type="info" title="Exercise 3.1.x Further Questions"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> 
- 
-  - compare the results with the output given [[https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/normalform/index.html|here]] (the output $y$ can be changed by clicking onto it) 
-  
-</WRAP></WRAP></panel> 
- 
-