ASM - Algorithmic State Machine

Jargon: State transition diagram or Algorithmic State Machine (ASM)chart

State machine design : Two different approaches: Moore model and Mealy model.

BACKGROUND:

IN any Digital System, both for simple and complex, it is partitioned into a controller (to generate the control signals) and the controlled architecture (data processor).

The model of the Controller (ASM) block in the above figure can be viewed as the combination of Mealy and Moore machines as shown below.

Mealy State Machines

In Mealy model circuit inputs, also known as primary inputs combine with memory elements to generate circuit output.

Primary inputs combine with memory elements to generate circuit output.

The output is derived from present state as well as input

It requires less number of states and thereby less hardware. Less Complex and Faster Speed.

The output is generated one clock cycle after

Input changes can cause IMMEDIATE Output Changes that cause GLITCH problems.

All Unspecified STATES (UNUSED STATES) must end up in a SPECIFIED STATE after next Clock Cycle or else this will produce OSCILLATION or SYSTEM HANG-UP. Must be avoided at ALL Times.

Moore State Machines

In Moore model circuit outputs, also called primary outputs are generated solely from secondary outputs or memory values.

The primary outputs are generated solely from secondary outputs or memory values.

The output depends only on present state and not on its input. More Robust.

It requires more number of states and thereby more hardware, hence more complex.

The output is generated one clock cycle earlier.

The output remains stable over entire clock period and changes only when there occurs a state change at clock trigger based on input available at that time. (No Glitch Problems)

If we are going to Analyze and Design the CONTROLLER (Control Unit - CU) part of a Digital System, the conventional methods of using Truth Table, State Table or State Diagram will not be suitable nor flexible to carry out the work. When designing the CU of a complex systems, it is often the case that:

– Control and conditional signals are in large numbers

– For every transition not all conditional signals are necessary (only one or few signals at a time)

– Most outputs have default values (corresponding to “do nothing” – ex. Inactive enable)

• In such case, drawing State Diagram might be an overkill and the best approach is the use of ASM or ALGORITHM STATE MACHINE and ALTERNATE STATE MACHINE CHARTS.

Just as flowcharts are useful in software design, special flowcharts called Algorithmic State Machines (ASM) are useful in digital systems hardware design. Digital systems typically consist of datapath processing and the control path. The control path is implemented using state machines which can be realized using state graphs. As the control path (behavior) of the system becomes complex, it becomes increasingly difficult to design the control path using the state graph technique. The ASM charts technique becomes useful and handy in designing complex and algorithmic circuits.

ASM CHART is a representation of a Finite State Machine suitable for FSMs with a larger number of inputs and outputs compared to FSMs expressed using state diagrams and state tables. It is a Representation of sequence of events together with timing relations between states of sequential controller and events occurring while moving between steps. It is a Flowchart defined specifically for digital hardware algorithms and so it is tied closely with a hardware implementation. An alternative to a state diagram which is sometimes nicer when our hardware is implementing an “algorithm” that can be drawn as a flowchart.

The ASM chart differs from an ordinary flowchart in that specific rules must be followed in constructing the chart. When these rules are followed, the ASM chart is equivalent to a state graph, and it leads directly to a hardware realization. The following diagram shows the three main components of an ASM chart.

State Box: The symbol is a rectangle, with a label (state name) and output control operations (Moore type) written inside. It has a single exit path (arrow).

Decision Box:The symbol is a diamond, with a condition variable and multiple exit paths, labeled with values of the input condition. It has a single entry path.

Conditional box:The symbol is a rounded rectangle, and it contains output control operations (only for paths out of a condition box). It has a single entry and exit path.

The ASM chart is constructed from SM blocks. Each SM block contains exactly one state box together with decision boxes and conditional output boxes associated with that state as shown below. An SM block has exactly one entrance path and one or more exit paths. Each SM block describes the machine operation during the time that the machine is in that state. A path through an SM block from entrance to exit is referred to as a link path. Refer to the FIgure below.

Let us consider an example of a state graph of a sequential network shown below. This state graph has

both Mealy and Moore outputs. The outputs Y1 and Y2 are the Mealy outputs and so should be conditional outputs. The Ya, Yb, and Yc are the Moore outputs so they should be part of state box. Input X can either be “0” or “1” and hence it should be part of the decision box.

The ASM chart of the above state graph is as shown below.

Algorithmic state machines can model both Mealy and Moore Finite State Machine.
ASM may have mixed type of both Moore Outputs and Mealy Outputs.

Mealy State diagram

More examples of MIXED Mealy and Moore Finite State Machines

ASM chart for a mod-8 binary counter

The State output here is state code, also note that there is no Input to test.

This is a TYPICAL ASM CHART for COUNTERS.

