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$, the 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 \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$. <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 '011'></imgcaption> \\ {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFaAmAbJA7AZgCweRmFpAJxoYYjyRVU3wCmAtGGAFAAyVyAHCEyVTc+LMMhDiIAMwCGAGwDODWpE4gcg-po1DR4ySFmLliVVxyocWoRat6JUQ-KUq2ADyoks-MNhAZ4OzAcbytkKwBjAHsAWwAjAEsAOxkAFyiAJwSI+QAdBVzcpLkogHNs93ULH0J1EhEwVD4wq2SABwBXVLZkTHVLayqRbRAADWQ2MGoQVHD+LHEMSDsFx29EeB6+nUGcHhoBGzH2Xsp4XkH4MV2x1VOQfYOBjB47AasATTYASSp0fgG8DIAKsNBgGzYAHd+nZtAMmANVNDbCC-k9QVDPOIEVZ0CJEZidoc6rpVkiSfNxHjKVBMedhkJ6Y5yUyaNSwZilitFr0aeTHjSBTjaQBZB5wVFCzT6aCbMXUpirBV7BzIWVseWQfG4rX8faq9Wavhs3UsIQyzbQhVKuaK8Tk9kzOYcq3Op1BIQO20q2ZvDGuv0zU0EjwUbG+cQ8LANVAkdQSKxRLqdbrQ-AHVZCslsIA 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} \cdot \overline{X_1} \cdot {X_2}$. * For ''111'', the boolean expression is ${X_0} \cdot {X_1} \cdot {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 certain instances a 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} \cdot X_1$ * A minterm results in a output of ''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+QAdBVzcpLkogHNs93V4bxZCOkQWVD4wq2SABwBXVLZkTHVLa3UcEW0QAA1kNjBqEFRw-ixxDEg7RagQb3oevp1B4ZoBG3H2Xsp4XkH4MT3x1VOQHjh+AYweOwGrAE0AcjYASSo6GeVngZGB6xgiHgbAA7v07NoBkwBqo4bZwfAgcirKjPOJsbNICIUbD1JpDmTdGtcbsmGt0CJqaTziMhCyIcyLjQGRy4ctVktegtxLjHgc1mLwaoALIPJ4EyUU-TQaGynl08Tq4YOZAqthqong9WPHV6g18bmGxqm6Fw9X0+YaqCknnc+Y0XFzHGzR1gISex3ar1Sl2Ogbqkl2+bhw2Rn1WE3BuPBsR8FPXT2G1Px8Bcl2GzTBzQywl8bM81j6CRm0uzKw87XK1W1wuGk1Nzlli6YmjZmmaTQ9kDF5lgmNpnGk9EDUGaycAoeDsHFpBQqYzItCfnD-0bda2nNgMdZsEBsKx+ZHkWhsKYnPhD35vjIO-Bl-+p8SaPzZDu-W198AJwGgO3NcBjzLDAhFAgDo0NXpn2rA92UAnlAP7aC4OfP84VncDNRPa80QGK88Xw51pjdMJ5m3X9vW8NdcOXIQeRHBcgWzPC+1XKhR0kC4KzzYj3isadJzRck1l2EdcK5YRcwtTsFPk9CpwHGxNDo51hLreFyNxbdNGwIQZP8IUtNov8PAofFfHEHgsBEP0SHUCQrCiLpOm6PkhSdRUmT5LATKESUR1lSUBklNYOzhUKQqeEl7giqxXnrUSQB+X4fJA+ZJS0ktJVIwqgRiuUcoTJ5SLuPpCrBVLyK+b4mrYIA 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 \cdot X_1 \cdot \overline{X_2}) & \quad + & (\overline{X_0} \cdot \overline{X_1} \cdot {X_2}) & \quad + & ({X_0} \cdot {X_1} \cdot {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+QAdBVzcpLkogHNs93V4CBY-am9amjCrZIAHAFdUtmRMdUtrdRwRbRAADWQ2MGoQVHD+LHEMSDsFqBBvem7enQGhmgEbMfYeynheAerxA-Ux1ROQHjh+foweO36rAE02AEkqdGeVngZEBaxgiHgbAA7n07Np+kx+qoYbZQfAAYirMjPFd+ugREjoepNNcdkxVtiyat8fNxNizsMhAywUTmTQaTRsUsVoserSoETHvtVkLQaoALIPJ6YqX7TT6aCQyU08niFVDBzIRVsZWQAlWFWPTXa3V8dl6nxCBWQmEq6lzVUC20W9lzTlE2ZYmYOsBCbGe-gagMy-0OvEWkMeubhviE21zI0BuPeqxiWNzVh0j0WtMp8Dnf0WzQBzQSmY5840zPGpXl2MGi0a606usgYsWo3NmHM3Pomi5ymaTR9tt+1kgmMzLFE1H9YFq6d-EfDkGlpAQybTEtCbmjtYbKhR1MTnMg0NhC0BsBno8SdF58Lu518ZD3gOvsfPiTRubIN0tmkP1bR8awA081RzDArQkE1gOjC0ehfGCbWEO8hEA+9ByteCX3-bsQWvCC+EIp1YXAEF53IrMpldMI5l3P8vW8Dd8PEds+FLX5-n7c5KIHddD1Y-NYwrM0ZwRD48WnFESVWHZOO7AtUIHVlzl7c4gKwvcdkY0jZysVESNUKZFiwIRNFFNdmME-w+UdfAaCNLk+SNbAhCcold00Ny9y5MzwDEWz+0C5zgt5GhdNC78rAYvDZT3UVHVUDwKCuXxxB4LARF9EgbjmKJOg6LogA noborder}} </well></WRAP> <WRAP column 100%> <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**. * 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 procucts, all 'don't care' terms outputing $0$. </WRAP></WRAP></panel> </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. In the following one possible optimization is shown: \begin{align*} Y &= & (X_0 \cdot X_1 \cdot \overline{X_2}) & \quad + & (\overline{X_0} \cdot \overline{X_1} \cdot {X_2}) & \quad + & ({X_0} \cdot {X_1} \cdot {X_2}) & \quad | \text{associative law} \\ Y &= & (\overline{X_0} \cdot \overline{X_1} \cdot {X_2}) & \quad + & (X_0 \cdot X_1 \cdot \overline{X_2}) & \quad + & ({X_0} \cdot {X_1} \cdot {X_2}) & \quad | \text{associative law } \\ Y &= & (\overline{X_0} \cdot \overline{X_1} \cdot {X_2}) & \quad + & ((X_0 \cdot X_1) \cdot \overline{X_2}) & \quad + & (({X_0} \cdot {X_1}) \cdot {X_2}) & \quad | \text{distributive law } \\ Y &= & (\overline{X_0} \cdot \overline{X_1} \cdot {X_2}) & \quad + & ((X_0 \cdot X_1) \cdot (\overline{X_2} + {X_2})) & & & \quad | \text{complementary element} \\ Y &= & (\overline{X_0} \cdot \overline{X_1} \cdot {X_2}) & \quad + & (X_0 \cdot X_1) \\ \end{align*} ===== 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. 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: \\ "$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=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. 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. <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. * In a maxterm an input variable with ''1'' has to be negated, in order to use it as an input for the OR. * A maxterm results in a output of ''0'' </WRAP></WRAP></panel> </WRAP> The <imgref pic07> shows all the maxterms for the Therm-o-Safety example. <WRAP center> <imgcaption pic07 | Therm-o-Safety truth table> </imgcaption> {{drawio>SoTtruthtable1}} </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$. <WRAP><well> <imgcaption pic08|logic circuit for the combinations '001', '010', '110'></imgcaption> \\ {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFaAmAbJA7AZgCweRmFpAJxoYYjyRVU3wCmAtGGAFAAyVyAHCEyVTc+LMMhDiIAMwCGAGwDODWpE4gcg-po1DR48TVmLliVVxyocWoRat6JUEEaUq2ADyoks-MNhAZ4OzAcbytkKwBjAHsAWwAjAEsAOxkAFyiAJwSI+QAdBVzcpLkogHNs93VUbxZUPngwRFrEMKtkgAcAV1S2ZEwqu20cEW0QAA1kXv6da3UeGgEbcfY+ynheWYbxRfVx1VWQeYXLfx47E6sATQByNgBJKnRHeDJHGhhEeDYAdwHZ234J1UvwBTBOL22QJ+nkhVnQIihIM0OxmTCwBmhqPRIHh-GxwOEmw272h6z49CeJN+GEgdmx+AW+OhRzx4hZYKsqgAsoc4ICrOzNPpoF8ebi0eJxcMHMgRWwxZAEXDFfx5jK5QryTiVbV1V9fuLsahwqyoNDcTRjZyzQaTZaTbqCVb+NLnRybTiHSdxYjPXDlXxfc61c6gyaxIHw2IPbiI37wMTzSrNM7NNztXw47Ho8LRRmcQG5nr5fmUyq1bnSRs4-AnnGCTNNLWaGnSa9vSrfQDwe3OfdHi2hBCQGmkJ9zeH2yqwK8nSa+pGrDOMbawrX4+EqfnkOvnTuhE6VcgTXu7SXcfvtzgaJXNeAp5mMEJb9uT0ejxI5b8yRJd0f1w2Qoms2Ehnt+rzLvmkENickEgdBbbiGWfCtuBkgbLGiYgic7rdn2SK6NijYHlWWo-vWpEJvUGyXoBQjaEB+F-BcsGztCNJWJo2D0SR1J9KBVgcQJZoeBQ2y+GyWAiGAqAkLsJpRN0XQ9HxjJsnyEoetxI5CCyrY8iyJwstila-Hpul8lCByGYJZwFrsNy3KpwkssefYGXykEsjJN6fvqvI3ia3lsdZnmvBgdmQVc1wxYhjgWh68EbMOFEPPBrwpbOY5UP2IFuTCwnvCKOVocJF5no0koOvStKmjQ3j0GwlXxlxtWjt447Naegm1fl9W0F8QA noborder}} </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>) <WRAP><well> <imgcaption pic09|logic circuit for therm-o-safety></imgcaption> \\ {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFaAmAbJA7AZgCweRmFpAJxoYYjyRVU3wCmAtGGAFAAyVyAHCEyVTc+LMMhDiIAMwCGAGwDODWpE4gcg-po1DR48TVmLliVVxyocWoRat6JUEEaUq2ADyoks-MNhAZ4OzAcbytkKwBjAHsAWwAjAEsAOxkAFyiAJwSI+QAdBVzcpLkogHNs93VUShZ8KjASH1RGsKtkgAcAV1S2ZEwqu20cEW0QAA1kXv6da3UeGgEbcfY+ynheWfgxWasx1VWQeYXLfx47E6sATTYASSp0R3gyRxoYRHg2AHcBnZOmE9U31s-BOT3E-ysgM84JO6BEAK+6k0iyRuiwBkRMyY6JAcP4OKh6xGQiJL0RpPoD1eiIwkDsOPwCwJiKO+PErIhUDYAFlDnAQVYOZp9NAPry8djxBLhg5kKKebjIPCrBL5rL5eKlY4JWAhCKPt8JTjUOE2VzDVqaCbIebcaaraaWEIodb+DLXZyXY7YVrPYjXT6+AjDaa1QHIf7TWIg1Hti6tdG7VZE-G+JpXZpVJq+Im8ax9BINYqgyqtTL9Qq8emtWqK99SYn4A8U5jNJomzRM+TnoHcRGgbCrGC+1y7h2QO3npmkO9I8mewnnl6wlrXQ0MSGwk2kxIcNSLXxkNvXUfnf6tchTSf7ZWL8eL3v1WLi+AFzmMHrC8+8ZfS4eL1+5IbKeL4gVCMy-vcNCQYSzzri+8HgSc8Hjoh3biNWaZnvWcEbHmGxIecVjAsGqJmjMXb1gRwjgARQE5hspJga2QjaMKN4DiqxHIUuNJ0hOQjYKx2H+H0EimrSYQ3h4FDgr47JYCIuotLuIBRN0XQ9DhBgvvuUG0Xww4tmOzbPEZS4zlQtz6ZBw4wZZBrQuJf7OVyYDrDukr+PxXk0N49BsO5UqmpokkCY43izkFO6QWF9mRVZ7k0EJ4UYGc4V+Y8LL8poHLMt8aVWLlOUiSlaqMnytoVeVYlOlVtUMrVupVVgQj5qJNDtVCFXtRVMFsEAA noborder}} </well></WRAP> Also the products of sum can be simplified: \begin{align*} 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}) \\ \end{align*} This result $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)$ * 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. <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**. * 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 care' terms outputing $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. </WRAP></WRAP></panel> </WRAP> ===== 3.2 Karnaugh Map ===== ===== 3.2.1 Introduction with example ===== For our therm-o-safety 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. For this, we try to interpret the inputs of our example 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 following pictures of this representation the values are shown as: * green dot, when the result is ''1'' * red dot, when the result is ''0'' * grey dot, when the result is ''don't care'' In the <imgref pic10> (d) the situation $X_0=1$, $X_1=1$, $X_2=0$ is shown. <WRAP center> <imgcaption pic10 | 3 dimensional cube represetation> </imgcaption> {{drawio>multicube0}} </WRAP> There is also an alternative way to look onto this representation: * The value ''1'' (independent from the inputs) lead to all positions are ''1'' * A single input equal ''1'' (independent from all other inputs, i.e. all others are ''don't care'') lead in our example to the edges of a side surface of the cube. \\ In out example $\color{green}{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). * Multiple given inputs equal ''1'' lead to smaller structures correspondingly. In our example: $\color{blue}{X_0=1}$ and $\color{green}{X_1=1}$ ($=X_0\cdot 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. * 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{green}{X_1=1}$ and $\color{olive}{X_2=0}$ ($=X_0\cdot X_1$) result in the two edges on a corner of the cube (<imgref pic11> (b)) <WRAP center> <imgcaption pic11 | examples in 3 dimensional cube represetation> </imgcaption> {{drawio>multicube01}} </WRAP> With this representation in mind, we can simpilify other representations much more simplier. \\# 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 kann 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 a paper. It will also get more stressfull for higher dimensions. <WRAP center> <imgcaption pic12 | Therm-o-Safety in multi-dimensional space> </imgcaption> {{drawio>multicube1}} </WRAP> <WRAP center> <imgcaption pic13 | Therm-o-Safety in multi-dimensional space> </imgcaption> {{drawio>multicube2}} </WRAP> [[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>