Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung Nächste Überarbeitung Beide Seiten der Revision | ||
introduction_to_digital_systems:combinatorial_logic [2021/10/17 08:01] tfischer |
introduction_to_digital_systems:combinatorial_logic [2023/11/17 21:36] mexleadmin |
||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== 3. Combinatorical Logic ====== | + | ====== 3 Combinatorical Logic ====== |
< | < | ||
Zeile 8: | Zeile 8: | ||
</ | </ | ||
- | The combinatorial logic shown in <impref | + | The combinatorial logic shown in <imgref |
Tasks: | Tasks: | ||
- Which output $Y_0$ ... $Y_6$ is generated from the input nibble '' | - Which output $Y_0$ ... $Y_6$ is generated from the input nibble '' | ||
- | - Is the output only depending on the input? Is there a dependance | + | - Is the output only depending on the input? Is there a dependence |
</ | </ | ||
- | ===== 3.1 Combinatorical Circuit | + | ===== 3.1 Combinatorial Circuits |
- | Up to now, we looked | + | Up to now, we looked |
- | In the following we have a look onto combinatorical | + | In the following, we have a look at combinatorial |
* $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 " | * no " | ||
- | They can be description | + | They can be described |
* 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:// | * [[http:// | ||
- | * Multiplexer / demultiplexer | + | * Multiplexer/ |
* 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 a 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 " | + | Imagine you are working for a company called " |
* 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 | + | * Additionally there are 2 non-selectable positions |
- | * The output $Y=1$ will activate | + | * 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 example, when the switch position is unclear. In this case the input of the combinatorial circuit is " | + | * 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 case, the input of the combinatorial circuit is " |
* 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> | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | <imgref pic01> shows one implementation of this requirements. The inputs '' | + | <imgref pic01> shows one implementation of these requirements. The inputs '' |
- | The output $Y$ is activated as requested. For the two combinations '' | + | The output $Y$ is activated as requested. For the two combinations '' |
- | By this, we have done the first step in order to syntesize | + | By this, we have done the first step to synthesize |
- | ==== 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 '' | + | 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 '' |
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 | + | This statement is similar to $X_0 \cdot X_1 \cdot \overline{X_2}$. The used conjunction results |
+ | The negation of $X_2$ takes account of the fact, that $X_2$ has to be $0$. | ||
<WRAP center> | <WRAP center> | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | <imgref pic02> shows the boolean expression for ths combination. In <imgref pic03>, this boolean expression is converted into a struction | + | <imgref pic02> shows the boolean expression for this combination. In <imgref pic03>, this boolean expression is converted into a structure |
< | < | ||
Zeile 83: | Zeile 84: | ||
</ | </ | ||
- | With the same idea in mind, we can have a look for the other combinations resulting in $Y=1$. These are the combinations '' | + | With the same idea in mind, we can have a look at the other combinations resulting in $Y=1$. These are the combinations '' |
- | * For '' | + | * For '' |
* For '' | * For '' | ||
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' | + | * A **minterm** is the conjunction (AND' |
- | * In a minterm an input variable with '' | + | * In a minterm an input variable with '' |
- | * A minterm results in a output of '' | + | * A minterm results in an output of '' |
</ | </ | ||
Zeile 99: | Zeile 100: | ||
<WRAP center> | <WRAP center> | ||
- | < | + | < |
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
Zeile 111: | Zeile 112: | ||
</ | </ | ||
- | 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 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*} | \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 | + | This leads to the logic circuit shown in <imgref pic06>. Here, you can input the different combinations by clicking |
< | < | ||
Zeile 128: | Zeile 129: | ||
<panel type=" | <panel type=" | ||
- | * 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 | + | * When synthesizing |
</ | </ | ||
</ | </ | ||
- | 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. Alternatively, it 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: | ||
</ | </ | ||
- | ==== 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 | + | In the sub-chapter before we had a look at the combinations which generate |
The first combination to look for is '' | The first combination to look for is '' | ||
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# | + | "$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 |
"$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 | + | This is the same as: $\overline{X_0} + X_1 + X_2$ \\ The boolean |
- | Simmilarly, the combinations '' | + | Similarly, the combinations '' |
<WRAP column 100%> <panel type=" | <WRAP column 100%> <panel type=" | ||
- | * A **maxterm** is the disjunction (OR' | + | * A **maxterm** is the disjunction (OR' |
- | * In a maxterm an input variable with '' | + | * In a maxterm an input variable with '' |
- | * A maxterm results in a output of '' | + | * A maxterm results in an output of '' |
</ | </ | ||
Zeile 175: | Zeile 176: | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | The formulas of <imgref pic07> can again be transformed into gate circiuts | + | The formulas of <imgref pic07> can again be transformed into gate circuits |
< | < | ||
Zeile 185: | Zeile 186: | ||
</ | </ | ||
- | When these intermediate outputs $Y'$, $Y'' | + | When these intermediate outputs $Y'$, $Y'' |
< | < | ||
Zeile 192: | Zeile 193: | ||
</ | </ | ||
- | Also the products | + | Also, the 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 |
- | * product of sums: $Y = (\overline{X_0} \cdot \overline{X_1} \cdot {X_2}) | + | * product-of-sums: $Y = (\overline{X_0} \cdot \overline{X_1} \cdot {X_2}) |
- | * 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 | + | In this case, these results |
<WRAP column 100%> <panel type=" | <WRAP column 100%> <panel type=" | ||
- | * 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 | + | * When synthesizing |
- | * The products of sum is the DeMorgan dual of the sum of products **__if__** there are no don't care terms. Otherwise the resuls | + | * The products-of-sum is the DeMorgan dual of the sum-of-products **__if__** there are no don't care terms. Otherwise, the results |
</ | </ | ||
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 introduction, we 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 |
- | The given logic expression can also be interpreted | + | 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: '' | + | * There are only two coordinates on each axis possible: '' |
- | * 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. | ||
- | In the following pictures of this representation the values are shown as: | + | In the following pictures of this representation, the values are shown: |
* green dot, when the result is '' | * green dot, when the result is '' | ||
* red dot, when the result is '' | * red dot, when the result is '' | ||
* grey dot, when the result is '' | * grey dot, when the result is '' | ||
- | For the given example the coordinate system shows four possible positions: | + | For the given example the coordinate system shows four possible positions: |
We will in the future write this as in <imgref pic13> (c). This diagram is also called **{{wp> | We will in the future write this as in <imgref pic13> (c). This diagram is also called **{{wp> | ||
- | 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, | + | 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$, |
<WRAP center> | <WRAP center> | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | The karnaugh | + | The Karnaugh |
- | ==== 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 | + | 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. |
- | 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 '' | + | 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 '' |
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: | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | 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 '' | * The formula $Y=1$ (independent from inputs $X_0...X_{n-1}$) lead to all positions are '' | ||
- | * A single input equal '' | + | * A single input equal '' |
- | * Multiple given inputs equal '' | + | * Multiple given inputs equal '' |
* A minterm (='' | * A minterm (='' | ||
- | On the right side of <imgref pic11> also the truth table is shown. There, the combinations for each side surfaces | + | On the right side of <imgref pic11> also the truth table is shown. There, the combinations for each side surface |
<WRAP center> | <WRAP center> | ||
- | < | + | < |
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | 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 | + | 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 |
<WRAP center> | <WRAP center> | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
Therefore, we try to find a better way to sketch the coordinates, | Therefore, we try to find a better way to sketch the coordinates, | ||
- | For the three dimensional Karnaugh map it is a good idea " | + | For the three-dimensional Karnaugh map, it is a good idea to " |
<WRAP center> | <WRAP center> | ||
- | < | + | < |
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | 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 horizontal direction is '' | + | - 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 '' |
- | - In other ways the columns / rows related to the dimension are marked with lines. In this represenation | + | - In other ways, the columns/ |
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 | + | In the following chapters mainly the visualization |
<WRAP center> | <WRAP center> | ||
- | < | + | < |
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | 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 | + | 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 neighboring |
- | * In light brown the group ('' | + | * In light brown the group ('' |
- | * In light blue the group ('' | + | * In light blue the group ('' |
- | * In light violet the group ('' | + | * In light violet the group ('' |
- | The first two groups are also neighbouring | + | The first two groups are also neighboring |
- | Therefore, | + | Therefore, |
- | 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 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}$ |
<WRAP center> | <WRAP center> | ||
- | < | + | < |
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | We also have to remember, that there are multiple permutations to show exacly | + | We also have to remember, that there are multiple permutations to show exactly |
- | Independent | + | Independent |
<WRAP center> | <WRAP center> | ||
- | < | + | < |
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
Zeile 336: | Zeile 337: | ||
<WRAP column 100%> <panel type=" | <WRAP column 100%> <panel type=" | ||
- | * The Karnaugh map is an alternative way to represent a logic relation. | + | * The Karnaugh map is an alternative way to represent a logical |
- | * There are possible | + | * There are possible |
* 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) | ||
</ | </ | ||
- | ==== 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 | + | For the four-dimensional Karnaugh map, the situation becomes |
- | 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> | ||
- | < | + | < |
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | In order to create a four dimensional Karnaugh map, we look at first how the two and three dimensional Karnaugh | + | To create a four-dimensional Karnaugh map, we look at first how the two and three-dimensional Karnaugh |
- | 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 this, we can visually derive the four-dimensional Karnaough map. |
<WRAP center> | <WRAP center> | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | 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> | ||
- | < | + | < |
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | For getting | + | To get used to the four-dimensional Karnaugh map, we expand our Therm-o-Safety: |
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: | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
Zeile 391: | Zeile 393: | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
=== Disjunctive Form === | === Disjunctive Form === | ||
- | The Karnaugh map can now be used to either get the disjunctive form (= sum of products) when looking | + | The Karnaugh map can now be used to either get the disjunctive form (= sum-of-products) when looking |
+ | We will first look at the disjunctive form. There are multiple | ||
<WRAP center> | <WRAP center> | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | The group $I$ in <imgref pic23> can be expanded, since 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> | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | This can be transformed back into a formula. We can derive the boolean terms from the Karnaugh map with the folloring | + | This can be transformed back into a formula. We can derive the boolean terms from the Karnaugh map with the following |
- | - Investigate | + | - Investigate |
- | - For the sum of products each group has to be the product (AND-combination) of the inputs / coordinates. | + | - For the sum-of-products, each group has to be the product (AND-combination) of the inputs/ |
- | - 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> | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | 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 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} | ||
Zeile 434: | Zeile 437: | ||
=== Conjunctive Form === | === Conjunctive Form === | ||
- | Similarily | + | Similarly, |
<WRAP center> | <WRAP center> | ||
Zeile 450: | Zeile 453: | ||
</ | </ | ||
- | Also here, we can derive the boolean terms from the Karnaugh map with the folloring | + | Also here, we can derive the boolean terms from the Karnaugh map with the following |
- | - Investigate | + | - Investigate |
- | - For the products | + | - For the product-of-sum, each group has to be the sum (OR-combination) of the inputs/ |
- | - In the end the formula can again be derived, now as the product of sums. | + | - In the end, the formula can again be derived, now as the product-of-sums. |
<WRAP center> | <WRAP center> | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
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 map, we 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 this, only 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> | ||
- | < | + | < |
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | 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, 4, or 8 cells are allowed. In <imgref pic30> some not allowed groups are shown |
<WRAP center> | <WRAP center> | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
=== 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=" | <callout icon=" | ||
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**: | * **Redundant prime implicants**: | ||
* **Selective prime implicants**: | * **Selective prime implicants**: | ||
Zeile 518: | Zeile 521: | ||
</ | </ | ||
- | <imgref pic31> depicts the different implicants | + | <imgref pic31> depicts the different implicants |
<WRAP center> | <WRAP center> | ||
Zeile 526: | Zeile 529: | ||
</ | </ | ||
- | 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 | + | * **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: | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
+ | |||
+ | === higher dimensional Karnaugh Maps === | ||
+ | |||
+ | For higher dimensional Karnaugh maps the implicants look more am more unintuitive (see <imgref pic33>). | ||
+ | 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> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | When solving higher dimensional boolean problems the [[https:// | ||
---- | ---- | ||
+ | ==== Exercises ==== | ||
+ | |||
+ | < | ||
+ | Tipp: You can check your answer yourself. | ||
+ | * Online: [[https:// | ||
+ | * in the [[https:// | ||
+ | * '' | ||
+ | * filling the truth table | ||
+ | * change the variable names by right click on the name | ||
+ | * '' | ||
+ | |||
+ | </ | ||
<panel type=" | <panel type=" | ||
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> | ||
- | < | + | < |
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | </WRAP></WRAP></panel> | + | 1. Write down the DNF for the function table. \\ <button size=" |
+ | 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=" | ||
+ | \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: | ||
+ | &= \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 | ||
+ | &= (\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 && | ||
+ | &= (\overline{X1} + {X2}) \cdot X0 && \\ | ||
+ | \end{align*} | ||
+ | </ | ||
- | <panel type="info" | + | <button size=" |
+ | The final result is | ||
+ | \begin{align*} | ||
+ | Y = (\overline{X1} + {X2}) \cdot X0 | ||
+ | \end{align*} | ||
+ | </collapse> | ||
- | A full BCD-to-7-Segment Decoder with positive logic shell be developed | + | 3. Write down the CNF for the function table \\ <button size=" |
- | As a base the following truth table shall be used. | + | For the CNF, one has to only use the following lines to get the maxterms: |
- | - Write down the DNF and CNF for the function table and the outputs a...g. OUse the don't care states wisely. | + | {{drawio> |
- | - | + | </ |
- | - 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. | + | |
+ | 4. Minimize the CNF step by step, starting with the used boolean rules \\ | ||
+ | <button size=" | ||
+ | \begin{align*} | ||
+ | Y &= (X2 + X1 + X0)_{\color{blue}{I}} \cdot \color{blue}{(X2 + \overline{X1} + X0)}_{\color{blue}{II}} && | ||
+ | &= (X2 + X1 + X0)_{\color{blue}{I}} \cdot (X2 + \overline{X1} + X0)_{\color{blue}{II}} | ||
+ | &= (X2 + X1 + X0)_{\color{blue}{I}} \cdot (\overline{X2} + X1 + X0)_{\color{blue}{IV}} | ||
+ | &= (X2 + \color{blue}{X1 + X0})_{\hphantom{I}} \cdot (\overline{X2} + \color{blue}{X1 + X0})_{\hphantom{IV}} && | ||
+ | &= (X1 + X0) \cdot (X2 + \overline{X2}) && | ||
+ | &= (X1 + X0) \cdot \color{blue}{(X2 + \overline{X2})} && | ||
+ | & | ||
+ | & | ||
+ | & | ||
+ | & | ||
+ | & | ||
+ | \end{align*} | ||
+ | </ | ||
+ | <button size=" | ||
+ | The final result is | ||
+ | \begin{align*} | ||
+ | Y = (\overline{X1} + {X2}) \cdot X0 | ||
+ | \end{align*} | ||
+ | </ | ||
+ | |||
+ | 5. Show, that the DNF can be converted into the CNF (duality principle) \\ <button size=" | ||
+ | <WRAP hide> | ||
+ | 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 \\ | ||
+ | &= \overline{X2}\cdot \overline{X1} \cdot X0 + \color{blue}{{X2}\cdot \overline{X1} \cdot X0} + {X2}\cdot {X1} \cdot X0 \\ | ||
+ | \end{align*} | ||
- | <WRAP center> | ||
- | < | ||
- | </ | ||
- | {{drawio> | ||
</ | </ | ||
+ | </ | ||
+ | |||
+ | 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=" | ||
+ | {{drawio> | ||
+ | </ | ||
</ | </ | ||
- | <panel type=" | + | <panel type=" |
- | Use the [[https:// | + | A full BCD-to-7-Segment Decoder with a positive logic shell be developed |
- | + | As a base, the following truth table shall be used. | |
- | </ | + | |
+ | - Optimize the functions by the use of 7 Karnaugh maps. | ||
+ | - Show, that the minimized DNF can be converted into the CNF (duality principle) | ||
+ | - Create | ||
+ | | ||
+ | - Use at first only the DNF and CNF. | ||
+ | - After this, use the minimized DNF and the minimized DNF | ||
+ | - Check whether a 7-Segment-Display works fine with the created logic | ||
- | <panel type=" | ||
- | - compare the results with the output given [[https:// | + | <WRAP center> |
- | + | < | |
+ | </ | ||
+ | {{drawio> | ||
+ | </WRAP> | ||
</ | </ | ||
+ | <panel type=" | ||
+ | |||
+ | * 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:// | ||
+ | * Use the [[https:// | ||
+ | | ||
+ | </ | ||