Introduction to state machines
Contents
Introduction to state machines#
What is a state machine in general?
Why do we need state machines in systems?
Solution to Exercise 155
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.
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 Exercise 99. 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 is a mathematical tool to describe the behavior of such systems based on 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#
Typically storage for a computer program is based on random access memory. Why are registers preferred over random access memory in state machines?
Solution to Exercise 156
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.
A state machine implemented in hardware typically consists of:
state memory (typically a register)
next state (transition) logic
output logic, (typically a decoder)
What do these components do?
How are these components connected?
Which component is the crucial connection in a state machine that enables the sequential behavior?
Solution to Exercise 157
These components are connected as follows:
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.
The feedback between state register and the next state logic.
What is the difference between a Moore and Mealy machine?
What is the advantage of a Mealy machine over the Moore machine?
Solution to Exercise 158
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.
The Mealy machine uses less state memory.
The design of state machines#
Many representations are available for state machines. Two main types are:
State table#
What does a state/transition table describe the behavior of a state machine?
Solution to Exercise 159
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.
How can we transform a state table to a circuit?
Solution to Exercise 160
The state machine has two combinational circuit blocks. We first prepare the truth tables for these blocks and then optimize these using Kmaps.
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#
What is the advantage of state diagrams over state tables?
Solution to Exercise 161
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.
State diagrams must obey the following requirements:
sum rule
mutually exclusive requirement
What do these requirements mean?
Solution to Exercise 162
The conditions of the edges coming out of a state ored (
+
) together must be 1. In other words, the set of all existing edges must contain all possible input combinations.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
What is a unitdistance code?
Give an example of such a code.
What could be the advantage of unitdistance code in a state machine?
Solution to Exercise 163
Unitdistance code is a coding scheme where only a single code bit changes if the coded word is incremented.
Gray code
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.
How can we get rid of the combinational output logic in a state diagram?
Solution to Exercise 164
By designing the state memory bits in such a way that they directly reflect the output bits.
Structural implementation of state diagrams#
How do we implement a state diagram using a structural approach?
Solution to Exercise 165
Code every state using an appropriate coding scheme
optional: Check for the requirements like the sum rule and the mutual exclusivity by creating Kmap like tables. For every state a table is required.
Create \(m \cdot n\) Kmaps, 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.
The Kmap has the previous (or current) state bits as Kmap index variables. The state machine circuit inputs are used as entered variables. We differentiate between the transition logic Kmap and the output logic Kmap:
Transition logic: If an input condition sets the state memory bit (that we have drawn the Kmap 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.Creating circuits using the Kmaps.
Requirements#
TODO