Skip to content
Tutorials Center
My learning

Topics

Lesson 40 of 57 ยท State Machines

State Machine Patterns and Pitfalls

Learn the practical side of state machines: one-hot versus binary encoding, unreachable states, reset, debouncing, edge detectors and synchronized, glitch-free outputs.

A state machine that works on paper can still fail on a real board. The table is right, the equations are right, and yet the circuit locks up after power-on, fires twice from a single button press, or misbehaves once a day when an input changes at an unlucky moment. These failures come from details that the textbook recipe in Designing a Sequential Circuit leaves out.

This lesson collects the patterns that experienced designers apply almost automatically: how to encode states, how to handle illegal states, how to reset, how to clean noisy and asynchronous inputs, and how to keep outputs free of glitches. Each pattern is small, and each one prevents a whole family of bugs.

Six habits of solid FSMs

Pick an encoding Binary is small, one-hot is fast.
Plan for leftovers Unused codes must lead home.
Always reset A known start state at power-up.
1 / 2

State encoding: binary versus one-hot

State encoding is the choice of bit patterns for the states. Two styles dominate.

  • Binary (dense) encoding: n states use ceil(log2 n) flip-flops. It is compact, but the next-state and output logic has to decode and encode the bit patterns, so the logic gets deeper as the machine grows.
  • One-hot encoding: n states use n flip-flops, and exactly one of them is 1 at any time. The state is "which flip-flop is hot". Decoding is free (a state is just one wire) and next-state logic is a simple OR of a few AND terms, so it is fast and easy to write. Flip-flops are plentiful in FPGAs, so this is the usual default there.

Gray encoding, where neighboring states differ in one bit, is a third option. It reduces glitching on the state outputs when the machine steps through a long linear sequence.

For one-hot, each flip-flop's input is "I am entered from some state while the right input is present": D_j = OR (s_i AND input condition) for every transition i -> j. Below, the 1011 detector from the previous lesson runs in both encodings and the outputs are compared on all streams.

Python Binary and one-hot encodings give the same behavior

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

One-hot machines spend flip-flops to save logic depth, and they have a catch: with n flip-flops there are 2^n bit patterns but only n legal ones. A single upset can create a pattern with zero or two hot bits, which the logic never expects. That brings us to unused states.

Unused and unreachable states

Two different problems share similar names.

  • An unreachable state is one that the machine can never enter from the reset state. It is usually a sign of a design bug (a typo in the table) or leftover work. Removing it makes the machine smaller. You can find unreachable states by starting at the reset state and following all transitions (a breadth-first search).
  • An unused code is a flip-flop pattern that is not assigned to any state, such as 11 in a three-state machine with two flip-flops. It is normally unreachable too, until something strange happens: a power-up glitch, noise, or radiation flips a bit. If such a code has no sensible next state, the machine can lock up forever.

A robust design makes every unused code lead back to the reset state or to another legal state. This is called a self-correcting or self-starting design. The program below finds unreachable states in a table and compares a lock-up design with a self-correcting one.

Python Finding unreachable states and recovering from illegal codes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both counters behave identically from reset, which is why a simulation that starts at reset never reveals the bug. The difference appears only in the unlikely case, so you have to look for it on purpose.

Reset

Every FSM needs a way to reach its start state. Two common styles:

  • Synchronous reset: the reset signal is just another input that overrides the next state and takes effect at the next clock edge. It fits the synchronous design style and is easy to time.
  • Asynchronous reset: the reset pin of the flip-flops forces them to the start code at once, without waiting for the clock. This is useful when the clock may not be running yet, but releasing the reset close to a clock edge can cause timing trouble, so the release should be synchronized.

Reset is also what makes simulation meaningful. Without it, flip-flops start in an unknown state and the simulation cannot predict anything. In hardware, an FPGA configuration often sets initial values for the flip-flops, but chips without that feature depend on a reset pin.

Cleaning the inputs

Real inputs are messy. A mechanical switch does not go cleanly from 0 to 1; it bounces for a few milliseconds. And inputs from another clock domain, or from a human, change at any moment, not neatly between your clock edges.

Debouncing

