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 justinput(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| S1Looking Forward
L28 turns these models into a repeatable design process, including state encoding and CAD tools.