Concept

Definition

<aside> ℹ️ Finite State Machine (FSM): abstract model to describe real world systems

• States: represent different situation of the system
• FSM models state changes (external input → external output relation) </aside>

$$ FSM = ( S, I, O, \pi) $$

• $S$: the finite set of states
• $I$: the finite set of external inputs
• $O$: the finite set of external outputs
• $\pi$: state transition function:
  • Define the relations among input, output, current state, next state.
  • Complete: for any $\{S_t,I_t\}$, $\{S_{t+1},I_{t+1}\}$ can be determined

Mealy Machine

• Output and state depends on both current state and input

Moore Machine

• Output only depends on current state

• Registers = Memory component
• Comb. logic = State transition function

Analysis

<aside> ℹ️ Core Idea: given state table → derive function (e.g., K-map)

</aside>

$$ S_{t+1}=f(I_t,\ S_t)\\ O_{t+1} = g(I_t, S_t) $$

Where $f$ and $g$ can be made using combinatorial logics.

Excitation Table

<aside> ℹ️ Excitation Table: what inputs are required to transit from one state to the next.

</aside>

Example