A debouncer accepts a new level only after the input has stayed at that level for several samples in a row. As a small FSM: keep the accepted output and a counter. If the sample equals the output, reset the counter. If it differs, count up, and when the counter reaches N copy the sample to the output. In hardware, N corresponds to a few milliseconds of clock cycles.

Edge detection

Often you do not want the level of a button but one pulse per press. An edge detector stores the previous sample in a flip-flop and produces x AND (NOT previous) for a rising edge, or (NOT x) AND previous for a falling edge. The pulse lasts exactly one clock cycle, which makes it the perfect trigger for a state machine: press once, advance one step.

Python Debounce a bouncing button, then detect the press

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The raw signal contains several rising edges for one physical press, so a state machine fed directly from it would advance several times. After the debouncer there is exactly one clean level change and one press pulse. The price is latency: the clean signal follows the real press a few samples late.

Synchronizing asynchronous inputs

If an input can change at any time relative to your clock, a flip-flop can sample it while it is changing and enter a metastable state (neither 0 nor 1) that may resolve late or wrongly. The standard defense is a two-flip-flop synchronizer: the first flip-flop samples the input and may go metastable; it has a full clock period to settle before the second one passes the value on to the rest of the design. You will study why this works in Timing, Clock Skew and Metastability. The rule for FSM design is simple: never feed an asynchronous signal straight into next-state logic. Pass it through a synchronizer first, and then through a debouncer or edge detector if needed.

Glitch-free outputs

Combinational logic can briefly show wrong values while its inputs settle, which is the topic of hazards. A Moore output built from the state register is steady during the cycle, apart from small glitches when several state bits change at once. A Mealy output also follows the inputs, so whatever happens on an input shows on the output. The cure is to put a register on the output: capture the combinational value at the clock edge and send out the stored value. The downstream circuit then sees one clean value per cycle, delayed by one clock period.

Python A combinational glitch versus a registered output

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The combinational output shows a spurious pulse in cycle 1, while the registered output stays clean. The glitch would be captured only if it happened right at the clock edge, which is why inputs are also kept stable around the edge (setup and hold times). Registering costs one cycle of latency; in exchange, the rest of the system sees clean data.

A short checklist

  • Choose an encoding on purpose (binary for small and slow, one-hot for fast logic and FPGAs).
  • Give every unused code a safe next state, and remove unreachable states.
  • Provide a reset and decide whether it is synchronous or asynchronous.
  • Debounce mechanical inputs, detect edges for one-cycle pulses, and synchronize anything asynchronous.
  • Register outputs that leave the module.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A machine has 16 states. How many flip-flops does one-hot encoding use?

    One-hot uses one flip-flop per state, so 16 flip-flops, compared with 4 for binary encoding.
  2. 2. What is the main danger of an unused flip-flop code?

    If an unused code has no defined way back to a legal state, a noise or power-up upset can leave the machine stuck. A self-correcting design maps every unused code to a legal state.
  3. 3. Which expression gives a one-cycle pulse on a rising edge of x, with 'prev' the registered previous value?

    A rising edge means x is 1 now and was 0 one cycle ago: x AND NOT prev. The mirrored expression NOT x AND prev detects a falling edge.
  4. 4. Why should an asynchronous input pass through two flip-flops before it reaches the FSM?

    The first flip-flop may sample the signal while it is changing and go metastable. The second one samples it a full cycle later, when it has almost certainly settled.
  5. 5. What does registering an FSM output cost, and what does it buy?

    The output flip-flop holds the value captured at the clock edge for the whole next cycle, so downstream logic never sees the combinational glitches, at the price of one cycle of delay.

Summary

  • Binary encoding minimizes flip-flops; one-hot uses one flip-flop per state and gives shallow, simple logic, with 2^n - n illegal codes to worry about.
  • Unreachable states can be found by search from the reset state; unused codes must lead back to a legal state so the machine cannot lock up.
  • Every FSM needs a reset; asynchronous reset releases should be synchronized.
  • Debounce mechanical inputs with a counter, turn levels into single-cycle pulses with an edge detector, and pass asynchronous inputs through a two-flip-flop synchronizer.
  • Registering outputs removes combinational glitches at the cost of one cycle of latency.

Next: ROM, RAM and Memory Organization.