Introduction to state machines

Source

Exercise 157

1. What is a state machine in general?

2. Why do we need state machines in systems?

Solution to Exercise 157

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 Exercise 101. 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

Source

Exercise 158

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 158

• 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 159

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 to Exercise 159

These components are connected as follows:

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 160

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 to Exercise 160

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

Many representations are available for state machines. Two main types are:

• State/transition table

• State diagram

State table

Exercise 161

What does a state/transition table describe the behavior of a state machine?

Solution to Exercise 161

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 162

How can we transform a state table to a circuit?

Solution to Exercise 162

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 163

What is the advantage of state diagrams over state tables?

Solution to Exercise 163

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 164

State diagrams must obey the following requirements:

1. sum rule

2. mutually exclusive requirement

What do these requirements mean?

Solution to Exercise 164

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

Exercise 165

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 to Exercise 165

1. Unit-distance code 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.

Exercise 166

How can we get rid of the combinational output logic in a state diagram?

Solution to Exercise 166

By designing the state memory bits in such a way that they directly reflect the output bits.

Structural implementation of state diagrams

Source

Exercise 167

How do we implement a state diagram using a structural approach?

Solution to Exercise 167

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