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 [2023/09/19 23:44] mexleadmin |
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 <imgref pic1> enables to output of distinct logic values for each logic input. When you change the '' | + | The combinatorial logic shown in <imgref pic1> enables to output of distinct logic values for each logic input. When you change the '' |
Tasks: | Tasks: | ||
Zeile 16: | Zeile 16: | ||
- | ===== 3.1 Combinatorial | + | ===== 3.1 Combinatorial |
Up to now, we looked at simple logic circuits. These are relatively easy to analyze and synthesize (=develop). The main question in this chapter is: how can we set up and optimize logic circuits? | Up to now, we looked at simple logic circuits. These are relatively easy to analyze and synthesize (=develop). The main question in this chapter is: how can we set up and optimize logic circuits? | ||
Zeile 39: | Zeile 39: | ||
==== 3.1.1 Example ==== | ==== 3.1.1 Example ==== | ||
- | In order to understand the synthesis of 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 in the case of failure. | * Additionally there are 2 non-selectable positions in the case of failure. | ||
Zeile 58: | Zeile 58: | ||
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 synthesize the requested logic. | + | By this, we have done the first step to synthesize the requested logic. |
==== 3.1.2 Sum-of-Products ==== | ==== 3.1.2 Sum-of-Products ==== | ||
Zeile 92: | 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 an output of '' | * A minterm results in an output of '' | ||
Zeile 152: | Zeile 152: | ||
==== 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 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 one distinct combination. | + | In the sub-chapter before we had a look at the combinations which generate an output of $Y=1$ using the AND operator. Now we are investigating the combinations with $Y=0$. Therefore, we need an operator, which results in $0$ for only one distinct combination. |
The first combination to look for is '' | The first combination to look for is '' | ||
Zeile 159: | Zeile 159: | ||
"$Y=1$ when $X_0$ is $0$ OR $X_1$ is $1$ OR $X_2$ is $1$ " | "$Y=1$ when $X_0$ is $0$ OR $X_1$ is $1$ OR $X_2$ is $1$ " | ||
- | This is the same like: $\overline{X_0} + X_1 + X_2$ \\ The boolean operator we need here is the OR-operator. | + | This is the same as: $\overline{X_0} + X_1 + X_2$ \\ The boolean operator we need here is the OR-operator. |
Similarly, the combinations '' | Similarly, the combinations '' | ||
Zeile 166: | Zeile 166: | ||
* 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 an output of '' | * A maxterm results in an output of '' | ||
Zeile 225: | Zeile 225: | ||
The given logic expression can also be interpreted in a coordinate system, with the following conditions: | The given logic expression can also be interpreted in a coordinate system, with the following conditions: | ||
* There are 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. | ||
Zeile 248: | Zeile 248: | ||
==== 3.2.2 The three-dimensional Karnaugh Map ==== | ==== 3.2.2 The three-dimensional Karnaugh Map ==== | ||
- | In this subchapter, we will have a look at our example of therm-o-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. | + | 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 '' | ||
Zeile 262: | Zeile 262: | ||
There is also an alternative way to look at 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 (='' | ||
Zeile 275: | Zeile 275: | ||
</ | </ | ||
- | With this representation in mind, we can simplify other representations much more simpler. \\ | + | 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$. | ||
Zeile 287: | Zeile 287: | ||
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> | ||
Zeile 298: | Zeile 298: | ||
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 the 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/ | + | - 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. | ||
Zeile 314: | Zeile 314: | ||
* In light violet 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 in order to flatten it. | + | 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! | Therefore, these cells are also neighboring. This leads to the conclusion, that the borders of the Karnaugh map are connected to opposite borders! | ||
Zeile 325: | Zeile 325: | ||
</ | </ | ||
- | We also have to remember, that there are multiple permutations to show exactly the same logic assignment. This can be interpreted as other ways to unwrap the cube. The <imgref pic17> shows the variant from before at (a). In the image (b) the coordinates are mixed ($X_0 \rightarrow X_1$, $X_1 \rightarrow X_2$, $X_2 \rightarrow X_0$). In the image (c) the position of the origin is not in the upper left corner anymore. \\ | + | 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, | Independent of the permutation, | ||
Zeile 338: | Zeile 338: | ||
* The Karnaugh map is an alternative way to represent a logical relation. | * The Karnaugh map is an alternative way to represent a logical relation. | ||
- | * 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) | ||
Zeile 346: | Zeile 346: | ||
For the four-dimensional Karnaugh map, the situation becomes more complicated in the classical coordinate system. | 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 on a page. | + | 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. | Here, a four-dimensional Karnaugh map might be a good representation. | ||
Zeile 355: | Zeile 355: | ||
</ | </ | ||
- | In order to create a four-dimensional Karnaugh map, we look at first how the two and three-dimensional Karnaugh maps can be derived. The <imgref pic19> (a) shows, that the two-dimensional Karnaugh map can be created from a one-dimensional one by folding the table on the x-axis and adding $10_2$ to all values. The additional line is marked with the new dimension $X_1$. | + | To create a four-dimensional Karnaugh map, we 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 three-dimensional one is created by folding the table on the __y-axis__ and adding $100_2$ to all values. The additional line is marked with the new dimension $X_2$ (<imgref pic19> (b) ). Be aware, that the $X_0$ marking now has to be extended - it is also folded to the right. | ||
Zeile 378: | Zeile 378: | ||
</ | </ | ||
- | 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 430: | Zeile 430: | ||
* 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 these 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 507: | Zeile 507: | ||
=== 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. This 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 529: | 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 prime implicants | * **No redundant prime implicant** is needed. They are covered by core prime implicants | ||
Zeile 582: | Zeile 582: | ||
</ | </ | ||
- | 2. Minimize the DNF step by step, starting the used boolean rules \\ <button size=" | + | 2. Minimize the DNF step by step, starting |
\begin{align*} | \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: | 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: | ||
Zeile 606: | Zeile 606: | ||
</ | </ | ||
- | 4. Minimize the CNF step by step, starting the used boolean rules \\ | + | 4. Minimize the CNF step by step, starting |
<button size=" | <button size=" | ||
Zeile 631: | Zeile 631: | ||
</ | </ | ||
- | 5. Show, that the DNF can be converted into the CNF (duality principle) \\ <button size=" | + | 5. Show, that the un-minimized |
- | <WRAP hide> | + | |
The distributive law ($a\cdot(b+c)=a\cdot b + a \cdot c$) can be generalized - similar to the conventional algebra: | The distributive law ($a\cdot(b+c)=a\cdot b + a \cdot c$) can be generalized - similar to the conventional algebra: | ||
\begin{align*} | \begin{align*} | ||
Zeile 643: | Zeile 643: | ||
\end{align*} | \end{align*} | ||
- | This can be applied | + | This can be applied |
\begin{align*} | \begin{align*} | ||
- | Y &= \overline{X2}\cdot \overline{X1} \cdot X0 + \color{blue}{{X2}\cdot \overline{X1} \cdot X0} + {X2}\cdot {X1} \cdot X0 \\ | + | 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*} | \end{align*} | ||
- | </ | ||
</ | </ | ||
Zeile 661: | Zeile 659: | ||
<panel type=" | <panel type=" | ||
- | A full BCD-to-7-Segment Decoder with positive logic shell be developed | + | A full BCD-to-7-Segment Decoder with a positive logic shell be developed |
As a base, the following truth table shall be used. | 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. | - Write down the DNF and CNF for the function table and the outputs a...g. Use the don't care states wisely. | ||
Zeile 686: | Zeile 684: | ||
* Write a random allocation of $0$s and $1$s to the variations of inputs. Write the min- and maxterms | * 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:// | * Compare the results with the output given [[https:// | ||
- | * Use the [[https:// | + | * Use the [[https:// |
| | ||
</ | </ | ||