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:



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




159.233 Lecture 7 -