Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
introduction_to_digital_systems:sequential_logic [2022/12/09 15:56] mexleadmin |
introduction_to_digital_systems:sequential_logic [2023/09/19 23:49] (aktuell) mexleadmin |
||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== 6. Sequential Logic ====== | + | ====== 6 Sequential Logic ====== |
"I Know What You Did Last Cycle" | "I Know What You Did Last Cycle" | ||
Zeile 5: | Zeile 5: | ||
===== 6.1 First Terminology ===== | ===== 6.1 First Terminology ===== | ||
- | The most important term for the upcoming topics is the word **state**. But what is a state? \\ It is a unique situation, where the possible next steps (= possible next states), the inner behavior or the outputs are distinguishable from other situations. | + | The most important term for the upcoming topics is the word **state**. But what is a state? \\ It is a unique situation, where the possible next steps (= possible next states), the inner behavior, or the outputs are distinguishable from other situations. |
- | Here some practical examples: | + | Here are some practical examples: |
* Being happy or being sad, are two different states, since the inner behavior is different (this least often also to a different output). | * Being happy or being sad, are two different states, since the inner behavior is different (this least often also to a different output). | ||
- | * Similarly, an empty memory (or harddrive) is in a different state compared to a filled one. | + | * Similarly, an empty memory (or hard drive) is in a different state compared to a filled one. |
- | * A traffic light showing green has a output distinguishable from red, or yellow. | + | * A traffic light showing green has an output distinguishable from red, or yellow. |
- | Sequential logic is used to describe logic cicruits which show internal states (" | + | Sequential logic is used to describe logic circuits that show internal states (" |
The following terminology is used in the upcoming explanations: | The following terminology is used in the upcoming explanations: | ||
- | * The **input vector** $\vec{X}$ represents the $k$ inputs $X_0 ... X_{k-1}$ | + | * The **input vector** $\vec{X}$ represents the $k$ inputs $X_0 ... X_{k-1}$. |
- | * The **output vector** $\vec{Y}$ represents the $l$ outputs $Y_0 ... Y_{l-1}$ | + | * The **output vector** $\vec{Y}$ represents the $l$ outputs $Y_0 ... Y_{l-1}$. |
- | * The **state vector** $\vec{Z}$ represents the $m$ inputs $Z_0 ... Z_{m-1}$ | + | * The **state vector** $\vec{Z}$ represents the $m$ inputs $Z_0 ... Z_{m-1}$. |
- | * The sign $(n)$ or $n$ marking the current point in time and therefore e.g. the current state $Z_0(n)$ | + | * The sign $(n)$ or $n$ marking the current point in time and therefore e.g. the current state $Z_0(n)$. |
- | * The sign $(n+1)$ or $n+1$ marking the next upcomming | + | * The sign $(n+1)$ or $n+1$ marking the next upcoming |
- | * Sequential logic circuits are also called **Finite State Machines** (FSM) or sometimes also shortened to " | + | * Sequential logic circuits are also called **Finite State Machines** (FSM) or sometimes also shortened to " |
The <imgref pic04> shows the different terms in an abstract diagram. The " | The <imgref pic04> shows the different terms in an abstract diagram. The " | ||
Zeile 24: | Zeile 24: | ||
< | < | ||
- | The principle interior of the blackbox | + | The principle interior of the black box in <imgref pic04> was already shown in one practical application in the [[: |
< | < | ||
Zeile 31: | Zeile 31: | ||
<imgref pic06> depicts a state machine. | <imgref pic06> depicts a state machine. | ||
- | * What happens, when $X$ is changed? On which edge the change is triggered? | + | * What happens, when $X$ is changed? |
* Write down how many components each vector $\vec{X}$ and $\vec{Y}$ has. | * Write down how many components each vector $\vec{X}$ and $\vec{Y}$ has. | ||
* How many bits (= flip flops) might the state vector $\vec{Z}$ need? | * How many bits (= flip flops) might the state vector $\vec{Z}$ need? | ||
Zeile 40: | Zeile 40: | ||
</ | </ | ||
- | One simple example of a sequential logic is shown in <imgref pic09>. There, the combnatorial | + | One simple example of sequential logic is shown in <imgref pic09>. There, the combinatorial |
< | < | ||
Zeile 47: | Zeile 47: | ||
===== 6.2 Classical State Machine Types ===== | ===== 6.2 Classical State Machine Types ===== | ||
- | The up-counter in the previous sub-chapter was able to count from $0$ to $3$. But what can we do in order to count differently, | + | The up-counter in the previous sub-chapter was able to count from $0$ to $3$. But what can we do to count differently, |
==== 6.2.1 Moore Machine ==== | ==== 6.2.1 Moore Machine ==== | ||
- | The first idea might be to use what we already have: an up-counter, which faciliate | + | The first idea might be to use what we already have: an up-counter, which facilitates |
- | The wanted new state machine needs 3 bits for the output, since the binary representation of our outputs | + | The wanted new state machine needs 3 bits for the output, since the binary representation of our outputs |
- | An simple idea is to take the 2-bit up-counter and add an combinatorial logic in behind. This logic shall convert the 2-bit up-counter output $00_2$ into $001_2$, the $01_2$ into $010_2$, $10_2$ into $011_2$ and $11_2$ into $101_2$. This can be logic can be created by: | + | A simple idea is to take the 2-bit up-counter and add a combinatorial logic in behind |
* writing down the truth table | * writing down the truth table | ||
* putting the values into a Karnaugh map | * putting the values into a Karnaugh map | ||
- | * extracting the formula with view onto the implicants | + | * extracting the formula with a view onto the implicants |
* generating the circuit with gates | * generating the circuit with gates | ||
Zeile 65: | Zeile 65: | ||
{{url> | {{url> | ||
- | This resembles a so called **Moore Machine** | + | This resembles a so-called **Moore Machine**. |
<WRAP column 100%> | <WRAP column 100%> | ||
<panel type=" | <panel type=" | ||
- | A state machine is a **Moore Machine**, when the output values $\vec{Y}$ | + | A state machine is a **Moore Machine**when the output values $\vec{Y}$ |
- | * The input circuit, which process | + | * The input circuit, which processes |
* The output circuit, which transform the state values $\vec{Z}(n)$ into the output values $\vec{Y}(n)$. | * The output circuit, which transform the state values $\vec{Z}(n)$ into the output values $\vec{Y}(n)$. | ||
- | The properties of a moore machine are: | + | The properties of a Moore machine are: |
- | * The number of flip-flops is only given by number of states $m$. | + | * The number of flip-flops is only given by the number of states $m$. |
- | * The output only changes when an edge on the clock input happen. The moore machine is a **synchronous state machine**. | + | * The output only changes when an edge on the clock input happens. The Moore machine is a **synchronous state machine**. |
- | * The moore machine usually | + | * The Moore machine usually |
</ | </ | ||
Zeile 84: | Zeile 84: | ||
==== 6.2.2 Mealy Machine ==== | ==== 6.2.2 Mealy Machine ==== | ||
- | When looking | + | When looking |
- | With this information the state machine in <imgref pic21> can be simplified by using the outputs of the input circuit for $Y_0$ and $Y_1$. This is shown in <imgref pic22>. | + | With this information, the state machine in <imgref pic21> can be simplified by using the outputs of the input circuit for $Y_0$ and $Y_1$. This is shown in <imgref pic22>. |
< | < | ||
Zeile 94: | Zeile 94: | ||
<panel type=" | <panel type=" | ||
- | A state machine is a **Mealy Machine**, when the output values $\vec{Y}$ | + | A state machine is a **Mealy Machine**when the output values $\vec{Y}$ |
- | * The input circuit, which process | + | * The input circuit, which processes |
- | * The output circuit, which transform | + | * The output circuit, which transforms |
The properties of a mealy machine are: | The properties of a mealy machine are: | ||
- | * The number of flip-flops is only given by number of states $m$. | + | * The number of flip-flops is only given by the number of states $m$. |
- | * The output **not** only changes when an edge on the clock input happen: It is also dependent on the input $\vec{X}(n)$. The mealy machine is an **__asynchronous__ state machine**. | + | * The output **not** only changes when an edge on the clock input happens: It is also dependent on the input $\vec{X}(n)$. The mealy machine is an **__asynchronous__ state machine**. |
- | * The mealy machine usually | + | * The mealy machine usually |
* The mealy machine has to be designed properly in order not to get invalid outputs. | * The mealy machine has to be designed properly in order not to get invalid outputs. | ||
Zeile 121: | Zeile 121: | ||
<panel type=" | <panel type=" | ||
- | A state machine is a **Medvedev Machine**, when the output values $\vec{Y}$ | + | A state machine is a **Medvedev Machine**when the output values $\vec{Y}$ |
- | The properties of a medvedev | + | The properties of a Medvedev |
- | * The number of flip-flops is given by number of outputs $l$. | + | * The number of flip-flops is given by the number of outputs $l$. |
* The output only changes when an edge on the clock input happens: The mealy machine is an **__synchronous__ state machine**. | * The output only changes when an edge on the clock input happens: The mealy machine is an **__synchronous__ state machine**. | ||
- | * The medvedev | + | * The Medvedev |
</ | </ | ||
Zeile 147: | Zeile 147: | ||
==== 6.3.1 Motivation ==== | ==== 6.3.1 Motivation ==== | ||
- | The diagrams of different states are well known from physics for example the state diagram (or better: phase diagram) of water, where its three states are: solid ice, liquid water and gaseous steam. The possible state transitions are due to temperature increase or decrease. | + | The diagrams of different states are well known from physics for example the state diagram (or better: phase diagram) of water, where its three states are: solid ice, liquid water, and gaseous steam. The possible state transitions are due to temperature increase or decrease. |
- | In <imgref pic01> image (1) the states of water are shown on the temperature axis. When only the state transistions | + | In <imgref pic01> image (1) the states of water are shown on the temperature axis. When only the state transitions |
< | < | ||
For matter not only the dimension " | For matter not only the dimension " | ||
- | By this, another variable is available and more transistions. These can be drawn into the state transition diagram (<imgref pic02> image (2)). | + | By this, another variable is available and more transitions. These can be drawn into the state transition diagram (<imgref pic02> image (2)). |
< | < | ||
Zeile 160: | Zeile 160: | ||
==== 6.3.2 Simple logic Example ==== | ==== 6.3.2 Simple logic Example ==== | ||
- | In German, often one has to pay for entering the toilet. An example of such a entrance control system is shown in <imgref pic03> | + | In Germany, often one has to pay for entering the toilet. An example of such an entrance control system is shown in <imgref pic03> |
Once paid, the turnstile will release and one can enter. Once the turnstile was pushed the entrance is closed again. | Once paid, the turnstile will release and one can enter. Once the turnstile was pushed the entrance is closed again. | ||
Zeile 166: | Zeile 166: | ||
The <imgref pic04> the state transition diagram is drawn. | The <imgref pic04> the state transition diagram is drawn. | ||
- | * The two states are that (1) the turnstile is opened and one is able to go through and (2) the turnstile is closed and one cannot enter anymore. | + | * The two states are that (1) the turnstile is opened and one can go through and (2) the turnstile is closed and one cannot enter anymore. |
* The transitions are given by the done actions: one can either insert a coin or push on the turnstile. | * The transitions are given by the done actions: one can either insert a coin or push on the turnstile. | ||
Important here are some additional considerations: | Important here are some additional considerations: | ||
- | * For the state transition diagram one has to **look for all possible transitions**. So, also pushing a closed turnstile or inserting more coins have to taken into account. | + | * For the state transition diagram one has to **look for all possible transitions**. So, also pushing a closed turnstile or inserting more coins have to take into account. |
- | * A state transition diagram is not complete without a **legend** and without an **beginning/ | + | * A state transition diagram is not complete without a **legend** and without an **beginning/ |
< | < | ||
- | Out of this state transition diagram one can create a table-like representation, | + | Out of this state transition diagram, one can create a table-like representation, |
- | < | + | < |
- | the inputs, outputs and states have to be encoded into binary, | + | the inputs, outputs, and states have to be encoded into binary, to investigate this table a bit more. How the binary value is connected to the outputs does not matter. We will choose the following coding: |
* Encoding of the states: turnstile closed ≙ $Z=0$, turnstile opened ≙ $Z=1$, | * Encoding of the states: turnstile closed ≙ $Z=0$, turnstile opened ≙ $Z=1$, | ||
* Encoding of the inputs: no coin inserted ≙ $Xc=0$, coin inserted ≙ $Xc=1$, turnstile not pushed ≙ $Xp=0$, turnstile pushed ≙ $Xp=1$, | * Encoding of the inputs: no coin inserted ≙ $Xc=0$, coin inserted ≙ $Xc=1$, turnstile not pushed ≙ $Xp=0$, turnstile pushed ≙ $Xp=1$, | ||
Zeile 190: | Zeile 190: | ||
Interestingly, | Interestingly, | ||
- | When looking deeper | + | When looking deeper |
==== 6.3.3 First Adaption for Up-Counter==== | ==== 6.3.3 First Adaption for Up-Counter==== | ||
- | In the previous sub-chapter (6.2) we had a look onto different implementations of an up counter and on this chapter the way to represent a state machine via a state transition diagram. So one question is: how does these up counter | + | In the previous sub-chapter (6.2) we had a look at different implementations of an up counter and in this chapter the way to represent a state machine via a state transition diagram. So one question is: what do these up-counters |
- | The Answer ist quite simple: there are 4 states, so 4 " | + | The answer is quite simple: there are 4 states, so 4 " |
- | With a deeper look onto is: This is therefore in particular a Medvedev machine! | + | With a deeper look at it: This is therefore in particular a Medvedev machine! |
In <imgref pic15> both types of state machines are shown. | In <imgref pic15> both types of state machines are shown. | ||
- | * In the Moore Machine | + | * In the Moore machine |
- | * In the Medvedev | + | * In the Medvedev |
- | < | + | < |
{{drawio> | {{drawio> | ||
<panel type=" | <panel type=" | ||
- | The shown state transistion | + | The shown state transition |
- Click on the menu '' | - Click on the menu '' | ||
- | - Here one either can add new states with a right click, or - more easier - go to the menu '' | + | - Here one either can add new states with a right click, or - easier - go to the menu '' |
- A (up) counter will get created | - A (up) counter will get created | ||
Zeile 215: | Zeile 215: | ||
- Make the state machine get alive: | - Make the state machine get alive: | ||
- Click to the menu '' | - Click to the menu '' | ||
- | - Here, click on the menu '' | + | - Here, click on the menu '' |
- Now, the circuit can be started via the start button. The present state in the state transition diagram will also get highlighted. | - Now, the circuit can be started via the start button. The present state in the state transition diagram will also get highlighted. | ||
</ | </ | ||
- | The next step is to transform this into a up counter from $1...4$. For this simply the output has to be changed. This means the numbers in the "lower half of the circles" | + | The next step is to transform this into an up counter from $1...4$. For this simply the output has to be changed. This means the numbers in the "lower half of the circles" |
- | < | + | < |
{{drawio> | {{drawio> | ||
<wrap # | <wrap # | ||
<panel type=" | <panel type=" | ||
- | This exercise directly attached | + | This exercise |
- | The counter shall now be changed in such a way, that it counts $1 - 2 - 3 - 4$. For this: right click on each present | + | The counter shall now be changed in such a way, that it counts $1 - 2 - 3 - 4$. For this: right-click on each present |
{{drawio> | {{drawio> | ||
Zeile 235: | Zeile 235: | ||
Tasks: | Tasks: | ||
- Make this state machine again get alive | - Make this state machine again get alive | ||
- | - Look at the circuit: Is it a Moore, Mealy or a Medvedev machine? | + | - Look at the circuit: Is it a Moore, Mealy, or a Medvedev machine? |
</ | </ | ||
- | Looking | + | Looking |
- | < | + | < |
{{drawio> | {{drawio> | ||
<panel type=" | <panel type=" | ||
- | This exercise directly attached | + | This exercise |
- | The last step is to add the transitions: | + | The last step is to add the transitions: |
{{drawio> | {{drawio> | ||
Zeile 256: | Zeile 256: | ||
<panel type=" | <panel type=" | ||
- | This exercise directly attached | + | This exercise |
- | With the state machine in 6.3.3.3 it is also possible to create a state machine | + | With the state machine in 6.3.3.3, it is also possible to create a state machine |
- | Use the following addition to the resulting | + | Use the following addition to the resulting |
{{drawio> | {{drawio> | ||
Zeile 273: | Zeile 273: | ||
<panel type=" | <panel type=" | ||
- | The following state transistion | + | The following state transition |
{{drawio> | {{drawio> | ||
- | * There are two transitions marked with $A$ and $B$. What values | + | * There are two transitions marked with $A$ and $B$. \\ What values |
- | * How many flipflops | + | |
+ | <WRAP indent>< | ||
+ | <button size=" | ||
+ | * Find the transitions wanted | ||
+ | * Look at which state these transitions start. | ||
+ | * Which other transitions start there? | ||
+ | * Which transition conditions are missing? | ||
+ | </ | ||
+ | * transition A | ||
+ | * Starts at state $000$ | ||
+ | * Also transition with $11$, $00$ starts here | ||
+ | * $01$, $10$ are missing | ||
+ | * transition B | ||
+ | * Starts at state $010$ | ||
+ | * Also transition with $0-$ starts here | ||
+ | * $1-$ are missing | ||
+ | </ | ||
+ | * A: $01$, $10$ | ||
+ | * B: $1-$ | ||
+ | </ | ||
+ | </ | ||
+ | |||
+ | * How many flip-flops | ||
+ | |||
+ | <WRAP indent>< | ||
+ | <button size=" | ||
+ | Each flipflop can store one Bit. Each stored bit can be used to address states. So, check the number of bits $i$ of states $Z_i$ ("size of the state vector" | ||
+ | Be aware, that one bit can address a maximum of 2 states, two bits a maximum of 4 states, three bits a maximum of 8 states, and so on. | ||
+ | </ | ||
+ | * Number of bits $i$ of states $Z_i$ is given in the legend. The number of bits $i$ has also to fit the number of states. | ||
+ | * Here the legend shows $Z_2, Z_1, Z_0$, so there are 3 bits. | ||
+ | * Also the number of states in the diagram is 5. This can only be numbered with at least 3 bits. | ||
+ | |||
+ | </ | ||
+ | 3 | ||
+ | </ | ||
+ | </ | ||
* Fill in the missing cells in the following state transition table: | * Fill in the missing cells in the following state transition table: | ||
{{drawio> | {{drawio> | ||
+ | |||
+ | |||
+ | <WRAP indent>< | ||
+ | <button size=" | ||
+ | Check for each line: | ||
+ | * What is the start/ | ||
+ | * Which transition is shown as start/ | ||
+ | Out of this orientation, | ||
+ | * At the end of the transition, the next state can be found (necessary for columns $\color{green}{Z_2(n+1), | ||
+ | * Within the state symbol of the present state, the output values can be found (necessary for columns $\color{violet}{Y_2(n), | ||
+ | {{drawio> | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | </ | ||
</ | </ | ||
Zeile 287: | Zeile 338: | ||
<panel type=" | <panel type=" | ||
- | Design a state machine, which result | + | Design a state machine, which results |
* The numbers shall repeat cyclic and without any other input than the clock $CLK$ | * The numbers shall repeat cyclic and without any other input than the clock $CLK$ | ||
* Draw the state transition diagram and the state transition table | * Draw the state transition diagram and the state transition table | ||
* Use alternatively the structure of a 3bit up-counter | * Use alternatively the structure of a 3bit up-counter | ||
- | * Draw the structure of this moore machine with the up-counter as a blackbox, the input and output values and - if necessary - further | + | * Draw the structure of this Moore machine with the up-counter as a black box, the input and output values, and - if necessary - further |
* draw and fill in the additional table. | * draw and fill in the additional table. | ||
Zeile 298: | Zeile 349: | ||
<panel type=" | <panel type=" | ||
- | Design a state transistion | + | Design a state transition |
- The milling machine has 4 states: Initialisation $I$, Component Change $C$, Running $R$, Error $E$ | - The milling machine has 4 states: Initialisation $I$, Component Change $C$, Running $R$, Error $E$ | ||
- The milling machine starts at the state $I$. | - The milling machine starts at the state $I$. | ||
- | - Once a limit switch $L$ is read as activated, the state $E$ shall be entered, independent which state the machine was in. | + | - Once a limit switch $L$ is read as activated, the state $E$ shall be entered, independent |
- Only in the state $E$ an alarm shall ring $A=1$. | - Only in the state $E$ an alarm shall ring $A=1$. | ||
- $E$ can only be exited with a reset. | - $E$ can only be exited with a reset. | ||
Zeile 308: | Zeile 359: | ||
- Initialisation $I$ only changes into Component Change $C$, when no limit switch $L$ is activated and the Key is deactivated (input $K=0$) and the Fixed Condition is reached $F=1$. | - Initialisation $I$ only changes into Component Change $C$, when no limit switch $L$ is activated and the Key is deactivated (input $K=0$) and the Fixed Condition is reached $F=1$. | ||
- | Explicitely | + | Explicitly |
{{drawio> | {{drawio> | ||
Zeile 322: | Zeile 373: | ||
- | * Draw the state transition diagram of the moore machine of the synchronous sequential circuit. | + | * Draw the state transition diagram of the Moore machine of the synchronous sequential circuit. |
- | * Create the digital | + | * Create the digital |
</ | </ | ||
Zeile 334: | Zeile 385: | ||
{{drawio> | {{drawio> | ||
- | * Draw the state transition diagram of the moore machine of the synchronous sequential circuit. | + | * Draw the state transition diagram of the Moore machine of the synchronous sequential circuit. |
- | * Create the digital | + | * Create the digital |
</ | </ | ||
Zeile 342: | Zeile 393: | ||
<panel type=" | <panel type=" | ||
- | Develop a sequential circuit, which generate | + | Develop a sequential circuit, which generates |
- | * Draw the state transition diagram of the moore machine of the synchronous sequential circuit. | + | * Draw the state transition diagram of the Moore machine of the synchronous sequential circuit. |
- | * Create the digital | + | * Create the digital |
</ | </ | ||