Finite State Machines Overview

Finite State Machines (FSM)

Definition

  • Finite State Machine (FSM): A behavior model with a finite number of states used to simulate sequential logic and control execution flow.
  • Components of FSM:
    • Inputs: Set of signals to process.
    • States: Finite number of conditions in which the FSM can exist.
    • Transition Function: Dictates how the FSM moves from one state to another.
    • Initial State: The state where the FSM begins its operation.
    • Output Events: Specifies outputs based on current state and transitions.

Applications

  • Commonly used in:
    • Sequence detectors
    • Vending machines
    • Video games
    • Traffic lights

Types of FSM

  • Moore Machine: Outputs depend solely on the current state.
  • Mealy Machine: Outputs depend on both the current state and input.
    • Mealy machines generally have fewer states than Moore machines but react faster to inputs.

Comparison: Mealy vs. Moore Machines

Mealy Machine:

  • Output depends on the present state and present input.
  • Changes in output can occur immediately when inputs change.
  • Requires more states generally due to input influence on output.

Moore Machine:

  • Output depends only on the present state.
  • Output changes only on state transitions, often leading to one clock cycle delay.
  • generally requires more logic for state output decoding.

Sequence Detection in FSM

  • Types of execution flow patterns:
    • Non-overlapping: Sequence matches exactly and resets after detection.
    • Overlapping: Sequence can overlap with the next sequence detection.
  • Detection Methodology:
    • Moore FSM requires one more state than the number of bits to be detected.
    • Mealy FSM requires the same number of states as the number of bits to detect.

State Transition Diagram

  • Models how states transition in an FSM for both overlapping and non-overlapping patterns.
  • Typically includes:
    • Initial state representation.
    • State transition rules based on inputs.

FSM Design Rules

  • Moore Machine:

    • Non-overlapping:
    • Compare the last bit with the corresponding state.
    • Transition to the state if matched; reset if not.
    • Overlapping:
    • Compare multiple bits to transition into states.
    • Requires cascading comparisons for non-matching sequences.

  • Mealy Machine follows similar principles but outputs change sooner as they incorporate inputs into their state decision processes.

Verilog Implementation for Sequence Detection

  • Moore FSM Code Sample:
module moore_110_seq_detector(
 input wire clk,
 input wire rst,
 // Other parameters
);

  // State definitions
  parameter S=2'b00, got1=2'b01, got11=2'b10, got110=2'b11;
  // Logic structure and assignments
endmodule

Design Considerations

  • Utilize FSM to simplify designs in digital logic, keeping track of various states and transitions logically.
  • Combine with additional digital elements like multipliers, registers for complete implementations in applications such as GCD processors and signal processing tasks in FPGAs.