Synthesize a finite-state controller

Prerequisites: Truth tables and clocked registers.

Learning objectives

• Construct a transition table from a sequence requirement.
• Distinguish Moore and Mealy output timing.
• Explain reset, invalid-state, and verification obligations.

State records the relevant past

A finite-state machine retains only the history needed to determine future behavior. To detect the serial bit pattern 101 with overlapping matches, keep track of the longest suffix of the bits already seen that is also a prefix of 101. Three states suffice before emitting a Mealy output: S0 means no useful suffix, S1 means the suffix is 1, and S2 means the suffix is 10.

A Mealy output depends on current state and current input. Here match becomes one when the current state is S2 and the input is 1. The transition after a match is S1 because that final 1 can begin another match. Resetting unconditionally to S0 would lose overlapping patterns such as 10101.

Current state	Input 0: next, match	Input 1: next, match
S0	S0, 0	S1, 0
S1	S2, 0	S1, 0
S2	S0, 0	S1, 1

Trace the input 10101 starting from S0. The states after each bit are S1, S2, S1, S2, S1. The output sequence is 0, 0, 1, 0, 1. The trace tests overlap directly rather than relying on a single isolated match.

Choose an encoding and derive logic

Assign S0=00, S1=01, and S2=10. The state register then needs two bits. For every combination of current state bits and input, the transition table supplies the next-state bits and output. Each next-state bit is a Boolean function that can be minimized and implemented with combinational logic feeding the register.

Encoding 11 remains unused by the intended transition graph. Decide its behavior explicitly, such as recovering to S0 with match=0, then include that decision in the logic and tests. Reset determines the initial state; power-up assumptions are not a substitute for a reset specification.

Outputs have timing semantics

A Moore output depends only on registered state. A Moore detector can add a distinct matched state and usually reports the event with a different cycle convention. Neither style is universally better. A Mealy combinational output may react within the cycle or glitch as inputs change, so a downstream interface may require registering it.

Verification should check all table entries, not just attractive examples. Useful properties include no match before three relevant bits, a match exactly when the observed suffix is 101, and correct recovery from the chosen invalid-state policy. State count is a design choice based on behavior and encoding costs, not a fixed template for every controller.

Primary reading

• Finite State Machines (MIT OpenCourseWare, Computation Structures).

Practice problem

Trace the detector on 1101010 and list the one-based input positions where matches occur. Explain what would go wrong if S2 on input 1 transitioned to S0. Then propose a test for the unused encoding 11 that checks the stated recovery policy.

Worked solution

Starting at S0, the states after the seven inputs are S1, S1, S2, S1, S2, S1, and S2. Matches occur at positions four and six, corresponding to the substrings at positions two through four and four through six. Returning to S0 after the first match would discard the final 1 that also begins the next candidate, so the match at position six would be lost. To test invalid-state recovery, initialize the state register to encoding 11 in a simulation and try both input values. Under the specified recovery policy, the next state must be 00 and match must be zero for each case. The following cycle should then behave exactly like an ordinary S0 transition.

Check your understanding

Why does S2 on input 1 return to S1?

• The last 1 is also the start of a possible next match.
• Every Mealy machine must return to state one.
• The machine has forgotten all input bits.
• The state register cannot hold zero.

Explanation

Retaining the useful suffix enables overlapping matches.

Which specification is necessary when a two-bit encoding uses only three states?

• The text color used to draw the states.
• A policy for the fourth encoding and reset behavior.
• A requirement to double the input width.
• A rule that the fourth encoding is physically impossible.

Explanation

Unused bit patterns can arise through reset mistakes or faults and need a deliberate behavior.

Primary reading

• Finite State Machines: MIT OpenCourseWare, Computation Structures

Open the study and save your work →