Finite State Machines & Control Logic

Ground-up guide to CMOS circuit design — transistors, gates, delay, power, memory, datapath and test

The Brains That Control a Chip

Datapaths do the heavy math. But something has to tell them what to do and when. That something is the control logic, and its most common form is the finite state machine (FSM). An FSM is a circuit that remembers what step it is on and decides the next step from that plus its inputs. Almost every chip is full of them. This chapter explains FSMs in plain words: states and transitions, the two classic styles, how they are built from flip-flops and gates, state encoding, and the timing and reset issues that trip people up.

A finite state machine has a small set of states — distinct situations it can be in. At any moment it is in exactly one state. On each clock edge it may move to another state, depending on its current state and its inputs. It also produces outputs that control the rest of the chip. Think of a traffic light: states are green, yellow, red. It moves through them in order, on a timer. That is an FSM. A chip uses the same idea to sequence reads, writes, handshakes, and operations.

There are two ways an FSM can make its outputs. A Moore machine sets its outputs from the current state alone. The output depends only on where you are, not on the inputs right now. This makes outputs steady and glitch-free, but they react one cycle later. A Mealy machine sets its outputs from the current state and the inputs together. This reacts faster — outputs can change the moment an input changes — but the outputs can be less stable and may glitch.

Worked example — reaction timing

An input asserts mid-cycle. A Moore output reflects it after the next clock edge; a Mealy output reflects it immediately.

Moore: input → (wait for clock edge) → output next cycle
Mealy: input → output same cycle (combinational path)

If you need an instant response, Mealy wins. If you need a clean, predictable output, Moore wins. Designers pick per situation.

How an FSM Is Built

An FSM is made of three pieces. A state register (flip-flops) holds the current state. A next-state logic block (gates) computes the next state from the current state and inputs. An output logic block (gates) computes the outputs. On each clock edge, the state register loads the next state. Then the logic settles, computing the following next state and the outputs. The loop repeats every cycle. So an FSM is just registers plus two clouds of combinational logic, wired in a loop.

Worked example — flip-flops needed

A machine has 6 states. How many flip-flops hold the state in binary?

need n where 2^n ≥ 6 → 2^3 = 8 ≥ 6 → n = 3 flip-flops

Three flip-flops cover six states (with two codes spare). Encoding choice changes this count, as the next section shows.

State Encoding

The states must be given binary codes. The choice of codes matters for speed and area. Binary encoding uses the fewest flip-flops (log of the state count), saving registers but needing more next-state logic. One-hot encoding uses one flip-flop per state, with only a single bit high at a time. It uses more flip-flops but makes the logic simple and fast, because checking a state is just reading one bit.

Worked example — encoding trade

A 16-state machine.

binary:  log2(16) = 4 flip-flops, complex decode
one-hot: 16 flip-flops, trivial decode (one bit per state)

Binary saves 12 flip-flops; one-hot makes the logic faster and easier to read. The right pick depends on whether area or speed matters more here.

Timing and the Critical Loop

The FSM's speed is set by its longest loop: from the state register, through the next-state logic, and back to the register input, all within one clock period. If that path is too slow, the machine cannot run at the target clock. Complex next-state logic lengthens this path. So very involved control may be split across more states (simpler logic per step) or pipelined. One-hot encoding often helps, because its next-state logic is shallow. Watching this loop is the heart of FSM timing.

Worked example — FSM clock limit

Next-state logic delay is 0.7 ns, flip-flop overheads (clock-to-output plus setup) total 0.2 ns.

minimum period = 0.7 + 0.2 = 0.9 ns
max clock ≈ 1 / 0.9 ns ≈ 1.1 GHz

To go faster, simplify the next-state logic or split the work into more states.

Reset and Safe States

An FSM must start in a known state. Without a reset, the flip-flops power up randomly and the machine could begin in nonsense. So every FSM has a reset that forces it into a defined start state. There is a subtler trap. With binary encoding, some codes may be unused (six states in three flip-flops leaves two spare codes). If noise ever pushes the machine into an unused code, it could lock up. Safe designs add transitions from every unused code back to a known state, so the machine always recovers.

Interview Q&A

states, moves between states on each clock edge based on its current state and inputs, and produces outputs that control the rest of the chip. A traffic light cycling green-yellow-red is a everyday example.

depend only on the current state, making them steady and glitch-free but reacting a cycle later. A Mealy machine's outputs depend on the state and the inputs together, reacting immediately but able to glitch — you choose per situation between stability and speed.

state logic (gates) computing the next state from the current state and inputs, and output logic (gates) computing the outputs. Each clock edge loads the next state, and the loop repeats.

the state count) but needs more complex next-state logic. One-hot uses one flip-flop per state with a single bit high, costing more registers but giving simple, fast logic since checking a state reads just one bit.

the next-state logic, and back to the register, all within one clock period. Complex next-state logic lengthens this path, so the fix is to simplify it, split work across more states, or use one-hot encoding for shallower logic.

the machine could start in nonsense, so a reset forces a known start state. With unused state codes (e.g. spare codes in binary encoding), noise could push the machine into a dead code, so safe designs route every unused code back to a known state to guarantee recovery.

Key Takeaways

• A finite state machine is in one state at a time and transitions each clock edge from state plus inputs.
• Moore outputs depend on state only (steady); Mealy outputs depend on state + inputs (faster, can glitch).
• An FSM is a state register plus next-state logic and output logic wired in a loop.
• Binary encoding saves flip-flops; one-hot gives simpler, faster logic — pick by area vs speed.
• Always provide a reset to a known state and route unused codes back to safety; watch the state- loop timing.