Beide Seiten der vorigen Revision
Vorhergehende Überarbeitung
Nächste Überarbeitung
|
Vorhergehende Überarbeitung
Nächste Überarbeitung
Beide Seiten der Revision
|
introduction_to_digital_systems:boolean_algebra [2021/09/16 16:10] tfischer |
introduction_to_digital_systems:boolean_algebra [2022/10/21 21:32] tfischer [Bearbeiten - Panel] |
====== 1. Boolean Algebra ====== | ====== 1. Boolean Algebra ====== |
| |
===== 1.0 Motivation: Digital electronics in daily life ===== | ===== 1.1 Motivation: Digital Electronics in Daily Life ===== |
| |
<callout> | <callout> |
| |
==== Goals ==== | === Learning Objectives === |
| |
After this lesson you should: | By the end of this section, you will be able to: |
- know the Boolean functions, their notations, and truth tables. | - know the Boolean functions, their notations, and truth tables. |
- be able to apply the Boolean rules of arithmetic. | - apply the Boolean rules of arithmetic. |
- be able to simplify Boolean expressions. | - simplify Boolean expressions. |
- know the following terms: (logic) gates, names of arithmetic rules. | - know the following terms: (logic) gates, names of arithmetic rules. |
| |
</callout> | </callout> |
==== 1.0.1 Everything is one exept zero... ==== | ==== 1.1.1 Everything is one, exept the zero... ==== |
| |
<WRAP center> | <WRAP center> |
<imgcaption BildNr01 | first Example: USB cable> | <imgcaption BildNr01 | first Example: USB cable> |
</imgcaption> | </imgcaption> |
{{drawio>ExamplerUSBCable}} | {{drawio>ExamplerUSBCable.svg}} |
</WRAP> | </WRAP> |
| |
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 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. |
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 is shows two different levels and rises and falls in between. What we see are the **logic states** 0 or 1! | 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 is 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://www.youtube.com/watch?v=wdgULBpRoXk|here]])) |
| |
Beyond data transmission, we can also encode other things with binary numbers: for example, we could look at | Beyond data transmission, we can also encode other things with binary numbers: for example, we could look at |
* 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 one state and the lower one (LOW or L) the second state the diagram ist also called the **level diagram**. In contrast to analog systems, a signal can only take one of the two valid states in digital systems. Similarly, boolean algebra only uses the states TRUE and FALSE. | 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 one state and the lower one ($LOW$ or $L$) the second state the diagram ist also called the **level diagram**. In contrast to analog systems, a signal can only take one of the two valid states in digital systems. Similarly, boolean algebra only uses the states $TRUE$ and $FALSE$. |
| |
<WRAP column 100%> <panel type="danger" title="Note!"> <WRAP group><WRAP column 7%>{{fa>exclamation?32}}</WRAP><WRAP column 80%> | <WRAP column 100%> <panel type="danger" title="Note!"> <WRAP group><WRAP column 7%>{{fa>exclamation?32}}</WRAP><WRAP column 80%> |
| |
* The smallest binary message set is called a "**bit**", which comes from the English term "__bi__nary digi__t__". A bit thus describes the logical state of a two-valued system. The binary characters can be written as, e.g.: | * The smallest binary message set is called a "**bit**", which comes from the English term "__bi__nary digi__t__". A bit thus describes the logical state of a two-valued system. The binary characters can be written as, e.g.: |
* '0', '1' | * $0$, $1$ |
* FALSE, TRUE | * $FALSE$, $TRUE$ |
* 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**: It may only rain softly, a light might be dimmed and also the voltage (which represents the bit) might be in an in-between state. This situation has to be coped with beyond the binary logic. Beyond binary logic, there is often an **invalid state** in reality, which separates the logic states. | * Therefore, binary logic has some **limitations for real world applications**: It may only rain softly, a light might be dimmed and also the voltage (which represents the bit) might be in an in-between state. This situation has to be coped with beyond the binary logic. Beyond binary logic, there is often an **invalid state** in reality, which separates the logic states. |
| |
<imgcaption BildNr1 | Inner 'Life' of an Integrated Cicuit > | <imgcaption BildNr1 | Inner 'Life' of an Integrated Cicuit > |
{{ :breaknes_mos_6502.jpg?200 }} | {{ grundlagen_der_digitaltechnik:breaknes_mos_6502.jpg?200 }} |
</imgcaption> | </imgcaption> |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ |
==== 1.0.2 At the heart of a computer ==== | ==== 1.1.2 At the Heart of a Computer ==== |
| |
<imgcaption pic1|A 'topless' microcontroller>{{ :Decapped_IC_Travis_Goodspeed.jpg?300 |View inside a microcontroller }}</imgcaption> | <imgcaption pic1|A 'topless' microcontroller>{{ grundlagen_der_digitaltechnik:decapped_ic_travis_goodspeed.jpg?300 |View inside a microcontroller }}</imgcaption> |
~~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, which can be found around us in almost every device: Mobile phones, cars, bank cards, washing machines... Often there are even several microcontrollers installed in the devices. | The core of a computer is the processor in which the instructions are executed. This central processing unit (CPU) is also used in microcontrollers, which can be found around us in almost every device: Mobile phones, cars, bank cards, washing machines... Often there are even several microcontrollers installed in the devices. |
| |
In the microcontroller, in addition to the command-executing microprocessor (more precisely, the {wp>arithmetic-logic unit}), other peripherals such as memory, clock generation, analog-to-digital converter and much more are built in. This makes it a compact tool for many applications. If you look at the microcontroller under an optical microscope, you will see the following picture (<imgref pic1>). | In the microcontroller, in addition to the command-executing microprocessor (more precisely, the {{wp>arithmetic-logic unit}}), other peripherals such as memory, clock generation, analog-to-digital converter and much more are built in. This makes it a compact tool for many applications. If you look at the microcontroller under an optical microscope, you will see the following picture (<imgref pic1>). |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ |
| |
<WRAP center> | <WRAP center> |
<imgcaption pic2|Microcontroller under the microscope>{{ :atmega8-hd_wiki.jpg?300 |atmega8-hd_wiki.jpg}}</imgcaption> | <imgcaption pic2|Microcontroller under the microscope>{{ grundlagen_der_digitaltechnik:atmega8-hd_wiki.jpg?300 |atmega8-hd_wiki.jpg}}</imgcaption> |
| |
<imgcaption pic3|Microcontroller schematic>{{ :atmega8-hd_interior.jpg?300 |atmega8-hd_interior.jpg}}</imgcaption> | <imgcaption pic3|Microcontroller schematic>{{ grundlagen_der_digitaltechnik:atmega8-hd_interior.jpg?300 |atmega8-hd_interior.jpg}}</imgcaption> |
</WRAP> | </WRAP> |
| |
<callout> | <callout> |
| |
==== Goals ==== | === Learning Objectives === |
| |
After this lesson you should: | By the end of this section, you will be able to: |
- know the Boolean functions, their notations, and truth tables. | - know the Boolean functions, their notations, and truth tables. |
- be able to apply the Boolean rules of arithmetic. | - apply the Boolean rules of arithmetic. |
- be able to simplify Boolean expressions. | - simplify Boolean expressions. |
- know the following terms: (logic) gates, names of arithmetic rules. | - understand the following terms: bit, the different (logic) gates, timing diagram, truth table. |
| - understand the purpose of the Tri-State gate and the "Z" state. |
| - understand the use of the "Don't care" state. |
| |
</callout> | </callout> |
==== 1.2.1 First steps into logic ==== | |
| ==== 1.2.1 First Steps into Logic ==== |
| |
We have already learned about the 'bit', and it's two-valued value. This can be connected to the ancient idea of a binary logic. | We have already learned about the 'bit', and it's two-valued value. This can be connected to the ancient idea of a binary logic. |
Other axioms help to combine statements. This is called 'reasoning' or 'deduction'. | Other axioms help to combine statements. This is called 'reasoning' or 'deduction'. |
* This was already used some sentences before: If 'at night, it is dark outside' and 'it is night' is true, one can make the **implication** 'it has to be dark outside'. \\ But be aware, that is is not always reversible: It could also be a solar eclipse. | * This was already used some sentences before: If 'at night, it is dark outside' and 'it is night' is true, one can make the **implication** 'it has to be dark outside'. \\ But be aware, that is is not always reversible: It could also be a solar eclipse. |
* Another deduction is the **equivalence**: when 'A' implies 'B', and 'B' implies 'A' both statements are equivalent. | * Another deduction is the **equivalence**: when '$A$' implies '$B$', and '$B$' implies '$A$' both statements are equivalent. |
| |
In the following, we will have a look onto the basic logic combinations, which are needed for digital systems. These basic logic combinations of logic statements (or bits) are called **logic operators** and can be used similarly to the algebraic "plus" or "minus". The mathematical construct, which describes the systematic of these combinations is called **boolean algebra**. | In the following, we will have a look onto the basic logic combinations, which are needed for digital systems. These basic logic combinations of logic statements (or bits) are called **logic operators** and can be used similarly to the algebraic "plus" or "minus". The mathematical construct, which describes the systematic of these combinations is called **boolean algebra**. |
This tools will get more familiar in the next subcapter. | This tools will get more familiar in the next subcapter. |
| |
==== 1.2.2 The logic operator NOT ==== | <WRAP> |
| A good introduction in binary logic |
| {{youtube>7bVnsXHO6Uw?start=123}} |
| </WRAP> |
| ==== 1.2.2 The logic Operator NOT ==== |
| |
<WRAP><well> | <WRAP><well> |
<imgcaption BildNr06 | Negation: Circuit symbols> | <imgcaption BildNr06 | Negation: Circuit symbols> |
</imgcaption> | </imgcaption> |
{{drawio>NegationCircuitsymbols}} | {{drawio>NegationCircuitsymbols.svg}} |
</WRAP> | </WRAP> |
| |
<imgcaption BildNr07 | Negation: Truth table and timing diagram> | <imgcaption BildNr07 | Negation: Truth table and timing diagram> |
</imgcaption> | </imgcaption> |
{{drawio>NegationFct}} | {{drawio>NegationFct.svg}} |
</WRAP> | </WRAP> |
| |
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, in order to analyse more complex logic. | * 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, in order to analyse more complex logic. Often instead they are also called **look-up table** or **LUT**. |
* 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 in the chapter [[Sequential Logic]]. | * 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 in the chapter [[Sequential Logic]]. |
* In **math** the inversion has also multiple representations e.g. | * In **math** the inversion has also multiple representations e.g. |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ |
==== 1.2.3 The logic operator AND ==== | ==== 1.2.3 The logic Operator AND ==== |
| |
<WRAP><well> | <WRAP><well> |
<imgcaption pic22|Simulation of a conjunction></imgcaption> \\ | <imgcaption pic22|Simulation of a conjunction></imgcaption> \\ |
| |
{{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFWBOeywA5kBZ4HYxJ0BmDAJhDIxEXkhoFMBaMMAKAHdxtsQA2XmB4gM9SGwBK4KuDAVRsihArZ6ZaInWJi0IWDRk+8YvCx5kxJPEndeA2+D5Rnqms7Ea2AcwdVqQ3mJIXjE2fWQHBQCHNXpCOATEtgAPEFclcjdeMl4AZwBLAFsABwAbBgAdXNyOfIAXAGMACzC+JWEyHN8MagoAEwYAMwBDAFdSuqZyvvB3JGIUkSdkf31wSAhs3gANcVTkNT4IQidDXi2QAE1Fvn88PBBkB8x6C+32cIcwPjiOrtj1okgTY5P5kPI4uDZhQyGoNJR4To9AYjCYzBYrGxVJY-NJqNhvpRINQ4mAAPpkMmQMnJDCEMB4MnwKmwBJPIxtZnUymU6msMnEFmJbDIUVi8USvhUsnvLGQHE9ESvQnfMTgCnS2n0xlc1lwdnwTnSnka8mCmDCiVW8VS6m7NgAWX4xPAUIEkIocOsqXgDP4NFQjzSlF4w1yVS8wzqDDlCrBKkJZDwnu4GupWo2Ut15L5abJ1y40VVX2E4ik8BkDKcIqcVehaS9CO0ugJKOMpieGJg1nLMlh+OQpxdyiJTbHSNb4NRHfMlm7YToNErbuHULUzmsQA noborder}} | {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFWBOeywA5kBZ4HYxJ0BmDAJhDIxEXkhoFMBaMMAKAHdxtsQA2XmB4gM9SGwBK4KuDAVRsihArZ6ZaInWJi0IWDRk+8YvCx5kxJPEndeA2+D5Rnqms7Ea2AcwdVqQ3mJIXjE2fWQHBQCHNXpCOATEtgAPEFclcjdeMl4AZwBLAFsABwAbBgAdXNyOfIAXAGMACzC+JWEyHN8MagoAEwYAMwBDAFdSuqZyvvB3JEhiFJEnZH99cEgIbN4ADXFU5DU+CEInQ15tkABNJb5-PDwQZEfMekud9nCHMD44jq7YhtEsCbHJ-Mh5HEIbMKGQ1BpKAidHoDEYTGYLFY2KpLH5pNRsD9KJBqHEwAB9MjkyDk5IYQhgPDk+DU2AJZ5GNosliU3k01jk4isxLYZBi8USyV8ankj7YhaUHoiN5En5icB82n0zZMlkwRIc+Bc8k8qlm8kUoX6hKiyV28XSml7NgAWX4JPA0IEUIo8OsqXgjP4NFQTzSlF4w1yVS8wzqDHluKVYGhhLOeF93E1dIZ0r1uhNFIpVJpNy40TV32E4ik8BkjKcoqcDZhaT9iO0ukJqOMpmemJg1lrMjhBOQZw9ymJHZnyO7ELRffMlkHYToNHrXsn0LUbmsQA noborder}} |
</well></WRAP> | </well></WRAP> |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ |
<imgcaption pic23| Conjunction: Circuit symbols> | <imgcaption pic23| Conjunction: Circuit symbols> |
</imgcaption> | </imgcaption> |
{{drawio>ConjunctionCircuitsymbols}} | {{drawio>ConjunctionCircuitsymbols.svg}} |
</WRAP> | </WRAP> |
| |
<imgcaption pic24 | Conjunction: Truth table and timing diagram> | <imgcaption pic24 | Conjunction: Truth table and timing diagram> |
</imgcaption> | </imgcaption> |
{{drawio>ConjunctionFct}} | {{drawio>ConjunctionFct.svg}} |
</WRAP> | </WRAP> |
| |
* $Y = X0 * X1$ (used e.g. for input with a keyboard) | * $Y = X0 * X1$ (used e.g. for input with a keyboard) |
* $Y = X_0 \cdot X_1$ (often used when handwriting or in math) | * $Y = X_0 \cdot X_1$ (often used when handwriting or in math) |
* ''Y = X0 && X1'' (used in c language), ''Y = X0 & X1'' (used in some other languages) | * ''Y = X0 & X1'' (used in c language bitwise) |
* $Y = X_0 \land X_1$ (used in logic) | * $Y = X_0 \land X_1$ (used in logic) |
| |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ |
==== 1.2.4 The logic operator NAND ==== | ==== 1.2.4 The logic Operator NAND ==== |
| |
<WRAP><well> | <WRAP><well> |
<imgcaption pic25|Simulation of a NAND operation></imgcaption> \\ | <imgcaption pic25|Simulation of a NAND operation></imgcaption> \\ |
| |
{{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFWBOeywA5kBZ4HYxJ0BmDAJhDIxEXkhoFMBaMMAKAHdxttLJqwPStnqROIDPTBUJUoWIBKIAGy8weZeE3rtlECMrREZIyGLRBYNGWXxi8LHmTEk8NksFqZn2VD8HEUVc2AHNuXmJINSFiMiCxK2RfH0k+AT5wOCzssQAPfXoKTApEXjJeAGcASwBbAAcAGwYAHQqKjiqAFwBjAAs2MGUioXK5CKi9ABMGADMAQwBXBs6mJsnwP1FoYjZ8siKhmghB0uEQAA08kGRCvDxMzSp6Mt4ATV3wWK1j5R-eF4u7ESaXCILi6TimRy2Xc4GQRQ0oJ0GwokJMxlM5ks1ls9kczmCIhcVAEMmwgxBUjIAH0aZBqbkMIR1NT4NSYNlkBp4EM2fSaXTqdJqcR2bAsthkFLpTLZcp2dTzuwiZQMNRUuTtMoggKFYzmXhWWLOdzeQrdbrRRyJbLbTL5fTLmwALIqfhwiiqKTwvzoj7wdQqGioa76M5zCqtEJzToMNgqkke-QUsh4ChSNmC-WQQZGmBgBUFwXvLjg0Fl6TUMSl92VpEyav19VUqviVIVkbuxs+Mu9ruw+DeRGS7SIiAUAzowyILHknF2BxcgkwNxKQfUMsjkHjjJTqezxI2Bf4lwrgYBmjeH3agQ+wo0GhsIA noborder}} | {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFWBOeywA5kBZ4HYxJ0BmDAJhDIxEXkhoFMBaMMAKAHdxttLJqwPStnqROIDPTBUJUoWIBKIAGy8weZeE3rtlECMrREZIyGLRBYNGWXxi8LHmTEk8NksFqZn2VD8HEUVc2AHNuXmJINSFiMiCxK2RfH0k+AT5wOCzssQAPfXoKTApEXjJeAGcASwBbAAcAGwYAHQqKjiqAFwBjAAs2MGUioXK5CKi9ABMGADMAQwBXBs6mJsnwP1FYYjZ8siKhmghB0uEQAA08kGRCvDxMzSp6Mt4ATV3wWK1j5R-eF4u7ESaXCILi6TimRy2Xc4GQRQ0oJ0GwokJMxlM5ks1ls9kczmCIhcVAEMmwgxBUjIAH0aZBqbkMIR1NT4NSYNlkBp4EM2SxaQL6dJqcR2bAsthkFLpTLZcp2dTzuwiZQMNRUuTtMogjS6QymZAWWyOVkubZedT+bqBTTRSa4JLZU7pfL6Zc2ABZFT8OEUVRSeF+dEfeDqFQ0VDXfRnOYVVohOadBhsFUk336ClkPAUKRsvWM5ny40WS1gallvXvLjg0E16TUMTVn31pEyRut9VUhviVJ1kY+9s+GvDgew+DeRGS7SIiAUAzowyILHknF2BxcgkwNxKcfUGtTkGzjILhfLxI2Nf4lxbgahmjeQPagSBwo0GhsIA noborder}} |
</well></WRAP> | </well></WRAP> |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ |
<imgcaption pic26| NAND Circuit symbols> | <imgcaption pic26| NAND Circuit symbols> |
</imgcaption> | </imgcaption> |
{{drawio>NANDCircuitsymbols}} | {{drawio>NANDCircuitsymbols.svg}} |
</WRAP> | </WRAP> |
| |
<imgcaption pic27 | NAND: truth table and timing diagram> | <imgcaption pic27 | NAND: truth table and timing diagram> |
</imgcaption> | </imgcaption> |
{{drawio>NANDFct}} | {{drawio>NANDFct.svg}} |
</WRAP> | </WRAP> |
| |
* $Y = /(X0 * X1)$ (used e.g. for input with a keyboard) | * $Y = /(X0 * X1)$ (used e.g. for input with a keyboard) |
* $Y = /(X_0 \cdot X_1)$ or $Y = \overline{X_0 \cdot X_1}$ (often used when handwriting or in math) | * $Y = /(X_0 \cdot X_1)$ or $Y = \overline{X_0 \cdot X_1}$ (often used when handwriting or in math) |
* ''Y = !(X0 && X1)'' (used in c language) | * ''Y = !(X0 & X1)'' (used in c language bitwise) |
* $Y = /(X_0 \land X_1)$ or $Y = \overline{X_0 \land X_1}$ (used in logic) | * $Y = /(X_0 \land X_1)$ or $Y = \overline{X_0 \land X_1}$ (used in logic) |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ |
==== 1.2.5 The logic operator OR ==== | ==== 1.2.5 The logic Operator OR ==== |
| |
<WRAP><well> | <WRAP><well> |
<imgcaption pic28|Simulation of a OR operation></imgcaption> \\ | <imgcaption pic28|Simulation of a OR operation></imgcaption> \\ |
| |
{{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFWBOeywA5kBZ4HYxJ0BmDAJhDIxEXkhoFMBaMMAKAHdxttLJqwPStnqROIDPTBUJUoWIBKIAGy8weZeE3rtlECMrREZIyGLRBYNGWXxi8LHmTEk8NksFqZn2VD8HEUVc2AHNuXmJINSFiMiCxK2RfH0k+ano48DhsnLEAD30M8HIafWEQAGcASwBbAAcAGwYAHQqKjiqAFwBjAAs2MGUKHzIDH0jeCgATBgAzAEMAVwbOpiap8D9RaGI2ArJhoZoIQcRJ3gANfJBkDLw8LM0qenOQAE098FitE+Vf3leF3YiTS4VBcXSfCyuRy7nAyGGGjBOk2FEyJmMpnMlmstnsjmcwRELioAhk2EGoKkZAA+rTIDS8hhCOoafAaTAcsgNPAhuyGbT6TTpDTiBzYNlsMhpTLZXLlByaUC2MTKBhqKkKdplEFBYqmSy8GzxVyeXzFXq9WLOZK5XbZQqGVc2ABZFT8eEUVRSBF+DGfeDqFQ0VA3MqjEDzCqtELzToMFWQEnqz36SlkPAUKTsoUGyCDY0wMCK4tCj5cCFgyvSdLiaveIQ1qDiHxN1JNsRcVLVoSVztVj2VvsDeAUUcCX06idZvT0NxKcfgJFS7RIiAUAwYwyIbEU3F2Bzcwkwec0GSVleg9dQrdb3eJGwHgkuE9sIA noborder}} | {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFWBOeywA5kBZ4HYxJ0BmDAJhDIxEXkhoFMBaMMAKAHdxttLJqwPStnqROIDPTBUJUoWIBKIAGy8weZeE3rtlECMrREZIyGLRBYNGWXxi8LHmTEk8NksFqZn2VD8HEUVc2AHNuXmJINSFiMiCxK2RfH0k+ano48DhsnLEAD30M8HIafWEQAGcASwBbAAcAGwYAHQqKjiqAFwBjAAs2MGUKHzIDH0jeCgATBgAzAEMAVwbOpiap8D9RWGI2ArJhoZoIQcRJ3gANfJBkDLw8LM0qenOQAE098FitE+Vf3leF3YiTS4VBcXSfCyuRy7nAyGGGjBOk2FEyJmMpnMlmstnsjmcwRELioAhk2EGoKkZAA+rTIDS8hhCOoafAaTAcsgNPAhuyWHTBQzpDTiBzYNlsMhpTLZXLlByaUC2MTKBhqKkKdplEFafTGczIKz2ZzstzbHyaQK9YLaWLTXApXLnTKFQyrmwALIqfjwiiqKQIvwYz7wdQqGioG5lUYgeYVVoheadBgqyAk9V+-SUsh4ChSdn6pkshUmixWsA0yv6j5cCFg+vSdLiRveIRNqDiHwd1IdsRcVKNoT1-sN331kcDeAUacCIM6uf5vT0NxKWfgJFS7RIiAUAwYwyIbEU3F2BzcwkwVc0GT1reg3dQg8H4+JGxngkuK9sIA noborder}} |
</well></WRAP> | </well></WRAP> |
| |
~~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://en.wikipedia.org/wiki/Logical_disjunction|logic OR]], [[https://en.wikipedia.org/wiki/OR_gate|OR gate]]). When there is one __or more__ input true the output is also true. <imgref pic28> shows an example: The light is only off ($Y=0$), when all inputs are on ($X0=1$, $X1=1$, ...). Doesn't it - at the first glimpe - seem similar to the NAND circuit? The main difference is that normally open switches are used. Only, when both switches are open the light is off. | 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://en.wikipedia.org/wiki/Logical_disjunction|logic OR]], [[https://en.wikipedia.org/wiki/OR_gate|OR gate]]). When there is one __or more__ input true the output is also true. <imgref pic28> shows an example: The light is only off ($Y=0$), when all inputs are off ($X0=0$, $X1=0$, ...). Doesn't it - at the first glimpe - seem similar to the NAND circuit? The main difference is that normally open switches are used. Only, when both switches are open the light is off. |
| |
<WRAP center> | <WRAP center> |
<imgcaption pic29| OR circuit symbols> | <imgcaption pic29| OR circuit symbols> |
</imgcaption> | </imgcaption> |
{{drawio>ORCircuitsymbols}} | {{drawio>ORCircuitsymbols.svg}} |
</WRAP> | </WRAP> |
| |
<imgcaption pic30 | OR: truth table and timing diagram> | <imgcaption pic30 | OR: truth table and timing diagram> |
</imgcaption> | </imgcaption> |
{{drawio>ORFct}} | {{drawio>ORFct.svg}} |
</WRAP> | </WRAP> |
| |
* 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 = X0 || X1'' (used in c language) | * ''Y = X0 | X1'' (used in c language biswise) |
* $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) |
| |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ |
==== 1.2.6 The logic operator XOR ==== | ==== 1.2.6 The logic Operator XOR ==== |
| |
<WRAP><well> | <WRAP><well> |
| |
<WRAP center> | <WRAP center> |
<imgcaption pic32| OR circuit symbols> | <imgcaption pic32| XOR circuit symbols> |
</imgcaption> | </imgcaption> |
{{drawio>XORCircuitsymbols}} | {{drawio>XORCircuitsymbols.svg}} |
</WRAP> | </WRAP> |
| |
| |
<WRAP center> | <WRAP center> |
<imgcaption pic33 | OR: truth table and timing diagram> | <imgcaption pic33 | XOR: truth table and timing diagram> |
</imgcaption> | </imgcaption> |
{{drawio>XORFct}} | {{drawio>XORFct.svg}} |
</WRAP> | </WRAP> |
| |
* In **math** the XOR operation has again multiple representations e.g. | * In **math** the XOR 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) |
* there is no bit operation in c language for XOR | * ''Y = X0 ^ X1'' (used in c language bitwise) |
* $Y = X_0 ⊕ X_1$ (used in logic) | * $Y = X_0 ⊕ X_1$ (used in logic) |
| |
<panel type="info" title="Excercise 1.2.1. NOR and XNOR"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> | <panel type="info" title="Exercise 1.2.1. NOR and XNOR"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> |
| |
- Think about a circuit (with multiple switches and one lamp) to implement NOR and XNOR. | - Think about a circuit (with multiple switches and one lamp) to implement NOR and XNOR. |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ |
| ==== 1.2.7 The Tri-State Gate ==== |
| |
===== 1.3 Convertibility of gates ===== | The [[https://en.wikipedia.org/wiki/Three-state_logic|tri-state gate]] is not a boolean gate, however it is still often used in logic circuits such as microcontrollers. |
| The essence of the tri-state gate is - in short - to be able to output 'nothing'. Nothing means: neither high nor low. |
| |
| One possible output of the tri-state gate - besides high and low - is 'high ohmic', which is often reffered as $Z$. In this case, the gate output is not controlled by the tri-state gate, but floats. The output can instead be controlled by an other external source. The main use of this gate is to disconnect one logic circuit from another one. |
| |
| <WRAP><well> |
| <imgcaption pic900|Simulation of a Tri-State gate></imgcaption> \\ |
| |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFWA2AzAJla5P1gBzLoAsAnKSOviIvJDQKYC0YYAUALIgvHHjL0WVfvXrpo8NgA9uYVHzDFUs9OnDFkIBdQCabAErdicSpGpNiYTejPhKNMRMpPU0RWHil0yeKnj5SAHZSZRhJAHcjEytBDHoYqGkjEnVAozA1D3ptEAANJIt0CjBSPgtIBSCtcGoAUQA5Ayj4gXTNBIhMk3FEHpBXd09vX38gkKR4CO4403NjMVtINg8KJipqBLWUhIXwOH2DpcithVaWQPbWo+50eHaLm7vZxOPb61smGZtqa8+bERu+A2VzYACdZA8wA9ztZjFA9vs2McofdNDCAb8UQCeKdRGwAEbTCrgYRrAjgUh4mRrJSUKprRAYNJ8FIMKQAFwYoIAdgBDAA2AB0AM4AcgAtgBLAAmTAA9gALKUAY1FIsFgu5ADc5fz2byAOYMEXK-m88UAB0l3INbGMymQCkhXkocNEAH0wO7IO6pPgwJAoe74N63N7PZ7oLdw3p7SBHa74i7UMT6MgIz6-QGrMHQ16fehI9GfenUKHIMX3fk4wmZiU1Kh8HwxBnff7A+mQzB8+7C2Ao13e+6yzAK4OGk10SRBFi3vDsvRQvOJJOsbxzGuE6ItIv5xMCUS+Fg0XhqKhSD8kRDNNgN7x+shL8iHo2yljb4lwejX9etMQfgicBXn8i6PoCZ5gb8c6WGiMwwS8jw3k2iFaFYCEnA+G4vpBwFwWh5TZGhSyGARmFtGRnQIs4vQuG4lhDD4fgBMEoQSJI1LEEUO5qOUfDGIgOQThxKR+IgFgZP0-jVOS+THPMZEgWRxHNKhaLwfBlF0NR2kDPRXiMaMLH7tSchHvAEBCA28B8TUIB6FwOIKRkEEAT0yz4II6wKaoR6QUgEABocBxsEAA noborder}} |
| </well></WRAP> |
| ~~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$. |
| |
| <WRAP center> |
| <imgcaption pic901| Tri-State gate circuit symbols> |
| </imgcaption> |
| {{drawio>TristateCircuitsymbols.svg}} |
| </WRAP> |
| |
| The circuit symbol is shown in <imgref pic901>. Usually the triangle sybmol ist used, the DIN / EN symbol is much less common and therefore here ignored. |
| Since the Tri-State gate is not an logical gate is does not have any mathematical representation. |
| |
| <WRAP center> |
| <imgcaption pic920 | Tri-State gate: truth table and timing diagram> |
| </imgcaption> |
| {{drawio>TristateFct.svg}} |
| </WRAP> |
| |
| In the <imgref pic920> the truth table is shown. In the case $EN=0$ the input $X$ does not matter. |
| The situation 'the input x does not matter' is usually simplified by the use of a **{{wp>don't care term}}** . \\ |
| The 'don't care' is written down as a ''x'' or a ''-''. |
| |
| <callout title="Example of an Application for a Tri-State Gate"> |
| |
| Let's imagine, we want to connect two microcontroller $A$ and $B$ in order to enable a communication, i.e. transmitting and receiving data on both sides. \\ |
| One posibility would be to use two wires: |
| * One wire for data sent from $A$ to $B$ |
| * 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 ''L'' and ''H'' nearby this labels. \\ |
| The big advantage of this configuration is, that both connected microcontroller can send data whenever they want. The biggest disadvantage is, that one need two wires. |
| |
| <WRAP><well> |
| <imgcaption pic910|Simulation for Communication with two Wires></imgcaption> \\ |
| |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BWcMBMcUHYMGZIA4UA2ATmIxAUgpABZsKBTAWjDACgB3EbBFEPKmBR5+VSGwAy3XqNo0RAqOBAAzAIYAbAM4Nq4gLLhhswjVlUU0BGwBGtYoRBMEj7D3DYR4gB5OIYEnAMYiC+MxQzAFsASwBjACcAe1jEgDsAFySNDQZ4gB0tAEFbIMdnRzAkME8oNkNPMyoaeSULK0lwQjEQU1aldW1dJHEuBqUA7p9ubDMAkIQwWYwwkAiQGITktMzE7NyCgCE2XzBiMyYRbEWnJHCzFSTIgsKC9MTD4-AHEGXuAJ-bqt7o9Dq93kVPqxBCJqnwUBBZiIABpTGiQeinWgoJAoFZgEQATSmYEgIVIHn8kDxhPYvjRZmIIhoRGQCPAyPYQA noborder}} |
| </well></WRAP> |
| |
| Once we think of only using one wire, it becomes more complicated: a single wire can only be driven by one digital input - only one can transmit data at any given time. |
| Therefore, we have to switch on both sides from reveive to transmit, e.g. by a Single Pole Double Throw switch. This can be seen in <imgref pic911> for the two situations "$A$ sends data to $B$" and "$B$ sends data to $A$". |
| Again, you can change the inputs $X0$ and $X1$ by clicking on the ''L'' and ''H'' nearby this labels. |
| |
| The problem is, that in one time the output becomes an input, but boolean gates an algebra result everytime in boolean outputs. |
| |
| <WRAP><well> |
| <imgcaption pic911|Simulation for Communication: first Try with one Wire></imgcaption> \\ |
| |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BWcMBMcUHYMGZIA4UA2ATmIxAUgpABZsKBTAWjDACgBlEbBFEPKjTj8qokADMAhgBsAzgyggUbAO7deI8ISoCobADK1hxQrUI0QJxVSlyFSSGwCy4MH3O08ID1RTQEbABGtFYoFtg84NhejgAeICxaxOAYyWAYfBZhIAC2AJYAxgBOAPYFJQB2AC6l0tIMRQA6sgCCQSmm2WBIYNF6LkJUHjQePkr+Bq58VjReVmK28tSOXGDamqx8ugsyS75s8REWa8kIYMcZtEoW+cVllTUldQ3NAEIH4FaX2GsgGEhZCziUo5ZotZpVEpvD5gKzYFBeH6mCIQQESEFvCFQ1ofI60FBIM4WGgIq7ZW6lcrVWr1Jqyd6rdYRUybbjYUxUCCLBT7QysniZREaHZ2ZbOIxUeGCDxSxR+ALBdKdXTdbjECxxBKogkpZIkrxoin3alPWlg9o0UK6CJIbDq-pTbhoTxOsTyyaDdSZGXCxTcsVqAVsllM9l6LhB5kS4OKLm7HlKD6XVgWe2scjHLwADU1JPICAzlu8gnAXgAmrmiNxLjRZtWAaWQFn2PEMJLepY+EirmByy2EoQG3WM9cQBw8lUAK6SKp5SrNftMBBeIhUBBIIj0NHjqczucVZrKIA noborder}} |
| </well></WRAP> |
| |
| We still could try solve it with gates, as seen in <imgref pic912>: Each microcontroller has an enable signal (''EN0'', ''EN1''). Both outputs from the microcontrollers have to be combined with another gate in such a way, that the result shows the enabled signal. |
| |
| The problem here: We are back to a two wire system. So, we need to "split up" the OR gate somehow.. |
| |
| <WRAP><well> |
| <imgcaption pic912|Simulation for Communication: with only boolean Gates></imgcaption> \\ |
| |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BWcMBMcUHYMGZIA4UA2ATmIxAUgpABZsKBTAWjDACgB3EFBQkQmuDAp+gyGwAytbCLCEqNAeHlRVAMwCGAGwDODauICyQkUpp5RqlNARsARrTLdy2bHxTZy4gB7duKsAJ-ekEUQQBbAEsAYwAnAHto+IA7ABcErS0GWIAdHQBBe3AsZ2VuTyg2Yxo4S0VBJSprWyk8KjkFCw7VKk1dfSQfEFdyIioEMFHCEO4ImISktIys3J0AITZfQIgwUln3FGJaWZA1BPC8nJzk-LzU+LyN30JZXhA8QTAEI8+LAA0hjRMBRyHQjipfiAAJpsL5UNrFPjdSZ8JqqFrvdrEETmcDY1QQPp6AybfhNFAQYhIFBhY6BEAAUQAcuI4dJZBg+NgEBzUX5xqS6DsEEgaAh6F8LJC-uxfEDqfTFOSIJDmewpHRZPj6niRFRetpiYNOLRakoeHxGrCedw3mAaKE3o1+RQTWF2g7Zu1OZUuO7Ecpvai3RhZJ7MLzfc5I9zI0MiF09q4Dj8TpcdGd4hcdFdkms7g8CmwgA noborder}} |
| </well></WRAP> |
| |
| For this we can use the Tri-State gate: This enables to switch an output to high ohmic. This means this output does not provide any current anymore, so this output is not driven anymore. |
| |
| <WRAP><well> |
| <imgcaption pic913|Simulation for Communication with Tri-State Gates></imgcaption> \\ |
| |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BWcMBMcUHYMGZIA4UA2ATmIxCJCQBZsqBTAWjDACgAZEbPa8DQkNUK8w-KOIBmAQwA2AZ3pUorALJ8BeSILwhN4lNASsARlUh1qEbJSLlIrAB4hmFPElHFXO3il4BbAEsAYwAnAHsgsIA7ABdwmRl6EIAdOQBBE3A8cm5kCmFlNWxsDS0hXj0tAyNOMBQdUQFqBrEtCGl5RSR7J2KfNyowfu8Kf2DwyNj4xJS5ACFHEEIUPhWePhoskAANHsFfEAxeWgEsQS2ATQ5wah98bQp7tpAOhSU9hE8UFE9iH2tzmAdABRABye1oEFEEGoCDoomOW22bCc1BQSBQ2GOhCq2HIIhBoLYnBKOjQ3gK5PEWleXWUAHcuCVdG0xJVWIzGiz1Dz7JyxFywDjeRymaUxSLGcUBFzsAgVlz7EC2vUeULWQItDAofBdfBkHq4KKhncGrdwMQVkq9NwRGI5QqBVBoDrDfqwG6+VxCGT7qSLVbWEA noborder}} |
| </well></WRAP> |
| |
| |
| |
| |
| </callout> |
| |
| ~~PAGEBREAK~~ ~~CLEARFIX~~ |
| ===== 1.3 Timing Diagram - A Deep Dive ===== |
| |
| <callout> |
| === Learning Objectives === |
| |
| By the end of this section, you will be able to: |
| - understand in which possible way the tri-state output is shown in timing diagrams |
| - know how the situation 'either''0'' or ''1'' ' is shown in timing diagrams |
| </callout> |
| |
| Since the timing diagram is of importance not only for the upcoming courses like Electronics (in the 3rd semester) I recommend to watch the following video sequence. |
| |
| <WRAP> |
| 24 minutes intro into applications of the timing diagram in real data sheets (a cutout from 5:08 to 28:52 from a full video of EEVblog) |
| {{youtube>AUGRBhfAabY?start=309&end=1732}} |
| </WRAP> |
| |
| ~~PAGEBREAK~~ ~~CLEARFIX~~ |
| ===== 1.4 Convertibility of Gates ===== |
| |
<callout> | <callout> |
==== Goals ==== | === Learning Objectives === |
| |
After this lesson you should: | By the end of this section, you will be able to: |
- | - convert simple gates into each other |
| - convert interconnections from a few logic gates to truth tables and vice versa. |
| - build-up other gates from NAND and NOR gates. |
</callout> | </callout> |
| |
Some of the circuits in the provious chapter looked suspiciously similar. We will now have a more deeper look onto this and try to converte some gates into each other. | Some of the circuits in the provious chapter looked suspiciously similar. We will now have a more deeper look onto this and try to convert some gates into each other. |
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 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. |
| |
==== 1.3.1 NAND in NOT ==== | ==== 1.4.1 NAND in NOT ==== |
| |
<WRAP><well> | <WRAP><well> |
A different approach to get an NOT is to set the second input to '1'. Here, the NOT can be 'deactivated' of with the second input. This can be tested in the <imgref pic34> by clicking on the input 'H' of the NAND gate on the right below. | A different approach to get an NOT is to set the second input to '1'. Here, the NOT can be 'deactivated' of with the second input. This can be tested in the <imgref pic34> by clicking on the input 'H' of the NAND gate on the right below. |
| |
==== 1.3.2 NAND in AND ==== | ==== 1.4.2 NAND in AND ==== |
| |
<WRAP><well> | <WRAP><well> |
<imgcaption pic35|From NAND to AND></imgcaption> \\ | <imgcaption pic35|From NAND to AND></imgcaption> \\ |
| |
{{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFWBOeywA5kBZ4HYxJ0BmDAJhDIxEXkhoFMBaMMAKACUQmN6zJqLMBX7UIFbH2iIy0kMWhhsYNGQBs8YvCx5kxJPDaT9xYmpC8Q2NdnBr6DgPplHkRwA8MhMHkfxXsHBEeBpqZP5uLlGujsQBQZDYyMkpqWlqMQAakGwAsuAhlGS2okW2UobG8mbgyBI2lHgUfM4xnt4ZEYoxYK1uAJpsKhDI5mTFBWMTfDQ0bADuFnwTlqU5i6sCIKOUW+vbY5JLlEf7q0er0wvcDcX0PHyn1w+7grd7Q-AQTLcTYFPlShQOaLf5lY7jcqcbjne6sERHcQQuSyRAKJQqOoaLQ6PQGIyQEw1YTUawlPbgOIuNztSA+PwBXqRPqOMBxOIwSDhLLsdxAo54Un6WyYEDZAA6AGdMmApXLJYM+eYGoU1HgrOBqJB5VLtZKdfrJbyQOYMOZClgNaK9fLZYaDcbEIRqHgnawrWIDTb7YbjeY2RBCmzbCLPT67QbdWw+f9-cRxMTiCHNeAHZHDTkYxpwJB1WQtOBCB7Uz7vQ7o3ZTTIahhSSmy0b01LjbGTfp88rzKGoF6m0aK-8KMRkJRSFYJCmJdKI4bFdxhPQwKhuMgxKvi9kK-xyWMwfwR925yx+KPvuv88nRTK2EA noborder}} | {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0lwrFWBOeywA5kBZ4HYxJ0BmDAJhDIxEXkhoFMBaMMAKACUQmN6zJqLMBX7UIFbH2iIy0kMWhhsYNGQBs8YvCx5kxJPDaT9xYmpC8Q2NdnBr6DgPplHkRwA8MhMHkfxXsHBEeBpqZP5uLlGujsQBQZDYyMkpqWlqMQAakGwAsuAhlGS2okW2UobG8mbgyBI2lHgUfM4xnt4ZEYoxYK1uAJpsKhDI5mTFBWMTfFA0bADuFnwTlqU5i6sCIKOUW+vbY5JLlEf7q0er0wvcDcX0PHyn1w+7grd7Q-AQTLcTYFPlSg0OaLf5lY7jcqcbjne6sERHcQQuSyRAKJQqOoaLQ6PQGIyQEw1YTUawlPbgOIuNztSA+PwBXqRPqOMBxOIwSDhLLsdxAo54Un6WyYEDZAA6AGdMmApXLJYM+eYGoU1HgrOBqJB5VLtZKdfrJbyQOYMOZClgNaK9fLZYaDcbEIRqHgnawrWIDTb7YbjeY2RBCmzbCLPT67QbdWw+f9-cRxMTiCHNeAHZHfdG7E7IOqyFpwIQPamfd6HZnYxYZDUMKSU6WjempcaK2p9HnleZQ1AvY3JTkY2F5MhKKQrBIUxLpRHDYruMJ6GBUNxkGIV0Xspn+OSxmD+MOu7OWPwR9813nk6KZWwgA noborder}} |
</well></WRAP> | </well></WRAP> |
| |
Therefore, the NOT hat to be set behind the NAND. | Therefore, the NOT hat to be set behind the NAND. |
| |
==== 1.3.2 NAND in OR ==== | ==== 1.4.3 NAND in OR ==== |
| |
<WRAP><well> | <WRAP><well> |
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 what happens when the inputs of the NAND are negated. | 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 what happens when the inputs of the NAND are negated. |
| |
<panel type="info" title="Excercise 1.3.1. further conversions"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> | |
| |
- | |
| |
</WRAP></WRAP></panel> | |
| |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ |
===== 1.4 Rules for boolean algebra ===== | ===== 1.5 Rules for boolean Algebra ===== |
| |
<callout> | <callout> |
| |
==== Goals ==== | === Learning Objectives === |
| |
| By the end of this section, you will be able to: |
| - know and use the arithmetic rules in boolean algebra. |
| |
After this lesson you should: | |
- Understand the purpose of the Tri-State gate and the "Z" state. | |
- Understand the use of the "Don't care" state. | |
- Be able to convert interconnections from a few logic gates to truth tables and vice versa. | |
- Be able to trace gates to NAND and NOR gates. | |
| |
</callout> | </callout> |
We have seen, that (at least) some of the gates can be represented by means of others. In order to approach this more systematically, we will now have a look onto the arithmetic rules of boolean algebra. These rules can be used to either build a logic cicruit out of the basis gates shown in chapter 1.2. On the other hand we are also able to simplify the logic circuits by ths rules. | We have seen, that (at least) some of the gates can be represented by means of others. In order to approach this more systematically, we will now have a look onto the arithmetic rules of boolean algebra. These rules can be used to either build a logic cicruit out of the basis gates shown in chapter 1.2. On the other hand we are also able to simplify the logic circuits by ths rules. |
| |
===== 1.4.1 The set of rules ===== | ==== 1.5.1 The Set of Rules ==== |
| |
^Nr^Math Term^Formula^Description^ | The following table shows the main rules which help us to generate and optimize logic expressions and circuits. \\ |
|1 |Closure: |$B \land B -> B , B \lor B -> B $ | the operators \land and \lor map elements from B=\{0,1\ to B. \\ | It is possible to click on "math representation" and "algebraic representation" to switch both. |
|2 |Duality: | | if A is a statement of boolean algebra, so is $A^*$ . $A^*$ is obtained by exchanging \land against \lor and vice versa. \\ | |
|3 |Neutral Element |$a \land 1 = a , a \lor 0 = a $ | there exist a neutral element to the operators \land and \lor. Applying the oparator to a and the neutral element results in a. \\ | |
|4 |Complementary Element |$a \land \overline{a = 0}$ , $a \lor \overline{a = 1}$ | there exist a complementary element to the operators \land and \lor. The negation of a is for both operators the complementary element. \\ | |
|5 |Idempotence |$a \land a = a , a \lor a = a $ | Applying the operators \land and \lor to a similar input a results in a.\\ | |
|6 |Commutative Law |$a \land b = b \land a , a \lor b = b \lor a $ | The inputs are interchangable. \\ | |
|7 |Associative Law |$a \land (b \land c) = (a \land b) \land c $ | for the same operator bracketing can be moved. \\ | |
| | |$a \lor (b \lor c) = (a \lor b) \lor c $ | \\ | |
|8 |Distributive Law |$a \land 1 = a , a \lor 0 = a $ | there exist a nuetral element to the operators \land and \lor. \\ | |
|9 |Law of Absorbtion |$a \land 1 = a , a \lor 0 = a $ | there exist a nuetral element to the operators \land and \lor. \\ | |
|10 |DeMorgan's Rule |$a \land 1 = a , a \lor 0 = a $ | there exist a nuetral element to the operators \land and \lor. \\ | |
| |
---- | Have a look for the algebraic representation. These are probably much simpler to remember! |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | Be also aware, that the logical expressions sometimes are written as $X0$, $X1$, ... and sometimes with other letters, like $a$, $b$, ... |
==== zwei Transistor(typ)en reichen ==== | |
<WRAP right><well> | |
<imgcaption pic4|n- und p-Kanal MOSFETs></imgcaption> \\ | |
| |
{{url>https://www.falstad.com/circuit/circuitjs.html?running=false&ctz=CQAgjCAMB0l3BOJyWoVaYDsYAcuA2BAJgFZdjcEBmSgkAFlJGYeoCgAzES3cBhiGrV6YAS2IZmMSMXYAlISJ74l9MvUhRGW6dpil2AczXgs9YaJJQFZ0eLCV+giJLDwe0ZsS-7oDBHYAdztncGsxQTkQy3ACLVjsTXYGSGo4rTBHFT5I7WoAfTACyCLiYgQGAtIS2Dhi0uICwo5uXiFIQVjqTpZ0rRlonlJ7KNU8yGNTWgTlalJJScVEp1iETW1Uln0pYOHR-Y7BSZCNI5zzyYAPIQJ1HBZIPmIsQRc+AAcAWgBpAEMAHZ-AA2AB0AM4AWQA8gBlABiAFEACrsG7ULDpSosMDMBBYRjgPgA36AkEQmEIlFolTMMB3HhIOLod4gADiNPatGYPUktD4rI56KYcR5pAJ9IFRJAsJp1BFFQS4sZ6VZsuFdPlQmVYAxhLwIAAInLxLQCfMLD19XxjZDQnkkhltD5DCEwBFxGcJuwgA 600,500 noborder}} | <accordion> |
| <panel title="math representation"> |
| |
</well></WRAP> | ^Nr^Math Term / Formula ^Description^ |
| |1 |**Closure** | The operators $\land$ and $\lor$ map elements from $B=\{a,b,...,n\}$ to $B$. | |
| |:::|$B \land B \rightarrow B $|::: | |
| |:::|$B \lor B \rightarrow B $|::: | |
| |2 |**Duality** | If $A$ is a statement of boolean algebra, so is $A^*$. \\ $A^*$ is obtained by exchanging $\land$ with $\lor$ and vice versa. | |
| |3 |**Neutral Element** | There exist a neutral element to the operators $\land$ and $\lor$. \\ Applying the oparator to a and the neutral element results in $a$. | |
| |:::|$a \land 1 = a $|::: | |
| |:::|$a \lor 0 = a $|::: | |
| |4 |**Complementary Element ** | There exist a complementary element to the operators $\land$ and $\lor$. \\ The negation of $a$ is for both operators the complementary element. | |
| |:::|$a \land \bar{a} = 0 $|::: | |
| |:::|$a \lor \bar{a} = 1 $|::: | |
| |5 |**Idempotence ** | Applying the operators $\land$ and $\lor$ to a similar input a results in $a$.| |
| |:::|$a \land a = a $|::: | |
| |:::|$a \lor a = a $|::: | |
| |6 |**Commutative Law** | Inputs $a$ and $b$ are interchangable. | |
| |:::|$a \land b = b \land a $|::: | |
| |:::|$a \lor b = b \lor a $|::: | |
| |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 \lor (b \lor c) = (a \lor b) \lor c $|::: | |
| |8 |**Distributive Law** | The bracketing is similer to mathematical multiplication: \\ $a \cdot (b + c) = (a \cdot b) + ( a \cdot c) $. \\ However this is true for both boolean operators! | |
| |:::|$a \land (b \lor c) = (a \land b) \lor (a \land c)$|::: | |
| |:::|$a \lor (b \land c) = (a \lor b) \land (a \lor c)$|::: | |
| |9 |**Law of Absorbtion** | In bracketed formulas similar expressions can "absorb" each other. \\ This law can be drived from the laws (8), (5), (7) | |
| |:::|$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 $|::: | |
| |10 |**DeMorgan's Rule** | $\land$ can be written as $\lor$, BUT one has to negate the inputs and outputs | |
| |:::|$\overline{a\land b} = \overline{\overline{\bar{a}\lor \bar{b}}} = \bar{a}\lor \bar{b} $ \\ $ \bar{a}\lor \bar{b}= \overline{\bar{\bar{a}}\land \bar{\bar{b}}} = \overline{a\land b} $|::: | |
| |:::|$\overline{a\lor b} = \overline{\overline{\bar{a}\land \bar{b}}} = \bar{a}\land \bar{b} $ \\ $ \bar{a}\land \bar{b}= \overline{\bar{\bar{a}}\lor \bar{\bar{b}}} = \overline{a\lor b} $|::: | |
| |
Ok, now we know at least that the chip consists of many transistors. But how do they work and how can you build something as complex as a processor from them? The exact function is the content of the course '(Analog) [[circuit_design:start|Circuit Design]]'. For digital applications it is sufficient to have a simple picture of a certain type of transistor - the MOSFET - in your head. This has the three terminals: | </panel> |
* **S**ource ("Quelle"), the inflow of charge carriers | <panel title="algebraic representation"> |
* **D**rain ("Senke"), the outflow of the charge carriers | |
* **G**ate ("Tor"), the gatekeeper, which regulates the passage between source and drain: If the correct voltage gate is present at the gate terminal ((to be correct: the voltage has to be between gate and source an, not at the gate terminal...)), the Source and Drain terminals are short-circuited, that is, a current can flow and the voltage drop between them becomes small. | |
| |
Two types of MOSFET are important in the following digital circuits: | ^Nr^Math Term / Formula ^Description^ |
* one that is __non-conductive__ for __low voltages__ ($0V$, logic $0$, Low, $L$, or False) at the gate (n-channel MOSFET) and | |1 |**Closure** | The operators $\cdot$ and $+$ map elements from $B=\{a,b,...,n\}$ to $B$. | |
* one that is __non-conductive__ for __high voltages__ ($5V$, logic $1$, High, $H$ or True) at the gate (p-channel MOSFET). | |:::|$B \cdot B \rightarrow B $|::: | |
| |:::|$B + B \rightarrow B $|::: | |
| |2 |**Duality** | If $A$ is a statement of boolean algebra, so is $A^*$. \\ $A^*$ is obtained by exchanging $\cdot$ with $+$ and vice versa. | |
| |3 |**Neutral Element** | There exist a neutral element to the operators $\cdot$ and $+$. \\ Applying the oparator to a and the neutral element results in $a$. | |
| |:::|$a \cdot 1 = a $|::: | |
| |:::|$a + 0 = a $|::: | |
| |4 |**Complementary Element ** | There exist a complementary element to the operators $\cdot$ and $+$. \\ The negation of $a$ is for both operators the complementary element. | |
| |:::|$a \cdot \bar{a} = 0 $|::: | |
| |:::|$a + \bar{a} = 1 $|::: | |
| |5 |**Idempotence ** | Applying the operators $\cdot$ and $+$ to a similar input a results in $a$.| |
| |:::|$a \cdot a = a $|::: | |
| |:::|$a + a = a $|::: | |
| |6 |**Commutative Law** | Inputs $a$ and $b$ are interchangable. | |
| |:::|$a \cdot b = b \cdot a $|::: | |
| |:::|$a + b = b + a $|::: | |
| |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 + (b + c) = (a + b) + c $|::: | |
| |8 |**Distributive Law** | The bracketing is similear like for multiplication: $a \cdot (b + c) = (a \cdot b) + ( a \cdot c) $. \\ However this is true for both boolean operators! | |
| |:::|$a \cdot (b + c) = (a \cdot b) + (a \cdot c)$|::: | |
| |:::|$a + (b \cdot c) = (a + b) \cdot (a + c)$|::: | |
| |9 |**Law of Absorbtion** | In bracketed formulas similar expressions can "absorb" each other. \\ This law can be drived from the laws (8), (5), (7) | |
| |:::|$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 $|::: | |
| |10 |**DeMorgan's Rule** | $\cdot$ can be written as $+$, BUT one has to negate the inputs and outputs | |
| |:::|$\overline{a\cdot b} = \overline{\overline{\bar{a}+ \bar{b}}} = \bar{a}+ \bar{b} $ \\ $ \bar{a}+ \bar{b}= \overline{\bar{\bar{a}}\cdot \bar{\bar{b}}} = \overline{a\cdot b} $|::: | |
| |:::|$\overline{a+ b} = \overline{\overline{\bar{a}\cdot \bar{b}}} = \bar{a}\cdot \bar{b} $ \\ $ \bar{a}\cdot \bar{b}= \overline{\bar{\bar{a}}+ \bar{\bar{b}}} = \overline{a+ b} $|::: | |
| |
In the picture on the right (<imgref pic4>) you can see the two variants in action, when the voltage at the gate just assumes the digital voltage values. | </panel> |
| </accordion> |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | The last 3 laws are probable a kind of unintuitive. Therefore, these are shown in other representations. in the following |
Now it is interesting, that these two kinds of transistors are sufficient to build all variants of logical functions. Logical functions combine one or more inputs ($X_1, ... X_n$) in such a way, that every kind of input uniquely leads to an output ($Y_1, ... Y_n$). In circuits, so-called gates correspond to logical functions. They need not be only such simple functions like an AND-gate. Mathematical operations can also be mapped in this way. To do this, gates must be cleverly combined with each other. In an exercise on binary logic, it is shown that all gates can be constructed using NAND or NOR gates. So, if we could figure out how to build a NAND or NOR gate from transistors, we could in turn build all gates up to addition from it. | |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ==== 1.5.2 Dive into Distributive Law ==== |
| |
==== Gatter logisch? ==== | The distributive law can be shown on a simple example of daily life. \\ |
| When one says |
| "I'm happy with fries AND (a water OR a coke)" |
| he will be happy with |
| (fries AND a water) OR (fries AND a coke) |
| |
<WRAP right><well> | Be aware, that the is no exclusiveness here. The person would also be happy with fries AND a water AND a coke! |
<imgcaption pic20|Simulation eines Inverters></imgcaption> \\ | |
| |
{{url>https://www.falstad.com/circuit/circuitjs.html?running=false&ctz=CQAgjCAMB0l3EwwEx2QdnQZkgDmQGwCcR6IyuIArNZAFABmIWuALM5O61sh+wZCjQCQyMjoBzEN149BM5lV70AStJ4giIha0qD5gmvqFU6arAUphW7HO2v3y5OOWg1kb5tGtgqRQlRYVLikRFhCunQA7syW4DbMbPHs9DEWVgnp5OjK0eq8yMhcWuRFUIyJ9gkKDiAEEAC0MCIwYnSskOFy4GCySbWCWAD6BKxDkEO9yERjVOOwCONDyEPDWHQAstIlhexUCbtQrqYd4ayj4P7UFKUpmiNjE6xIK3MwYEtgeQolNTep+XAAkBhwBCkO4NwejyWQwsjidnKaQRnEqfCRPVkqNqiIBYF62V4+KxKTyYGBh3JgjhGKp4HQIjpoLJwJKdOJ5S2h25HVuRw8phiTLK3LKeIJtQ5NPFRISkoSqkxyTqVUcBRcAuOXh8fgCQRC6DCEVwZiBgjZwN0RwM1GtJkkZuYFkdQVyviIjo57IZ4Gc4HgAfgdHdjppdKwzupgiQgYDdAAHtc6pdeB72GUALYASwALgAdADOAGUAMYACwAhgAbHMAUwATgA7BPkXA0PbOsjp9jZ-MFgDCGwA8kWGgAVesVxsFrMFnMAe3rtebQA 600,500 noborder}} | The gate represenation is shown in <imgref pic37>. At the first glimpse, the output $Y$ of the upper circuit and the lower circuit look similar (they are indeed the same). |
| Also the truth tables for the first gate ($Y'$, $Y''$, $Y'''$) and a larger truth table for all results is given. \\ |
| But the conversion of the upper one to the lower one is not intuitive here. That is why the multiple represenations and remembering the rules for boolean algebra is very important. Translating from one represenation into another one helps to use other tools in order to simplify systems! |
| |
| <WRAP><well> |
| <imgcaption pic37| Distributive Law></imgcaption> \\ |
| |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BOJyWoSALNATAVm2JABzbyQBs2A7OtkSLg5AwKYC0YYAUAEohtFmg-p2whhEMRmbZojWYwDM0MBjC4E2crkW4iCGoqhyu0o3nKY4IRUQyZhzSAH1F2Zy4AeRQmCrPcD1h4A21KQJd3KI9XILIMNESkchiADUguAFlwKksMYVJ6fKcQBVNIc1xLKuZbe3JpKFLXdy8fSDAUiJUYsGdW5wBNLgB3fgbwMDEBZlEoUf5hYTYJx15F2amRLbnJcRk5UsPlVXVNbV19Q2Nccsq8-Js7BjomlLcY719-br7I-pi7zieDS3E84HIsyoVBsinsYGE8Po6QAOgBnVJgdGpbDovFowYAcnRROJBMJFJJXHBnXspAgijhpUg9iRUHx6MgHLRXLR3M53N5+KFfJ51IhdOwRkZkry4HoIoFovRWOVatVwsFgvFnXMGCUjNKjzZirRGtFpvx5qVmrVGRpEy09BlpSoEBN3OtZv5oq9pv9OskuEYPlKekw8vAnp9Kp1MkUEAKTLZfpjZsDzPQoYIUkjpq9VozCJhobACGYHrtaftIBhuvElk6coRIEx2NxaqJ4o4pBA5BhbAQ9CoFcj6XFpHsVHoBEsobZw3BPdmFX4Q-AFAjLcxOomuhhLsUkK39C9Z7T5-Vnt30qZjNvMJT0araqtz9thYd9gTYkP6hPUYvm+r6+lqV7qrudLlrCUFGE+QEWtWYEfha3ZTLMuhrqetgATi6wzOAGD2BwOxEeApQQgc8jHCoagaFoOh6AYCBGDAtxjCs8JkQRqj2Bk6gVvQCCNq8wlNGIzC3Oo0wTFMp4iQqFGMOxOSWGJckgGJGRjI8cxuJMEkLPpeliBp2k2KZrydOArzmY8yyrE4dxhnkYl1AwuTie8AxfB0XRBH8AIDFosQwJAIIuHhYx+HkEivMU8zSQ4DizPFjgUZJXACeMrLGXk+kyE0KmcQw3HCLgZEZHwBEVcRcy1eRpnHgoRxKLRZwMZczGsSYS7oQwmGDvQOhFGO2Bob2GCKOgQ2YBgubbmCzKspQpTWRg2gAYuIiTaus3SM2yJVRsc30CRUi6RRBSHC1Jx0ecjFXCxNwLARaiWCV73zBxExEWdiKPBk2QxZpliFKD4kmNViLWedmDWXsjQtbd7X0RcTHXGx+HlVscO4DsFFIzdNGnGjj3dS9HE4zJ9j44ZfWTUgWFMAtR1ZbgzAlfg8kvIpEkMAs636caBULCLUhFBMdlFGJjzc99yXy9Z8s1geBDiOgbismOvJtp2FIZnCIYMsaebISBNacDY-biAyI4Afm1Zxk8Wa1JoAGpiBnIZmoRjzutkaXj6S07H4ro2aOLZdjS6D6rUj46FtBs0jCDQlqnHMe++IEh5YlB+3nWhZwh2op32HTiKnLIO9npc5B5WYwnorPsiXdo6kYwaMEzwajduusdvipKEjqTe9tNLxwZGw9cEAA noborder}} |
</well></WRAP> | </well></WRAP> |
| |
Before the NAND gate is considered, a very simple circuit is to build, which generates the output value $Y(0)=1$ from the digital input value $X=0$ and for $X=1$ correspondingly $Y(1)=0$. This circuit always negates the input value and is called inverter. For this purpose the two types of transistors are combined similar to a voltage divider or a half bridge. Thus, only one transistor (TRANSfer ResISTOR) becomes conductive at a time, the other one correspondingly high impedance. | |
In <imgref pic20> the corresponding circuit with normally open and normally closed switch is also drawn. It is important for the following consideration that the logic voltages ($0V$, $5V$) are just switched complementary via the switches. For this reason this technique is also called CMOS technique: __C__omplementary __MOS__FET. In today's electronics, this technology is used throughout and has completely replaced older variants (e.g. TTL). | |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ==== 1.5.3 Dive into Law of Absorbtion ==== |
| |
| We will also try to transfer the law of absorbtion to a example of daily life. \\ |
| When one says |
| "I'm happy with fries OR (fries AND a coke)" |
| he will be happy with |
| fries.. |
| No matter whether there is coke with it. |
| |
| The absortion of the inverse ($a + (\bar{a} \cdot b) = a + b $) is also possible:\\ |
| When one says |
| "I'm happy with fries OR (no fries AND a coke)" |
| he will be happy with |
| fries OR a coke |
| When he only gets fries the first part is true. When he only gets coke, the secont part is true. When he gets both, he of cource gets fries and therefore the firt part is true.. |
| |
| The gate represenation is shown in <imgref pic38>. When ignoring the blinking High and Low of the lines, also here the similarity of the upper and lower circuits may be not really intuitive. |
<WRAP><well> | <WRAP><well> |
<imgcaption BildNr1 | Inverter gate in CMOS on chip> | <imgcaption pic38|Law of Absorbtion></imgcaption> \\ |
</imgcaption> | {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BOJyWoSALNATAVm2JABzbyQBs2A7OtkSLg5AwKYC0YYAUAEohtFmGehzDZM9COIzNs0RnMYBmaGAxhcCbOVxLcRBDSVR5XALLgq5EAmul6tqCEVcA7v3IZwY-oO-jIN18hEU8JKC4AD29nXEYiKX1McEkAHQBnDIywLMy87KjwWSUIP2wlLy8wNPz0yFyG9O5ozmdIdATnHyr6etqc2tzmmOqqEE6wBCEUqEa+xozA6LGwcmMia1XrHpAADT7dgdyATQByQo5SED1+BHoleh39wtIvKnoCa06d44uxZjANzYd3AD2S1T23D4AgBGC8onEaiqznGsnkznRKjUGi0Oj0BiMJlwQTYYSRwXAcIiGhCNk2dDpTgCDC4GnEpKqDNW4AZsgYLPcYCsjLEDmsgXcwh590RvKCUs40kkcvcSllknpvSCavCHPCSx53jGShWVx+YHOkse1tREVVSvCUolFLCMP1JL8rr8ioiLSojFWYzwECF0wh+wyh0avz96EmUgwcYQlRm8zyabmhSFtEBzkTXW2qcaR0GdSz72cN2wUvKjxmJcWCzyw2zsVo+e00nrxabBXt13w0oHAW14j07LC47tlmsU9Fw99bS8SgqBeuJvB9Bj-H+6-QwPuGC74edbqneqngQsQtng-sC7RxOhfnPPrnKJkGIUmNU6k02l0fRDAQYwYGJIA noborder}} |
{{drawio>InverterGatterMikroskop}} | |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BOJyWoSALNATAVm2JABzbyQBs2A7OtkSLg5AwKYC0YYAUAO4hsJyIUvQFCwCbFC4BJfoOHF5QvEOYxGuXuBXYMIAMxTse6XzDjJO4achcAHv33ZyETsPL79YegE0A5NoW4FZsRMwSUnbmKlRRwnFm1qrJidGGxrjiKllJFsx6EWDGGOpcYPj84Qnx1LUMDOW4zEbCpeDFberCUI18YQVEogp09HYASsrCQ-zF9KPgPdXY0IwrjAbQYBgVkuS4BrhECDQGUKsOswax6Bzb01Le9AAa3I4+8yaKBXiY4H6XDjXcA0Wb3HyPf4gZ52RwCQyQKggKgtQh-HzQyAAHQAzq9cQScQFARsDBB9oYDF4odicYTaYTCW9+BsDiAKYchE8oIycWBeUzAUIDFRGJ5DFR6Nz+XTZQzZfSSYYkOzGKVIRiZUyBbLuP0FJEqhErOkBsJcmJzWouABZHQFdqGwq9dZcSaWw0cOghKQQR4FVbCQObba7FwHI4nBBnDSXCrCpTYVpkiDcmG4-EKolx8gtVpJvNqmm8+UlnMtXDOAwVpHc0t8nW42HgXDoEW6Nug6Ulxs45v5TBwYTVwdnbtZrVZ3Hcd0KDAYURzTALxb+oNrYNbHat8OHY6nc5aO0DjAGqyntTr7SW+eiaq36RwsDAjCHMFeAxSqEwuMzDCS75MCIVMoV8QFnyECN3wYT90ReGcpkrfQvXoJDVxAZZA3WQwtzDfY9yjGMLn6ao0MtNC7AqFpHgNToLxdXotBiZh6M4GjrT4VpcE6YJuKiIJIJ4yD5zyYTkNIkT0mCB8zQfKSuRXaTqnkoDqNU6QgA noborder}} |
</well></WRAP> | </well></WRAP> |
| |
From this example, it can be seen how a logical $1$ can become $0$ in mobile phones, vehicle control units, and television sets. The <imgref BildNr1> shows the realization of this gate in silicon: | ==== 1.5.4 Dive into DeMorgan's Rule ==== |
* Figure (1) shows the image of a scanning electron microscope, which shows several layers at the same time. The three circular elements are electrical passages ("vias") through several layers. In green are the two structures of the MOSFETs, which can act as a "valve" to open the connection up ($5V$) or down ($0V$). | |
* Figure (2) is a false color image. In beige is the top conductive layer and in blue is the non-conductive region of the top layer. | |
* In figure (3), the different signals have been highlighted. \\ The output $A$ is taken out via a via with the right connection. | |
| |
| At last, let's have a look onto DeMorgan's rule. The following instance shows it in daily life. \\ |
| When one says |
| "I don't like fries AND i don't like coke" |
| he will be unhappy when he gets either fries, or coke, or (fries and coke). |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | The gate represenation is shown in <imgref pic39>. All four circuits show the same behaviour. \\ |
==== not-AND, or? ==== | On the left the NOT gate is explicitely shown. On the right the NOT gates are shrinked down to the circles either on the input or on the output. |
| |
<WRAP right><well> | |
<imgcaption pic21|Simulation of a CMOS NAND gate></imgcaption> \\ | |
| |
{{url>https://www.falstad.com/circuit/circuitjs.html?running=false&ctz=CQAgDOB0YzBMICMZJ3gdnQZjADjgGwCcR6IcuIArNWAFABmIWazVCWBlW7IBEKAlDBxGzVhW5dyuSvyhCUIugHdm0xIg4aALDvCr1lODoidj6BPQDmRu+ZCmBdAEp2dUygPCOINbyhUrkh6IERC4WFCiOTkMOSQNHCJzJCIOohURIRUPLikRFhQHsHp+ojykRUQMQjIEMlJKVhp6AQ6JHBYuARw4ehEXomGZVHklmP0anATkSwQkVPjCJEzHKxLo9XMYOXySzh7ZqzbB7tI8ofkpgZqDiYQHUIPBkwZEUI67WMEMQC0gmEoiY8zGDkivxAAMgimgolMRS0cn0cCoHx8BAA+u1MWBMVo+jpMVRcdAYIhcZi4NjMVg6AikBRGcY0RdvOhsUS8RkRMTSbAwKQCGjUZTqRy6QBZaihF78Yw3BrDBl6Yx4ahta7eRBETmUnnUkkoCl4xCGByITX3RXmk7yd5s26OCqOh2Lc3SDx2XDOO6eyhffRepaBxwB74+p2hzQIaOakPfS1CC3xj2UUYpxSGJ5amUom1+7jnBxYThOq4vCuycvnSTiBrVpZrevLNhWQzNnjrMy8ejSrbyLbxhJBfuhKqhGM+Rp0AAeIGrmCQ50j+ZAAEE5wvojoaMg6l61wAhLdZIpwdJ8QXkS2Oa4gACadGlDr+kVVUMWI63XzIfy0MQeEU-6IAG95PncuD6G+nwujBBhuM2fyRqiQjITUsRoEqTQ0C06SZNkwp5AURQoCUiETCBCCoVCU61Mu2EjqkSYdNk3S9P0gxQEE0yUZGVzoU6SFTgJU59q2glIV+M7SsJWgSUi07DPOF5EJ+548J+jz3puKk6rRJjkJp-4XnehknpkMQCXMUGfoosQ0EEQA 600,500 noborder}} | |
| |
| <WRAP><well> |
| <imgcaption pic39|DeMorgan's Rule></imgcaption> \\ |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BOJyWoSALNATAVm2JABzbyQBs2A7OtkSLg5AwKYC0YYAUAEpSbkMINgGZsAoRHEZm2aIzmMR0MBjC4E2crhG4iCGiKjyuAWXBhxuS+AxDr42SYDu-DIPDkJULgA9hMpjWwmD0GLhCkvQAGpB+tswYCJL4mAaY4PQAmvFsgbjBHPQFkZkg0dx8zLjkzKJWteAg4kROCvIgyqrqmtq6+obGuFyuYF41zNWNcerMYgw2nFY2Qo4MI51WdJ4M23Gj49tjDNMbx+6SXkle+zvXm2k3Z154XvOvPgfN2JfNNZ87Oj0Y5iSYbd5EYEvSEAkGkfignxVTZ1eaIqQgVrNDqKToqNQaLQ6PQGBBGGDDfx5OacEL0ESqDKhcrcfyqWQRcCpPBUJnZXKBAgQIrNRlRcq3WQ-QHSuLmJbNKjiVSrJX8RS8dXS+rfSTNTBtbFKfE9In9UnkkzqIzvNUK6hrNbDcwcRoOkJ2RWOkxU1T0PBCDgiF64XninKuUSQVYw+qyGG3OPNWOIxGJxHYbUZ-7p+EfKOrHMbJP3AuPAEljwlhBPSOI-D0JMTCsiaO7Rv1vZcWbCVv2GxsTP9x38YZ8alTOpqcaNDFY3G4roE3rEgZkoYC6UFYUyKyc8UVTeRQq7oKlZmxTUT7x5c4eDGCnEdJemvokwYUrgASWEP1katdf81gpdZ1HEMt3UHQU1VkBh1h-a8Ll7eEkMmDphgQmRJ2Q7C0MYYZIyHBZwLGaobDiccsN1AJjiIh9DUXE1CTfNdLQIgI4GopMiLiKkMGlIUOPEAhzxiXiAmlBkd0gcQGVElkryoxFbzeeE5wY58mJXc0PxcHCUQ4uZ4XEjgMDCZIQmDNIwzKHIXVI4iPWHdUfRCchgQAkhwCoRgXiEWIAB0AGcAoAB2Cw9fVDTBMxCbZ+N85p-JMwgrlitgqDDPAQD8hTfWwIwCRCQhMGZSJ6GgLggA noborder}} |
</well></WRAP> | </well></WRAP> |
| |
But how does the NAND gate work, on which logic can be built it? The concept behind this gate is that the output will only output logic false ($Y=0$) if both inputs are set to logic true ($A=1$ and $B=1$). The gate is shown in <imgref pic21> above. This must be implemented using the two types of transistors , which were already explained. So, this structure must be built in such a way that: | The important thing about DeMorgan's rules is: any expression stays the same, when |
- only if both inputs switch transistors with $A=1$ and $B=1$ at the same time, $0V$ shall be applied, | * all parts of the expression are inverted plus |
- if one of the inputs $A$ or $B$, or both equal 0, $5V$ shall be applied. | * any AND is substituted with OR plus |
| * any OR is substituted with AND |
| Important is, that also the most upper expression also have to be inverted. |
| |
The first one is possible via a series connection of transistors at $0V$. These must short the source and drain terminals at a gate voltage of $5V$ (input to logic $1$), so n-channel MOSFETs are required. \\ | ==== 1.5.5 Example of a logic Simplification ==== |
The second one requires a parallel connection of transistors against $5V$. These must short the source and drain with a gate voltage of $0V$. Here p-channel MOSFETs are used (<imgref pic21> below). | |
| |
The implementation in silicon (<imgref BildNr2>) again appears somewhat unclear at first glance. In this figure three pictures are to be seen, again. In the first picture the transistors are marked green again and also the vias are to be recognized again over white circles. If you take a closer look at the diagram, you will notice that the via at $5V$ can be reached via the left or right MOSFET. However, the via at $0V$ can only be reached if both lower MOSFETs short-circuit. Thus, the structure is consistent with the circuit determined so far. The <imgref pic7> and <imgref pic22> should show this in more details. | {{url>https://wiki.mexle.org/_export/revealjs/introduction_to_digital_systems/calc_logic_example?theme=white&fade=fade&controls=1&show_progress_bar=1&build_all_lists=1&show_image_borders=0&horizontal_slide_level=2&enlarge_vertical_slide_headers=0#/ 400,400}} |
| |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ |
| ===== 1.6 Examples of Gate Circuits ===== |
| |
<WRAP right> | ==== 1.6.1 Logic Gates with multiple Inputs ==== |
<WRAP group><WRAP column> | |
<WRAP right><well> | |
<imgcaption BildNr2 | NAND-Gatter in CMOS auf Chip> | |
</imgcaption> | |
{{drawio>NANDGatterMikroskop}} | |
</well></WRAP> | |
| |
<imgcaption pic7|>{{ :cmos_nand_schematic.gif|NAND Gate in CMOS auf Chip (schematisch)}}</imgcaption> | 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 input. The two AND-gates shown in <imgref pic40> can be substituted with a single one. |
| |
</WRAP><WRAP column> | The essence auf the AND gate is: An AND gate - no matter how much inputs it has - will only output high, when all inputs are high. |
<well> | |
<imgcaption pic22|Simulation eines CMOS NAND-Gatters (Struktur ähnlich Si-Die)></imgcaption> \\ | |
| |
{{url>https://www.falstad.com/circuit/circuitjs.html?running=false&ctz=CQAgDOB0YzCMI5kgJhig7BgzGAHCgGwCcxGIKArCNZWAFADmFeeI2hbKrIALHIXD0ASnzaVu7FDUkJpaCCkjUl1bJDj9KxIpWyU8ZYtii88IsX0K8pVm3MQwKy52o0ZrpFNjyEUxQgxiNmRKegB3Swk2XmsZEPpeMBM8CF4Ainx48EQAfWtcsFy4FH9eXMpC6HhC3JRi3OxE5JBUvmx5LNibRXzyov4wesrkWDAyQko-EbrZpoBZCiSpNLYOiEVlZpTFHjQ1tBzCPtrB4aq4WrgI9g5EXhsONk0em6f7mySIF6FI7Dv3oDOL92MD3l9QQlIrwOpCxBB3gxItw1mCwI9gQxRLhPmt0TkNnwINRCaE3vizO1pJSkVTLDDpD9aTjLCymW9DnAdCsKChXtCBBQpnxBesQfxBFzqYL9uKZV0ZXzxTE4vpqXFmYcqIIxWLmcCfu8SlClgjDmYzRsbhaeTbEfRFpTolESjlVA76XFKQ8Qq56AAzHn-HWHd4SRAuUYoAMikNpUXA8NwSPQaOBsVSnk-PQRkmpjmWoN3BiBiWIbll7MmZN5ob0AAeIAAtLQ4NQ4AhKHAYksQABBBvN6i8JMIEfD3sAITeBskfO+klp88yXGWepuy9ly+N4rizu6pt3NmXDMPzLuy7VZ7e4cv4YPDEbTdDVHYZp7SoA8gBVAAq1plYVT2XWlgOWMtSn5HlINuQQQLeC81y1YUGDbBAIDaTDCWkYlBybPBaGkJsSBoCclWnJ8CNaExiOIVpBGPGwB0WJtYTiVjqV9d0WNhDIONabCtkifiNRADUbn4jIICkiwRJsJtKTiBwkE2FQXHUOAPHSHQfD8AIghCLZREkwQFLYDIHAUVxrI0rQdEmfRDCCExkDMG4sMQV02lpDtpDaXzm0FHzXSbQUzMCwRH0CylQoQJtgmbD8bB-f8WJisK2lCyK-SAA 600,600 noborder}} | <WRAP><well> |
| <imgcaption pic40|AND gate with multiple inputs></imgcaption> \\ |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BOJyWoSALNATAVm2JABzbyQBs2A7OtkSLg5AwKYC0YYAUAEqb1FmHMNhCDwIURmbZojWYwDM0MBjC4E2crkW4iCGoqhyu0o4sgZw5ZhkWjs0qFAD69l5BcAPIoTBUXXA9YeANtSiDPbBdo6M9FYLIMNBSkcg8XAA1ILgBZEARyTHtJYmLRGRMzEAsre1sS6WYZNzjvX0gwdMiVDLAYjIBNXhA2citOUWFRSYlRcQVJORqVNQ0tHT0DBCMYXFNIc0tS+jsHInpbVoyfPwCe-qiBzww3RLwMzO4va2Z-Kkk5CKYHEE3o2QAOgBnL7QzLYaGIqGDADkXB+XSspAgWixxzBUCR0MgRKhJKhpOJ0PR1ix2CMeFoWkw4EupPJSLAlIpZJpXQZGHkekkGFOrMJPOhXMlZO5xL540B9EZkioEAJHJ50s5ct5GJxuEYvkkwoJ2q1uu+4BkiggC0UVjN7N1OX1pXQxoIUnFmqlLr5EBBAONYAQth9zplSNdIAB-LEwKBLJBIFhMIRMtRNI4pBA5ABbAQ9Co4ZT2RppCsVGVXTE6vFwx+Ob+h1GRetRQJXwVdVwAJVihsyfo5r9MtH44V5gdJvoikUAKd48j3JjmJqIhN6FtjCX0dJE+jPckYa3J6Me55vtlUav2ZEf10bZHijFZewIzGEwwVmm4B-cy-Es8jLMoqjqJo2i6PohjGPs6i2PQhTgHQBRFDIDAMFwADu-DgJuJSzDkuGEQRMyocRNTkSOwIUQcRxYrgnYlPO6Eitcni3J03TBI8AxtI4bwwJAHyePCn61hgip-lJEySEBiyLGBayQZsME7HB965oKjCFqcpriuJTYPpg9LPqZnaGValaYKokiSf4w4gI2owma+Bbtoop5djkfCSSUMmEfJCzLEpqwQRs0HbLsJj5CISFFKQCXOAoEmdnArmbk0gFOIpoHhesUFbLBex8jMjnUChpb0FmCGjIq8XWChlzyYw8G4H8zGiMhZzOEYbU4U1ahFBwna1pRo22SNkkZZRkmiq5nYLRN830JNslQFwQA noborder}} |
| </well></WRAP> |
| |
</well> | |
| |
</WRAP></WRAP></WRAP> | <panel type="info" title="Exercise 1.6.1. Other gates with multiple inputs"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | - What is the essence of an OR gate? what will the truth table of an OR gate with 3 inputs look like? |
==== eine einfache Rechnung ==== | - What is the essence of an XOR gate? what will the truth table of an XOR gate with 3 inputs look like? (keep in mind, that this question might have multiple answers for XOR) |
| |
<WRAP right><well> | </WRAP></WRAP></panel> |
<imgcaption pic24|Simulation eines Addierers></imgcaption> \\ | |
| |
{{url>https://www.falstad.com/circuit/circuitjs.html?running=false&ctz=CQAgjCAMB0l3BWcMBMcUHYMGZIA4UA2ATmIxAUgpABZsAoMBCFGqsDQkbNcTqECmoJ6AGT5d2-ALTFJAgGYBDADYBnAKbVIYwWxBy9VWfKrL1WpDoCyFGjQl2HJgSmgimEbNi4cuNMF9+KiEqEQB3bh9wYiFvIMl6SPjwQioUvygkqITuXkydTxyQPCoArlLXYWzWdljBfBjQ7MzAkP02rNsEGUCKGUMQ90ZmYuk+8pBx+SEkD1G6IWmKMCW+kIEI2h4pncWp9ez95cnlnUj9sp3K8+2hSsmb7Iy04sIHW5T3sZ3bycyECg8I5PtFDLUDIlImhgeDGmB6qD5AUspEUa1XrdmGsuD0uGdsgh7I5AcCCjV9HDYYkAB4NJZ4YiCPrSPD+PQgAA6AAd6HTKBBZGEmFM8OQHKwuQBHegAI3AxOk3zS5BQKGwWTpYDZU2JaCWAVoHIAgnzBJRdRLCPjDRKHAAhM0IUbSGizQjA6TYJl2kAAYSdeCQro1aUF+l9AGVGMQkClxvU2MYEc1xPGU4I8J6M1QzKpNNpdOnXkDs5jwCBzAWrPRbMcMzRKgnQoJhnWdtMyk3OkMREA 600,500 noborder}} | ==== 1.6.2 Switchable Inverter ==== |
| |
| 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. |
| |
| <WRAP><well> |
| <imgcaption pic41|switchable inverter></imgcaption> \\ |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BOJyWoSALNATAVm2JABzbyQBs2A7OtkSLg5AwKYC0YYAUAEohsBmbCCLMOYYaPAhJzbNEbzGA6GAxhcCbOVwDcRBDQFQFXDJGNgq5EOQwgBke2vvNIAfSHuPADyKErd1xvWHhDHUpgj2x3GJiPARCyDDRUpHJvdwANSC4AWUx6BBsJIps5U3NLa3Aax3s8cplPePc-AIyo1UywWMyATV5+IXAJfk5hCelhcxkFOeVVdU1tXX1DBGMYXDMLWpKx+vAtKEwWzPbIQK7e6L6PDE8kvEys7h9RmVxGfy-6Z3oYAAOgBnUGg4FgqHgkG5D6EGQCCBSbACewA8Aw0GQLHQkHvT6kdC-AgzcD0HF4yG4iFceEQMBEKgiBkIZgYykwzl47F0kDMsDkYy-QU2DEAUQAcqCsjSQYMPhxSLZmRxiPz2eSQFk+RJ7FRAQIbL8MQrxsrCMY2AhGIQxVqpVwNPZBMJioUQO65KcdkA noborder}} |
</well></WRAP> | </well></WRAP> |
| |
Wie können nun die NAND-Gatter so verschaltet werden, dass das Rechenwerk Operationen wie $y=a+b$ durchführen kann? Dazu wird die Operation zunächst nur für binäre Werte betrachtet. Um die binäre Größen von dezimalen Größen zu unterscheiden wird diesen ein $0b$ vorangestellt. Folgende Kombinationen sind also möglich: | 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 |
* $0 + 0 = 0$ bzw. $0b0 + 0b0 = 0b00$ | [[https://www.falstad.com/circuit/circuitjs.html?ctz=CQAgjCAMB0lwTAFkWRkBs8CsIDMMxd0AOI44ksATnXRHmJBy0iYFMBaMMAKDRy4MQNEB0SMRrRsR5hiVUWHStEueIrDrV6qfVxUeAJUXKQidIhMrx4erfjQcDnKxjEsfQqKqaQF0RSW-qy4IIyufnToAOy2EDGRUIqi8DwATsJ0uFjqImgRYJDp4ELZ6pqM+UmFxf5lfpZVrDUZang5eFpw1UUAMt6+-hw0rMG2AGYAhgA2AM5sTFA8-RzESuB0w6brEVNzCy7FW+3qx03gRRkcdR3Xjd3Nl0n1Kg8XR231HG3nNXKWq3WIg40WIlkkeFk7hS5EyJjhIVkQzIZmR8BUY1CrBcID28yWAHcUtEtENqKTLEUiRx4EgzMD4CT6XQqcT1DlGDSsHQOYTRNEOryQR1cGC+SCSEwhML2UJWSD0cz+ZLEJIeNSSSExQqVGrqSRKkMDXgxfLoiqjbDzJSkQDCpBGNhNiN6NznotdjN8UVjKt-NaAnl-BB1P5nPRHEkYB4lADAqi4+sAyEkji8Qt5SiA98VQ91aIs90-fdXPni2Yi-Hk2XjVhzYpIHS6yyy4Um-WuI3LE7xW3u27Ow7XS39VbLYxm0swFgAVVgfhwSy7Niy1VuKd0G71+LN3RgbvwL4+qIqm0OFhfG1PfsPa2qFpgeSE7378+uK-RTbqbTLJ+UnTVRHFI3T-LkeTlMs1jodZASiL9FFfQCrCVeVT1OKpiFLakFzhGlYTVNBQjEdZUABBhHSHFRogAfSUajIGogAPNZIDorB6OgMB6Oo+BaOgbBuMQGjcA4xt2IYgARABBAAVKSeAAIwbWFvg3C8-GnJYlLEM82jAUENNiIpGIbIcxAEdwIDELR6EsABZABLABjNIAHsnNcgA7AAXNzpmmNg0h4EzvlwKzEA3BRvgUbtLAkhzZgAB2mSYAE8AB1ZgJBzvIAC0yiS0gcgA3QLMt6VyAHNnOC7wqAUWkBCoML6CEWKQAAYVcgBXHzAtq1ZEBwVRNmiMazH0MxbM6nq+qCkLslCVRYjw4a0Cmukut67z+pCqhIEaKy1kqRpprstgAFtXLSVKBrGyxoiIkkFHrdq7O6xiBqQHBolYLh0Bepbpoky6PoGrBmFwWJogUGcVGmgBlXKHPGbzMrSNhqtmHb5o0VhoggVBGGiU66V6ABRCTMoAEwS5K0sygB6TLEocxi2GmTLJjSNI0oGzAiKEk9shAWJGkYABJAA5AA1cnDBkzL0vSzzMoACXl8meCAA| this more complex example]], where the display smiley can be inverted via the XOR gate during data transmission. The other logic component in this example will be explained in the following (sub)chapters. |
* $0 + 1 = 1$ bzw. $0b0 + 0b1 = 0b01$ | |
* $1 + 0 = 1$ bzw. $0b1 + 0b0 = 0b01$ | |
* $1 + 1 = 2$ bzw. $0b1 + 0b1 = 0b10$ | |
| |
Es ist zu sehen, dass nur wenn beide Eingänge gerade $1$ sind die zweite Stelle des Bitwertes gesetzt ist. Dies entspricht gerade einem AND. Da aber alles aus NAND-Gattern aufgebaut werden soll, muss eine geschickte Zusammenschaltung dieser Gatter gefunden werden. Hierzu wird einem NAND-Gatter ein Inverter-Gatter nachgeschalten. Das Inverter-Gatter wiederum erhält man über ein NAND-Gatter, wenn beide Eingänge verbunden werden. In <imgref pic24> ist diese Schaltung unten durch die beiden unteren NAND-Gatter dargestellt. \\ Auch für die erste Stelle des Bitwertes lässt sich eine Schaltung finden. Wie kann man auf diese Schaltungen kommen? Dies wird im Kapitel [[Schaltnetze]] erklärt. | Another usage is the inversion of binary numbers in the arithmetic logical unit of the processor. |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ==== 1.6.3 Data Valve ==== |
Werden viele Eingänge oder Ausgänge zusammengefasst, können größere Zahlenwerte umgesetzt werden. Das heißt, die Rechnung $3+3$ bzw. im binären $0b\color{green}1\color{violet}{1} + 0b\color{blue}{1}\color{red}{1}$ wird auf mehrere Einzelrechnungen heruntergebrochen. Dies ähnelt der händischen Addition durch Untereinanderschreiben der Zahlenwerte und schrittweiser Rechnung. In diesem Beispiel müsste zunächst $0b\color{violet}{1} + 0b\color{red}{1}$ berechnet werden, was $0b\boldsymbol{1}0$ ergibt. Im nächsten Schritt $0b\color{green}1 + 0b\color{blue}{1}$ muss zusätzlich noch der Überlauf aus der vorherigen Rechnung $0b\boldsymbol{1}$ berücksichtigt werden. So können prinzipiell beliebig lange Zahlen miteinander verknüpft werden. | |
| |
Um die Zahlen handhabbarer für Mensch und Maschine zu gestalten wurde eine sinnvolle Gruppierung eingerichtet: 8 binäre Zahlenwerte werden zu einem Byte zusammengefasst. Dieses kann für Menschen lesbar als Dezimalwert $0...255$ oder Hexadezimalwert $0x00 ... 0xFF$ in Programmen dargestellt werden. Im Microprozessor werden diese Zahlenwerte stets als Binärwert gehandhabt. | To deactivate a data flow a simple AND gate can be used. This is also useful for channelize data in multiple directions. |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | 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$. |
==== Nano-Lego ==== | |
| |
<imgcaption pic10|>{{ https://upload.wikimedia.org/wikipedia/commons/a/aa/Silicon_chip_3d.png?300|dreidimensionale Struktur eines Silizium Chips}}</imgcaption> | 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. |
| |
| <WRAP><well> |
| <imgcaption pic42|Data valve(s)></imgcaption> \\ |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BOJyWoSALNATAVm2JABzbyQBs2A7OtkSLg5AwKYC0YYAUAEohsBmbCCLMOYYaPAhJzbNEbzGA6GAxhcCbOVwDcRBDQFQFXDJGMCB5EOQyY74DPeaQA+kLfuAHkUJgqN1wvWHhDHUpg92w3GJj3ARCyDDRUpHIvNwANSC4AWUx6BBspYqgZU3NLa3AqGwxHPBs5D3i3X38MqNVMsFjMgE1efiFwCX5OYUnpYXMKxQUQFTUNLR09AyMTXDMLJZrphvswLXKMVsyOyACgkL7o-vdzxJhIPEys7m9aqnAiemwGF+Jwgx3oYAAOgBnaHQyEwhGwqFfWo2MCNBrgci-MHgJHQyD4xFQ3LfALAjDCQEUxi4wnE+FEglcMlUYGkGRA8DYYx0on0pkklm1YxlakgJCYP4gACiADloVlBUNvhwOdiJsQQFRmLissKqIwaCJfiQpWB6CqJhzCMY2AhGIR6tL5VwNGJRmUMEVmjJyjt3SNhAIiPZvUtQ+VhMwdt86ktyDYEPRrOhcQNSdbmHpGBwtRtzfR9XwOM4GOQxCdhLgKzNMHJFkolqp1JptLp9IYEMYYDsCuGQ-YpIOo6YS45rPRxMHyOC-VIm03lq21h3Nt3tvlCg4h7rHA3Y9r6pjk5gUoWQANuIHBLNHOGjlH-VwAO5Bs9T+-h3Jvthfz-2JOUCvvwE6zu+QG5AAkhMZb4FOahhvu2wMCBpZIfY6H1q4aGIdh77mDhv6jN6lbjKRwG-nhNZkdWtY-hM4w0YxsxSJmbB0PQ54cIaDCzJyIAACIAIYAC7CdCABuwkADaSSwwocWaAjjGwGDKBoUqAiAADCAD2AC2ABGACWAB2LAACbQpZYkSVC0lySwUKKaQ1bqRMbIMA+LpysKAQQHoxh0MGNYXvKirKvSV7+bxAhedQyhSHyxICsSBL8tCsXKJK1C6m8F5pXCgrFalsVhgQMjkGm2m4oyCJFal-LZWeig6h+F71aVgqNdwVFwXQsH2MxuRAA noborder}} |
| </well></WRAP> |
| |
| ==== 1.6.4 Multiplexer and Demultiplexer ==== |
| |
| In the linked 'display example' in 1.6.2 there were a Multiplexer (MUX) and a Demultiplexer (DEMUX) visible. |
| |
| 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 'inner live' of the multiplexer will be shown in the chapter 3. |
| |
| A **demultiplexer** is the counterpart to the multiplexer: It has one data input $D$ and several data outputs $Y0$, $Y1$, ... . Again there are also state inputs $S0$, $S1$ ... . Here, the state inputs address to which data __output__ the single data input is routed. also this is shown in <imgref pic43>. |
| |
| <WRAP><well> |
| <imgcaption pic43|Multiplexer and Demultiplexer></imgcaption> \\ |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BOJyWoSALNATAVm2JABzbyQBs2A7OtkSLg5AwKYC0YYAUAB4huMAzLkEgq9YeUzh6YADoBnRYvlK1yhQBFBvflMHZ0VKiEEHpYWRsWRr6rdl0DTkE+NOEL9W-dV3Fmtx8znSM7nT0GDJQdj7+WpBOtOQQVNgg2ORRUZYgAMqqeXH2AJpO2FHYpCAI6VWilVEAsgCuADYALgCWAA5tLDwsAE5cllFs5hhwNVJTzMyOlowVzHOm+JjTC05gGNmQ42AEmyY59JqJADL8k9NsCLNbUCAAZgCGbQosDFBcAO4zTYLKZA37XCbpDDme6zczMCDvT7fRiJYK7bKCKQcY5Q9BnECBHZ7JjMbEQXCQBrRbRccGTB78BkYBnzV4fL4-K43SFZRmzXnwtlIzlE7LkehkzBUCD4zSONHE3BEUlHdJKqm5Iq07kMKhYhm4PXPZiIjko7UQkDkYh8q021mm5G-BVRFLpbHpFKMfEFf46w36NVGxIA8wB0xq62-AGW630Xlx6NW1023m4KMhiO6qTUINSTO57MZNIMDN+hM2wQHO3eP1VlMSavp+ZcJqmcWgqGQp7YaC4VvtyKTYfpBZ9geYyK8ruYAUZcdtyeYJn0-Pz-t8DAiWd4qjekv4kryzDbikyvdMbLREo6TfbqGnC97VbXoInhqQffem2H1E1USCAgECEEICBXrkZR8JkdS4HigiVJQXj5IUxQaCUPglKoR6KDeuiZDmRANBUGRELM0SoQoFHxJosS0fYf74S43rEVWkTkXYfj2HRGg0fRsR4eQQjUJg2AAVWSGcTY8TcWoFG8RoDHkPouAyixuDgVYvjSXxOkKXYmh4XQphARkIKARpBJcHkGTpmI1T1nZrImuy3wylZgJUJimD0J5a7OcKbkAgyvk2VIIUMRg9BVOk5kZHg0jEZoLAALbtN0fQDMMRLoGY6AcJAECYnipkgAAKkMACeyhyAAdgAFsMLB+ngYVeS1jnOlaVoXvBojkO4jQgAAogAji0XQAG4fCwNUdIoXQ1Yobw1R8AD2ADmigsP0ADGHRDKtNVdDtChcEAA noborder}} |
| </well></WRAP> |
| |
| With the background given in subcapter 1.6.3 the demultiplexer can be derived. The example in the subchapter 1.6.3 an input were forwarded to 2 outputs. We will now have a look onto a demultiplexer with 4 outputs. For this instead of an AND gate with two inputs an AND gate with three inputs are used. The top-most input is the data input $D$ for all gates. The other two inputs address which of the AND gate will route the data input. When one has a detailed look onto the addressing inputs, one can see in any time that only one AND gate has both lower inputs high. |
| |
| <WRAP><well> |
| <imgcaption pic42|Demultiplexer exposed></imgcaption> \\ |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BOJyWoSALNATAVm2JABzbyQBs2A7OtkSLg5AwKYC0YYAUGLs2wGZsIAUQyZ6o8cwFQGXAB4gq5EeVUJJ5dOLD0AmtkUhBYYWASNBccJszh6AES4AlE2Azjc5fh68JzEGEMZmxoRjDGAWgPXgDyXAFcIgQaWRhcLgBZCRExECIZfNDw1xM8VVJ6a3Eq8CCCkojwkRiMOOwEpJS0qFKcjHoMcnFCzBG5SOMVTGGQO08dBxB9AR4+EyFx8UHtuXT5AHdN4N22Cc96SC5j852ziYFyK5uTR+eTtReASXdPBn+HH+g2YoJamVufgkvmBNmukNh-C2IVBr0EwTGHDM0KgaKh3l82IJuMhRJ87mxINxSg4uCoIHIYHpHCSDNI9j0IAAytcaXhZIzmdgBBBKMxdPQudxbtgQgxyWxZcxcP94eU5cTFcR5aiZdqpJ8DWrFXKqSbxXCuL9zQDxDaqWDGJk3DbNUqGAF6sJ2ZEgi1orFcPFEslUgh0qVbsiJlqhhNjXVhna6ka0XU3dqkyTyvr8rGRJBpGn9YWc-RsLLs+iC8m5QJSwm66WbRWizK5a3Pp3GzJm+6UVWofW7VCB8atkJCcJJ4P-u7q+7jUPm1DF2iJnUF9rjRuiNUN9u0Vs6PvanvcbwkdPS7th-s5JklDM6BpyykOQZuANJKWxnemtkuSdmM3Z+o+yiVBQ8zlpASycvo1yXl2la7KBBwQhSGJTiI7JLtiM5YuYMxLnOcpAroxHFuWlb5kyqg9kENHunRVYVEE2p3OxLy3Lup5fFWFwPF45K8iYljgOSuAQGA5CyLU4iOCwAC2ACuAA2AAuACWAAOaksAoLAAE7GEykgzAITwiDQH7gAAOgAzo5jlgM5TnuW5jmQJ5DneR5vk+c4ShMvSSTTqySSMBK9n+X5Pk+XF7mJY5jgJaZVCSPWIhWZZcnLMlDmuf58UBf5qWxWlwUZQWmWqCKEDRQVBUleVblNZV4BUGe4gCHMdD0tFUqOTyJUIY5+hFYY41rAARuUVBEaouBOlQup-MJMJeKqXBAA noborder}} |
| </well></WRAP> |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ |
* [[https://www.symbolab.com/solver/boolean-algebra-calculator|Solver for Boolean functions]]: The solver specifies with which axioms Boolean equations can be simplified. | * [[https://www.symbolab.com/solver/boolean-algebra-calculator|Solver for Boolean functions]]: The solver specifies with which axioms Boolean equations can be simplified. |
* [[https://www.wolframalpha.com/widgets/view.jsp?id=a52797be9f91295a27b14cb751198ae3|Wolfram Alpha]] shows the different representations for boolean statements | * [[https://www.wolframalpha.com/widgets/view.jsp?id=a52797be9f91295a27b14cb751198ae3|Wolfram Alpha]] shows the different representations for boolean statements |
* [[http://siliconzoo.org/nxp.html|Silicon Zoo]]: Here you can see the practical implementation of logic gates in silicon. | |
| |
* A nice overview of core ideas for [[https://informatik.mygymer.ch/ef2019/rechnen-mit-strom|calculating with electricity]] has been compiled by Gymnasium Kirchenfeld (CH, in German) | * A nice overview of core ideas for [[https://informatik.mygymer.ch/ef2019/rechnen-mit-strom|calculating with electricity]] has been compiled by Gymnasium Kirchenfeld (CH, in German) |
* [[http://www.righto.com/2016/12/die-photos-and-analysis-of_24.html|http://www.righto.com/2016/12/die-photos-and-analysis-of_24.html]] | |
* Explanation of [[https://ca.wikipedia.org/wiki/CMOS|CMOS]] in the english Wikipedia | * Explanation of [[https://ca.wikipedia.org/wiki/CMOS|CMOS]] in the english Wikipedia |
* Wiki page on [[https://en.wikipedia.org/wiki/Integrated_circuit|integrated circuits]] | * Wiki page on [[https://en.wikipedia.org/wiki/Integrated_circuit|integrated circuits]] |
| |
| * [[http://siliconzoo.org/nxp.html|Silicon Zoo]]: Here you can see the practical implementation of logic gates in silicon. |
| * [[http://www.righto.com/2016/12/die-photos-and-analysis-of_24.html|Die photos and analysis ICs]] |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ |
| |
~~PAGEBREAK~~ ~~CLEARFIX~~ | ~~PAGEBREAK~~ ~~CLEARFIX~~ |
==== Excercises ==== | ==== Exercises ==== |
| |
Details can be found in [[Introduction]] to Digital Systems | <panel type="info" title="Exercise 1.6.2. truth tables"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> |
| |
| Determine the value of the output $Y$ for the following logic using truth tables! |
| |
| <WRAP><well> |
| <imgcaption excer1|logic ciruits></imgcaption> \\ |
| |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&running=false&ctz=CQAgjCAMB0lwrFWBOeywA5kBZ4HYxJ0BmDAJhDIxEXkhoFMBaMMAKACUQmyztvs1HvABsA6hArZ6ZaIlmJi0MNjBoyI+MXhY8yYknhsAsiEHgxGemDEy5nbr34sxw1zfCUQVynN+LlVXVNbV19QzYAD0cRZxEIHmwKJh0zcGoADUgokDxXCgwJNMwQAE0cnljHRETk3mLM9jUEsDzuYmTkVw6oL3ojNXomcw8R2z6aNjVk1rEqpi6QKpleowB3blmzITBkKWpsjZY97c2T4YO2I93k8xY2i6grs9uhJ3Eno-eXR0gd22ePD+m3ywJ8h1+1B890s9AhMJBkMR8MWTB6THmPXhmOSy0+3DxjzhgPM6KqWMB5Nx-GWlJpzh8tKOjOci1pQA noborder}} |
| |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&running=false&ctz=CQAgjCAMB0lwrFWBOeywA5kBZ4HYxJ0BmDAJhDIxEXkhoFMBaMMAKACUQmyztvs1HvABsA6hArZ6ZaIlmJi0MNjBoyI+MXhY8yYknhsAsiEHgxGemDEy5nbr34sxw1zfCUQVynN+LlVXVNbV19QzYAD0cRZxEIHmwKJh0zcGoADUgokDxXCgwJNMwQAE0cnljHRETk3mLM9gB3bjA8syEwZClqbJaWbo7WwaZzPuHk8xZ20d62fq7JoSdxKHnHPlb8yE7bdZ5Nn2nLenHjrccdi7PkV2JkqqZ7tf7H56Yq0-3P1a-+83eVWeZyBD34n2+4OcPgh-RhzluIAh0Uq-AIjiSuX4-BKGTIDgO-COZFE3msXjIdnkfiUKjU3RCOmQegMMCMamcbTuyURTwoMhoNDYHNa7UeiJ+FFowvgznMHnlti89CMQA noborder}} |
| |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&running=false&ctz=CQAgjCAMB0lwrFWBOeywA5kBZ4HYxJ0BmDAJhDIxEXkhoFMBaMMAKACUQmyztvs1HvABsA6hArZ6ZaIlmJi0MNjBoyI+MXhY8yYknhsAsiGIUm5kCP6WKMuZ269bYMcPdvwlEBgfy5M2VVdU1tXX1DNgAPZxtuEQgebAsdEH5MEAANSBjreiY6EDwLbDx08GoATTyeeOFnFOcpSuz2AHduMGRSoTA8d0EoNk6WHvFm2yHc0Zcu9zJIPrEZybN7deHR-s8Fpfmt7mR3KztuK1zYuv4yA2SKDQrMrLInHj5Nj03JSn9KQKUKjUPTCOmQegMMCMagsO3OFmO8KgPno0LQSLOpwuv3AcDx+NW9GxLBWtTIST8ZiEoie1AALgAnACWAGc6QBDOkMAA6LO53IAdgBzTkMNhAA noborder}} |
| |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&running=false&ctz=CQAgjCAMB0lwrFWBOeywA5kBZ4HYxJ0BmDAJhDIxEXkhoFMBaMMAKACUQmyztvs1HvABsA6hAoZ6ZaIlmJi0MNjBoyI+MXhY8yYknhsAsuDH1BUKws7de-FmOFOwYySGwy5lb0pVrkDS0dZD0DGCMADzsRBxEIHmwKJh0PcGoADUg2aOwHTBoXRH4CgE0cmIcyRETk3jSCjPYAd24wQPE2vCdLbNaWDqZLHj5OvrtRxztIIVcoNn6wbranMhmV+eieWJA8OyTwC3SQDLJbEZLV0TNwSkoveV9lVXVNbV19Q3P7DyFqsUs7kIPkeimeASC71CnwiFW2-GIyH2FAOJUyxDYAEkui4XFQNvQIjQsTjfm18b1DMS1AYmDt6HNCWl6EZ+j85nTLvNFvippyCQsJvxhksAdRxvymMRkqxktLuW0wHKZUqxoKWKqhrNllqFSwKbNVb11bKyRqKPKJab5fzLWwgA noborder}} |
| </well></WRAP> |
| |
| </WRAP></WRAP></panel> |
| |
| |
| <panel type="info" title="Exercise 1.6.3. timing diagram"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> |
| |
| Complete the timing diagram for input signals $X0$ and $X1$: |
| |
| <WRAP center> |
| <imgcaption excer2|Timing Diagram></imgcaption> |
| {{drawio>exctimingdiagram.svg}} |
| </WRAP> |
| |
| <button size="xs" type="link" collapse="Solution_1_6_3_1_Solution_path">{{icon>eye}} Solution</button><collapse id="Solution_1_6_3_1_Solution_path" collapsed="true"> |
| |
| {{url>https://wiki.mexle.org/_export/revealjs/introduction_to_digital_systems/aufgabe_1.6.3_mit_rechnung?theme=white&fade=fade&controls=1&show_progress_bar=1&build_all_lists=1&show_image_borders=0&horizontal_slide_level=2&enlarge_vertical_slide_headers=0#/ 400,400}} |
| |
| Alternatively see [[:introduction_to_digital_systems:aufgabe_1.6.3_mit_rechnung|here]]. |
| |
| </collapse> |
| |
| |
| </WRAP></WRAP></panel> |
| |
| <panel type="info" title="Exercise 1.6.4. NAND-based gates"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> |
| |
| Realize the logic functions of NOT, AND, OR, NOR, XOR and XNOR exclusively with NAND gates. |
| |
| |
| <button size="xs" type="link" collapse="Solution_1_6_4_1_Solution_path">{{icon>eye}} Solution </button><collapse id="Solution_1_6_4_1_Solution_path" collapsed="true"> |
| |
| **__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 vise versa. |
| |
| <WRAP> |
| <imgcaption Ex_1_6_4_1 | NOT based on NAND> |
| </imgcaption> \\ |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BWKsBMBOAHANjQFixmihtgOwa4gKRUi4DMVApgLRhgBQA7iCqSuFJZe-cESjcRAsOL4CUkDBIAyUsdPEyBNGgDMAhgBsAzk1qQOAWRD0K6uriVaovaAg5gEEOfduVnNAJI7tb0BDYKDkr0kYFuHKrE0ZHOMTouBiZmSBYAkrwkETRhyekwwRwAHuCE4NR0GNIIjJQolAByAPIAKgA6xgDm+gAuTP1cAJbDABb97QCC7QAi-UOjxlU1aCJK6IzEEK0dPasjTBxAA noborder}} |
| </WRAP> |
| |
| **__AND__** |
| |
| With the realization of the NOT gate an AND gate is also simple: just put the NOT after a NAND. |
| |
| <WRAP> |
| <imgcaption Ex_1_6_4_2 | AND based on NAND> |
| </imgcaption> \\ |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BWKsBMBmFA2dmEHYBOMPFAlPEBSSkAFjUoFMBaMMAKABkQUFMfIADnBkBw6hABmAQwA2AZ0Y1I7ALJ0w-MKNq1h2lFB7QE7MAgi8totGmuHqhpKfV3ht-rvd2jKE1x5BdxQJGxCjahkFJSQVcwgPEUNaTSTfI1MAdxBEgxyfEPF2bNy8flzRFW4rcDK04n5qSLlFZTMqQO9yzC706lNqoJyEQzy0EaMpFpiodgAPcEFRtAI6PCQwWmSeWhAAQQA5ABEAHXkAc2kAF0YzzIBLK4ALM4PD04vrxnl5xYZSQwoQQUUhIXYoXbvM6XG7sIA noborder}} |
| </WRAP> |
| |
| **__OR__** |
| |
| With the realization of the NOT gate an AND gate is also simple: just put the NOT after a NAND. |
| |
| <WRAP> |
| <imgcaption Ex_1_6_4_3 | OR based on NAND> |
| </imgcaption> \\ |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BWKsDMCBMAOAbNymwAWBTTQzAThAUmpEJWoFMBaMMAKABkR0Fte+cBXSDMUcCABmAQwA2AZyZ1IHALL0wAsAHYBhcuD0T00BBzAIIKFNuOEtRgbVFJzG2+Jv7D3k2e5eUhAUdFowERCwiVpZRWUkVUsIPgEwr1sxEwlzAHdefizU3nRCKA584ojRYvTyniqDYVEiMtpY+SUVQKwvDGaQ-vDpToTygA9wHBAKcUJsMrBICDLSkAB5ACUAHQUAcxkAFyZd3IBLQ4ALXYA5AEEbgBFdg+OFDkmwTEZ0SKsqX5IVZlLYvI4nBQACgUZwAtgAHORnKRnJgAE1OF2uCnuTwAlBUCtosETwE1VJVCq1SVp2hYrDSmn5qS46HkQplqcy8OV8szIn46kkGb0OQJPGL6Lw2fSasF5mUJQrsm4PlNGIRougdKJNRreCCdvtwT15ZhwpFyO1JHEuolTXNDNV6IZrbaxqoPNg5gsXT62rwAkA noborder}} |
| </WRAP> |
| |
| **__NOR__** |
| |
| Again the NOR gate can be derived from the NOT gate an OR gate. |
| |
| <WRAP> |
| <imgcaption Ex_1_6_4_4 | NOR based on NAND> |
| </imgcaption> \\ |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BWKsBMB2ALADjCgzFpAggJzYkBsFICkNIGeNApgLRhgBQAMiCihj6Qs4EiiEi6EAGYBDADYBnZvUicAsgwqCwaahkrg9UPtAScwCCHkg7jBO9Trik5zRjDU8efYe9PTc14ULBE8FCkxEHC6WJA5JRUkNUsIfkEIsNsJE3E6cwB3PgEc9OLBNSKysCiyzKgecvAMHSiwFpM6BOVVRpCwhHEa8TxBkxkFHuTOAA9wLGoSEWwhyAgMwQA5AHkAJQAdRQBzWQAXZkOCgEtTgAtDzYBBTYARQ5PzxVn5phQohB8fBISA2IB2B2OZwuigAFIorgBbAAO8iu0iuzAAJpcbvdFE9XgBKThVEq4ETVDqVJrtDJkiixCxWGkdGw6Kl8eiFaLZWk8nQMhpFNmiEbZepqOZgLBMDARPhYEgMfAMPhbPbvKF9UIMQii3VxCaJXrBHUtETDBjYTrxSZJBruTxaQQGfTaXJmJnWLCOZ1GAJ5Ggk6I+-UOf1CkO+8OeRmWX5m90eN0VTn5JnOHX+BhO7MZEzmIA noborder}} |
| </WRAP> |
| |
| **__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}$, which is only $1$ for both inputs are $0$. |
| - This 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 build based on NAND gates. This is shown in <imgref Ex_1_6_4_5 >. |
| |
| <WRAP> |
| <imgcaption Ex_1_6_4_5 | XOR based on NAND> |
| </imgcaption> \\ |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgzCAMB0l3BWKsBMB2ALADgIwrFpAggJzYkBsFICkNIGECApgLQ44BQAMiPijRR0cJAQiFRJAMwCGAGwDOzepB58E1bFhAiBWyThCzFypKoAeOrJswNCDNGgZ8MIABoB5AEoAdBQHMZABdmPwB3AEsggAs-ADkAQTiAET9AkIVOSxFDHAoSPkodND0Xd2804OY1FA1wcT4UVzAGujpjJRUakvAJFCbetp0jeU6zThwECBQsbQw4cAo5hboBOgROML5Z8CxXdAECV1Utmbm89U0Lk8uGC9rqFrXNvh6j18OJG4PB7e0wL4vM71AQPEFQCa0P7gMCPJYw6irSQbLaw5Z0NG7Y4vTFPRb-WEQgCyDGw+LsGPhq2gG0mEFx8IwZMxSPWkOakH2kH+ez43MkaxoajAnJ0oluugMIxMXV4Iv2AzB-WO0lGpmJWL552oQm01I22SwBRQJCYRsKmjKnl8ASqfgAFJEYn4kqkFDIAHYAE3iFVtGQAlJDDGCEGhHqKw9QQ8jg7cKPz5SAE9oY2zJoYk6RDg1s8NBbSEJnc+L5utxWmhac6hR7jWVkC6gheaGqXGkxginjO9G+LGM+CewwFkPKyi7tQpldJ4CthgLhptTRWnGi2ImTQEzQN2O4xgKK4EBu19vXLuB-PJ1v94et+eixPBHMD0-87HUZHw+BI7ybkmExioophCqINAB4J5n+JY5mIv44rmordkUUF6F2DT6DcN7LnoL4aG0LxYVODC4TMIE0Hgp7kWIhI3CeR6HhRxDPHOC6Mgsi5kWWm7ojQ4qYSORRceI+FzuxEiXoIIl8ACknSQItaIkCMkKfG1yNle2hghh6l2P8oraR+h59DJwlkVmEhZqKqgknhlF5vRAo0pwQA noborder}} |
| </WRAP> |
| |
| 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 build by one NAND-, one OR- and one AND-gate. This circuitry needs also 6 NAND gates. \\The cicuitry is not shown. |
| * The circuity with the least NAND gates is shown in <imgref Ex_1_6_4_6 > |
| |
| <WRAP> |
| <imgcaption Ex_1_6_4_6 | XOR based on NAND, alternatives> |
| </imgcaption> \\ |
| {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgzCAMB0l3BWKsBMB2ALADgIwrFpAggJzYkBsFICkNIGECApgLQ44BQAHiDlhhBYsICmggkcDECkEANAPIAlADoBnAOYBDAC7N1ACgByAQSMARddr1r1AdwCWOgBYB7AK471AEw8AjABt9NSMFABU1AEoePiwScBx4jHRwFBRpWRBFVU1dYIMtAL0AJwA7XQcAN2ZogFkGSnAKEVJ0sGaoGWgEThwEKQxsJpEMRvaRKXSkHr6pcfABBhxqAkFJ+hn+4fAEdIxlnfT1uh6AGRlhcEG+EjbruikAM0K1ZnpITjtDvgo6MF2+Cg6B8vv8jmgVgCUAcQQwKGsId8cIjYRh4T8-gDlsDOOd8EdrokCYJgSBngFXu9cTIENQOEdbnw8J0ni83kgPrMadQgX9IIJeXwZJ1NpNaTIwG1+RKjsLpr0tmBpdDIekVUKpjRPtyZBg6ChxWkSdqDTzICJTTd0pzFdK8JijkCNRsFVJ+kcOrSHh11vKuWi1p7mcsJsKTtqlQK4OBleaoBHlZlIzL4193T8WsHfqmaFnM+DqLD8XxrsXZDivmW9TryznLUSdfS6+Km8mm7C26XJSXjaC7dc2ygRB96l6MzRGSHOihuq6LiJ5mB2ttfVq8ZcwJPGZvrZ1yZSOdr9qqGEMwTnjwtBIMF4sO8vFx15h2n9nH8OI6+F0+USaN6WN2zIt-0ERd7j-BdESHBdGWAmC2ifWCjzPAEbyaCtT0g6g0NWeMgA noborder}} |
| </WRAP> |
| |
| |
| |
| </collapse> |
| |
| </WRAP></WRAP></panel> |
| |
| <panel type="info" title="Exercise 1.6.5. NOR-based gates"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> |
| |
| Realize the logic functions of NOT, OR, AND, NAND, XOR and XNOR exclusively with NOR gates. |
| </WRAP></WRAP></panel> |
| |
| <panel type="info" title="Exercise 1.6.6. simplification of logic expressions"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> |
| |
| Simplify the following expressions with boolean algebra. Write down the rule for each step! |
| |
| - $Y = (/X0*/X1*/X2) $$+ (X0*X1*/X2) $$+ (/X0*/X1*X2) $$+ (X0*X1*X2)$ \\ |
| - $Y = (X0*X1*X2*X3) $$+ (X0*X1*X2*/X3) $$ + (X0*X1*/X2*/X3) $$+ (/X0*X1*X2*X3)$ \\ |
| - $Y = (X0*X1*X2*X3) $$+(/X0*X1*X2*X3) $$+ (/X0*X1*/X2*X3)$ \\ |
| - $Y = (/X0*X1*/X2*/X3) $$+ (/X0*X1*X2*X3) $$+ (X0*/X1*/X2*X3) $$+ (/X0*/X1*/X2*/X3)$\\ |
| - $Y = (/X0*/X1*/X2*/X3) $$+ (/X0*X1*/X2*/X3) $$+ (/X0*/X1*/X2*X3) $$+ (/X0*X1*/X2*X3)$\\ |
| |
| |
| <button size="xs" type="link" collapse="Solution_1_6_6_1_Solution_path">{{icon>eye}} Solution for 1. </button><collapse id="Solution_1_6_6_1_Solution_path" collapsed="true"> |
| |
| Often the formula can be easier analysed with in the more compact terminology. \\ |
| 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$ |
| |
| $Y = \color{blue}{\overline{X_0}}\;\color{green}{\overline{X_1}}\;\color{red}{\overline{X_2}}$$ + \color{cornflowerblue}{X_0 }\;\color{yellowgreen}{ {X_1}}\;\color{red}{\overline{X_2}}$$ + \color{blue}{\overline{X_0}}\;\color{green}{\overline{X_1}}\;\color{salmon}{ {X_2}}$$ + \color{cornflowerblue}{X_0 }\;\color{yellowgreen}{ {X_1}}\;\color{salmon}{ {X_2}}$ |
| |
| With the **commutative law** switching term 2 and term 3 is possible: |
| |
| $Y = \color{blue}{\overline{X_0}}\;\color{green}{\overline{X_1}}\;\color{red}{\overline{X_2}} $$ + \color{blue}{\overline{X_0}}\;\color{green}{\overline{X_1}}\;\color{salmon}{ {X_2}}$$ + \color{cornflowerblue}{X_0 }\;\color{yellowgreen}{ {X_1}}\;\color{red}{\overline{X_2}} $$ + \color{cornflowerblue}{X_0 }\;\color{yellowgreen}{ {X_1}}\;\color{salmon}{ {X_2}}\\ |
| $ |
| |
| Based on the **distributive law** the parts $\color{blue}{\overline{X_0}}\;\color{green}{\overline{X_1}}$ and $\color{cornflowerblue}{X_0 }\;\color{yellowgreen}{ {X_1}}$ can be placed outside the brackets: |
| |
| $Y = \color{blue}{\overline{X_0}}\;\color{green}{\overline{X_1}}\;(\color{red}{\overline{X_2}} + \color{salmon}{ {X_2}})$$ + \color{cornflowerblue}{X_0 }\;\color{yellowgreen}{ {X_1}}\;(\color{red}{\overline{X_2}} + \color{salmon}{ {X_2}})$ |
| |
| The rule of the **complementary element** tells us that $a +\overline{a} = 1$ and based on the **neutral element** $a\cdot 1 = a$: |
| |
| $Y = \color{blue}{\overline{X_0}}\;\color{green}{\overline{X_1}}\cdot 1$$ + \color{cornflowerblue}{X_0 }\;\color{yellowgreen}{ {X_1}}\cdot 1$ |
| \\ \\ ÷ |
| |
| $Y = \color{blue}{\overline{X_0}}\;\color{green}{\overline{X_1}}$$ + \color{cornflowerblue}{X_0 }\;\color{yellowgreen}{ {X_1}}\\ \\ |
| $ |
| |
| 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}}\;\color{green}{\overline{X_1}} = 1$ or $\color{cornflowerblue}{X_0 }\;\color{yellowgreen}{ {X_1}} = 1$. \\ |
| Therefore, $Y$ is only $1$ in two cases: |
| * $\color{cornflowerblue}{X_0 }=0$ and $\;\color{yellowgreen}{ {X_1}} = 0$ or |
| * $\color{cornflowerblue}{X_0 }=1$ and $\;\color{yellowgreen}{ {X_1}} = 1$ |
| This is the definition of the $XNOR$. So the final step would be: |
| |
| $Y = \overline{\color{cornflowerblue}{X_0} \text{#} \color{yellowgreen}{X_1} }$ |
| |
| </collapse> |
| <button size="xs" type="link" collapse="Solution_1_6_6_1_final_result">{{icon>eye}} Final result for 1. </button><collapse id="Solution_1_6_6_1_final_result" collapsed="true"> |
| \begin{align*} |
| Y = \overline{{X_0} \text{#} {X_1} } |
| \end{align*} |
| </collapse> |
| \\ \\ |
| |
| |
| <button size="xs" type="link" collapse="Solution_1_6_6_3_Solution_path">{{icon>eye}} Solution for 3. </button><collapse id="Solution_1_6_6_3_Solution_path" collapsed="true"> |
| |
| Again, the formula can be easier analysed with in the more compact terminology. \\ |
| 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{cornflowerblue}{X_0 }\;\color{yellowgreen}{ {X_1}}\;\color{salmon}{ {X_2}}\;\color{brown}{\overline{X_3}} |
| + \color{blue}{\overline{X_0}}\;\color{yellowgreen}{ {X_1}}\;\color{salmon}{ {X_2}}\;\color{brown}{\overline{X_3}} |
| + \color{blue}{\overline{X_0}}\;\color{yellowgreen}{ {X_1}}\;\color{red}{\overline{X_2}}\;\color{brown}{\overline{X_3}}\\ |
| \end{align*} |
| |
| With the **idempotence** the term 2 can be doubled: |
| \begin{align*} |
| Y &= \color{cornflowerblue}{X_0 }\;\color{yellowgreen}{ {X_1}}\;\color{salmon}{ {X_2}}\;\color{brown}{\overline{X_3}} |
| + \color{blue}{\overline{X_0}}\;\color{yellowgreen}{ {X_1}}\;\color{salmon}{ {X_2}}\;\color{brown}{\overline{X_3}} |
| + \color{blue}{\overline{X_0}}\;\color{yellowgreen}{ {X_1}}\;\color{salmon}{ {X_2}}\;\color{brown}{\overline{X_3}} |
| + \color{blue}{\overline{X_0}}\;\color{yellowgreen}{ {X_1}}\;\color{red}{\overline{X_2}}\;\color{brown}{\overline{X_3}}\\ |
| \end{align*} |
| |
| The **commutative law** enables to rearrange within the terms: |
| \begin{align*} |
| Y &= \color{yellowgreen}{ {X_1}}\;\color{salmon}{ {X_2}}\;\color{brown}{\overline{X_3}}\;\color{cornflowerblue}{X_0 } |
| + \color{yellowgreen}{ {X_1}}\;\color{salmon}{ {X_2}}\;\color{brown}{\overline{X_3}}\;\color{blue}{\overline{X_0}} |
| + \color{blue}{\overline{X_0}}\;\color{yellowgreen}{ {X_1}}\;\color{brown}{\overline{X_3}}\;\color{salmon}{ {X_2}} |
| + \color{blue}{\overline{X_0}}\;\color{yellowgreen}{ {X_1}}\;\color{brown}{\overline{X_3}}\;\color{red}{\overline{X_2}}\\ |
| \end{align*} |
| |
| Based on the **distributive law** the parts $\color{yellowgreen}{ {X_1}}\;\color{salmon}{ {X_2}}\;\color{brown}{\overline{X_2}}$ and $\color{blue}{\overline{X_0}}\;\color{yellowgreen}{ {X_1}}\;\color{brown}{\overline{X_2}}$ to place outside the brackets: |
| |
| \begin{align*} |
| Y &= \color{yellowgreen}{ {X_1}}\;\color{salmon}{ {X_2}}\;\color{brown}{\overline{X_3}}\;(\color{cornflowerblue}{X_0 } + \color{blue}{\overline{X_0}}) |
| + \color{blue}{\overline{X_0}}\;\color{yellowgreen}{ {X_1}}\;\color{brown}{\overline{X_3}}\;(\color{salmon}{ {X_2}} + \color{red}{\overline{X_2}})\\ |
| \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$: |
| |
| \begin{align*} |
| Y &= \color{yellowgreen}{ {X_1}}\;\color{salmon}{ {X_2}}\;\color{brown}{\overline{X_3}}\cdot 1 |
| + \color{blue}{\overline{X_0}}\;\color{yellowgreen}{ {X_1}}\;\color{brown}{\overline{X_3}}\cdot 1\\ \\ |
| |
| Y &= \color{yellowgreen}{ {X_1}}\;\color{salmon}{ {X_2}}\;\color{brown}{\overline{X_3}} |
| + \color{blue}{\overline{X_0}}\;\color{yellowgreen}{ {X_1}}\;\color{brown}{\overline{X_3}}\\ |
| |
| \end{align*} |
| |
| Again, the **commutative law** can be used: |
| \begin{align*} |
| Y = \color{yellowgreen}{ {X_1}}\;\color{brown}{\overline{X_3}}\;\color{salmon}{ {X_2}} |
| + \color{yellowgreen}{ {X_1}}\;\color{brown}{\overline{X_3}}\;\color{blue}{\overline{X_0}}\\ |
| \end{align*} |
| |
| And the **distributive law**: |
| \begin{align*} |
| Y = \color{yellowgreen}{ {X_1}}\;\color{brown}{\overline{X_3}}\;(\color{salmon}{ {X_2}} + \color{blue}{\overline{X_0}})\\ |
| \end{align*} |
| |
| |
| </collapse> |
| <button size="xs" type="link" collapse="Solution_1_6_6_3_final_result">{{icon>eye}} Final result for 3. </button><collapse id="Solution_1_6_6_3_final_result" collapsed="true"> |
| \begin{align*} |
| Y = X_1\;\overline{X_3} (X_2 + \overline{X_0})\\ |
| \end{align*} |
| </collapse> |
| |
| </WRAP></WRAP></panel> |
| |
| |
| <panel type="info" title="Exercise 1.6.7. only using NAND"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> |
| |
| Rewrite the following expressions using only NAND. Check the result for equality using truth tables. |
| |
| - $Y = X0 + X1*/X2$ |
| - $Y = /(/X0*X1)$ |
| - $Y = X0*X1 + /X2$ |
| - $Y = /X0*/X1$ |
| - $Y = /(/(X0+X1) + X0*X1)$ |
| - $Y = /(/X0+X1+/X2) + /(X0+/X1+X2)$ |
| |
| <button size="xs" type="link" collapse="Solution_1_6_7_5_Solution_path">{{icon>eye}} Solution for 5. </button><collapse id="Solution_1_6_7_5_Solution_path" collapsed="true"> |
| |
| \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 next steps is to do substitutions with 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> |
| <imgcaption Solution_1_6_7_5 | Truth Table> |
| </imgcaption> |
| {{drawio>Solution1675tt.svg}} |
| </WRAP> |
| |
| </collapse> |
| |
| </WRAP></WRAP></panel> |
| |
| <panel type="info" title="Exercise 1.6.8. step by step example for logic simplification using boolean rules"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> |
| |
| Hints for the clip: |
| * 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 2 starts at 17:17 |
| * Example 3 starts at 21:00 |
| * Example 4 starts at 28:27 |
| * Example 5-8 start at 32:33 |
| |
| {{youtube>59BbncMjL8I}} |
| |
| </WRAP></WRAP></panel> |
| |
| |
| |
| <panel type="info" title="Exercise 1.6.9. XOR in Cryptography"> <WRAP group><WRAP column 2%>{{fa>pencil?32}}</WRAP><WRAP column 92%> |
| |
| In the following EXCEL file an example of symmetric encryption can be found: {{introduction_to_digital_systems:xor_in_cryptography.xlsx}} |
| |
| * Try to understand {{wp>XOR_cipher}} with this example. |
| * Which advantages and disadvantages does symmetric encryption have? |
| </WRAP></WRAP></panel> |
| |
| |