Finite state machine design is a way to model systems that move through a limited number of states based on inputs and clock timing. This cheat sheet helps students organize FSM problems from a written specification into a working diagram, table, and logic design. It is useful for digital electronics, robotics, embedded systems, and computer engineering projects where behavior must be predictable.
The most important ideas are states, transitions, inputs, outputs, reset behavior, and the next-state rule. A Moore machine makes outputs depend only on the current state, while a Mealy machine makes outputs depend on the current state and inputs. A complete FSM design usually includes a state diagram, state table, state encoding, flip-flop equations, and output logic.
Key Facts
- An FSM is defined by the set FSM = {states, inputs, outputs, transition rules, initial state}.
- The next-state function is written as next state = f(current state, inputs).
- For a Moore machine, output = g(current state), so outputs change only when the state changes.
- For a Mealy machine, output = g(current state, inputs), so outputs can change immediately when inputs change.
- The minimum number of flip-flops needed for N states is n = ceiling(log2(N)).
- With n flip-flops, the maximum number of binary-encoded states is 2^n.
- A state table must list every valid current state and input combination with a next state and output.
- A reset state gives the FSM a known starting condition, usually written as reset = 1 means state becomes S0.
Vocabulary
- Finite State Machine
- A digital system model that can be in one state at a time and changes state based on inputs and rules.
- State
- A named condition or mode of the system, such as idle, count, wait, or done.
- Transition
- A directed change from one state to another caused by an input condition or clock event.
- Moore Machine
- An FSM in which outputs depend only on the current state.
- Mealy Machine
- An FSM in which outputs depend on both the current state and the current inputs.
- State Encoding
- The assignment of binary values to state names so flip-flops can store the current state.
Common Mistakes to Avoid
- Leaving out input cases is wrong because an FSM must define what happens for every valid current state and input combination.
- Mixing Moore and Mealy outputs is wrong because Moore outputs are tied to states, while Mealy outputs are tied to transitions or input conditions.
- Using too few flip-flops is wrong because n flip-flops can store only 2^n states, so 5 states require ceiling(log2(5)) = 3 flip-flops.
- Forgetting the reset state is wrong because real hardware needs a known starting state after power-up or restart.
- Changing state without a clock in a synchronous FSM is wrong because the state register should update only on the active clock edge.
Practice Questions
- 1 An FSM has 6 states. What is the minimum number of flip-flops needed to encode the states?
- 2 A machine has 3 flip-flops. What is the maximum number of binary state codes it can represent?
- 3 For a Moore FSM with states S0, S1, and S2, the output is 1 only in S2. What is the output when the current state is S1?
- 4 A traffic light controller changes outputs only after entering a new light state. Explain why this design is better modeled as a Moore machine than a Mealy machine.