Finite State Machines (FSMs): Design, Analysis & Applications

What is a Finite State Machine (FSM)?

A Finite State Machine (FSM) is a mathematical model of computation used to design sequential circuits. It consists of:

• A finite number of states (current state of the system).
• Inputs (external signals that trigger transitions).
• Outputs (responses generated based on state and/or inputs).
• State transitions (rules defining how inputs change the current state).
• Initial state (starting state when the system is reset).

FSMs are classified into two types:

1. Moore Machine: Output depends only on the current state.
2. Mealy Machine: Output depends on both current state and inputs.

In the Real World

FSMs are everywhere in digital systems. Here’s how they power apps and services students use daily:

1. eSewa Payment System

   • FSM Idea Used: State-based transaction validation
   • How? When you pay a bill via eSewa, the system follows a Moore-like FSM with states: Unverified → Verified → Processing → Completed → Failed. Each state triggers a different action (e.g., sending an OTP, deducting money, or showing a failure message).
   • Key Transition: The system moves from Verified to Processing only if the OTP matches and funds are available.

2. Pathao Ride Booking

   • FSM Idea Used: Mealy Machine for dynamic pricing
   • How? Pathao’s algorithm adjusts fares based on:
     • Current state (e.g., Low Demand, Peak Hours, Surge Pricing).
     • Input (e.g., number of riders waiting, driver availability).
     • Output (fare multiplier, e.g., 1.5x or 2.0x).
   • Real Example: If you book a ride during Peak Hours (state) and demand is high (input), the fare jumps to 2.0x (output).

3. NTC Traffic Light Control

   • FSM Idea Used: Sequential state transitions for traffic management
   • How? Traffic lights at busy intersections (e.g., Thapathali) use a Moore FSM with states: Green (East-West) → Yellow → Red → Green (North-South) → .... Each state has a fixed duration (e.g., 30 sec green, 5 sec yellow), and sensors (inputs) can trigger early red if no vehicles are detected.

FSM Design Steps

Designing an FSM involves these steps:

1. Define the Problem

• Identify inputs, outputs, and states.
• Example: A vending machine has:
  • Inputs: Coin inserted (0 or 1), Select button (0 or 1).
  • Outputs: Dispense item (0 or 1), Error message (0 or 1).
  • States: IDLE, COIN_INSERTED, ITEM_SELECTED, DISPENSING, ERROR.

2. Draw the State Diagram

• Represent states as circles and transitions as arrows labeled with input/output.
• Example: Vending machine state diagram (see below).

stateDiagram-v2
    [*] --> IDLE
    IDLE --> COIN_INSERTED : Input=1 (Coin)
    COIN_INSERTED --> ITEM_SELECTED : Input=1 (Select)
    ITEM_SELECTED --> DISPENSING : Output=1 (Dispense)
    DISPENSING --> IDLE : Timeout
    COIN_INSERTED --> ERROR : Input=0 (No Coin)
    ERROR --> IDLE : Reset

3. Construct the State Transition Table

• List all states, inputs, next states, and outputs.

4. Assign Binary Codes to States (State Assignment)

• Use binary encoding (e.g., 2-bit for 4 states).
• Example:
  • IDLE = 00
  • COIN_INSERTED = 01
  • ITEM_SELECTED = 10
  • DISPENSING = 11
  • ERROR = 00 (same as IDLE, but with error output).

5. Derive Excitation Tables

• Determine flip-flop inputs (e.g., D, T, JK) for each state transition.
• Example for JK flip-flops:

6. Implement the FSM Using Flip-Flops and Logic Gates

• Use JK/D flip-flops for state storage.
• Design combinational logic for next-state and output functions.
• Example: For the vending machine, use 2 JK flip-flops (Q1, Q0) and combinational circuits for inputs/outputs.

Moore vs. Mealy Machines: Key Differences

FSM Implementation Example: Traffic Light Controller

Problem: Design an FSM for a 3-state traffic light (Green → Yellow → Red → Repeat). States:

• GREEN (East-West)
• YELLOW
• RED (North-South)

Step 1: State Diagram

Step 2: State Transition Table

Step 3: State Assignment (2-bit encoding)

• GREEN = 00
• YELLOW = 01
• RED = 10

Step 4: Excitation Table (JK Flip-Flops)

Step 5: Output Logic

• East-West Green (EW): Q1'Q0' (only GREEN state)
• North-South Green (NS): Q1Q0 (only RED state)

Step 6: Circuit Implementation

FSM Optimization Techniques

1. State Encoding:
   • Use binary, one-hot, or Gray code to minimize hardware.
   • One-hot encoding reduces glitches but uses more flip-flops.

2. State Merging:

   • Combine equivalent states (e.g., two states with identical outputs and transitions).

3. Hazard-Free Design:

   • Use pulse generators or state assignment to avoid race conditions.

Exam Tip

How to Score Full Marks in FSM Questions

1. For Output Sequence Questions:

   • Start from the initial state.
   • Follow the input sequence step-by-step, updating the state and output at each step.
   • Example: Given an FSM and input 001010110110110111, trace each bit and list the output sequence.

2. For Flip-Flop Selection:

   • JK flip-flops are most common in exams (universal, can emulate D/T).
   • If the question asks for D flip-flops, derive the excitation table accordingly.

3. For State Diagrams:

   • Always label states clearly and show transitions with inputs/outputs.
   • Use standard symbols (circles for states, arrows for transitions).

4. For Implementation:

   • Show both flip-flop excitation tables and combinational logic (e.g., K-map for next-state/output functions).
   • Use real IC symbols (e.g., 74LS76 for JK flip-flops) in diagrams.

5. Common Pitfalls:

   • Forgetting to reset the FSM to the initial state.
   • Misassigning outputs (Moore vs. Mealy confusion).
   • Not showing all possible transitions in the state table.