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:boolean_algebra [2022/10/19 15:46] tfischer |
introduction_to_digital_systems:boolean_algebra [2023/09/19 23:44] mexleadmin |
||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== 1. Boolean Algebra ====== | + | ====== 1 Boolean Algebra ====== |
- | ===== 1.1 Motivation: Digital | + | ===== 1.1 Motivation: Digital |
< | < | ||
Zeile 14: | Zeile 14: | ||
</ | </ | ||
- | ==== 1.1.1 Everything is one exept zero... ==== | + | ==== 1.1.1 Everything is one, except the zero... ==== |
<WRAP center> | <WRAP center> | ||
Zeile 22: | Zeile 22: | ||
</ | </ | ||
- | Before we start to dive deeper into the digital systems, it is a good idea to approach the topic with a first practical example. For this, we have a look onto an USB cable and mentally cut the cable. | + | Before we start to dive deeper into digital systems, it is a good idea to approach the topic with a first practical example. For this, we look at a USB cable and mentally cut the cable. |
- | We will see a total of four wires waiting for us. Two of them are called D+ and D-. These are the wires that are used for digital data transmission. With special tools - like an oscilloscope we can measure the time course of the voltage between D+ and D-. This voltage | + | We will see a total of four wires waiting for us. Two of them are called D+ and D-. These are the wires that are used for digital data transmission. With special tools - like an oscilloscope, we can measure the time course of the voltage between D+ and D-. This voltage shows two different levels and rises and falls in between. What we see are the **logic states** $0$ or $1$! ((In detail it is a bit more complicated since USB is not using the voltage levels but the edges to encode the bits. Details [[https:// |
Beyond data transmission, | Beyond data transmission, | ||
Zeile 29: | Zeile 29: | ||
* or a switch that is open or closed. | * or a switch that is open or closed. | ||
* or a light that is on or off. | * or a light that is on or off. | ||
- | * even whether it is raining or not raining, whether a dog is barking or not barking or other things - we can encode all of that in binary units. | + | * even whether it is raining or not raining, whether a dog is barking or not barking, or other things - we can encode all of that in binary units. |
- | In reality, the measured voltage on the USB cable would also show noise and only roughly depict the two states. When we ignore the noise and only assume that an upper level ($HIGH$ or $H$) encode | + | In reality, the measured voltage on the USB cable would also show noise and only roughly depict the two states. When we ignore the noise and only assume that an upper level ($HIGH$ or $H$) encodes |
<WRAP column 100%> <panel type=" | <WRAP column 100%> <panel type=" | ||
Zeile 40: | Zeile 40: | ||
* $HIGH$, $LOW$ | * $HIGH$, $LOW$ | ||
* In binary logic, every expression can only be **true or false**. If something is not true, it has to be false - and vice versa. | * In binary logic, every expression can only be **true or false**. If something is not true, it has to be false - and vice versa. | ||
- | * Therefore, binary logic has some **limitations for real world applications**: | + | * Therefore, binary logic has some **limitations for real-world applications**: |
</ | </ | ||
- | We will find out more of the details behind | + | We will find out more of the details behind |
< | < | ||
Zeile 51: | Zeile 51: | ||
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | ==== 1.1.2 At the heart of a computer | + | ==== 1.1.2 At the Heart of a Computer |
< | < | ||
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | The core of a computer is the processor in which the instructions are executed. This central processing unit (CPU) is also used in microcontrollers, | + | The core of a computer is the processor in which the instructions are executed. This central processing unit (CPU) is also used in microcontrollers, |
- | In the microcontroller, | + | In the microcontroller, |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
Zeile 70: | Zeile 70: | ||
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | But now let's take a look at the structure of the processor. The processor shown in <imgref pic2> | + | But now let's take a look at the structure of the processor. The processor shown in <imgref pic2> |
- | The images depict various peripheral components: The processor, FLASH, EEPROM and fuses will be shown in the following chapters. The voltage supply (German ' | + | The images depict various peripheral components: The processor, FLASH, EEPROM, and fuses will be shown in the following chapters. The voltage supply (German ' |
The following clip shows a zoom into the smallest parts of the controller. | The following clip shows a zoom into the smallest parts of the controller. | ||
Zeile 81: | Zeile 81: | ||
- | One question is still unclear: how can we connect the zeros and ones in such a way, that the processor can calculate something like $23 + 42$? For this we need to have a look onto binary logic. | + | One question is still unclear: how can we connect the zeros and ones in such a way, that the processor can calculate something like $23 + 42$? For this, we need to have a look at binary logic. |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
Zeile 94: | Zeile 94: | ||
- apply the Boolean rules of arithmetic. | - apply the Boolean rules of arithmetic. | ||
- simplify Boolean expressions. | - simplify Boolean expressions. | ||
- | - understand the following terms: bit, the different (logic) gates, timing diagram, truth table. | + | - understand the following terms: bit, the different (logic) gates, timing diagram, |
- understand the purpose of the Tri-State gate and the " | - understand the purpose of the Tri-State gate and the " | ||
- understand the use of the " | - understand the use of the " | ||
Zeile 100: | Zeile 100: | ||
</ | </ | ||
- | ==== 1.2.1 First steps into logic ==== | + | ==== 1.2.1 First Steps into Logic ==== |
- | We have already learned about the ' | + | We have already learned about the ' |
- | The Greek Philosopher Aristotle started to build up a systematic in order to conclude from statements like 'at night, it is dark outside' | + | The Greek Philosopher Aristotle started to build up a system |
- | It might seem a bit unrelated to comtrollers | + | It might seem a bit unrelated to controllers |
- | {{wp> | + | {{wp> |
- | One axiom we have already seen: If something is true, it cannot be false ans vice versa (the ' | + | One axiom we have already seen: If something is true, it cannot be false and vice versa (the ' |
Other axioms help to combine statements. This is called ' | Other axioms help to combine statements. This is called ' | ||
- | * This was already used some sentences before: If 'at night, it is dark outside' | + | * This was already used in some sentences before: If "at night, it is dark outside" |
* Another deduction is the **equivalence**: | * Another deduction is the **equivalence**: | ||
- | In the following, we will have a look onto the basic logic combinations, | + | In the following, we will have a look at the basic logic combinations, |
- | In digital systems the logic operators can be represented as a circuit of transistors or switches. This can be blackboxed | + | In digital systems, the logic operators can be represented as a circuit of transistors or switches. This can be black-boxed |
- | This tools will get more familiar in the next subcapter. | + | These tools will get more familiar in the next subchapter. |
< | < | ||
- | A good introduction | + | A good introduction |
{{youtube> | {{youtube> | ||
</ | </ | ||
- | ==== 1.2.2 The logic operator | + | ==== 1.2.2 The logic Operator |
< | < | ||
Zeile 133: | Zeile 133: | ||
The first very simple circuit negates the input value. It is also called an inverter or negation ([[https:// | The first very simple circuit negates the input value. It is also called an inverter or negation ([[https:// | ||
- | When you think about the inputs and outputs in the shown picture above, you realise, that the input is a voltage, but the output is a current. This is sometimes beneficial, but inside an digital systems commonly only voltages are used. | + | When you think about the inputs and outputs in the shown picture above, you realize, that the input is a voltage, but the output is current. This is sometimes beneficial, but within |
< | < | ||
Zeile 142: | Zeile 142: | ||
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | In order to control | + | To control |
- | With this setup the logic voltages ($0V$, $5V$) are just switched | + | With this setup, the logic voltages ($0~\rm V$, $5~\rm V$) are just switched |
- | Comparing the circuits in <imgref pic20> and <imgref pic21>, one could simply see, that double the amount | + | Comparing the circuits in <imgref pic20> and <imgref pic21>, one could simply see, that double the number |
<WRAP center> | <WRAP center> | ||
Zeile 154: | Zeile 154: | ||
</ | </ | ||
- | The circuit symbols of the NOT-gate are shown in <imgref BildNr06> | + | The circuit symbols of the NOT-gate are shown in <imgref BildNr06> |
<WRAP center> | <WRAP center> | ||
Zeile 163: | Zeile 163: | ||
Besides the symbol other representation are also common (see also <imgref BildNr07> | Besides the symbol other representation are also common (see also <imgref BildNr07> | ||
- | * The **truth table** shows the input(s) $X$ on the left and the output(s) $Y$ on the right. There is a row for each distinct combination of inputs. This representation will get handy in the next chapters, | + | * The **truth table** shows the input(s) $X$ on the left and the output(s) $Y$ on the right. There is a row for each distinct combination of inputs. This representation will get handy in the next chapters, to analyze |
- | * The **timing diagram** shows the sequential behavior. For this diagram, the input variables are stimulated with all possible state combinations. Also this will become handy especialy | + | * The **timing diagram** shows the sequential behavior. For this diagram, the input variables are stimulated with all possible state combinations. Also, this will become handy, especially |
* In **math** the inversion has also multiple representations e.g. | * In **math** the inversion has also multiple representations e.g. | ||
* $Y = /X$ (used e.g. for input with a keyboard) | * $Y = /X$ (used e.g. for input with a keyboard) | ||
Zeile 174: | Zeile 174: | ||
* Inputs are always denoted with $X$ | * Inputs are always denoted with $X$ | ||
* Outputs are always denoted with $Y$ | * Outputs are always denoted with $Y$ | ||
- | * There are multiple ways for representing | + | * There are multiple ways for representing logic. The most common ones are: \\ electric |
* When you use a representation: | * When you use a representation: | ||
Zeile 180: | Zeile 180: | ||
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | ==== 1.2.3 The logic operator | + | ==== 1.2.3 The logic Operator |
< | < | ||
Zeile 189: | Zeile 189: | ||
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | The next circuit will generate | + | The next circuit will generate |
<WRAP center> | <WRAP center> | ||
Zeile 203: | Zeile 203: | ||
</ | </ | ||
- | Again, the other representation | + | Again, the other representations |
* The truth table and timing diagram are depicted in <imgref pic24>. | * The truth table and timing diagram are depicted in <imgref pic24>. | ||
* In **math** the AND operation has again multiple representations e.g. | * In **math** the AND operation has again multiple representations e.g. | ||
Zeile 211: | Zeile 211: | ||
* $Y = X_0 \land X_1$ (used in logic) | * $Y = X_0 \land X_1$ (used in logic) | ||
- | For upcoming, more complex terms the algebraic notation ($Y = X_0 \cdot X_1$) usually | + | For upcoming, more complex terms the algebraic notation ($Y = X_0 \cdot X_1$) usually |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | ==== 1.2.4 The logic operator | + | ==== 1.2.4 The logic Operator |
< | < | ||
Zeile 223: | Zeile 223: | ||
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | The NOT gate is often used in front of or after other gates. When used after AND gates, this creates | + | The NOT gate is often used in front of or after other gates. When used after AND gates, this creates |
<WRAP center> | <WRAP center> | ||
Zeile 231: | Zeile 231: | ||
</ | </ | ||
- | The circuit symbols are shown in <imgref pic26> | + | The circuit symbols are shown in <imgref pic26> |
<WRAP center> | <WRAP center> | ||
Zeile 239: | Zeile 239: | ||
</ | </ | ||
- | Again, the other representation | + | Again, the other representations |
* The truth table and timing diagram are depicted in <imgref pic27>. | * The truth table and timing diagram are depicted in <imgref pic27>. | ||
* In **math** the NAND operation has again multiple representations e.g. | * In **math** the NAND operation has again multiple representations e.g. | ||
Zeile 248: | Zeile 248: | ||
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | ==== 1.2.5 The logic operator | + | ==== 1.2.5 The logic Operator |
< | < | ||
Zeile 258: | Zeile 258: | ||
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | We already had a look onto the AND gate. So what about OR? Of course there is also this kind of operation. This is called a logical **__dis__junction** ([[https:// | + | We already had a look at the AND gate. So what about OR? Of course, there is also this kind of operation. This is called a logical **__dis__junction** ([[https:// |
<WRAP center> | <WRAP center> | ||
Zeile 266: | Zeile 266: | ||
</ | </ | ||
- | The circuit symbols are shown in <imgref pic29>. The DIN symbol is derived from the fact, that one ore more inputs have to be true to get an true output. | + | The circuit symbols are shown in <imgref pic29>. The DIN symbol is derived from the fact, that one or more inputs have to be true to get a true output. |
<WRAP center> | <WRAP center> | ||
Zeile 274: | Zeile 274: | ||
</ | </ | ||
- | Again, the other representation | + | Again, the other representations |
* The truth table and timing diagram are depicted in <imgref pic30>. | * The truth table and timing diagram are depicted in <imgref pic30>. | ||
* In **math** the OR operation has again multiple representations e.g. | * In **math** the OR operation has again multiple representations e.g. | ||
* $Y = X0 + X1$ (used e.g. for input with a keyboard or in handwriting) | * $Y = X0 + X1$ (used e.g. for input with a keyboard or in handwriting) | ||
- | * '' | + | * '' |
* $Y = X_0 \lor X_1$ (used in logic, the $\lor$ stands for the Latin //vel//, which means or) | * $Y = X_0 \lor X_1$ (used in logic, the $\lor$ stands for the Latin //vel//, which means or) | ||
- | For upcoming, more complex terms the algebraic notation ($Y = X_0 + X_1$) usually | + | For upcoming, more complex terms the algebraic notation ($Y = X_0 + X_1$) usually |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | ==== 1.2.6 The logic operator | + | ==== 1.2.6 The logic Operator |
< | < | ||
Zeile 293: | Zeile 293: | ||
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | Beside the OR there is also an " | + | Beside the OR there is also an " |
<WRAP center> | <WRAP center> | ||
Zeile 309: | Zeile 309: | ||
</ | </ | ||
- | Again, the other representation | + | Again, the other representations |
* The truth table and timing diagram are depicted in <imgref pic33>. | * The truth table and timing diagram are depicted in <imgref pic33>. | ||
* In **math** the XOR operation has again multiple representations e.g. | * In **math** the XOR operation has again multiple representations e.g. | ||
Zeile 328: | Zeile 328: | ||
==== 1.2.7 The Tri-State Gate ==== | ==== 1.2.7 The Tri-State Gate ==== | ||
- | The [[https:// | + | The [[https:// |
The essence of the tri-state gate is - in short - to be able to output ' | The essence of the tri-state gate is - in short - to be able to output ' | ||
- | One possible output of the tri-state gate - besides high and low - is 'high ohmic', | + | One possible output of the tri-state gate - besides high and low - is 'high ohmic', |
< | < | ||
Zeile 340: | Zeile 340: | ||
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | <imgref pic28> shows the function of a tri-state gate: When the $EN$able input is set to high this gate becomes transparent and the output $Y$ equals the input $Y$. When $EN$ is set to low, the output is not pinned to the input anymore. In the simulation above with $EN = 0$ the output voltage is clamped by the voltage behind the resistor (here $3V$). Since this voltage could be any value this output cannot called low or high, but is called the (undefined) state $Z$. | + | <imgref pic28> shows the function of a tri-state gate: When the $EN$able input is set to high this gate becomes transparent and the output $Y$ equals the input $Y$. When $EN$ is set to low, the output is not pinned to the input anymore. In the simulation above with $EN = 0$ the output voltage is clamped by the voltage behind the resistor (here $3V$). Since this voltage could be any value this output cannot |
<WRAP center> | <WRAP center> | ||
Zeile 348: | Zeile 348: | ||
</ | </ | ||
- | The circuit symbol is shown in <imgref pic901>. Usually the triangle | + | The circuit symbol is shown in <imgref pic901>. Usually, the triangle |
- | Since the Tri-State gate is not an logical gate is does not have any mathematical representation. | + | Since the Tri-State gate is not a logical gate it does not have any mathematical representation. |
<WRAP center> | <WRAP center> | ||
Zeile 357: | Zeile 357: | ||
</ | </ | ||
- | In the <imgref pic920> the truth table is shown. In the case $EN=0$ the input $X$ does not matter. | + | In the <imgref pic920> the truth table is shown. In this case, $EN=0$ the input $X$ does not matter. |
- | The situation 'the input x does not matter' | + | The situation 'the input x does not matter' |
The ' | The ' | ||
<callout title=" | <callout title=" | ||
- | Let's imagine, we want to connect two microcontroller | + | Let's imagine, we want to connect two microcontrollers |
- | One posibility | + | One possibility |
* One wire for data sent from $A$ to $B$ | * One wire for data sent from $A$ to $B$ | ||
* One wire for data sent from $B$ to $A$ | * One wire for data sent from $B$ to $A$ | ||
- | This is shown in <imgref pic910>. You can change the inputs $X0$ and $X1$ by clicking on the '' | + | This is shown in <imgref pic910>. You can change the inputs $X0$ and $X1$ by clicking on the '' |
- | The big advantage of this configuration is, that both connected | + | The big advantage of this configuration is, that both connected |
< | < | ||
Zeile 377: | Zeile 377: | ||
Once we think of only using one wire, it becomes more complicated: | Once we think of only using one wire, it becomes more complicated: | ||
- | Therefore, we have to switch on both sides from reveive | + | Therefore, we have to switch on both sides from receive |
- | Again, you can change the inputs $X0$ and $X1$ by clicking on the '' | + | Again, you can change the inputs $X0$ and $X1$ by clicking on the '' |
- | The problem is, that in one time the output becomes an input, but boolean gates an algebra result | + | The problem is, that at one time the output becomes an input, but boolean gates an algebra result |
< | < | ||
Zeile 388: | Zeile 388: | ||
</ | </ | ||
- | We still could try solve it with gates, as seen in <imgref pic912>: Each microcontroller has an enable signal ('' | + | We still could try to solve it with gates, as seen in <imgref pic912>: Each microcontroller has an enable signal ('' |
- | The problem here: We are back to a two wire system. So, we need to "split up" the OR gate somehow.. | + | The problem here: We are back to a two-wire system. So, we need to "split up" the OR gate somehow.. |
< | < | ||
Zeile 398: | Zeile 398: | ||
</ | </ | ||
- | For this we can use the Tri-State gate: This enables to switch | + | For this we can use the Tri-State gate: This enables |
< | < | ||
Zeile 422: | Zeile 422: | ||
</ | </ | ||
- | Since the timing diagram is of importance not only for the upcoming courses like Electronics (in the 3rd semester) I recommend | + | Since the timing diagram is of importance not only for the upcoming courses like Electronics (in the 3rd semester) I recommend |
< | < | ||
Zeile 430: | Zeile 430: | ||
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | ===== 1.4 Convertibility of gates ===== | + | ===== 1.4 Convertibility of Gates ===== |
< | < | ||
Zeile 441: | Zeile 441: | ||
</ | </ | ||
- | Some of the circuits in the provious | + | Some of the circuits in the previous |
- | In this subchapter we will focus on combining NAND gates in order to build other gates. As we will see, based on the NAND and NOR gates any other gate and any other logic can be created. | + | In this subchapter, we will focus on combining NAND gates to build other gates. As we will see, based on the NAND and NOR gates any other gate and any other logic can be created. |
==== 1.4.1 NAND in NOT ==== | ==== 1.4.1 NAND in NOT ==== | ||
Zeile 452: | Zeile 452: | ||
</ | </ | ||
- | The conversion from NAND to NOT is relatively simple: When both inputs to NAND are the same (either ' | + | The conversion from NAND to NOT is relatively simple: When both inputs to NAND are the same (either ' |
- | A different approach to get an NOT is to set the second input to ' | + | A different approach to get a NOT is to set the second input to ' |
==== 1.4.2 NAND in AND ==== | ==== 1.4.2 NAND in AND ==== | ||
Zeile 464: | Zeile 464: | ||
</ | </ | ||
- | With the knwoledge | + | With the knowledge |
- | Therefore, the NOT hat to be set behind the NAND. | + | Therefore, the NOT had to be set behind the NAND. |
==== 1.4.3 NAND in OR ==== | ==== 1.4.3 NAND in OR ==== | ||
Zeile 475: | Zeile 475: | ||
</ | </ | ||
- | When each input of a NAND gate is inverted the result acts like an OR gate. In order to understand this, one can again look onto the truth table of the NAND and the OR gate and try to invetigate | + | When each input of a NAND gate is inverted the result acts like an OR gate. To understand this, one can again look at the truth table of the NAND and the OR gate and try to investigate |
Zeile 481: | Zeile 481: | ||
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | ===== 1.5 Rules for boolean | + | ===== 1.5 Rules for boolean |
< | < | ||
Zeile 493: | Zeile 493: | ||
</ | </ | ||
- | We have seen, that (at least) some of the gates can be represented | + | We have seen, that (at least) some of the gates can be represented |
- | ==== 1.5.1 The set of rules ==== | + | ==== 1.5.1 The Set of Rules ==== |
The following table shows the main rules which help us to generate and optimize logic expressions and circuits. \\ | The following table shows the main rules which help us to generate and optimize logic expressions and circuits. \\ | ||
It is possible to click on "math representation" | It is possible to click on "math representation" | ||
- | Have a look for the algebraic representation. These are probably much simpler to remember! | + | Have a look at the algebraic representation. These are probably much simpler to remember! |
Be also aware, that the logical expressions sometimes are written as $X0$, $X1$, ... and sometimes with other letters, like $a$, $b$, ... | Be also aware, that the logical expressions sometimes are written as $X0$, $X1$, ... and sometimes with other letters, like $a$, $b$, ... | ||
Zeile 512: | Zeile 512: | ||
|:::|$B \lor B \rightarrow B $|::: | | |:::|$B \lor B \rightarrow B $|::: | | ||
|2 |**Duality** | |2 |**Duality** | ||
- | |3 |**Neutral Element** | + | |3 |**Neutral Element** |
|:::|$a \land 1 = a $|::: | | |:::|$a \land 1 = a $|::: | | ||
|:::|$a \lor 0 = a $|::: | | |:::|$a \lor 0 = a $|::: | | ||
Zeile 524: | Zeile 524: | ||
|:::|$a \land b = b \land a $|::: | | |:::|$a \land b = b \land a $|::: | | ||
|:::|$a \lor b = b \lor a $|::: | | |:::|$a \lor b = b \lor a $|::: | | ||
- | |7 |**Associative Law** | For the same operator bracketing can be moved. \\ associative means "to unite" or " | + | |7 |**Associative Law** | For the same operator bracketing can be moved. \\ associative means "to unite" or "to connect" |
|:::|$a \land (b \land c) = (a \land b) \land c $|::: | | |:::|$a \land (b \land c) = (a \land b) \land c $|::: | | ||
|:::|$a \lor (b \lor c) = (a \lor b) \lor c $|::: | | |:::|$a \lor (b \lor c) = (a \lor b) \lor c $|::: | | ||
Zeile 530: | Zeile 530: | ||
|:::|$a \land (b \lor c) = (a \land b) \lor (a \land c)$|::: | |:::|$a \land (b \lor c) = (a \land b) \lor (a \land c)$|::: | ||
|:::|$a \lor (b \land c) = (a \lor b) \land (a \lor c)$|::: | |:::|$a \lor (b \land c) = (a \lor b) \land (a \lor c)$|::: | ||
- | |9 |**Law of Absorbtion** | In bracketed formulas similar expressions can " | + | |9 |**Law of Absorption** | In bracketed formulas similar expressions can " |
|:::|$a \land (a \lor b) = a$ \\ $a \land (\bar{a} \lor b) = a \land b $|::: | | |:::|$a \land (a \lor b) = a$ \\ $a \land (\bar{a} \lor b) = a \land b $|::: | | ||
|:::|$a \lor (a \land b) = a$ \\ $a \lor (\bar{a} \land b) = a \lor b $|::: | | |:::|$a \lor (a \land b) = a$ \\ $a \lor (\bar{a} \land b) = a \lor b $|::: | | ||
Zeile 545: | Zeile 545: | ||
|:::|$B + B \rightarrow B $|::: | | |:::|$B + B \rightarrow B $|::: | | ||
|2 |**Duality** | |2 |**Duality** | ||
- | |3 |**Neutral Element** | + | |3 |**Neutral Element** |
|:::|$a \cdot 1 = a $|::: | | |:::|$a \cdot 1 = a $|::: | | ||
|:::|$a + 0 = a $|::: | | |:::|$a + 0 = a $|::: | | ||
Zeile 557: | Zeile 557: | ||
|:::|$a \cdot b = b \cdot a $|::: | | |:::|$a \cdot b = b \cdot a $|::: | | ||
|:::|$a + b = b + a $|::: | | |:::|$a + b = b + a $|::: | | ||
- | |7 |**Associative Law** | For the same operator bracketing can be moved. \\ associative means "to unite" or " | + | |7 |**Associative Law** | For the same operator bracketing can be moved. \\ associative means "to unite" or "to connect" |
|:::|$a \cdot (b \cdot c) = (a \cdot b) \cdot c $|::: | | |:::|$a \cdot (b \cdot c) = (a \cdot b) \cdot c $|::: | | ||
|:::|$a + (b + c) = (a + b) + c $|::: | | |:::|$a + (b + c) = (a + b) + c $|::: | | ||
Zeile 563: | Zeile 563: | ||
|:::|$a \cdot (b + c) = (a \cdot b) + (a \cdot c)$|::: | |:::|$a \cdot (b + c) = (a \cdot b) + (a \cdot c)$|::: | ||
|:::|$a + (b \cdot c) = (a + b) \cdot (a + c)$|::: | |:::|$a + (b \cdot c) = (a + b) \cdot (a + c)$|::: | ||
- | |9 |**Law of Absorbtion** | In bracketed formulas similar expressions can " | + | |9 |**Law of Absorption** | In bracketed formulas similar expressions can " |
|:::|$a \cdot (a + b) = a$ \\ $a \cdot (\bar{a} + b) = a \cdot b $|::: | | |:::|$a \cdot (a + b) = a$ \\ $a \cdot (\bar{a} + b) = a \cdot b $|::: | | ||
|:::|$a + (a \cdot b) = a$ \\ $a + (\bar{a} \cdot b) = a + b $|::: | | |:::|$a + (a \cdot b) = a$ \\ $a + (\bar{a} \cdot b) = a + b $|::: | | ||
Zeile 573: | Zeile 573: | ||
</ | </ | ||
- | The last 3 laws are probable a kind of unintuitive. Therefore, these are shown in other representations. in the following | + | The last 3 laws are probably |
==== 1.5.2 Dive into Distributive Law ==== | ==== 1.5.2 Dive into Distributive Law ==== | ||
- | The distributive law can be shown on a simple example of daily life. \\ | + | The distributive law can be shown as a simple example of daily life. \\ |
When one says | When one says | ||
" | " | ||
he will be happy with | he will be happy with | ||
- | | + | |
- | Be aware, that the is no exclusiveness here. The person would also be happy with fries AND a water AND a coke! | + | Be aware, that the is no exclusiveness here. The person would also be happy with fries AND water AND a coke! |
- | The gate represenation | + | The gate representation |
- | Also the truth tables for the first gate ($Y'$, $Y'' | + | Also, the truth tables for the first gate ($Y'$, $Y'' |
- | But the conversion of the upper one to the lower one is not intuitive here. That is why the multiple | + | But the conversion of the upper one to the lower one is not intuitive here. That is why the multiple |
< | < | ||
Zeile 596: | Zeile 596: | ||
- | ==== 1.5.3 Dive into Law of Absorbtion | + | ==== 1.5.3 Dive into the Law of Absorption |
- | We will also try to transfer the law of absorbtion | + | We will also try to transfer the law of absorption |
When one says | When one says | ||
" | " | ||
he will be happy with | he will be happy with | ||
- | | + | fries... |
No matter whether there is coke with it. | No matter whether there is coke with it. | ||
- | The absortion | + | The absorption |
When one says | When one says | ||
" | " | ||
he will be happy with | he will be happy with | ||
fries OR a coke | fries OR a coke | ||
- | When he only gets fries the first part is true. When he only gets coke, the secont | + | When he only gets fries the first part is true. When he only gets coke, the second |
- | The gate represenation | + | The gate representation |
< | < | ||
Zeile 623: | Zeile 623: | ||
==== 1.5.4 Dive into DeMorgan' | ==== 1.5.4 Dive into DeMorgan' | ||
- | At last, let's have a look onto DeMorgan' | + | At last, let's have a look at DeMorgan' |
When one says | When one says | ||
- | " | + | " |
he will be unhappy when he gets either fries, or coke, or (fries and coke). | he will be unhappy when he gets either fries, or coke, or (fries and coke). | ||
- | The gate represenation | + | The gate representation |
- | On the left the NOT gate is explicitely | + | On the left, the NOT gate is explicitly |
< | < | ||
Zeile 640: | Zeile 640: | ||
* any AND is substituted with OR plus | * any AND is substituted with OR plus | ||
* any OR is substituted with AND | * any OR is substituted with AND | ||
- | Important is, that also the most upper expression also have to be inverted. | + | Important is, that also most upper expressions |
- | ==== 1.5.5 Example of a logic simplification | + | ==== 1.5.5 Example of a logic Simplification |
{{url> | {{url> | ||
Zeile 648: | Zeile 648: | ||
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ | ||
- | ===== 1.6 Examples of gate circuits | + | ===== 1.6 Examples of Gate Circuits |
- | ==== 1.6.1 Logic gates with multiple | + | ==== 1.6.1 Logic Gates with multiple |
Based on the associative law, when purely AND gates or purely OR gates are stacked the inputs are interchangeable. \\ | Based on the associative law, when purely AND gates or purely OR gates are stacked the inputs are interchangeable. \\ | ||
- | Therefore, this stacking can be substituted with a gate symbol with multiple | + | Therefore, this stacking can be substituted with a gate symbol with multiple |
- | The essence | + | The essence |
< | < | ||
Zeile 670: | Zeile 670: | ||
</ | </ | ||
- | ==== 1.6.2 Switchable | + | ==== 1.6.2 Switchable |
- | Sometimes it is important switch between inverting and not inverting an output. This can be done with the XOR gate. When the $EN$ in <imgref pic41> is active, the input $X$ will be inversed. | + | Sometimes it is important |
< | < | ||
Zeile 679: | Zeile 679: | ||
</ | </ | ||
- | One application for a switchable inverter would be an monochrome display, where every pixel can be set by one bit. When the display (or a small part like the cursor symbol) has to be inverted it would be great to do so with a simple gate. This can be seen in | + | One application for a switchable inverter would be a monochrome display, where every pixel can be set by one bit. When the display (or a small part like the cursor symbol) has to be inverted it would be great to do so with a simple gate. This can be seen in |
[[https:// | [[https:// | ||
- | Another usage is the inversion of binary numbers in the arithmetic | + | Another usage is the inversion of binary numbers in the arithmetic |
- | ==== 1.6.3 Data valve ==== | + | ==== 1.6.3 Data Valve ==== |
- | To deactivate a data flow a simple AND gate can be used. This is also useful for channelize | + | To deactivate a data flow a simple AND gate can be used. This is also useful for channelizing |
- | In the upper part of <imgref pic42> a single data valve is shown. Only when $EN=1$, then the value of the data input $D$ will set as the output $Y$. | + | In the upper part of <imgref pic42> a single data-valve is shown. Only when $EN=1$, then the value of the data input $X$ will set as the output $Y$. |
- | The lower part of <imgref pic42> shows the combination of two data valves. In this circuit depending on $EN$ the output of the the data input $DX$ will either be $Y0$ or $Y1$. This is also visible in the truth table. The truth table van be shortened which is also shown. | + | The lower part of <imgref pic42> shows the combination of two data valves. In this circuit depending on $EN$ the output of the data input $X$ will either be $Y0$ or $Y1$. This is also visible in the truth table. The truth table can be shortened which is also shown. |
< | < | ||
Zeile 699: | Zeile 699: | ||
==== 1.6.4 Multiplexer and Demultiplexer ==== | ==== 1.6.4 Multiplexer and Demultiplexer ==== | ||
- | In the linked ' | + | In the linked ' |
- | A **multiplexer** is a electronic switcher, which has several data inputs $D0$, $D1$ ... and one data output $Y$. Additionally to the data input there are also state inputs $S0$, $S1$, ... . The state inputs address which of the data input is routed to the data output. An example is given in <imgref pic43>. When $S0 = 0$ and $S1 = 0$ the zeroth data input $D0$ is the output, for $S0 = 1$ and $S0 = 0$ the first data input $D1$, for $S0 = 0$ and $S0 = 1$ the second. The ' | + | A **multiplexer** is an electronic switcher, which has several data inputs $D0$, $D1$ ... and one data output $Y$. Additionally to the data input, there are also state inputs $S0$, $S1$, ... . The state inputs address which of the data input is routed to the data output. An example is given in <imgref pic43>. When $S0 = 0$ and $S1 = 0$ the zeroth data input $D0$ is the output, for $S0 = 1$ and $S0 = 0$ the first data input $D1$, for $S0 = 0$ and $S0 = 1$ the second. The ' |
- | A **demultiplexer** is the counterpart to the multiplexer: | + | A **demultiplexer** is the counterpart to the multiplexer: |
< | < | ||
Zeile 710: | Zeile 710: | ||
</ | </ | ||
- | With the background given in subcapter | + | With the background given in subchapter |
< | < | ||
Zeile 725: | Zeile 725: | ||
* A nice overview of core ideas for [[https:// | * A nice overview of core ideas for [[https:// | ||
- | * Explanation of [[https:// | + | * Explanation of [[https:// |
* Wiki page on [[https:// | * Wiki page on [[https:// | ||
Zeile 781: | Zeile 781: | ||
<panel type=" | <panel type=" | ||
- | Realize the logic functions of NOT, AND, OR, NOR, XOR and XNOR exclusively with NAND gates. | + | Realize the logic functions of NOT, AND, OR, NOR, XOR, and XNOR exclusively with NAND gates. |
+ | |||
+ | |||
+ | <button size=" | ||
+ | |||
+ | **__NOT__** | ||
+ | |||
+ | An inverter can be realized with a NAND gate when both inputs are connected to the same input. \\ | ||
+ | When the input is $1$ the output will be $0$ and vice versa. | ||
+ | |||
+ | < | ||
+ | < | ||
+ | </ | ||
+ | {{url> | ||
+ | </ | ||
+ | |||
+ | **__AND__** | ||
+ | |||
+ | With the realization of the NOT gate an AND gate is also simple: just put the NOT after a NAND. | ||
+ | |||
+ | < | ||
+ | < | ||
+ | </ | ||
+ | {{url> | ||
+ | </ | ||
+ | |||
+ | **__OR__** | ||
+ | |||
+ | With the realization of the NOT gate an AND gate is also simple: just put the NOT after a NAND. | ||
+ | |||
+ | < | ||
+ | < | ||
+ | </ | ||
+ | {{url> | ||
+ | </ | ||
+ | |||
+ | **__NOR__** | ||
+ | |||
+ | Again the NOR gate can be derived from the NOT gate and OR gate. | ||
+ | |||
+ | < | ||
+ | < | ||
+ | </ | ||
+ | {{url> | ||
+ | </ | ||
+ | |||
+ | **__XOR__** | ||
+ | |||
+ | The XOR gate is a bit more complex. One path to a solution is the following: | ||
+ | - The XOR-gate only outputs a $0$ in the two cases $(X0=0, X1=0)$, $(X0=1, X1=1)$. | ||
+ | - Therefore, as a first idea, it would be great to have gates detecting $X0=0\; and\; X1=0$ such as $X0=1\; and\; X1=1$. | ||
+ | - The ladder one is $X0\cdot X1$, which is only $1$ for both inputs as $1$. \\ | ||
+ | - For detecting $X0=0\; and\; X1=0$ one can use $\overline{X0+X1}$, | ||
+ | - These two gates have to be combined in such a way that, only for $(X0=0, X1=0)$, $(X0=1, X1=1)$ the final output is $1$. \\ In other words: only when the output of the AND- and the NOR-gates is $0$, the final output has to be $1$. \\For this, a NOR gate can be used. | ||
+ | - All of the mentioned gates can be built based on NAND gates. This is shown in <imgref Ex_1_6_4_5 >. | ||
+ | |||
+ | < | ||
+ | < | ||
+ | </ | ||
+ | {{url> | ||
+ | </ | ||
+ | |||
+ | The shown circuit can even be simplified: | ||
+ | * Two Not-gates in series can be skipped since $\overline{\overline{X}}=X$. \\ With this knowledge, the XOR-gate needs 6 NAND gates. | ||
+ | * An alternative setup for the XOR-gate can be built by one NAND-, one OR-, and one AND-gate. This circuitry needs also 6 NAND gates. \\The circuitry is not shown. | ||
+ | * The circuity with the least NAND gates is shown in <imgref Ex_1_6_4_6 > | ||
+ | |||
+ | < | ||
+ | < | ||
+ | </ | ||
+ | {{url> | ||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | </ | ||
</ | </ | ||
<panel type=" | <panel type=" | ||
- | Realize the logic functions of NOT, OR, AND, NAND, XOR and XNOR exclusively with NOR gates. | + | Realize the logic functions of NOT, OR, AND, NAND, XOR, and XNOR exclusively with NOR gates. |
</ | </ | ||
Zeile 802: | Zeile 878: | ||
<button size=" | <button size=" | ||
- | Often the formula can be easier | + | Often the formula can be easier |
- | Additionally the brackets can be ignored in the case of products - similar to the convention in math for $(a \cdot b) + (c \cdot d) = ab + cd$ | + | Additionally, the brackets can be ignored in the case of products - similar to the convention in math for $(a \cdot b) + (c \cdot d) = ab + cd$ |
- | \begin{align*} | + | |
- | Y &= \color{blue}{\overline{X_0}}\; | + | $Y = \color{blue}{\overline{X_0}}\; |
- | | + | |
- | | + | |
- | | + | |
- | \end{align*} | + | |
With the **commutative law** switching term 2 and term 3 is possible: | With the **commutative law** switching term 2 and term 3 is possible: | ||
- | \begin{align*} | + | $Y = \color{blue}{\overline{X_0}}\; |
- | Y &= \color{blue}{\overline{X_0}}\; | + | $ |
- | | + | |
- | | + | |
- | | + | |
- | \end{align*} | + | |
- | Based on the **distributive law** the parts $\color{blue}{\overline{X_0}}\; | + | Based on the **distributive law** the parts $\color{blue}{\overline{X_0}}\; |
- | \begin{align*} | + | $Y = \color{blue}{\overline{X_0}}\; |
- | Y &= \color{blue}{\overline{X_0}}\; | + | |
- | | + | |
- | \end{align*} | + | |
The rule of the **complementary element** tells us that $a +\overline{a} = 1$ and based on the **neutral element** $a\cdot 1 = a$: | The rule of the **complementary element** tells us that $a +\overline{a} = 1$ and based on the **neutral element** $a\cdot 1 = a$: | ||
- | \begin{align*} | + | $Y = \color{blue}{\overline{X_0}}\; |
- | Y &= \color{blue}{\overline{X_0}}\; | + | \\ \\ ÷ |
- | | + | |
- | Y &= \color{blue}{\overline{X_0}}\; | + | $Y = \color{blue}{\overline{X_0}}\; |
- | | + | $ |
- | + | ||
- | \end{align*} | + | |
At this point, there is no other law available. But when we look onto the last formula $Y$ is only $1$ when either $\color{blue}{\overline{X_0}}\; | At this point, there is no other law available. But when we look onto the last formula $Y$ is only $1$ when either $\color{blue}{\overline{X_0}}\; | ||
Zeile 844: | Zeile 906: | ||
This is the definition of the $XNOR$. So the final step would be: | This is the definition of the $XNOR$. So the final step would be: | ||
- | \begin{align*} | + | $Y = \overline{\color{cornflowerblue}{X_0} \text{#} \color{yellowgreen}{X_1} }$ |
- | Y = \overline{\color{cornflowerblue}{X_0} \text{#} \color{yellowgreen}{X_1} } | + | |
- | \end{align*} | + | |
</ | </ | ||
<button size=" | <button size=" | ||
Zeile 858: | Zeile 919: | ||
<button size=" | <button size=" | ||
- | Again, the formula can be easier | + | Again, the formula can be easier |
- | Additionally the brackets can be ignored in the case of products - similar to the convention in math for $(a \cdot b) + (c \cdot d) = ab + cd$ | + | Additionally, the brackets can be ignored in the case of products - similar to the convention in math for $(a \cdot b) + (c \cdot d) = ab + cd$ |
\begin{align*} | \begin{align*} | ||
Y &= \color{cornflowerblue}{X_0 }\; | Y &= \color{cornflowerblue}{X_0 }\; | ||
Zeile 924: | Zeile 985: | ||
<panel type=" | <panel type=" | ||
- | Rewrite the following expressions using only NAND, NOT and AND. Check the result for equality using truth tables. | + | Rewrite the following expressions using only NAND. Check the result for equality using truth tables. |
- $Y = X0 + X1*/X2$ | - $Y = X0 + X1*/X2$ | ||
Zeile 932: | Zeile 993: | ||
- $Y = /(/(X0+X1) + X0*X1)$ | - $Y = /(/(X0+X1) + X0*X1)$ | ||
- $Y = / | - $Y = / | ||
+ | |||
+ | <button size=" | ||
+ | |||
+ | \begin{align*} | ||
+ | Y = \overline{\overline{X0+X1} + X0\cdot X1} | ||
+ | \end{align*} | ||
+ | |||
+ | Generally, the first step would be to see which of the parts show already a NAND configuration. In the following, these are marked in $\color{magenta}{magenta}$.\\ | ||
+ | In this case, there are no terms with NAND available. | ||
+ | |||
+ | One of the next steps is to do substitutions with the DeMorgans rule: $\overline{a+b}=\overline{a}\cdot\overline{b}$. \\ | ||
+ | This can be used on the outer negation: | ||
+ | |||
+ | \begin{align*} | ||
+ | Y = \overline{\overline{X0+X1}} \cdot \color{magenta}{\overline{X0 \cdot X1}} | ||
+ | \end{align*} | ||
+ | |||
+ | This can be done again on $\overline{X0+X1}$: | ||
+ | |||
+ | \begin{align*} | ||
+ | Y = \color{magenta}{\overline{\color{black}{\overline{X0}}\cdot \color{black}{\overline{X1}}}} \cdot \color{magenta}{\overline{X0 \cdot X1}} | ||
+ | \end{align*} | ||
+ | |||
+ | The last step is the substitution of the inverted parts: $\overline{X}=\color{magenta}{\overline{X\cdot X}}$ | ||
+ | |||
+ | \begin{align*} | ||
+ | Y = \color{magenta}{\overline{\overline{X0 \cdot X0}\cdot \overline{X1 \cdot X1}}} \cdot \color{magenta}{\overline{X0 \cdot X1}} | ||
+ | \end{align*} | ||
+ | |||
+ | |||
+ | <WRAP center> | ||
+ | < | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | |||
+ | </ | ||
</ | </ | ||
- | <panel type=" | + | <panel type=" |
Hints for the clip: | Hints for the clip: | ||
* The ladder logic is not necessary for our course. | * The ladder logic is not necessary for our course. | ||
- | * Example 1 ist quiet exhausting including a recap of the boolean rules $\rightarrow$ you can skip this example | + | * Example 1 is quite exhausting including a recap of the boolean rules $\rightarrow$ you can skip this example |
* Example 2 starts at 17:17 | * Example 2 starts at 17:17 | ||
* Example 3 starts at 21:00 | * Example 3 starts at 21:00 | ||
* Example 4 starts at 28:27 | * Example 4 starts at 28:27 | ||
- | * Example | + | * Examples |
{{youtube> | {{youtube> | ||
Zeile 953: | Zeile 1051: | ||
<panel type=" | <panel type=" | ||
- | In the following EXCEL file an example of symmetric encryption can be found: {{introduction_to_digital_systems: | + | In the following EXCEL file, an example of symmetric encryption can be found: {{introduction_to_digital_systems: |
* Try to understand {{wp> | * Try to understand {{wp> |