Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung Nächste Überarbeitung Beide Seiten der Revision | ||
introduction_to_digital_systems:sequential_logic [2021/12/13 03:48] tfischer |
introduction_to_digital_systems:sequential_logic [2023/02/05 02:06] mexleadmin [Bearbeiten - Panel] |
||
---|---|---|---|
Zeile 5: | Zeile 5: | ||
===== 6.1 First Terminology ===== | ===== 6.1 First Terminology ===== | ||
- | The most important term 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 |
Here some practical examples: | Here 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). Similarly, an empty memory (or harddrive) is in a different state compared to an compared to a full one. Even a fresh deleted one is distingisable, | + | * 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 |
- | Sequential logic is used to describe logic cicruits which show internal states (" | + | * A traffic light showing green has a output distinguishable from red, or yellow. |
+ | Sequential logic is used to describe logic cicruits which 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{Q}$ represents the $m$ inputs $X_0 ... X_{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 $Q_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 point in time and therefore e.g. the next state $Q_0(n+1)$ | + | * The sign $(n+1)$ or $n+1$ marking the next upcomming point in time and therefore e.g. the next state $Z_0(n+1)$ |
* Sequential logic circuits are also called **Finite State Machines** (FSM) or sometimes also shortened to "state machine" | * Sequential logic circuits are also called **Finite State Machines** (FSM) or sometimes also shortened to "state machine" | ||
The <imgref pic04> shows the different terms in an abstract diagram. The " | The <imgref pic04> shows the different terms in an abstract diagram. The " | ||
- | < | + | < |
The principle interior of the blackbox in <imgref pic04> was already shown in one practical application in the [[: | The principle interior of the blackbox in <imgref pic04> was already shown in one practical application in the [[: | ||
- | < | + | < |
<panel type=" | <panel type=" | ||
<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{Q}$ need? | + | * How many bits (= flip flops) might the state vector $\vec{Z}$ need? |
< | < | ||
Zeile 42: | Zeile 43: | ||
< | < | ||
- | {{url> | + | {{url> |
===== 6.2 Classical State Machine Types ===== | ===== 6.2 Classical State Machine Types ===== | ||
Zeile 51: | Zeile 52: | ||
The first idea might be to use what we already have: an up-counter, which faciliate 2 flip-flops in order to result into 2-bit output. | The first idea might be to use what we already have: an up-counter, which faciliate 2 flip-flops in order to result into 2-bit output. | ||
- | The wanted new state machine needs 3 bits for the output, since the binary representation of our outputs are $%001$,$%010$,$%011$,$%100$. | + | The wanted new state machine needs 3 bits for the output, since the binary representation of our outputs are $001_2$,$010_2$,$011_2$,$100_2$. |
- | 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$ into $%001$, the $%01$ into $%010$, $%10$ into $%011$ and $%11$ into $%101$. This can be logic can be created by: | + | 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: |
* writing down the truth table | * writing down the truth table | ||
* putting the values into a Karnaugh map | * putting the values into a Karnaugh map | ||
Zeile 62: | Zeile 63: | ||
< | < | ||
- | {{url> | + | {{url> |
This resembles a so called **Moore Machine** | This resembles a so called **Moore Machine** | ||
Zeile 69: | Zeile 70: | ||
<panel type=" | <panel type=" | ||
- | A state machine is a **Moore Machine**, when the output values $\vec{Y}$ depends only on the state values $\vec{Q}$. For this the moore machine uses two combinatorial circuits: | + | A state machine is a **Moore Machine**, when the output values $\vec{Y}$ depends only on the state values $\vec{Z}$. For this the moore machine uses two combinatorial circuits: |
- | * The input circuit, which process the input values $\vec{X}(n+1)$ and the state values $\vec{Q}(n)$ (of the previous step) in such a way that the new states $\vec{Q}(n+1)$ are generated. | + | * The input circuit, which process the input values $\vec{X}(n+1)$ and the state values $\vec{Z}(n)$ (of the previous step) in such a way that the new states $\vec{Z}(n+1)$ are generated. |
- | * The output circuit, which transform the state values $\vec{Q}(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: | ||
Zeile 83: | Zeile 84: | ||
==== 6.2.2 Mealy Machine ==== | ==== 6.2.2 Mealy Machine ==== | ||
- | When looking onto <imgref pic21> a bit more in detail, one can see, that the outputs $Y_0$ and $Y_1$ just equals output of the first combinatorial logic circuit. This is not surprising: the input logic circuit shows the $\vec{Q}(n+1)$ and this is for the counter always the stored value plus one, except when the maximum is reached. | + | When looking onto <imgref pic21> a bit more in detail, one can see, that the outputs $Y_0$ and $Y_1$ just equals output of the first combinatorial logic circuit. This is not surprising: the input logic circuit shows the $\vec{Z}(n+1)$ and this is for the counter always the stored value plus one, except when the maximum is reached. |
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>. | ||
< | < | ||
- | {{url> | + | {{url> |
<WRAP column 100%> | <WRAP column 100%> | ||
<panel type=" | <panel type=" | ||
- | A state machine is a **Mealy Machine**, when the output values $\vec{Y}$ depends not only on the state values $\vec{Q}$. For this the mealy machine uses two combinatorial circuits: | + | A state machine is a **Mealy Machine**, when the output values $\vec{Y}$ depends not only on the state values $\vec{Z}$. For this the mealy machine uses two combinatorial circuits: |
- | * The input circuit, which process the input values $\vec{X}(n+1)$ and the state values $\vec{Q}(n)$ (of the previous step) in such a way that the new states $\vec{Q}(n+1)$ are generated. | + | * The input circuit, which process the input values $\vec{X}(n+1)$ and the state values $\vec{Z}(n)$ (of the previous step) in such a way that the new states $\vec{Z}(n+1)$ are generated. |
- | * The output circuit, which transform the state values $\vec{Q}(n)$ __and__ some inputs from ahead of the flip-flops into the output values $\vec{Y}(n)$. | + | * The output circuit, which transform the state values $\vec{Z}(n)$ __and__ some inputs from ahead of the flip-flops into the output values $\vec{Y}(n)$. |
The properties of a mealy machine are: | The properties of a mealy machine are: | ||
Zeile 115: | Zeile 116: | ||
< | < | ||
- | {{url> | + | {{url> |
<WRAP column 100%> | <WRAP column 100%> | ||
<panel type=" | <panel type=" | ||
- | A state machine is a **Medvedev Machine**, when the output values $\vec{Y}$ is directly given by the state values $\vec{Q}$. For this the medvedev machine uses only one combinatorial circuit. This circuitprocess the input values $\vec{X}(n+1)$ and the state values $\vec{Q}(n)$ (of the previous step) in such a way that the new states $\vec{Q}(n+1)$ and the output values $\vec{Y}(n+1)= \vec{Q}(n+1)$ are generated. | + | A state machine is a **Medvedev Machine**, when the output values $\vec{Y}$ is directly given by the state values $\vec{Z}$. For this the medvedev machine uses only one combinatorial circuit. This circuitprocess the input values $\vec{X}(n+1)$ and the state values $\vec{Z}(n)$ (of the previous step) in such a way that the new states $\vec{Z}(n+1)$ and the output values $\vec{Y}(n+1)= \vec{Z}(n+1)$ are generated. |
The properties of a medvedev machine are: | The properties of a medvedev machine are: | ||
Zeile 127: | Zeile 128: | ||
* The medvedev machine usually need more logic gates. | * The medvedev machine usually need more logic gates. | ||
+ | </ | ||
+ | </ | ||
+ | |||
+ | |||
+ | The <imgref pic101> shows the principle differences in the architecture of the state machines. | ||
+ | |||
+ | < | ||
+ | |||
+ | \\ \\ | ||
+ | <WRAP column 100%> | ||
+ | <panel type=" | ||
+ | This chapter is only focussing on Moore machines. | ||
</ | </ | ||
</ | </ | ||
Zeile 138: | Zeile 151: | ||
In <imgref pic01> image (1) the states of water are shown on the temperature axis. When only the state transistions are relevant, the states are simplified to a circle, showing the state name and behaviour. The transitions are depict as arrows, where the needed condititon is written onto (See <imgref pic01> image (2) ). This diagram is called **state transition diagram**. | In <imgref pic01> image (1) the states of water are shown on the temperature axis. When only the state transistions are relevant, the states are simplified to a circle, showing the state name and behaviour. The transitions are depict as arrows, where the needed condititon is written onto (See <imgref pic01> image (2) ). This diagram is called **state transition diagram**. | ||
- | < | + | < |
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 transistions. These can be drawn into the state transition diagram (<imgref pic02> image (2)). | ||
- | < | + | < |
==== 6.3.2 Simple logic Example ==== | ==== 6.3.2 Simple logic Example ==== | ||
Zeile 150: | Zeile 163: | ||
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. | ||
- | < | + | < |
The <imgref pic04> the state transition diagram is drawn. | The <imgref pic04> the state transition diagram is drawn. | ||
Zeile 160: | Zeile 173: | ||
* 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, in order 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: | the inputs, outputs and states have to be encoded into binary, in order 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 ≙ $Q=0$, turnstile opened ≙ $Q=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$, | ||
* Encoding of the outputs: disallow entrance ≙ $Y=0$, allow entrance ≙ $Y=1$, | * Encoding of the outputs: disallow entrance ≙ $Y=0$, allow entrance ≙ $Y=1$, | ||
Zeile 173: | Zeile 186: | ||
This table is shown in <imgref pic06a> and is called **state transition table**. | This table is shown in <imgref pic06a> and is called **state transition table**. | ||
- | < | + | < |
+ | {{drawio> | ||
Interestingly, | Interestingly, | ||
Zeile 180: | Zeile 194: | ||
==== 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 from $1...4$ | + | In the previous sub-chapter (6.2) we had a look onto different implementations of an up counter |
- | For the Moore machine | + | The Answer ist quite simple: there are 4 states, so 4 " |
+ | With a deeper | ||
- | < | + | In <imgref pic15> both types of state machines are shown. |
+ | * In the Moore Machine the already seen " | ||
+ | * In the Medvedev Machine only one value is written in the circle, since here the state vector is also the output vector. | ||
+ | |||
+ | < | ||
+ | {{drawio> | ||
+ | |||
+ | <panel type=" | ||
+ | The shown state transistion diagram can easily be created in the tool Digital: | ||
+ | - Click on the menu '' | ||
+ | - Here one either can add new states with a right click, or - more easier - go to the menu '' | ||
+ | - A (up) counter will get created | ||
+ | |||
+ | Tasks: | ||
+ | - Make the state machine get alive: | ||
+ | - Click to 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. | ||
+ | |||
+ | </ | ||
+ | |||
+ | 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" | ||
+ | |||
+ | < | ||
+ | {{drawio> | ||
+ | |||
+ | <wrap # | ||
+ | <panel type=" | ||
+ | This exercise directly attached onto Exercise 6.3.3.2 | ||
+ | |||
+ | The counter shall now be changed in such a way, that it counts $1 - 2 - 3 - 4$. For this: right click on each present states beginning with state 0 and add for '' | ||
+ | |||
+ | {{drawio> | ||
+ | |||
+ | Tasks: | ||
+ | - Make this state machine again get alive | ||
+ | - Look at the circuit: Is it a Moore, Mealy or a Medvedev machine? | ||
+ | |||
+ | </ | ||
+ | |||
+ | Looking on what we got, there is one part missing: the state machine does not have any input.. So the input vectors have to be added onto the transition (arrows). For an activateable counter, there only have to be one input $X$, which acts as an enable input. | ||
+ | |||
+ | < | ||
+ | {{drawio> | ||
+ | |||
+ | <panel type=" | ||
+ | This exercise directly attached onto Exercise 6.3.3.2 | ||
+ | |||
+ | The last step is to add the transitions: | ||
+ | |||
+ | {{drawio> | ||
+ | |||
+ | Tasks: | ||
+ | - Make this state machine again get alive | ||
+ | </ | ||
+ | |||
+ | <panel type=" | ||
+ | This exercise directly attached onto Exercise 6.3.3.3 | ||
+ | |||
+ | With the state machine in 6.3.3.3 it is also possible to create a state machine which can resemble a traffic light state machine. This shall transit from red, to red-yellow, to green, to yellow and then back to red. | ||
+ | |||
+ | Use the following addition to the resulting citcuit in order to get the light running: | ||
+ | {{drawio> | ||
+ | |||
+ | |||
+ | Tasks: | ||
+ | - Think about the right way to change the outputs in the state machine. | ||
+ | - Implement the needed correction and test the state machine. | ||
+ | </ | ||
====== Exercises ====== | ====== Exercises ====== | ||
- | <panel type=" | + | <panel type=" |
The following state transistion diagram shall be given: | The following state transistion diagram shall be given: | ||
- | {{drawio> | + | {{drawio> |
+ | |||
+ | |||
+ | * There are two transitions marked with $A$ and $B$. \\ What values does the inputs need to have in order show all transistions explicitely? | ||
+ | |||
+ | <WRAP indent>< | ||
+ | <button size=" | ||
+ | * Find the transitions wanted | ||
+ | * Look at which state these transitions starts. | ||
+ | * Which other transitions starts 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-$ | ||
+ | </ | ||
+ | </ | ||
- | * There are two transitions marked with $A$ and $B$. What values does are the input need to have at thies transitions? | ||
* How many flipflops are necessary for such a Moore Machine? | * How many flipflops are necessary for such a Moore Machine? | ||
+ | |||
+ | <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 maximum 2 states, two bits maximum 4 states, three bits maximum 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 to the number of states. | ||
+ | * Here the legend shows $Z_2, Z_1, Z_0$, so there are 3 bits. | ||
+ | * Also the number of states i the diagram are 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 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 valuse can be found (necessary for columns $\color{violet}{Y_2(n), | ||
+ | {{drawio> | ||
+ | </ | ||
+ | {{drawio> | ||
+ | </ | ||
+ | </ | ||
</ | </ | ||
- | <panel type=" | + | <panel type=" |
Design a state machine, which result in an output of the following (decimal) numbers: $4 - 5 - 2 - 1 - 6 - 7 - 0 - 3 - 4 - ...$ | Design a state machine, which result in an output of the following (decimal) numbers: $4 - 5 - 2 - 1 - 6 - 7 - 0 - 3 - 4 - ...$ | ||
Zeile 211: | Zeile 347: | ||
</ | </ | ||
- | <panel type=" | + | <panel type=" |
Design a state transistion diagram for a automatic milling machine as Moore machine, under the following conditions: | Design a state transistion diagram for a automatic milling machine as Moore machine, under the following conditions: | ||
- 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 any limit switch $L$ got 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 which state the machine was in. |
- Only in the state $E$ an alarm shall ring $A=1$. | - Only in the state $E$ an alarm shall ring $A=1$. | ||
- | - $D$ can only be exited with a reset. | + | - $E$ can only be exited with a reset. |
- In order to change from Component Change $C$ to Running $R$, the user has to activate a Key $K=1$. | - In order to change from Component Change $C$ to Running $R$, the user has to activate a Key $K=1$. | ||
- Only when the machine is running $R$ and the Fixed Condition is reached $F=1$, the state Component Change $C$ shall be entered. | - Only when the machine is running $R$ and the Fixed Condition is reached $F=1$, the state Component Change $C$ shall be entered. | ||
- | - The Initialisation $I$ only changes into Component Change $C$, when no limit switch $L$ is activated and the Key is deactive | + | - Initialisation $I$ only changes into Component Change $C$, when no limit switch $L$ is activated and the Key is deactivated (input |
- | {{drawio> | + | Explicitely draw all possible transitions. |
+ | |||
+ | {{drawio> | ||
</ | </ | ||
+ | |||
+ | <panel type=" | ||
+ | |||
+ | Develop a sequential circuit, which creates the following output | ||
+ | |||
+ | {{drawio> | ||
+ | |||
+ | |||
+ | * Draw the state transition diagram of the moore machine of the synchronous sequential circuit. | ||
+ | * Create the digital ciruit. | ||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | <panel type=" | ||
+ | |||
+ | Develop a sequential circuit, which allows driving the following LED sequence | ||
+ | |||
+ | {{drawio> | ||
+ | |||
+ | * Draw the state transition diagram of the moore machine of the synchronous sequential circuit. | ||
+ | * Create the digital ciruit. | ||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | <panel type=" | ||
+ | |||
+ | Develop a sequential circuit, which generate a clock driven up-counter from $1..6$. The not reqired states shall lead after one clock cycle to the state of number $1$. | ||
+ | |||
+ | * Draw the state transition diagram of the moore machine of the synchronous sequential circuit. | ||
+ | * Create the digital ciruit. | ||
+ | |||
+ | </ | ||