State machines
A set of states, a rule for moving between them, and outputs: the pattern behind every controller.
Circuits that remember where they are
Every circuit in this stage so far has been a circuit with a memory: a register remembers a value, a counter remembers how far it has counted. There is a general way to describe any such circuit, and it is worth learning because engineers use it for everything from traffic lights to the control unit of a processor.
A finite state machine has three parts. A fixed set of states: the situations the machine can be in, of which it is always in exactly one. A rule for the next state: given the state it is in and the input it sees, which state it moves to on the clock edge. And outputs: what the machine says to the outside world. "Finite" just means the list of states is fixed in advance and there are only so many of them. Each move from one state to another is called a transition.
You have already built one. A counter is a state machine with no input at all: its states are the counts, every state has one arrow to the next, and the clock edge takes it. A traffic light is one with a handful of states, red, red and amber, green, amber, and a timer telling it when to move on. A vending machine is one whose states are how much money has been put in so far, with a coin as the input and "release the item" as an output.
Two pictures of the same thing
A machine is usually drawn as a state diagram: one circle per state, and one arrow per transition, labelled with the input that causes it. An arrow from a state back to itself means "stay here". The very same information can be written as a state table: one row for each combination of present state and input, giving the next state and the output. The diagram is easier to think with; the table is what you build the circuit from. They are two views of one thing, and you should be able to turn either into the other.
Here is a real one to drive. It watches a stream of bits, one per clock, and raises its output z for one clock after it has seen the bits 1, 0, 1 arrive in order. Its four states are how much of the pattern it has seen so far. Press 1, 0, 1 and watch.
Notice that the machine never stores the bits themselves. It only remembers how much of the pattern the recent input could still be part of. After 1, 0, 1 it is in S3, and if another 1 arrives it goes to S1, "seen 1", because that final 1 might be the start of the next 101. That is what a state is: a summary of the past that is just enough for the future.
Worked example. The detector starts in S0 and receives 1, 0, 1, 1. Which states does it pass through, and when is z 1?
Follow the table one bit at a time: from S0 on a 1 it goes to S1; from S1 on a 0 it goes to S2; from S2 on a 1 it goes to S3; from S3 on a 1 it goes to S1. The output belongs to the state, and only S3 (seen 101) has z = 1, so z is 1 for the one clock cycle the machine spends in S3, which is the cycle after the third bit arrived. It ends in S1, seen 1, with z = 0.
Moore and Mealy
The detector above is a Moore machine: its output depends on the state alone. The output is written inside each circle, it changes only when the state changes, on a clock edge, and it holds steady for a whole cycle. The other kind is a Mealy machine, whose output depends on the state and the current input. Its outputs are written on the arrows, as input/output, and they can change the moment an input does.
The same detector as a Mealy machine needs only 3 states, because it can raise z on the very arrow that completes the pattern, from "seen 10" on a 1, instead of needing a fourth state to be in. It also flags the pattern a cycle earlier. The price is an output that can flicker while the input is settling, which a Moore output never does. Either kind can be turned into the other; which you choose depends on whether you would rather have fewer states or a steadier output.
Why?: why bother with a formal description?
Because once a design is a state table, the rest is mechanical. The next lesson turns a table into flip-flops and gates by a fixed procedure, and a test can check every row. Controllers written as a vague pile of conditions are where bugs live; controllers written as state machines can be drawn, checked and explained.
Common mistake: a state for every input, or a state for every bit seen
Beginners either make far too many states, one for every possible input history, or too few, forgetting a situation the machine really must tell apart. The test is always the same: two histories need different states only if the machine must behave differently after them. The detector treats "seen 1" and "seen 1, 1" as the same state, because in both cases the next useful bit is a 0.
What to remember
- A finite state machine is a fixed set of states, a next-state rule based on the current state and input, and outputs.
- The state diagram (circles and arrows) and the state table (one row per state and input) hold the same information.
- A state summarises the past: it holds only what the machine needs to decide what to do next.
- Moore: output from the state alone, steady for a cycle. Mealy: output from state and input, faster and often fewer states.
- A counter is a state machine with no input; a controller is one with several.
Check yourself
Get 5 right in a row and the lesson is done. A wrong answer costs the run, not the lesson.
Starting in S0, the 101 detector is fed the bits 0, 1, 1, 1, 0, one per clock edge. Which state is it in afterwards, and what is its output there?
01110
Already know this? and come back to the quiz any time.