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 [2023/11/21 07:13] – mexleadminintroduction_to_digital_systems:combinatorial_logic [2024/11/22 00:03] (aktuell) – mexleadmin
Zeile 1: Zeile 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:
Zeile 159: Zeile 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 as: $\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.
Zeile 198: Zeile 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%>
Zeile 212: Zeile 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>
Zeile 236: Zeile 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>
Zeile 248: Zeile 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 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.+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.
Zeile 325: Zeile 325:
 </WRAP> </WRAP>
  
-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. \\ +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 the image (c) the position of the origin is not in the upper left corner anymore. \\ 
 Independent of the permutation, the grouped cells are always neighboring each other.  Independent of the permutation, the grouped cells are always neighboring each other. 
  
Zeile 355: Zeile 355:
 </WRAP> </WRAP>
  
-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.
Zeile 560: Zeile 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>