# Introduction to state machines
[Source](https://www.realdigital.org/doc/bead67a33e35670e2b362c37f109b5e7)
```{exercise}
:label: what_is_a_state_machine
1. What is a state machine in general?
2. Why do we need state machines in systems?
```
```{solution} what_is_a_state_machine
:class: dropdown
1. A state machine has
- some inputs
- a state that can change to another state.
- some outputs that can change based on the *last* state and the current inputs.
2. Many systems' behavior depend not only on the current events but also on the past events which was the motivation for sequential logic in problem {ref}`sequential_circuits_motivation`. Designing systems like a calculator or a traffic light controller could be hardly realized without any sequential components. Imagine how would you factor in the sequence of numbers entered in a calculator or creating a sequence of red, yellow, green lights in a traffic light.
[State machine](https://en.wikipedia.org/wiki/Finite-state_machine) is a mathematical tool to describe the behavior of such systems based on [sequential logic](https://en.wikipedia.org/wiki/Sequential_logic).
```
```{note}
A state machine does not have to be synchronous, in other words *clocked*. Still most of the systems are based on synchronous circuits, so most state machines are clocked.
```
## Learning Goals
- Understand how to design state machines
- Be able to write behavioral Verilog for state machines
- Be familiar with the need for good design partitioning
## Background
### State machine models
[Source](https://www.realdigital.org/doc/d92ad2a0f9846d5d11206d6398a9c3ce)
```{exercise}
:label: what_are_the_advantages_of_registers_over_ram
Typically storage for a computer program is based on random access memory. Why are registers preferred over random access memory in state machines?
```
```{solution} what_are_the_advantages_of_registers_over_ram
:class: dropdown
- Registers can be implemented in the proximity of a state machine, so they can be accessed much faster compared to a random access memory.
- Typically state machines do not require a lot of space for the state machine.
```
```{exercise}
:label: what_do_the_components_of_a_state_machine_do
A state machine implemented in hardware typically consists of:
- state memory (typically a register)
- next state (transition) logic
- output logic, (typically a decoder)
1. What do these components do?
2. How are these components connected?
3. Which component is the crucial *connection* in a state machine that enables the sequential behavior?
```
````{solution} what_do_the_components_of_a_state_machine_do
:class: dropdown
These components are connected as follows:
```{image} https://upload.wikimedia.org/wikipedia/commons/1/1f/Moore-Automat-en.svg
:alt: Biezl, Public domain, via Wikimedia Commons
:target: https://commons.wikimedia.org/wiki/File:Moore-Automat-en.svg
```
1.
- state register stores the current state
- next state logic is a combinational logic that prepares the next state based on the inputs and current state
- output decoder is a combinational circuit that forms the output signals dependent on the state register signals.
2. The feedback between state register and the next state logic.
````
```{exercise}
:label: what_is_the_difference_between_moore_and_mealy_machine
1. What is the difference between a Moore and Mealy machine?
2. What is the advantage of a Mealy machine over the Moore machine?
```
```{solution} what_is_the_difference_between_moore_and_mealy_machine
1. In a Moore machine, the output only depends on the state memory. In contrast a Mealy machine forms its output by additionally depending on the inputs.
2. The Mealy machine uses less state memory.
```
### The design of state machines
[Source](https://www.realdigital.org/doc/fc26cf6e35d2a61c6e2871dd9be9e21a)
[Many representations are available for state machines](https://en.wikipedia.org/wiki/Finite-state_machine#Representations). Two main types are:
- [State/transition table](https://en.wikipedia.org/wiki/State-transition_table)
- [State diagram](https://en.wikipedia.org/wiki/State_diagram)
#### State table
```{exercise}
:label: how_does_a_state_table_describe_a_state_machine
What does a state/transition table describe the behavior of a state machine?
```
```{solution} how_does_a_state_table_describe_a_state_machine
:class: dropdown
A state table looks as follows:
| | 0 | 1 |
| - | - | - |
| s1| s2| s1|
| s2| s1| s1|
For each state there is a line and for each input there is a column. The field corresponding to a state and input describes the next state.
```
```{exercise}
:label: how_can_we_transform_a_state_table_to_a_circuit
How can we transform a state table to a circuit?
```
```{solution} how_can_we_transform_a_state_table_to_a_circuit
:class: dropdown
The state machine has two combinational circuit blocks. We first prepare the truth tables for these blocks and then optimize these using K-maps.
How do the truth tables for the transition and output logic look like?
In both transition and output logic we have a column for each state memory bit and input bit. The output bits are next state logic bits and state machine output bits, respectively.
The state memory register is typically connected to a clock and a reset.
```
#### State diagram
```{exercise}
:label: what_is_the_advantage_of_state_diagrams_over_state_tables
What is the advantage of state diagrams over state tables?
```
```{solution} what_is_the_advantage_of_state_diagrams_over_state_tables
:class: dropdown
The state tables are poor as a visual representation, the states are written in a sequential manner on table. The state diagrams use nodes and edges which can be scattered on a paper, which can be typically perceived and sketched easier.
```
```{exercise}
:label: what_do_sum_rule_and_mutually_exclusive_requirement_mean
State diagrams must obey the following requirements:
1. sum rule
2. mutually exclusive requirement
What do these requirements mean?
```
```{solution} what_do_sum_rule_and_mutually_exclusive_requirement_mean
:class: dropdown
1. The conditions of the edges coming out of a state or-ed (`+`) together must be 1. In other words, the set of all existing edges must contain all possible input combinations.
2. Each outgoing edge condition in a state must be mutually exclusive. In other words, one condition is only associated with one edge, so that a particular condition must not be able to lead to multiple states.
For figures refer to the pages 2 and 3 of [this slidedeck](https://gab.wallawalla.edu/~larry.aamodt/engr433/hw1_20.pdf)
```
```{exercise}
:label: what_is_a_unit_distance_code
1. What is a *unit-distance code*?
2. Give an example of such a code.
3. What could be the advantage of unit-distance code in a state machine?
```
```{solution} what_is_a_unit_distance_code
:class: dropdown
1. [Unit-distance code](https://en.wikipedia.org/wiki/Gray_code#Unit-distance) is a coding scheme where only a single code bit changes if the coded word is incremented.
2. Gray code
3. Changing only one bit during the state transition could help to minimize the errors. Refer to the example on the [Wikipedia article on Gray code](https://en.wikipedia.org/wiki/Gray_code).
```
```{exercise}
:label: how_can_we_get_rid_of_the_output_logic
How can we get rid of the combinational output logic in a state diagram?
```
```{solution} how_can_we_get_rid_of_the_output_logic
:class: dropdown
By designing the state memory bits in such a way that they directly reflect the output bits.
```
### Structural implementation of state diagrams
[Source](https://www.realdigital.org/doc/915f0203e4e1265055d179da5d5449ea)
```{exercise}
:label: how_do_we_implement_a_state_diagram_using_a_structural_approach
How do we implement a state diagram using a structural approach?
```
```{solution} how_do_we_implement_a_state_diagram_using_a_structural_approach
:class: dropdown
1. Code every state using an appropriate coding scheme
2. optional: Check for the requirements like the sum rule and the mutual exclusivity by creating K-map like tables. For every state a table is required.
3. Create $m \cdot n$ K-maps, where $m$ is the number of state memory bits and $n$ the number of outputs. In other words, for each bit we require the transition circuit and for every output we require an output circuit.
4. The K-map has the previous (or current) state bits as K-map index variables. The state machine circuit inputs are used as entered variables. We differentiate between the transition logic K-map and the output logic K-map:
Transition logic: If an input condition sets the state memory bit (that we have drawn the K-map for), then we write the input condition as entered variables in the field.
Output logic: We enter a `1` if the current state sets the corresponding output in a Moore machine. Mealy machine is additionally dependent on the input conditions, so the fields for the states which activate the output will contain entered variables.
5. Creating circuits using the K-maps.
```
## Requirements
TODO