Finite State Machines

ENGR 445: Embedded System Design

Understanding and Implementing FSMs in C++

What is a Finite State Machine?

A Finite State Machine (FSM) is a computational model that can be in exactly one of a finite number of states at any given time.

Key Concepts

State: A distinct condition or situation the system can be in
Transition: Movement from one state to another based on inputs/events
Input: External events or data that trigger transitions
Action: Operations performed in a state or during a transition

                Real-World Examples:
                Traffic lights (Red → Yellow → Green)
Vending machines (Idle → Selecting → Dispensing)
Door locks (Locked → Unlocked)
Protocol handlers (Waiting → Receiving → Processing)

            

Why Use FSMs in Embedded Systems?

Benefits

Clarity: Clear visual representation of system behavior
Maintainability: Easy to modify and extend
Predictability: Deterministic behavior - same input always produces same output
Testability: Each state can be tested independently
Documentation: FSM diagrams serve as living documentation

Embedded Systems Context:
FSMs are ideal for embedded systems because they:

Use minimal memory (just state variables)
Execute quickly (simple switch statements)
Handle interrupts and events cleanly
Scale well from simple to complex behaviors

Example Problem: Number Summer

Problem Statement

Design a system that:

Reads a stream of integer numbers from input
Accumulates (sums) all numbers received
When the value 9 is received, output the sum
Reset and start over for the next sequence

Example

Input:  3, 5, 2, 9, 1, 4, 7, 9, ...
        ─────────┘     └─────────┘
         sum = 10       sum = 12

Output: 10            12

                Think: What states do we need? What transitions occur? What actions happen in each state?
            

FSM Diagram: Number Summer (Moore Machine)

State Descriptions (Moore Machine)

State	Description	Output/Action
IDLE	Waiting for first input	sum = input (initialize)
ACCUMULATING	Reading and summing numbers	sum += input (if not terminator)
OUTPUTTING	Displaying result	print sum, reset sum (output)

Moore Machine: Outputs are determined by the current state only. Each state has an associated action that executes while in that state.

C++ Implementation Strategy

Key Components

1. Define States Using Enum

enum State {
    STATE_IDLE,
    STATE_ACCUMULATING,
    STATE_OUTPUTTING
};

2. State Variables

State current_state = STATE_IDLE;
State next_state = STATE_IDLE;
int sum = 0;

3. Main Loop Structure (Moore Machine)

while (true) {
    // Execute current state logic
    switch (current_state) {
        case STATE_IDLE:
            // State action (output based on state)
            // Next state logic (based on input)
            break;
        // ... other states
    }
    
    // Update state at end of iteration
    current_state = next_state;
}

Moore Machine Pattern: Actions execute based on the current state, then next state is determined by examining inputs.

Complete C++ Implementation

#include <iostream>
using namespace std;

// Define the states
enum State {
    STATE_IDLE,
    STATE_ACCUMULATING,
    STATE_OUTPUTTING
};

int main() {
    // State variables
    State current_state = STATE_IDLE;
    State next_state = STATE_IDLE;
    
    // Data variables
    int sum = 0;
    int input;
    
    cout << "Enter numbers (9 to output sum, Ctrl+D to exit):" << endl;
    
    // Main FSM loop
    while (true) {
        // Read input at top of loop
        if (!(cin >> input)) {
            break;  // Exit on EOF
        }
        
        switch (current_state) {
            case STATE_IDLE:
                // State Action: Initialize with first value (Moore output)
                sum = input;
                
                // Next State Logic: Examine input
                if (input != 9) {
                    next_state = STATE_ACCUMULATING;
                } else {
                    // Edge case: first input is the terminator
                    next_state = STATE_OUTPUTTING;
                }
                break;
                
            case STATE_ACCUMULATING:
                // State Action: Add to sum (Moore output)
                if (input != 9) {
                    sum += input;
                    // Next State Logic: Stay in ACCUMULATING
                    next_state = STATE_ACCUMULATING;
                } else {
                    // Don't add the terminator
                    // Next State Logic: Move to OUTPUTTING
                    next_state = STATE_OUTPUTTING;
                }
                break;
                
            case STATE_OUTPUTTING:
                // State Action: Display result (Moore output)
                cout << "Sum: " << sum << endl;
                sum = 0;  // Reset for next sequence
                
                // Next State Logic: Always return to IDLE
                next_state = STATE_IDLE;
                break;
        }
        
        // Update state at end of loop iteration
        current_state = next_state;
    }
    
    return 0;
}

