Introduction to state machines#


Exercise 157

  1. What is a state machine in general?

  2. Why do we need state machines in systems?


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


State machine models#


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?

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?

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#


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

State table#

Exercise 161

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

Exercise 162

How can we transform a state table to a circuit?

State diagram#

Exercise 163

What is the advantage of state diagrams over state tables?

Exercise 164

State diagrams must obey the following requirements:

  1. sum rule

  2. mutually exclusive requirement

What do these requirements mean?

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?

Exercise 166

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

Structural implementation of state diagrams#


Exercise 167

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