Introduction to State Machines

A finite state machine (FSM) is a digital system that can be in one of a finite number of states at any time. It transitions between states based on inputs and a clock signal, and produces outputs based on the current state (and possibly inputs). FSMs are the key to designing any digital system with sequencing behavior, from traffic lights to CPU control units.

Objectives

• Define states, transitions, inputs, and outputs in an FSM
• Draw and interpret state diagrams
• Understand the general FSM structure: combinational logic + state register
• Distinguish between Moore and Mealy machines (introduction)
• Design simple FSMs for real-world problems

Key Takeaways

• FSM = states + transitions + inputs + outputs, synchronized by a clock
• State diagrams use circles (states) and arrows (transitions)
• Hardware: state register (flip-flops) + next-state logic + output logic
• Number of flip-flops: ceil(log₂(number of states))
• FSMs are the foundation of all digital controller design

Applications

• Protocol Controllers: USB, Ethernet, SPI all use FSMs for protocol handling.
• Vending Machines: Accept coins, track total, dispense product.
• Traffic Lights: Sequencing through green-yellow-red with pedestrian requests.
• CPU Control Units: The fetch-decode-execute cycle is an FSM.

Practice Problems

Problem 1: A traffic light cycles Green→Yellow→Red→Green. How many states does this FSM have?

Problem 2: Draw a state diagram for a coin-operated turnstile (states: Locked, Unlocked).

Problem 3: How many flip-flops are needed to encode 5 states?

Problem 4: What is the difference between the next-state logic and the output logic in an FSM?