Synchronous sequential circuit design and state machines

Why it matters

Batch controllers, interlock sequences, protocol decoders and the control unit of every microcontroller are finite state machines. Being able to turn a word description ("open the valve after three consecutive high readings") into a state diagram and then into flip-flops and gates is the core design skill of sequential logic, and the reverse skill, analysing a given circuit to find what it does, is what most exam questions test.

Key ideas

Synchronous sequential circuit. Combinational logic plus a bank of flip-flops sharing one clock. The flip-flop outputs are the present state; the logic computes the next state (from the present state and inputs) and the outputs. State changes only at clock edges, so delays inside the logic do not matter as long as everything settles within one clock period.

Mealy and Moore machines.

• Moore: outputs depend only on the present state. Outputs are stable for a whole clock period and change only after a clock edge. Usually needs more states.
• Mealy: outputs depend on the present state and the present inputs. Fewer states and the output responds in the same clock cycle, but an input glitch can appear at the output.
• A Mealy machine can be converted to an equivalent Moore machine (and vice versa); the Moore version is one clock later in its response.

Representations. A state diagram shows states as circles and transitions as arrows labelled input/output (Mealy) or with outputs written inside the states (Moore). A state table lists, for each present state and input, the next state and output.

Design procedure.

1. From the specification draw a state diagram.
2. Write the state table.
3. Reduce states: two states are equivalent if, for every input, they give the same output and go to equivalent next states; merge them.
4. Assign binary codes to states. With S states you need n = ⌈log₂S⌉ flip-flops; one-hot assignment uses S flip-flops but simpler logic. Unused codes become don't-cares, but check they lead back into the main sequence (self-starting design).
5. Choose flip-flops and use their excitation tables to find the required inputs for every transition.
6. Minimise each flip-flop input equation and output equation with K-maps, and draw the circuit.

Excitation tables (present → next).

• D: D = Q⁺.
• T: T = Q ⊕ Q⁺.
• JK: 0→0: J = 0, K = X; 0→1: J = 1, K = X; 1→0: J = X, K = 1; 1→1: J = X, K = 0. JK flip-flops give the most don't-cares and usually the simplest logic; D flip-flops give the most direct design.

Analysis procedure. For a given circuit, write the flip-flop input equations, substitute them into the characteristic equations to obtain next-state equations, build the state table and draw the diagram. Then describe the behaviour (counter, detector, etc.).

Sequence detectors. Classic design problem: output 1 when a given bit pattern arrives on a serial input. "Overlapping" detection lets the end of one pattern be the start of the next. For a pattern of length L with overlap, a Mealy machine typically needs L states and a Moore machine L + 1.

Lock-out. If unused states form a loop that never returns to the main sequence, the machine can be trapped after a power-on glitch. Design unused states to lead to a valid state or use a reset.

Formulas

n = ⌈log₂ S⌉

• n: number of flip-flops with binary encoding; S: number of states.

Q⁺ = D, Q⁺ = T ⊕ Q, Q⁺ = J·Q′ + K′·Q

• Characteristic equations used for analysis.

T_clk ≥ t_pd(FF) + t_logic(max) + t_su

• Same timing rule as for any synchronous circuit (s).

Worked examples

Example 1 (standard: design). Design a Mealy machine with input x and output z that sets z = 1 whenever the last three input bits were 1, 0, 1 (overlapping allowed).

1. States: S0 = nothing useful seen; S1 = last bit was 1; S2 = last two bits were 1, 0.
2. From S0: x = 0 → S0, z = 0; x = 1 → S1, z = 0.
3. From S1: x = 0 → S2, z = 0; x = 1 → S1, z = 0 (the new 1 can start a pattern).
4. From S2: x = 0 → S0, z = 0; x = 1 → S1, z = 1 (pattern complete; the final 1 starts the next pattern).
5. Three states need ⌈log₂3⌉ = 2 flip-flops. Assign S0 = 00, S1 = 01, S2 = 10 (11 unused, don't-care).
6. With D flip-flops (A = MSB, B = LSB): D_A = 1 only for S1 with x = 0 → D_A = Bx′ (using 11 as don't-care). D_B = x (every x = 1 goes to S1, which is 01). z = Ax.
7. Check input 1 0 1 0 1: states S1, S2, S1 (z = 1), S2, S1 (z = 1). Two detections, overlapping as required.

Answer: 3 states; D_A = Bx′, D_B = x, z = Ax

Example 2 (GATE level: analysis). A circuit has two JK flip-flops A and B on a common clock with J_A = B, K_A = B′, J_B = A′, K_B = A. Starting from AB = 00, find the sequence.

1. A⁺ = J_A·A′ + K_A′·A = B·A′ + B·A = B.
2. B⁺ = J_B·B′ + K_B′·B = A′·B′ + A′·B = A′.
3. From 00: A⁺ = 0, B⁺ = 1 → 01.
4. From 01: A⁺ = 1, B⁺ = 1 → 11.
5. From 11: A⁺ = 1, B⁺ = 0 → 10.
6. From 10: A⁺ = 0, B⁺ = 0 → 00.

Answer: 00 → 01 → 11 → 10 → 00: a 2-bit Gray-code (MOD-4) counter

Example 3 (counting resources). A controller has 10 states. How many flip-flops are needed with binary and with one-hot encoding?

1. Binary: n = ⌈log₂10⌉ = ⌈3.32⌉ = 4, leaving 16 − 10 = 6 unused codes.
2. One-hot: one flip-flop per state = 10.

Answer: 4 (binary) or 10 (one-hot)

Common mistakes

• Writing Mealy outputs inside the state circles, or Moore outputs on the arrows.
• In sequence detectors, returning to the start state after a match when overlap is allowed.
• Forgetting that unused state codes are don't-cares only if the circuit is reset reliably; otherwise check self-starting.
• Using the characteristic table where the excitation table is needed (design needs excitation).
• Counting flip-flops as log₂S without rounding up.

For GATE IN

Common questions: find the state sequence or modulus of a given circuit of D, T or JK flip-flops; the minimum number of states for a sequence detector (Mealy vs Moore, overlapping vs non-overlapping); the output after a given input sequence; state reduction; and the number of flip-flops required. Practise the analysis method of Example 2 until it takes under two minutes.

Quick check

1. In which machine does the output depend on the present input?
2. How many flip-flops are needed for 9 states (binary encoding)?
3. Minimum states of a Moore machine detecting overlapping 101?
4. For a T flip-flop, what T is needed for the transition 1 → 0?

Answers: 1. Mealy 2. 4 3. 4 4. 1