FSM and ASM

FSM and ASM in detail

1. FSM and ASM Charts 1 FINITE STATE MACHINE ALGORITHMIC STATE MACHINE BY UNSA SHAKIR

2. Finite State Machine A finite-state machine (FSM) or finite-state automaton is a mathematical model of computation . We have a fixed set of states that the machine can be in The machine can only be in one state at a time A sequence of inputs is sent to the machine Every state has a set of transitions and every transition is associated with an input and pointing to a state

3. ASM (algorithmic state machine ) Flowchart-like diagram Algorithmic State Machine are suitable for FSMs with a larger number of inputs and outputs compared to FSMs expressed using state diagrams and state tables . Provide the same info rmation as an FSM More descriptive, better for complex description algorithm = sequencing + data manipulation Algorithmic state machines can model both Mealy and Moore Finite State Machines

4. Algorithmic State Machines 4 ASMs have three types of building blocks: State Box Decision Box Conditional Output Box

5. The State Box 6

6. State Box Indicated with a rectangle Equivalent to a node in the State diagram The name of the state is written outside the box Moore-type outputs are written inside the box Only the output that must be set to 1 is written (by default, if an output is not listed it is set to 0)

7. The Decision Box S ym bol 8 Alternate Symbol

8. Decision Box Indicated with a diamond shape Used for a condition expression that must be tested The exit path is chosen based on the outcome of the test The condition is on one or more inputs to the FSM Shortcut notation: w means “ is w equal to 1? ”

9. The Conditional Output Box 10

10. Conditional Output Box Indicated with an oval shape Used for a Mealy-type output signals Not used for a Moore-type output signals The outputs depend on the state variables and inputs The condition that determines when such outputs are generated is placed in a separate decision box It is mostly use for high (1) output state.

11. tal a r i c o @g o n za g a. e d u 12

12. tal a r i c o @g o n za g a. e d u 13

13. Another Looping example 1 S0 X C X X C X 1 S0 14

14. Incorrect ASM charts:

15. correct ASM charts 16

16. State diagram and ASM chart conversion

17. State diagram and ASM chart conversion

18. State Diagram Example 1

19. State Table Example 1

20. ASM Chart for Moore FSM – Example 1

21. A w = z = ¤ w 1 = z 1 = ¤ B w = z = ¤ Reset w 1 = z = ¤ Mealy State diagram Example 2

22. ASM Chart for Mealy FSM – Example 2

23. State diagram C z 1 = ¤ Reset B z = ¤ A z = ¤ w = w 1 = w 1 = w = w = w 1 = Example 3

24. Present Next state Output state w = w = 1 z A A B B A C C A C 1 State table Example 3

25. practice Design an FSM that detects if the previous two values of the input w were equal to 00 or 11 If either condition is true then the output z should be set to 1; otherwise to 0. Implement this as a Mealy-type machine