Understanding Each State

STATE_IDLE

Purpose: Entry point, start new sequence
State Action (Moore Output): Initialize sum with first input value
Next State Logic: If input ≠ 9 → ACCUMULATING, else → OUTPUTTING

STATE_ACCUMULATING

Purpose: Collecting numbers and building the sum
State Action (Moore Output): Add current input to sum (skip if input == 9)
Next State Logic: If input ≠ 9 → stay in ACCUMULATING, else → OUTPUTTING

STATE_OUTPUTTING

Purpose: Display the accumulated result
State Action (Moore Output): Print sum, then reset sum to 0
Next State Logic: Always → IDLE (ready for next sequence)

                Moore Machine Key Point: Each state's action (output) executes based on being in that state, not on the transition. Actions are associated with states, not transitions.
            

Example Execution Trace

Input	Current State	State Action	Sum	Next State
3	IDLE	sum = 3	3	ACCUMULATING
5	ACCUMULATING	sum += 5	8	ACCUMULATING
2	ACCUMULATING	sum += 2	10	ACCUMULATING
9	ACCUMULATING	(skip - terminator)	10	OUTPUTTING
(awaiting next)	OUTPUTTING	print "Sum: 10", reset	0	IDLE
1	IDLE	sum = 1	1	ACCUMULATING
4	ACCUMULATING	sum += 4	5	ACCUMULATING
7	ACCUMULATING	sum += 7	12	ACCUMULATING
9	ACCUMULATING	(skip - terminator)	12	OUTPUTTING
(awaiting next)	OUTPUTTING	print "Sum: 12", reset	0	IDLE

Note: This is a practical Moore machine - actions are determined by the state, but may conditionally process the input. The key is that outputs/actions are associated with states, not transitions.

FSM Best Practices in C++

✅ Do's

Use enum or enum class for states (type-safe)
Keep action logic and next-state logic separate within each case
Always update current_state = next_state at the end of loop
Initialize next_state explicitly in every case
Document state transitions with comments
Draw the FSM diagram before coding

❌ Don'ts

Don't modify current_state directly inside the switch
Don't use magic numbers for states - always use named enums
Don't forget the break statement in switch cases
Don't create overly complex states - break them down
Don't leave transition conditions ambiguous

Key Takeaway: FSMs provide a structured, maintainable way to handle complex control flow in embedded systems. The pattern of enum + switch + state variables is efficient and scales well.

FSM Variations

Moore vs. Mealy Machines

Type	Moore Machine	Mealy Machine
Output depends on	Current state only	Current state AND input
When actions execute	On entering a state	During transitions
Code pattern	Actions at start of case	Actions in transition logic

Our Example: The Number Summer is a Moore machine because outputs (printing sum, accumulating, resetting) are determined by which state we're in, not by the input that caused the transition.

Extensions You Can Try

Add a state to compute average instead of sum
Use different terminator values (e.g., negative numbers)
Add error handling for invalid inputs
Implement timeout states using timers
Create nested FSMs for complex behaviors

Summary

What We Learned

✓ Finite State Machines model systems as discrete states
✓ Moore machines associate actions with states (outputs determined by state)
✓ FSMs are ideal for embedded systems - efficient and clear
✓ Implementation pattern: enum + switch + state variables
✓ Each state case handles actions and determines next state
✓ Update current_state = next_state at end of loop

Key Implementation Pattern (Moore Machine)

enum State { /* define states */ };
State current_state = INITIAL_STATE;
State next_state = INITIAL_STATE;

while (running) {
    switch (current_state) {
        case STATE_A:
            // 1. State action/output (determined by being in STATE_A)
            doStateAction();
            
            // 2. Determine next_state based on conditions
            if (condition) {
                next_state = STATE_B;
            }
            break;
        case STATE_B:
            // ...
            break;
    }
    current_state = next_state;  // Update at end
}

Next Steps: Practice by implementing FSMs for common embedded scenarios: button debouncing, protocol handlers, LED sequences, menu systems.