What a finite state machine is
Every sequential circuit built so far stores a value, but a finite state machine (FSM) goes a step further: it stores one of a fixed, finite set of named states, and its next state is a function of the current state and the current input – not of the input alone. This is what makes an FSM the natural model for anything that has to remember "where it is" in a sequence of events: a traffic-light controller, a vending-machine, a UART receiver watching for a start bit, or the sequence detector worked through in this lesson. An FSM is described compactly by a state diagram (a circle per state, an arrow per transition, each arrow labelled with the input that causes it) or, equivalently, by a state table that lists the same information as rows.
Moore versus Mealy machines
There are two standard ways to attach an output to an FSM, and the difference between them is where the output comes from. In a Moore machine, the output depends only on the current state – each state has one fixed output value, which is why a Moore machine's outputs are often drawn written inside the state circle itself. In a Mealy machine, the output depends on both the current state and the current input, so the output is associated with a transition (an arrow) rather than with a state. The practical consequence is timing: a Mealy output can react within the same clock cycle that causes the transition, one cycle earlier than the equivalent Moore output, which only appears once the machine has actually settled into the new state on the next clock edge. The cost is that a Mealy output can glitch if the input is not already clean and synchronous, since it is a combinational function of a still-changing input; a Moore output cannot glitch this way, because it only depends on state that already settled on the last clock edge.
Worked example: detecting the sequence 1011
Let us design a Moore machine that watches a serial bit stream and outputs 1 for one clock cycle whenever the most recently received four bits were 1, 0, 1, 1 – allowing overlapping matches, so the stream 101011 is correctly detected as containing the pattern starting at position 0 and should also be checked for a second match starting at position 2. The standard technique is to name each state after the longest suffix of the bits seen so far that is also a prefix of the target pattern 1011, since that suffix is exactly the information the machine needs to carry forward.
| State | Meaning | Input 0 | Input 1 | Output |
|---|---|---|---|---|
| S0 | no match yet | S0 | S1 | 0 |
| S1 | matched "1" | S2 | S1 | 0 |
| S2 | matched "10" | S0 | S3 | 0 |
| S3 | matched "101" | S2 | S4 | 0 |
| S4 | matched "1011" | S2 | S1 | 1 |
Two rows reward a closer look, because they are exactly where overlap detection usually goes wrong if the machine is reset to S0 on every match instead of re-synchronizing. From S4, an incoming 0 leaves the running suffix "10" (from "…1011" + "0" = "…10110", whose longest matching prefix is "10"), landing on S2, not S0; an incoming 1 leaves the suffix "1" (from "…1011" + "1" = "…10111"), landing on S1, not S0. Re-synchronizing this way is what lets the detector catch the second, overlapping match in a stream like 101011 instead of discarding the final 1 of one match as if it could not also begin the next one.
Building a Mealy version of the same detector removes state S4 entirely: the transition out of S3 on input 1 is relabelled "1 / output 1" and goes directly to S1 (the state S4 would have moved to on a following 1) or to S2 (on a following 0) – but since a Mealy machine cannot look ahead at the next input to decide which, the honest Mealy equivalent still needs a state to represent "just matched," so in practice the two styles end up with a similar state count for this particular pattern. The timing gain shows up in the output: the Mealy machine's output pin goes high during the same cycle the fourth bit (the final 1) arrives, one cycle earlier than the Moore machine's output, which only goes high on the next clock edge after the FSM has moved into S4.
From state diagram to hardware
Implementing either style follows the same recipe already used for the combinational blocks in this path. Encode each state as a bit pattern (three bits are enough for five states, with two patterns left unused), store the current encoding in a bank of flip-flops, and build two pieces of combinational logic around those flip-flops: a next-state function (state register bits and input bits in, next encoding out) and an output function (state register bits in, for Moore; state and input bits in, for Mealy). The state table above is nothing more than the truth table for both of those functions once the states are encoded as bits, which means every technique from the earlier lessons – K-maps, don't-cares for the unused encodings – applies directly to deriving the next-state and output logic.
Key takeaways
- An FSM's next state depends on both the current state and the current input; a state diagram or state table records this compactly.
- A Moore machine's output depends only on the current state; a Mealy machine's output depends on the current state and input, letting it react one cycle earlier at the cost of being glitch-sensitive to a still-changing input.
- Naming each state after the longest matched prefix of the target pattern is the standard technique for building a sequence detector.
- Correct overlap detection depends on where the accepting state's outgoing transitions land – re-synchronize to the right partial-match state, not back to the start state.
- Once states are bit-encoded in a register, the next-state and output logic are ordinary combinational functions, designable with the same K-map techniques as any other truth table.