A Moore sequential network. (a) State diagram. (b) ASM chart.

NOTE: The that there outputs are in the STATE Box, that is, the outputs changed with the STATE Changes. It is a Function of the PRESENT STATE. In other words, the OUTPUTS changed SYCHRONOUSLY (At the same time) with the STATE Changes. THis is the Main Characteristics of a MOORE Machine.

Mealy sequential network. (a) State diagram. (b) ASM chart.

NOTE: The that there outputs are outside the STATE Box and are with the TRANSITION ARROW of the CHART, that is, the OUTPUT changes as the INPUT Changes. It is a Function of the PRESENT INPUTS and STATE. In other words, the OUTPUTS changed IMMEDIATELY with INPUTS Changes and are not anymore SYNC with their OUTPUTS. THis is the Main Characteristics of a MEALY Machine.

ASM chart to recognize the sequence x1x2 = 01,01,11,00.

Derive the ASM Chart of a Complex Counter

A sync. 3 bit counter has a mode control M. When M = 0, the counter counts up in the binary sequence. When M = 1, the counter advances through the Gray code sequence.

Binary: 000, 001, 010, 011, 100, 101, 110, 111

Gray: 000, 001, 011, 010, 110, 111, 101, 100

Design of a clocked sequential circuit from an ASM chart is the same as from a state diagram in so far as we start by generating a state table. once we have a state table, we are pretty much go to go using what we have talked about previously in the course.

Assume we have an ASM Chart for a circuit with three states (S0, S1 and S2), three inputs (G, W and Z) and one output (A).

Assume the 3 state assignments below:

S0 <- 00

S1 <- 01

S2 <- 10

ASM CHART is as folows:

We can obtain our state table from the ASM Chart…

From here, we would proceed as normal in order to get a circuit implementation… Pick FF type, generate

Excitation Tables,KMAPs, COntrol equations, and then Logic Circuit Diagram.

COMPLETE DESIGN PROCEDURE

OF A MEALY MACHINE SEQUENCE DETECTOR

USING ASM

Below is the specification of the Mealy Machine Sequence Detector.

We have a 3 digit sequence to detect, therefore each ‘digit’ will correspond to a state.

How do we produce an ASM chart design

1st - We need to completely understand the requirements of the Design Problem.

a) The circuit asserts Z when any binary input sequence ends with 101.

note: that this circuit does not reset.

b) We need to remember receiving the three symbols 1->0->1, which implies three states. The output is asserted when at the same time the final ‘1’ in the sequence is detected.

S0 – waiting for a ‘1’ state

S1 – waiting for a ‘0’ state

S2 – waiting for the second ‘1’ state

c) Three states, therefore, three ASM blocks are required

d) No Moore outputs, if they were they would be placed in the state boxes

e) Mealy outputs appear as conditional output boxes

f) In this example, each ASM block only has one decision box associated with it since only one input variable is tested

Remember … this is a Mealy machine …

what do we know about Mealy machines and ASM charts????

Mealy Machines has their outputs as function of Inputs and States.

Let us start constructing the STATE DIAGRAM for a Mealy Machine Sequence Detector of '101'.

The above figure is a Step-by-step process of building the STATE DIAGRAM from INITIAL State to its COMPLETE PROCESS.

a) If a 1 is received, we have identified the start of a possible sequence, hence, move to the next state

(state S0 detects the first ‘1’)

b) If a 0 is then received, then we have identified the second digit in the sequence, move to the next

state (state S1 detects the second digit ‘0’)

c) If a 1 is received then the sequence has been detected and we need to assert the output (state S2

detects the final digit ‘1’). As this could also be the start of another sequence, we move back to state

S1 to detect the possible next ‘0’.

d) If we are in S0 and a zero is received, then we haven’t detected a start of sequence, so stay in state

S0. If we are in S1 and a ‘1’ is received then this could be the start of a new sequence, so stay in S1.

e) If we are in S2 and a 0 is received, then we haven’t detected a correct sequence, so return to state

S0 and start again.

Make sure all paths are covered, for all input combinations.

Let us start creating our ASM from start to complete process ( a to e).

a) If a 1 is received, we have identified the start of a possible sequence, hence, move to the next state (state S0 detects the first ‘1’)

b) If a 0 is then received, then we have identified the second digit in the sequence, move to the next state (state S1 detects the second digit ‘0’)

c) If a 1 is received then the sequence has been detected and we need to assert the output (state S2 detects the final digit ‘1’). As this could also be the start of another sequence, we move back to state S1 to detect the possible next ‘0’.

d) If we are in S0 and a zero is received, then we haven’t detected a start of sequence, so stay in state S0. If we are in S1 and a ‘1’ is received then this could be the start of a new sequence, so stay in S1.