Algorithmic State Machines (ASMs)

The functionality of complex machines is divided into two parts:

An architecture - details of the components that perform

actions, and their interconnections

A controller - instructs the architecture to perform particular

actions, and when to do them.

Architectures can be of many different types:

Digital eg a CPU

Mechanical eg a lift

Electrical eg a set of traffic lights

Hydraulic etc

For a computer processor:

Machine instructions are stored in the memory

The controller executes a loop performing these actions:

• tell the processor to fetch an instruction from memory

• tell the processor to perform the actions requested by the instruction

status lines contain:

The instruction

Other status information eg

Z flag

NEG flag

OVFL flag

which will give the state of the accumulator after the instruction

Using these status flags the controller can follow different paths through the program

command lines allow the controller to perform specific actions

The processor architecture will contain specific logic elements eg

registers

multiplexors

adders

Command lines will control these devices:

Load a register

Output enable a register

Select a multiplexors input

Read/write enable memory

The controller is implemented as a state machine

Each state starts in a square box and lasts until you reach the next square box.

Everything within a state happens simultaneously

States can be numbered arbitrarily but it makes sense to try and keep to some pattern and to label the most common state 0

Command lines (outputs), listed in the square boxes, are true (1) when the controller is in that state false (0) otherwise.

Status lines (inputs) are tested in diagonal boxes. The two paths leading away from the test will be labelled with either T or F.

Outputs listed in rounded boxes are only asserted if that path is taken.

The state machine goes from one state to another on the tick of a clock.

How to implement an ASM:

1. Use a register to store the present state number

2. Use some combinatorial logic to calculate what the next state

should be.

3. On the tick of the clock transfer that new state into the register

4. repeat indefinitely

The register stores the number of the current state.

How many bits does it take to store a state?

If there are 2 states we only need 1 bit wide register

0 -> 0

1 -> 1

if there are 4 states we will need a 2 bit wide register

0 -> 00

1 -> 01

2 -> 10

3 -> 11

if there are 8 states we will need a 3 bit wide register

0 -> 000

1 -> 001

etc

If we have seven states we will have to use 3 bits - one of the states will never occur.

We have a practical problem when we first start the machine:

Which state will it start in?

To make sure we don’t start in a state that could lead to self-destruction, we make sure we always start in state 0

This is achieved by holding a Reset line high when power is first applied, removing the Reset only after a little time has elapsed