A finite-state machine (FSM) combines stored state with combinational next-state and output logic. The K-map does not simplify the entire sequential system in one step. Instead, the design process encodes states as bit patterns, writes a state table, and minimizes each next-state bit and output function separately. This separation is essential: the flip-flops hold the current state, while the K-maps describe what combinational logic should feed them.
This guide works through a four-state cyclic machine using two D flip-flops. It shows how to turn each row of the state table into one output column for the next-state bits, place those values in separate K-maps, derive the equations, and check the sequence. It then explains how the same process extends to machines with inputs, different state encodings, and synchronous design constraints.
Separate state from combinational logic
An FSM has a state register, next-state logic, and output logic. At each active clock edge, the register captures a new encoded state. Between edges, combinational logic reads the present state and any external inputs, then computes the next state and outputs. A state diagram describes the abstract transitions; a state table makes those transitions explicit; Boolean minimization simplifies the logic that implements them.
For a binary encoding with n state bits, the state register can represent 2ⁿ bit patterns. Each next-state bit is a Boolean function of the present-state bits and, for a machine with inputs, the external input bits. For a Moore machine, outputs depend on present state. For a Mealy machine, outputs may depend on both present state and current inputs. Either way, each binary output column can be minimized independently with a K-map, while considering shared terms if the implementation can reuse logic.
Do not put the next-state bits into a single map as though they were one multi-valued output. Make one Boolean function per flip-flop input. That gives an equation for each D input when using D flip-flops. If using JK or T flip-flops, first determine the required excitation inputs from the present and next states; their maps are not identical to the D-input maps.
Define a four-state machine
Consider a synchronous sequence with encoded states 00→01→10→11→00. Let the register bits be A and B, where A is the most significant bit. We use two D flip-flops, so at a clock edge the next-state values A⁺ and B⁺ are captured directly. Add a Moore output Z that is high only in state 11. This example has no external input; each present state has exactly one successor.
| Present A B | Present state label | Next A⁺ B⁺ | Z |
|---|---|---|---|
| 00 | S0 | 01 | 0 |
| 01 | S1 | 10 | 0 |
| 10 | S2 | 11 | 0 |
| 11 | S3 | 00 | 1 |
Translate the next-state column into separate truth tables. A⁺ is 0,1,1,0 for present states 00,01,10,11. B⁺ is 1,0,1,0. The output Z is 0,0,0,1. Since A and B are the only inputs to these functions, each map has four cells. If a machine has a condition input X, the maps have three variables; with two condition inputs X and Y, they have four variables.
Build one map per next-state bit
Use a two-variable map with A as the row and B as the column. For A⁺, place ones at present states 01 and 10. These two cells are not adjacent in a two-variable map: they differ in both A and B. They remain two single-cell implicants, so the SOP is A′B+AB′, which is the XOR function A⊕B. For B⁺, ones occur at 00 and 10. They share B=0 while A changes, so group them as B′.
For the output Z, only state 11 is high, so its equation is AB. The three maps can be summarized as:
| Function | On-set present states | Minimized equation |
|---|---|---|
| A⁺ | 01, 10 | A′B + AB′ = A ⊕ B |
| B⁺ | 00, 10 | B′ |
| Z | 11 | AB |
In a larger map, present-state bits label some axes and external inputs label the remaining axes. The state table tells you the output value for every combination. A transition condition that leads to a next-state bit value of 1 becomes a 1-cell in that bit’s map; a condition leading to 0 becomes a 0-cell. Keep the current-state and next-state labels visually distinct so that values do not get placed under the wrong variable assignment.
Derive D-input and output equations
For D flip-flops, the input equations are simply DA=A⁺ and DB=B⁺. Therefore DA=A⊕B and DB=B′. The Moore output equation is Z=AB. The circuit has two flip-flops and combinational gates feeding their D inputs and the output. At each rising edge, the state register updates; the equations then settle for the next edge.
One should not simplify A′B+AB′ incorrectly to A+B or A′+B. The two product terms represent the two unequal input combinations, which is exactly XOR. A truth-table check is quick: 00 gives 0, 01 gives 1, 10 gives 1, and 11 gives 0. B′ also matches the B⁺ column independent of A. The output AB is only high at state 11.
If the machine used JK flip-flops, the required J and K inputs would be derived from the transition of each state bit using the JK excitation table. For each bit, 0→0 permits J=0 and K=X; 0→1 requires J=1,K=X; 1→0 requires J=X,K=1; 1→1 permits J=X,K=0. Those X entries are excitation don't-cares, not automatically evidence that the state itself is unreachable. Map each excitation input separately and verify the resulting sequential transition table.
Verify transitions and reset
Substitute each present state into the equations. At 00, DA=0 and DB=1, so the next state is 01. At 01, the values are 1 and 0, giving 10. At 10, the values are 1 and 1, giving 11. At 11, the values are 0 and 0, returning to 00. This row-by-row check confirms that the equations reproduce the intended cycle.
Reset is a separate requirement. If reset initializes the register to 00, the reset circuitry must make that state reliably available at startup. The combinational next-state equations do not implement reset unless reset is explicitly included in the design. A synchronous reset becomes another condition in the next-state logic; an asynchronous reset uses a separate flip-flop control pin and has its own timing requirements.
Check output timing too. A Moore output derived from state bits can change after a clock edge when the state register changes, and the combinational decoder may briefly glitch if bit propagation differs. If Z controls a sensitive interface, consider registering it or using a state assignment and output structure that meet the timing needs. The K-map proves the stable output equation, not a glitch-free waveform through the transition.
Add external inputs
Suppose the machine advances only when enable E=1 and otherwise holds its state. The table gains two rows for each present state, one for E=0 and one for E=1. When E=0, A⁺=A and B⁺=B. When E=1, use the original cycle. Each next-state function is now a three-variable function of A,B,E. Fill every map cell from that expanded table before grouping.
For example, DB is B when E=0 and B′ when E=1, regardless of A. That function is B XOR E, because it is 1 when B and E differ. DA is A when E=0 and A⊕B when E=1. A direct expression is A′B E + A B′ E + A E′. A K-map may reveal a shorter equivalent form or a useful factorization. This illustrates why external control conditions must be included in the map variables rather than treated as prose after minimization.
With multiple inputs, undefined combinations deserve careful classification. A row omitted from a table might mean an input combination is impossible, a transition is unspecified, or the design document is incomplete. Only a formally justified don't-care can be used freely for minimization. If the control inputs can take the value in real operation, define the resulting next state and outputs.
State encoding choices
The binary code assigned to each symbolic state changes the shapes of the K-map patterns and therefore the equations. The sequence example uses a natural binary order. A different assignment could make one next-state bit simpler, reduce output decode logic, or improve transition behavior. One-hot encoding uses one flip-flop per state and often makes state decoding straightforward, at the cost of more registers. Gray-like assignments can make selected transitions change one bit, which can be useful in some asynchronous or low-switching contexts.
State encoding is a design choice, not a property of the abstract FSM. Before minimizing, confirm the mapping from state labels to bit patterns. A K-map built with stale state codes can produce a perfectly minimized implementation of the wrong machine. When re-encoding, update the entire table, the reset state, output decode, and any assumptions about unused codes.
For a machine with unused binary codes, those rows require an explicit policy. They may be treated as don't-cares to reduce logic only if behavior from those codes is truly outside the required behavior. If the design must recover from an upset into an unused state, assign a safe next state rather than X. The guide to FSM unused-state codes and safe don't-care use explores the tradeoff.
A design checklist
- Choose and document state encoding. Record the bit pattern for every symbolic state.
- Write the full transition table. Include every legal state and every relevant input combination.
- Make one output column per register input. For D flip-flops, these are next-state bits.
- Build a separate K-map for each function. Use present-state and external input variables as coordinates.
- Handle unspecified rows deliberately. Mark a value X only when the specification permits either behavior.
- Derive output equations separately. Distinguish Moore and Mealy dependencies.
- Verify every transition by substitution. Check reset, legal sequences, and behavior from unused codes.
- Review timing and implementation. K-map minimization does not establish setup, hold, or hazard safety.
For the four-state example, the procedure produces DA=A⊕B, DB=B′, and Z=AB, and substitution confirms the full cycle. In a real design, the hardest work is often not drawing the maps; it is deciding exactly what each state/input combination is required to do. A complete and accurate state table is the foundation for every next-state equation.
University digital-logic exercises commonly use this same workflow: derive next-state functions from a state table, fill K-maps, then implement the resulting flip-flop input logic. See the University of Utah FSM review exercise for a related instructional example.