Activity 4.1.2 — State Machines¶
Learning Objectives¶
By the end of this lesson, students will be able to:
- Define what a state machine is and its components
- Distinguish between Moore and Mealy machines
- Draw state diagrams for sequential systems
- Create state tables from state diagrams
- Design a simple state machine using flip-flops
Vocabulary¶
Vocabulary (click to expand)
| Term | Definition |
|---|---|
| State Machine | A circuit with a finite number of states that transitions between states based on inputs |
| State | A specific condition or mode of the system |
| State Diagram | A graphical representation showing states and transitions |
| State Table | A table showing current state, inputs, next state, and outputs |
| Moore Machine | A state machine where outputs depend only on the current state |
| Mealy Machine | A state machine where outputs depend on both current state and inputs |
| State Encoding | Assigning binary codes to each state |
Part 1: What is a State Machine?¶
Definition¶
A state machine is a mathematical model that describes a system that: 1. Can be in one of a finite number of states 2. Can transition between states based on inputs 3. Produces outputs based on the current state (and possibly inputs)
Real-World Examples¶
| System | States | Inputs | Outputs |
|---|---|---|---|
| Traffic Light | Green, Yellow, Red | Timer | Light colors |
| Vending Machine | Idle, Accepting, Dispensing | Coins, Buttons | Product, Change |
| Door Lock | Locked, Unlocked | Key code | Motor lock/unlock |
| Elevator | Floor numbers | Floor buttons | Motor direction |
Part 2: Moore vs Mealy Machines¶
Moore Machine¶
Outputs depend only on the current state.
Example: Traffic Light
- State: GREEN → Output: Green light ON
- State: YELLOW → Output: Yellow light ON
- State: RED → Output: Red light ON
Mealy Machine¶
Outputs depend on current state AND inputs.
Example: Edge Detector
- State: LOW, Input: 0 → Output: 0
- State: LOW, Input: 1 → Output: 1 (transition to HIGH)
- State: HIGH, Input: 1 → Output: 0 (no change)
- State: HIGH, Input: 0 → Output: 0 (transition to LOW)
Key insight: Mealy machines often require fewer states than Moore machines because outputs can change immediately based on inputs, not just on state changes.
Part 3: State Diagrams¶
State diagrams use circles for states and arrows for transitions.
Notation¶
Example: Traffic Light Controller¶
Problem: Design a traffic light that cycles Green → Yellow → Red → Green
State Diagram:
Timer = 30s Timer = 5s
┌──────────────▶┌──────────────┐
│ │ │
│ │ │
│ ┌─────▼─────┐ │
│ │ GREEN │ │
│ └─────┬─────┘ │
│ Timer = 30s │ │
│ │ Timer = 5s │
│ ▼ │
│ ┌─────────┐ │
│ │ YELLOW │──────────┘
│ └────┬────┘
│ │ Timer = 5s
│ ▼
│ ┌─────────┐
│ │ RED │─────────────┐
│ └─────────┘ │
│ │
└────────────────────────────────┘
Timer = 30s
Transition Labels¶
- Moore: Label the arrow with just the input
- Mealy: Label the arrow with "Input/Output"
Example Mealy (button press detector):
1/1 (press) 0/0
┌──────────────▶┌──────────────┐
│ │ Pressed │
│ └──────┬───────┘
│ 0/0 │
│ │
└──────────────────────┘
0/0 (no press)
Part 4: State Tables¶
A state table shows all possible combinations of current state and inputs.
Example: Traffic Light State Table¶
Encoding: - S0 = GREEN - S1 = YELLOW - S2 = RED
State Table:
| Current State | Timer (T) | Next State | Output (Light) |
|---|---|---|---|
| S0 (GREEN) | 0 | S0 (GREEN) | GREEN |
| S0 (GREEN) | 1 | S1 (YELLOW) | GREEN |
| S1 (YELLOW) | 0 | S1 (YELLOW) | YELLOW |
| S1 (YELLOW) | 1 | S2 (RED) | YELLOW |
| S2 (RED) | 0 | S2 (RED) | RED |
| S2 (RED) | 1 | S0 (GREEN) | RED |
Part 5: State Machine Design Process¶
Step-by-Step Process¶
- Define the problem - What inputs, outputs, and states are needed?
- Draw the state diagram - Show all states and transitions
- Create the state table - List all state/input combinations
- Assign binary codes - Each state gets a unique binary pattern
- Choose flip-flop type - JK or D flip-flops are common
- Derive input equations - Use Karnaugh maps or truth tables
- Draw the circuit - Implement with flip-flops and gates
Example: Design a "101" Sequence Detector¶
Problem: Detect the sequence 1-0-1 in a serial input stream.
Step 1: Define states - S0: No 1s detected (initial) - S1: One 1 detected - S2: Sequence 1-0 detected, waiting for final 1 - S3: Sequence 1-0-1 detected (output = 1)
Step 2: State Diagram
Input = 1 Input = 0 Input = 1
┌──────────────▶┌───────────────▶┌──────────────┐
│ │ │ │
│ ┌─────▼─────┐ ┌─────▼─────┐ │
│ │ S0 │ │ S1 │ │
│ │ (initial)│ │ (got '1') │ │
│ └─────┬─────┘ └─────┬─────┘ │
│ Input = 0 │ │Input = 1 │
│ ▼ │ │
│ ┌─────────┐ ▼ │
│ │ S2 │◀──┌─────────┐ │
│ │ (got 10)│ │ S3 │────────┘
│ └─────────┘ │(101 found)│ Output=1
│ └─────────┘ Input=1 (stay)
└───────────────────────────────────────────
Input = 0
Step 3: State Table
| Current State | Input | Next State | Output |
|---|---|---|---|
| S0 | 0 | S0 | 0 |
| S0 | 1 | S1 | 0 |
| S1 | 0 | S2 | 0 |
| S1 | 1 | S1 | 0 |
| S2 | 0 | S0 | 0 |
| S2 | 1 | S3 | 1 |
| S3 | 0 | S2 | 0 |
| S3 | 1 | S1 | 0 |
Step 4: State Encoding - S0 = 00 - S1 = 01 - S2 = 10 - S3 = 11
Part 6: Implementing State Machines¶
Using D Flip-Flops¶
For each flip-flop, determine what D input is needed to achieve the next state.
Deriving Input Equations¶
From the state table, create a truth table for each flip-flop input:
For Q1 (MSB):
| Q1 | Q0 | Input | Q1⁺ | D1 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 |
Simplify using Karnaugh map: D1 = Q1·Q0 + Q1·Input + Q0·Input
Part 7: Practice Problem¶
Problem Statement¶
Design a state machine that monitors a single input button. When the button is pressed three times, turn on an LED.
Requirements: 1. Input: Pushbutton (HIGH when pressed) 2. Output: LED (turns ON after 3 presses) 3. Use Moore machine approach 4. Draw state diagram and create state table
States needed:¶
- S0: No presses counted
- S1: One press counted
- S2: Two presses counted
- S3: Three presses counted (LED ON)
Show Solution
State Diagram (Moore Machine):
Button = 1 Button = 1 Button = 1
┌──────────────▶┌──────────────▶┌──────────────┐
│ │ │ │
│ ┌─────▼─────┐ ┌─────▼─────┐ ┌─────▼─────┐
│ │ S0 │ │ S1 │ │ S2 │
│ │ (0) LED:0│ │ (1) LED:0│ │ (2) LED:0│
│ └─────┬─────┘ └─────┬─────┘ └─────┬─────┘
│ │ │ │
│ │Button=0 │Button=0 │Button=0
│ ▼ ▼ ▼
│ (stay in same state when button not pressed)
│
│Button = 1
│
└───────────────▶┌──────────────┐
│ S3 │
│ (3) LED:1 │
└──────┬───────┘
│
│Button = 0
▼
(reset to S0)
State Table:
| Current State | Button | Next State | LED Output |
|---|---|---|---|
| S0 (0) | 0 | S0 | 0 |
| S0 (0) | 1 | S1 | 0 |
| S1 (1) | 0 | S1 | 0 |
| S1 (1) | 1 | S2 | 0 |
| S2 (2) | 0 | S2 | 0 |
| S2 (2) | 1 | S3 | 0 |
| S3 (3) | 0 | S0 | 1 |
| S3 (3) | 1 | S3 | 1 |
Encoding (2 bits): - S0 = 00 - S1 = 01 - S2 = 10 - S3 = 11
Summary¶
- A state machine has states, transitions based on inputs, and outputs
- Moore machines: outputs depend only on current state
- Mealy machines: outputs depend on state AND inputs
- State diagrams visualize states (circles) and transitions (arrows)
- State tables list current state, inputs, next state, and outputs
- Design process: define states → draw diagram → create table → encode → derive equations → implement
Key Reminders¶
- Start with state diagram to visualize the problem
- Use binary encoding (00, 01, 10, 11) for each state
- Karnaugh maps simplify flip-flop input equations
- Moore machines are often easier to implement (outputs stable after clock)
- Mealy machines can use fewer states
Custom activity — adapted from PLTW Digital Electronics