DW EditSeite anzeigenÄltere VersionenLinks hierherAlles aus-/einklappenNach oben Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt. CKG Editor ====== 3. Combinatorical Logic ====== <callout title="introductional example"> <WRAP><well> <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}} </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. Tasks: - 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? </callout> ===== 3.1 Combinatorical Circuit ===== 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? In the following we have a look onto combinatorical circuits. These are generally logic circuits with * $n$ inputs $X_0$, $X_1$, ... $X_{n-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 They can be description by * truth table * boolean formula * hardware description language The ladder one is not in the focus of this course. The applications range: * (simple) half/full adder * [[http://www.falstad.com/circuit/e-digcompare.html|digital comparator]]s (logic circuit to compare 2 values) * Multiplexer / demultiplexer * Arithmetic logic units in microcontrollers and processors * much more ===== 3.1.1 Example ===== In order to understand the synthesis of a 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: * The intelligent switch has 4 user selectable positions: $1$, $2$, $3$, $4$ * Additionally there are 2 non-selectable positions for the case of failure. * The output $Y=1$ will activate a 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 example, when the switch position is unclear. In this case the input of the combinatorial circuit is "ON". * There are no other cases of inputs. This requirements are put into a truth table: <WRAP center> <imgcaption pic01 | Therm-o-Safety truth table> </imgcaption> {{drawio>ToStruthtable1}} </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''. \\ 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''. By this, we have done the first step in order to syntesize the requested logic. ===== 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$. If this input combination would be the only one for the output of $Y=1$, tha following could be stated: \\ "$Y=1$ (only) when the $X_0$ is $1$ AND $X_1$ is $1$ AND $X_2$ is $0$ ". It can also be re-arranged to: \\ "$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 \& X_1 \& \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$. <WRAP center> <imgcaption pic02 | Therm-o-Safety truth table - first analysis> </imgcaption> {{drawio>ToStruthtable2}} </WRAP> <imgref pic02> shows the boolean expression for ths combination. In <imgref pic03>, this boolean expression is converted into a struction with logic gates. <WRAP><well> <imgcaption pic03|logic circuit for the combination '100'></imgcaption> \\ {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFaAmAbJA7AZgCweRmFpAJxoYYjyRVU3wCmAtGGAFAAyVyAHCEyVTc+LMMhDiIAMwCGAGwDODWpE4gcg-po1DR4ySFmLliVVxyocWoRat6JUQ-KUq2ADyoks-MNhAZ4OzAcbytkKwBjAHsAWwAjAEsAOxkAFyiAJwSI+QAdBVzcpLkogHNs93Vwn3wqCx9UEnUJK2SABwBXVPykhLi4uQY2ZEx1S2t1HBFtEAANZDYwahBUaqYscQxIOw3Hb0R4YdGdCamaARs59hHKeF4J+DFTudUbkB44fnGMHjtxqwAmmwAJJUdBfKzwMgQxwwA5sADuYzs2nGTHGqiRthh8HB6KsmM84nxK0gIgxiPUmguVN0u0JJ3W4nQInplLu0yEHNh7PuNBZPKRWx2mxG-DZSI+512UphqgAsu9PiTZTT9NBDoqBUzSSIpg5kBq2FqyTDtR8DUaTXx+aaWEJ1YckdrdqsRVBKQL+dUaIS3Y5-faPc61vrAxSQ38rNqKR4KMTfOIeKhdGBGs1qlEup1UpT8NKk8q2UA noborder}} </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'': * 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} \& \overline{X_1} \& {X_2}$. * For ''111'', the boolean expression is ${X_0} \& {X_1} \& {X_2}$. <WRAP column 100%> <panel type="danger" title="Note!"> <WRAP group><WRAP column 7%>{{fa>exclamation?32}}</WRAP><WRAP column 80%> * 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 ceratin instances an negation have 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} \& X_1$ </WRAP></WRAP></panel> </WRAP> <WRAP center> <imgcaption pic04 | Therm-o-Safety truth table - sum of products> </imgcaption> {{drawio>ToStruthtable3}} </WRAP> In <imgref pic04> all minterms for $Y=1$ are shown. The <imgref pic05> depicts all the logic circuits for the three minterms. These lead to the outputs $Y'$, $Y''$, and $Y'''$. <WRAP><well> <imgcaption pic05|logic circuit for the combinations '100', '110', '111'></imgcaption> \\ {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFaAmAbJA7AZgCweRmFpAJxoYYjyRVU3wCmAtGGAFAAyVyAHCEyVTc+LMMhDiIAMwCGAGwDODWpE4gcg-po1DR4ySFmLliVVxyocWoRat6J4Q-KUq2ADyoks-MNhAZ4OzAcbytkKwBjAHsAWwAjAEsAOxkAFyiAJwSI+QAdBVzcpLkogHNs93Vwn3wqCx9UEnUJK2SABwBXVPykhLi4uQY2ZEx1S2t1HBFtEAANZDYwahBUaqYscQxIOw2oEG96YdGdCamaARs59hHKeF4J+DFTudUbkB44fnGMHjtxqwAmgByNgASSo6C+VngZChexgiHgbAA7mM7NpxkxxqpUbY4fBIVirDjPOIiStICJsSj1JoLrTdLsSSd1uJ0CImTS7tMhNz4Vz7jR2fzUVsdpsRvxOaiPuddrK4aoALLvT7khX0-TQJEq4WsikiKYOZDati6ylwvUfY2m818IUWlhCLVI1F63arcVQGnCoXVGgkz17INO71utZGkPU8N-Kx66MrarjYUJoPWoOp6piPhB1jiQMW7OJqxFgt8TRBzTKg3ge7CvM2nU15MWo0us01isW63t1F8osEmilmknTSDkBVrmwls54kj5PQ6dz8HjsewqtIRGLZaVoRiidCGgHKg+rPTwuwwPVEY5s-509hAnFloBn0W5BPoMfw9vvjIJPXv6HbCt+NbhDQ7Z2uA558L4zoSLaYFJu+74Ia6wgSJ+75Psymj-nG75AX2sJgDB0H3ri4ykeIMKSJe25+mE1T7vhezeFuxHiF25Y-iukIDiRgqbienG1jmhaCvOsZoisc64nSuyjj+fZCf2kkqbB9x8qBuFCNoeFETJ-xUfRorbAe-hYHpyn+JKrEsUBHgUGSvjiDwqC6GAjTNNUURdJ0qQ0vgcpuWq0qWdZqo0JOKoKuMCq7L2UUWXFc5vKl-i-LJzTAiCop2dUCqsdWCrUclXkQWhNJFYVnxla8oylbCPwlrCgJAh1bBAA noborder}} </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: \begin{align*} Y &= & Y' & \quad | & Y'' & \quad | & Y''' \\ Y &= & (X_0 \& X_1 \& \overline{X_2}) & \quad | & (\overline{X_0} \& \overline{X_1} \& {X_2}) & \quad | & ({X_0} \& {X_1} \& {X_2}) \\ \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. <WRAP><well> <imgcaption pic06|logic circuit for therm-o-safety></imgcaption> \\ {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFaAmAbJA7AZgCweRmFpAJxoYYjyRVU3wCmAtGGAFAAyVyAHCEyVTc+LMMhDiIAMwCGAGwDODWpE4gcg-po1DR4ySFmLliVVxyocWoRat6J4Q-KUq2ADyoks-MNhAZ4OzAcbytkKwBjAHsAWwAjAEsAOxkAFyiAJwSI+QAdBVzcpLkogHNs93Vwn3wqCx9UEnUJK2SABwBXVPykhLi4uQY2ZEx1S2t1HBFtEAANZDYwahBUaqYscQxIOw2oEG96YdGdCamaARs59hHKeF4J+DFTudUbkB44fnGMHjtxqwAmmwAJJUdBfKzwMgQvYwRDwNgAdzGdm04yY41UyNsMPg4IxVixnnEBJWkBEmKR6k0F2pul2RJO63E6BEDKpd2mQk5sI59xorN5yK2O02I347ORH3Ou2lMNUAFl3p9SXLafpoAilYLmWSRFMHMhNWxteSYTqPobjaa+AKzSwhBqEcidbtVqKoFTBQLqjQie69gGHZ6XWsDUHKaG-lYdZGVtVxoK4wHLQHk9UxHwA6xxP6zZn41YC3m+JoA5pFXrwPdBTmrVqq4mzQanSaq2WzZbW8ieQW8TRi1STpp+yAKxzoU2s4Sh4nIZOZ6DRyPoRWkPDFsty0IRWOhDQDlQvRnJ-nof7qiMsyfc8ewnjCy0-V6zcgHwG3-uX3xkAnL7620FT8q3CGhWxtcBTz4XxHQka0QITV9Xzg51hAkd9XwfRlNF-GNXwAntoTAKDINvbFxmI8QoUkc9Nx9MJql3XC9m8DdCPEDtSy-JdwT7Ij+XXI92OrLN835WdoxRFYZ2xGldmHL8ewE3txKU6D7h5YDsKEbQcIIqT-go2ilk2LAdKEOU11YoT-HFXV8BoS0iQc5V-DM1znO2Pc3PMkMfPAJ4XLrZzxTrFzmJCsDGK8iKqUsiyVXZDwKBJXxxB4VBdDARpmmqKIuk6VI2CAA noborder}} </well></WRAP> When we analyze a single combination in order to output one single output we can combine __all inputs__ Analysis of the "Canonical normal form" * Sum of minterms: $$ * disjunctive normal form (DNF) ===== 3.1.3 Product of Sums ===== * Product of maxterms * conjunctive normal form (CNF) ===== 3.2 ===== ===== 3.2.1 The Karnaugh Map ===== [[https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/karnaughmap/index.html|interactive example]] <panel type="info" title="Exercise 3.1.x Further Querstions"> <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>