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
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:
Other status information eg
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
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
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
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
159.233 Lecture 7 -