JKoch notes

lecture_EE1D1_lec7_FSM_2025-10-07

4 min read

📌 Overview

This lecture provides a comprehensive introduction to Finite State Machines (FSMs), covering their design, implementation, and analysis. We will explore fundamental concepts through practical examples, including a traffic light controller and a candy dispenser. A key distinction between Moore and Mealy FSM models will be detailed, along with a step-by-step guide to implementing FSMs using state tables, Karnaugh maps, and various logic gates.

🎯Learning Objectives

  • Understand the fundamental principles of Finite State Machines.
  • Differentiate between Moore and Mealy FSMs.
  • Design and analyze FSMs for real-world applications.
  • Implement FSMs using state tables, Karnaugh maps, and logic gates.
  • Develop a SystemVerilog model and test bench for an FSM.

💡Key Concepts & Definitions

  • Finite State Machine (FSM): A computational model consisting of a finite number of states, transitions between those states, and actions. It’s used to design sequential logic circuits.
  • State: A specific condition in which an FSM can be.
  • Transition: A change from one state to another, triggered by an input.
  • Moore Machine: An FSM where the output depends only on the current state.
  • Mealy Machine: An FSM where the output depends on both the current state and the current input.
  • State Diagram: A graphical representation of an FSM, showing states and transitions.
  • State Table: A tabular representation of an FSM, detailing state transitions and outputs.
  • Karnaugh Map (K-map): A method to simplify Boolean algebra expressions, often used in FSM design to derive logic for next states and outputs.

➗ Formulas

  • Next State Logic: S' = f(S, I) where S' is the next state, S is the current state, and I is the input.
  • Output Logic (Moore): O = g(S) where O is the output.
  • Output Logic (Mealy): O = h(S, I)

✍️ Notes

FSM Design Example: Traffic Light Controller

A classic example of an FSM is a traffic light controller at an intersection.

  1. Define Inputs and Outputs:

    • Inputs: CLK, Reset, TA, TB (traffic sensors).
    • Outputs: LA, LB (traffic lights with Green, Yellow, Red states).

  2. Create State Diagram: Visualize the states and transitions. For a traffic light, this would involve states for Green, Yellow, and Red lights for each direction and the conditions (sensor inputs) that cause transitions.

    graph TD
    S0 -- TA' --> S0;
    S0 -- TA --> S1;
    S1 --> S2;
    S2 -- TB' --> S2;
    S2 -- TB --> S3;
    S3 --> S0;

    subgraph Legend
        direction LR
        S0[S0: LA=Green, LB=Red]
        S1[S1: LA=Yellow, LB=Red]
        S2[S2: LA=Red, LB=Green]
        S3[S3: LA=Red, LB=Yellow]
    end

  3. Develop State Transition and Output Tables: Convert the state diagram into a tabular format. This includes encoding the states into binary values.

Current State (S)Inputs (TA, TB)Next State (S’)
S01XS0
S00XS1
S1XXS2
S2X1S2
S2X0S3
S3XXS0

  1. Derive Logic Equations: Use K-maps to derive Boolean expressions for the next state and output logic from the tables.

  2. Implement the Circuit: Draw the schematic using flip-flops (for state memory) and combinational logic gates (for next state and output logic).

Moore vs. Mealy FSMs

The key difference lies in how the output is generated.

FeatureMoore MachineMealy Machine
OutputDepends only on the current state.Depends on the current state and input.
TimingOutput is synchronized with the clock.Output can change asynchronously with inputs.
State CountOften requires more states.Often requires fewer states.
ExampleSnail smiles when it has seen “01”.Snail smiles when it sees a “1” after a “0”.

Snail Crawler Example:

  • Moore: The FSM enters a specific “smile” state (S2) after the sequence “01” is detected. The output Y is 1 only in this state.
  • Mealy: The FSM transitions from a “seen 0” state (S1) to the initial state (S0) when the input is 1, and the output is 1 during that transition.

FSM Implementation Steps (Courselab Assignment)

  1. State Table Creation: List all current states, inputs, next states, and outputs.
  2. Karnaugh Maps: Create K-maps for each next-state bit and each output bit to derive simplified logic equations.
  3. Gate Implementation:
    • NAND: Use Sum-of-Products (SOP). AB+CD = ((AB)'(CD)')'
    • NOR: Use Product-of-Sums (POS). (A+B)(C+D) = ((A+B)'+(C+D)')'
    • AOI (AND-OR-Invert): Implement the inverted output using SOP.
    • OAI (OR-AND-Invert): Implement the inverted output using POS.
  4. Circuit Diagram: Draw the final schematic using D-flip-flops and the derived gate logic.
  5. SystemVerilog and Test Bench: Model the circuit in SystemVerilog and write a test bench to verify its functionality by simulating all state transitions.

🔗 Resources

❓ Post lecture

  • How does the choice between a Moore and Mealy FSM affect the timing and complexity of a digital circuit?
  • What are the advantages of using K-maps for logic simplification in FSM design?
  • In what scenarios would an AOI or OAI gate be more efficient than standard AND/OR gates?

📖 Homework

  • Reading: “Digital Design and Computer Architecture,” Section 3.4.
  • Assignments: Complete the Gated Practice Assignment for Lecture 7.

Graph View

Backlinks