Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
introduction_to_digital_systems:combinatorial_logic [2023/03/27 11:24] – mexleadminintroduction_to_digital_systems:combinatorial_logic [2024/11/22 00:03] (current) – mexleadmin
Line 1: Line 1:
-====== 3. Combinatorical Logic ======+====== 3 Combinatorial Logic ======
  
-<callout  title="introductional example">+<callout  title="Introductional example">
  
 <WRAP><well> <WRAP><well>
 <imgcaption pic1|Simulation of a 7-segment encoder and display></imgcaption> \\ <imgcaption pic1|Simulation of a 7-segment encoder and display></imgcaption> \\
-{{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFaAmSBmSA2SAWSBOTTNHAdhwA40R5Iaa74BTAWjDACgx5SRTMKIFpRAURwwXV51IXfLx6YhIzHmWSOAGRrJBLCo11D2yEKYgAzAIYAbAM5N6s7TkJCDIV0rZhT5kNb2jojOnmim+nQ44ca+ZuABtg5OWp6q7lHpPn4JgckhHADuOnoe8EYissXlgiKKnhrV-OBKXi1QRZ5uYK1ukR1N3j1pOMZKVSNjk-0T9RJhEZWd0Yu1MTOdpLjqfAI7E-x6w1ujbOOb28d7wwd7IicNA3zbHlSmHgeXcRTpJk8-o1evzin1GYBwgO6EP+UMhSg+HAAHjR5MY0IhSPAjpBEKNkKMAMYAewAtgAjACWADsrAAXIkAJwpBNsAB07KzWVSbESAObMpGeIxsEg0WhoiB40bUgAOAFdaeyqRSyWSbExBaR8NQRaN8FhjNspXwWA5eSSmFTFVyiQr5bSOKgFM15nMYqMABpoR2QZ1DJT1KIgD3IH1+9r1d3BzhOmjNOrNdKe2Sxh7zNNRgCaKd9z1Ox22QczMdzDwLoyzodTRsEDyTIEz3urgKk2zco0zODDefAcTLFQb8G7ZehZewngbmA4QA noborder}}+{{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFaAmSBmSA2SAWSBOTTNHAdhwA40R5Iaa74BTAWjDACgx5SRTMKIFpRAURwwXV51IXfLx6YhIzHmWSOAGRrJBLCo11D2yEKYgAzAIYAbAM5N6s7TkJCDIV0rZhT5kNb2jojOnmim+nQ44ca+ZuABtg5OWp6q7lHpPn4JgckhHADuOnoe8EYissXlgiKKnhrV-OBKXi1QRZ5uYK1ukR1N3j1pOMZKVSNjk-0T9RJhEZWd0Yu1MTOdpLjqfAI7E-x6w1ujbOOb28d7wwd7IicNA3zbHlSmHgeXcRTpJk8-o1evzin1GYBwgO6EP+UMhSg+HAAHjR5MY0IhyENIIhRshRgBjAD2AFsAEYASwAdlYAC6EgBO5NsAB07MzmZSbISAObk-FIzxGNgkGi0NEQXGjKkABwArjTWZTyaTSTYmALSPhqMLRvgsMZtpK+CwHNziUxKQqOYT5XKaRxUApmvM5jFRgANNAOyBOoZKepREDu5De33tepuoOcR00Zp1ZrpD2yGMPeapyMATWTPuep2O20DGejOYe+dGmZDKcNggeiZAGa9VcBUm2blGGZwodz4DipYq9fgXdL0NL2E89cwHCAA noborder}}
 </well></WRAP> </well></WRAP>
  
-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. +The combinatorial logic shown in <imgref pic1> enables the 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:
Line 16: Line 16:
  
  
-===== 3.1 Combinatorial Circuit =====+===== 3.1 Combinatorial 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? 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?
Line 39: Line 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 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:+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 in the case of failure.    * Additionally there are 2 non-selectable positions in the case of failure. 
Line 58: Line 58:
 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''.  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 synthesize 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 ====
