L27: State Machines A

Objective
Model a system with a finite state machine: identify states, transitions, inputs, and outputs, and draw both state diagrams and ASM charts.


Before the Lecture

Required Textbook Reading:

  • 6.1–6.3 (State Machines)

Finite State Machines

A finite state machine (FSM) is a model of a system with:

  • A finite set of states $S$.
  • A finite set of inputs (alphabet).
  • A finite set of outputs.
  • A transition function $\delta: S \times \text{inputs} \to S$.
  • An output function $\lambda$ (Moore: $S \to \text{outputs}$; Mealy: $S \times \text{inputs} \to \text{outputs}$).

The machine is in exactly one state at a time. Each clock edge (or input event) moves it along one transition.

Identifying States

The hardest part of FSM design is usually deciding what to remember. A good state captures exactly the information needed to decide future behavior – no more, no less. Two classic pitfalls:

  • Too few states: the machine forgets something it needs (e.g. a sequence detector that only remembers the last bit, not the last two).
  • Too many states: redundant states that can be merged later (this is what L29 fixes).

Mealy vs. Moore (revisited)

Moore Mealy
Output depends on state only state + input
Output changes on clock edge can change with input
States needed often more often fewer
Glitch risk low high if inputs are asynchronous

A Mealy machine can assert an output before the state changes, which is sometimes exactly what you want (e.g. a “sequence detected” pulse that lasts one cycle starting the moment the final bit arrives). But if that input is noisy, the output is noisy too.

State Diagrams

Conventions:

  • Circle = state; label with state name (and output for Moore).
  • Arc = transition; label input / output (Mealy) or just input (Moore, output shown in circle).
  • Reset arrow points to the initial state.

State Tables

A state table has one row per present state and one column per input combination. Each cell gives the next state (and output for Mealy). It is the canonical form used by CAD tools and by minimization.

ASM Charts

For larger controllers, state diagrams get messy. An Algorithmic State Machine (ASM) chart is a flowchart-like notation:

  • State box: rectangular, one per clock cycle; lists Moore outputs.
  • Decision box: diamond, tests an input; branches.
  • Conditional output box: oval; lists Mealy (conditional) outputs taken on a particular branch.

ASM charts make it natural to describe controllers with many inputs and outputs (e.g. the reaction-timer case study). Every ASM chart converts mechanically to a state table.

Case Study: Swap Controller

A controller that swaps the contents of two registers using three states (Idle, Load R1$\to$R2, Load R2$\to$R1) is the textbook’s first nontrivial FSM. It is small enough to hand-design but large enough to show why Mealy outputs (register enable signals) are convenient.

ASM Chart (Simple Moore Machine)

flowchart TD
    S0[State S0\nz=0] -->|w=0| S0
    S0 -->|w=1| S1
    S1[State S1\nz=1] -->|w=0| S0
    S1 -->|w=1| S1

Looking Forward

L28 turns these models into a repeatable design process, including state encoding and CAD tools.