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 [2022/06/28 03:46] tfischer |
introduction_to_digital_systems:sequential_logic [2023/03/27 11:52] mexleadmin |
||
---|---|---|---|
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 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). 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 hard drive) 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 an output distinguishable from red, or yellow. |
+ | 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 " | ||
- | < | + | < |
- | 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 [[: |
- | < | + | < |
<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{Z}$ need? | * How many bits (= flip flops) might the state vector $\vec{Z}$ need? | ||
Zeile 39: | 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 46: | 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 in order 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$ into $%001$, the $%01$ into $%010$, $%10$ into $%011$ and $%11$ into $%101$. 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 64: | 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 83: | 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 93: | 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 120: | 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 133: | Zeile 134: | ||
The <imgref pic101> shows the principle differences in the architecture of the state machines. | The <imgref pic101> shows the principle differences in the architecture of the state machines. | ||
- | < | + | < |
\\ \\ | \\ \\ | ||
Zeile 150: | 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 162: | 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 172: | 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: | ||
Zeile 186: | Zeile 187: | ||
< | < | ||
- | {{drawio> | + | {{drawio> |
Interestingly, | Interestingly, | ||
Zeile 195: | Zeile 196: | ||
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 look like in the state transition diagram? | 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 look like in the state transition diagram? | ||
- | The Answer ist quite simple: there are 4 states, so 4 " | + | The Answer ist 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 onto is: This is therefore in particular a Medvedev machine! | ||
Zeile 203: | Zeile 204: | ||
< | < | ||
- | {{drawio> | + | {{drawio> |
<panel type=" | <panel type=" | ||
Zeile 222: | Zeile 223: | ||
< | < | ||
- | {{drawio> | + | {{drawio> |
<wrap # | <wrap # | ||
Zeile 230: | Zeile 231: | ||
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 '' | 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> | + | {{drawio> |
Tasks: | Tasks: | ||
Zeile 241: | Zeile 242: | ||
< | < | ||
- | {{drawio> | + | {{drawio> |
<panel type=" | <panel type=" | ||
Zeile 248: | Zeile 249: | ||
The last step is to add the transitions: | The last step is to add the transitions: | ||
- | {{drawio> | + | {{drawio> |
Tasks: | Tasks: | ||
Zeile 260: | Zeile 261: | ||
Use the following addition to the resulting citcuit in order to get the light running: | Use the following addition to the resulting citcuit in order to get the light running: | ||
- | {{drawio> | + | {{drawio> |
Tasks: | Tasks: | ||
Zeile 272: | Zeile 274: | ||
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 the inputs need to have in order show all transistions explicitely? | ||
* 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> | ||
+ | </ | ||
+ | </ | ||
</ | </ | ||
Zeile 287: | Zeile 342: | ||
* 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 blackboxes | + | * Draw the structure of this Moore machine with the up-counter as a blackbox, the input and output values and - if necessary - further blackboxes |
* draw and fill in the additional table. | * draw and fill in the additional table. | ||
Zeile 306: | Zeile 361: | ||
Explicitely draw all possible transitions. | Explicitely draw all possible transitions. | ||
- | {{drawio> | + | {{drawio> |
</ | </ | ||
Zeile 315: | Zeile 370: | ||
Develop a sequential circuit, which creates the following output | Develop a sequential circuit, which creates the following output | ||
- | {{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 ciruit. | * Create the digital ciruit. | ||
Zeile 327: | Zeile 383: | ||
Develop a sequential circuit, which allows driving the following LED sequence | Develop a sequential circuit, which allows driving the following LED sequence | ||
- | {{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 ciruit. | * Create the digital ciruit. | ||
Zeile 337: | Zeile 393: | ||
<panel type=" | <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 . | + | 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 |
- | * 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 ciruit. | * Create the digital ciruit. | ||
</ | </ | ||