Line 92: Line 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 under 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 an output of ''1''   * A minterm results in an output of ''1''
  
Line 152: Line 152:
 ==== 3.1.3 Product-of-Sums ==== ==== 3.1.3 Product-of-Sums ====
  
-In the sub-chapter before we had a look at the combinations which generate 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 one 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''.
Line 159: Line 159:
 "$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 boolean operator we need here 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.
  
 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. 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.
Line 166: Line 166:
  
   * A **maxterm** is the disjunction (OR'ing) of all inputs, where under certain instances a negation has 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 an output of ''0''   * A maxterm results in an output of ''0''
  
Line 198: Line 198:
 Y &=  & (\overline{X_0} + X_1 + X_2) & \quad \cdot & ({X_0} + \overline{X_1} + X_2) & \quad  \cdot & (\overline{X_0} + \overline{X_1} + X_2)  \\ Y &=  & (\overline{X_0} + X_1 + X_2) & \quad \cdot & ({X_0} + \overline{X_1} + X_2) & \quad  \cdot & (\overline{X_0} + \overline{X_1} + X_2)  \\
   &=  & ...  \\   &=  & ...  \\
-Y &=  & (\overline{X_0} + X_1 + X_2) & \quad \cdot & (\overline{X_0} + \overline{X_1})   \\+Y &=  & (\overline{X_0} + X_1 + X_2) & \quad \cdot & (\overline{X_1} + \overline{X_2})   \\
 \end{align*} \end{align*}
  
 This result from $Y$ by the sum-of-products is different compared to the result in a product-of-sums: This result from $Y$ by the sum-of-products is different compared to the result in a 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_1} + \overline{X_2})$
  
-In this case, these results cannot be transformed into each other with the means of boolean rules. +In this case, these results cannot be transformed into each other using boolean rules. This is because the don't-care-terms are used in one case as $1$ in the other as $0$. 
  
 <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%>
Line 212: Line 212:
   * 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 synthesizing a logic circuit by the sum-of-products, all "don't care" terms outputting $1$   * When synthesizing a logic circuit by the sum-of-products, all "don't care" terms 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 results 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 **__when__** there are no don't care terms. Otherwise, the results cannot be transformed into each other with the means of boolean rules. 
  
 </WRAP></WRAP></panel> </WRAP> </WRAP></WRAP></panel> </WRAP>
Line 225: Line 225:
 The given logic expression can also be interpreted 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 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 example, we 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.
  
Line 236: Line 236:
  
 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$, 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 a 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 a 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 it simplifies the fill-in of the map and helps for the start.
  
 <WRAP center> <WRAP center>
Line 248: Line 248:
 ==== 3.2.2 The three-dimensional Karnaugh Map ==== ==== 3.2.2 The three-dimensional Karnaugh Map ====
  
-In this subchapter, we will have a look at our example of therm-o-safety. For this example, we 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. But we do not know how we can find the optimum implementation.+In this subchapter, we will have a look at our example of thermo--safety. For this example, we 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.
Line 262: Line 262:
 There is also an alternative way to look at 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'') 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) 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 these 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))
Line 275: Line 275:
 </WRAP> </WRAP>
  
-With this representation in mind, we can simplify other representations much more simpler. \\+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$.
  
Line 287: Line 287:
  
 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 map, it is a good idea to "unwrap" the cube. This can be done as shown in <imgref pic14>. 
  
 <WRAP center> <WRAP center>
Line 298: Line 298:
 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 cube, we 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 the 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 representation only the ''TRUE'' (=''1'') position of the coordinate is highlighted.+  - In other ways, the 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. 
  
Line 314: Line 314:
   * 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}$    * 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 neighboring 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 one, we have to keep in mind, that we had to cut the surface of the cube to flatten it. 
 Therefore, these cells are also neighboring. This leads to the conclusion, that the borders of the Karnaugh map are connected to opposite borders! Therefore, these cells are also neighboring. This leads to the conclusion, that the borders of the Karnaugh map are connected to opposite borders!
  
