Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
introduction_to_digital_systems:combinatorial_logic [2021/10/10 00:01] tfischer |
introduction_to_digital_systems:combinatorial_logic [2023/11/21 07:15] (aktuell) mexleadmin |
||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== 3. Combinatorical | + | ====== 3 Combinatorial |
< | < | ||
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 | ||
- | ===== 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 '' | ||
- | <WRAP column 100%> <panel type=" | + | <WRAP column 100%> |
+ | <panel type=" | ||
* 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 '' |
- | </ | + | </ |
+ | </ | ||
<WRAP center> | <WRAP center> | ||
- | < | + | < |
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
Zeile 109: | 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 116: | 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 123: | Zeile 126: | ||
</ | </ | ||
- | <WRAP column 100%> <panel type=" | + | <WRAP column 100%> |
+ | <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: | ||
+ | < | ||
\begin{align*} | \begin{align*} | ||
Y & | Y & | ||
Zeile 142: | Zeile 148: | ||
Y & | Y & | ||
\end{align*} | \end{align*} | ||
+ | </ | ||
+ | ==== 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 |
- | + | ||
- | In the sub-chapter before we had a look onto the combinations which generates | + | |
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 170: | 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 180: | Zeile 186: | ||
</ | </ | ||
- | When these intermediate outputs $Y'$, $Y'' | + | When these intermediate outputs $Y'$, $Y'' |
< | < | ||
Zeile 187: | Zeile 193: | ||
</ | </ | ||
- | Also the products | + | Also, the product-of-sum can be simplified: |
\begin{align*} | \begin{align*} | ||
Zeile 195: | 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 212: | Zeile 218: | ||
===== 3.2 Karnaugh Map ===== | ===== 3.2 Karnaugh Map ===== | ||
- | ===== 3.2.1 Introduction with example ===== | + | ==== 3.2.1 Introduction with the two dimensional Map ==== |
- | For our therm-o-safety example | + | For a simple introduction, |
+ | In <imgref pic13> (a) the truth table of this is shown. The leftmost 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}$). | ||
- | For this, we try to interpret the inputs of our example as dimensions | + | The given logic expression can also be interpreted |
+ | * There are only two coordinates on each axis possible: | ||
+ | * There are as many axes as variables given in the logic: For the example, we have two variables | ||
+ | * 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: These are the edges of a square (<imgref pic13> (b)). | ||
+ | |||
+ | 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$, 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. | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | The Karnaugh map will help us in the following to find simplifications of more complex logic expressions. | ||
+ | |||
+ | ==== 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. | ||
+ | |||
+ | 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. | ||
<WRAP center> | <WRAP center> | ||
- | < | + | < |
</ | </ | ||
- | {{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 value '' | + | * The formula $Y=1$ (independent from inputs |
- | * 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 surface of the cube are marked with the corresponding color. | ||
<WRAP center> | <WRAP center> | ||
- | < | + | < |
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
+ | |||
+ | 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$. | ||
+ | |||
+ | 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 cube onto a flat monitor or paper. It will also get more stressful for higher dimensions. | ||
<WRAP center> | <WRAP center> | ||
< | < | ||
</ | </ | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
- | [[https:// | + | Therefore, we try to find a better way to sketch the coordinates, |
+ | For the three-dimensional Karnaugh map, it is a good idea to " | ||
- | <panel type=" | + | <WRAP center> |
+ | <imgcaption pic14 | flattening the 3-dimensional cube represetation> | ||
+ | </imgcaption> | ||
+ | {{drawio>kmap3D.svg}} | ||
+ | </ | ||
- | | + | |
+ | 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 '' | ||
+ | - In other ways, the columns/ | ||
+ | In <imgref pic15> the dimensions are additionally marked with colors. | ||
+ | |||
+ | In the following chapters mainly the visualization shown in <imgref pic15> (b) is used. | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | With this representation, | ||
+ | * In light brown the group ('' | ||
+ | * In light blue the group ('' | ||
+ | * In light violet the group ('' | ||
+ | |||
+ | 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! | ||
+ | |||
+ | 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> | ||
+ | < | ||
+ | </imgcaption> | ||
+ | {{drawio> | ||
+ | </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. \\ | ||
+ | Independent of the permutation, | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </WRAP> | ||
+ | |||
+ | |||
+ | <WRAP column 100%> <panel type=" | ||
+ | |||
+ | * The Karnaugh map is an alternative way to represent a logical relation. | ||
+ | * 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) | ||
+ | |||
+ | </WRAP>< | ||
+ | |||
+ | ==== 3.2.3 Four-Dimensional Karnaugh Map ==== | ||
+ | |||
+ | 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 a page. | ||
+ | Here, a four-dimensional Karnaugh map might be a good representation. | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | 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$. | ||
+ | |||
+ | 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) ). | ||
+ | |||
+ | By this, we can visually derive the four-dimensional Karnaough map. | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{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 in an example in <imgref pic20>. | ||
+ | |||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | 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> | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | Now we can fill the Karnaugh map: | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | === Disjunctive Form === | ||
+ | |||
+ | The Karnaugh map can now be used to either get the disjunctive form (= sum-of-products) when looking at the groups of $1$s, or the conjunctive form (= product-of-sums) out of the groups of $0$s. | ||
+ | We will first look at the disjunctive form. There are multiple ways to group the minterms. One is shown here: | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | The group $I$ in <imgref pic23> | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | This can be transformed back into a formula. We can derive the boolean terms from the Karnaugh map with the following steps (see <imgref pic26>): | ||
+ | - Investigate every single group individually. | ||
+ | - For the sum-of-products, | ||
+ | - Then the formula can be derived as the sum-of-products... | ||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | 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 $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: | ||
+ | \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} | ||
+ | \end{align*} | ||
+ | |||
+ | === Conjunctive Form === | ||
+ | |||
+ | Similarly, we look at the conjunctive form. Here we have to find groups of $0$s. One way of grouping the maxterms is shown here: | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | The optimization would be: | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | Also here, we can derive the boolean terms from the Karnaugh map with the following steps (see <imgref pic27>): | ||
+ | - Investigate every single group individually. | ||
+ | - For the product-of-sum, | ||
+ | - In the end, the formula can again be derived, now as the product-of-sums. | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | \begin{align*} | ||
+ | Y &= ( \color{magenta}{X_2}) \cdot( \color{green}{\overline{X_3}} + \color{blue}{X_1}) | ||
+ | \end{align*} | ||
+ | |||
+ | Beyond the maxterms this formula can be optimized to | ||
+ | |||
+ | \begin{align*} | ||
+ | Y & | ||
+ | \end{align*} | ||
+ | |||
+ | When comparing the disjunctive solution ($X_3 \cdot X_1 \cdot X_0 + \cdot \overline{X_3} \cdot X_2 $) with the conjunctive one ($X_2 \cdot X_1 \cdot X_0 + \cdot \overline{X_3} \cdot X_2 $) we see, that these are definitely different. The given truth table had don't care states. This can be taken as $0$s or $1$s - and therefore combined in groups of $0$s or groups of $1$s. | ||
+ | |||
+ | |||
+ | ==== 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 at some definitions. | ||
+ | |||
+ | === 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). | ||
+ | |||
+ | 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 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 8: Derived from 1 input , e.g. $\overline{X_1} $ | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{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 | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | === Necessary and Important Groups === | ||
+ | |||
+ | 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=" | ||
+ | |||
+ | * **implicant** (I) is what we called " | ||
+ | * **prime implicant** (PI) is an implicant, which is not completely included in any other possible 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: | ||
+ | * **Redundant prime implicants**: | ||
+ | * **Selective prime implicants**: | ||
+ | |||
+ | </ | ||
+ | |||
+ | <imgref pic31> depicts the different implicants in one example. | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | 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. | ||
+ | * **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>) | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{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=" | ||
+ | |||
+ | The following truth table is given. | ||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | 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> | ||
+ | </ | ||
+ | |||
+ | 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*} | ||
+ | </ | ||
+ | |||
+ | <button size=" | ||
+ | The final result is | ||
+ | \begin{align*} | ||
+ | Y = (\overline{X1} + {X2}) \cdot X0 | ||
+ | \end{align*} | ||
+ | </ | ||
+ | |||
+ | 3. Write down the CNF for the function table \\ <button size=" | ||
+ | For the CNF, one has to only use the following lines to get the maxterms: | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | 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 un-minimized DNF can be converted into the un-minimized CNF (duality principle) \\ <button size=" | ||
+ | |||
+ | 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 | ||
+ | \end{align*} | ||
+ | |||
+ | </ | ||
+ | |||
+ | 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=" | ||
+ | |||
+ | A full BCD-to-7-Segment Decoder with a positive logic shell be developed | ||
+ | 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. | ||
+ | - Optimize the functions by the use of 7 Karnaugh maps. | ||
+ | - Show, that the minimized DNF can be converted into the CNF (duality principle) | ||
+ | - Create a Karnaugh map and mark the smallest number of the largest prime implicants. Derive the minimized DNF and CNF from the map. Mark the smallest number of the largest prime implicants. \\ Write down the derived, smallest formula based on CNF and DNF. | ||
+ | - Check the expressions with the program " | ||
+ | - 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 | ||
+ | |||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | <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:// | ||
+ | | ||
+ | </ | ||