Line 338: Line 338:
  
   * The Karnaugh map is an alternative way to represent a logical 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)
  
Line 346: Line 346:
  
 For the four-dimensional Karnaugh map, the situation becomes more complicated in the classical coordinate system.  For the four-dimensional Karnaugh map, the situation becomes more complicated in the classical coordinate system. 
-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.+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. Here, a four-dimensional Karnaugh map might be a good representation.
  
Line 355: Line 355:
 </WRAP> </WRAP>
  
-In order 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$. +To create a four-dimensional Karnaugh map, we first look at 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.
Line 378: Line 378:
 </WRAP> </WRAP>
  
-For getting 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. +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>
Line 430: Line 430:
   * 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 these groups we can get the full formula by disjunctive combination:+Out of these groups, we 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}
Line 507: Line 507:
 === 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. This 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!">
Line 529: Line 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 prime implicants   * **No redundant prime implicant** is needed. They are covered by core prime implicants
Line 560: Line 560:
   * 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]]   * 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    * in the [[https://wiki.mexle.org/introduction_to_digital_systems/tools|Tool digital]]: via 
-    * ''Analysis >> Synthesis''  +    * ''File'' >> ''New'' 
-    * filling the truth table  +    * ''Analysis'' >> ''Synthesis'' 
-    * change the variable names by right click on the name +    * ''New'' >> ''Combinatorial'' >> ''4 variables'' (or requested numbers of inputs) 
-    * ''Kmap >> Kmap''+    * Change the variable names by right click on the name 
 +    * Filling the truth table  
 +    * ''Kmap'' >> ''Kmap'' 
 +    * The Kmap can be resorted by moving the rows in the truth table via drag-and-drop
  
 </callout> </callout>
Line 582: Line 585:
 </collapse>  </collapse> 
  
-2. Minimize the DNF step by step, starting 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">+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*} \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}} \\ 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}} \\
Line 606: Line 609:
 </collapse>  </collapse> 
  
-4. Minimize the CNF step by step, starting the used boolean rules \\+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"> <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">
  
Line 631: Line 634:
 </collapse>  </collapse> 
  
-5. Show, that the DNF can be converted into the CNF (duality principle) \\ <button size="xs" type="link" collapse="Solution_3_1_1_5_Final_result">{{icon>eye}} Result </button><collapse id="Solution_3_1_1_5_Final_result" collapsed="true"> +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"> 
-<WRAP hide>+
 The distributive law ($a\cdot(b+c)=a\cdot b + a \cdot c$) can be generalized - similar to the conventional algebra: The distributive law ($a\cdot(b+c)=a\cdot b + a \cdot c$) can be generalized - similar to the conventional algebra:
 \begin{align*} \begin{align*}
Line 643: Line 646:
 \end{align*} \end{align*}
  
-This can be applied on the DNF:+This can be applied to the DNF:
 \begin{align*} \begin{align*}
-Y &= \overline{X2}\cdot \overline{X1} \cdot X0 + \color{blue}{{X2}\cdot \overline{X1} \cdot X0} + {X2}\cdot {X1} \cdot X0 \\ +Y &= \overline{X2}\cdot \overline{X1} \cdot X0 + \color{blue}{{X2}\cdot \overline{X1} \cdot X0} + {X2}\cdot {X1} \cdot X0 
-  &= \overline{X2}\cdot \overline{X1} \cdot X0 + \color{blue}{{X2}\cdot \overline{X1} \cdot X0} + {X2}\cdot {X1} \cdot X0 \\+
 \end{align*} \end{align*}
  
-</WRAP> 
 </collapse>  </collapse> 
  
Line 661: Line 662:
 <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 a positive logic shell be developed
 As a base, the following truth table shall be used. As a base, the 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.
Line 686: Line 687:
   * Write a random allocation of $0$s and $1$s to the variations of inputs. Write the min- and maxterms   * 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)   * 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 in order to get an individual test for a minterm optimization via a Karnaugh map.+  * 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>