Related Concepts: 5.01 Sequential Logic Fundamentals, Latches & Flip-Flops (SR & JK) | 5.04 Synchronous Sequential Circuit Analysis & Synthesis | 5.03 Flip-Flop Conversions & Functional Transformation Mechanics

5.05 State Reduction Algorithms & Output Sequence Analysis

Six appearances — 2016, 2018, 2022, 2023, 2024, 2025

Worth 10 to 15 marks, and the same 7-state table is used every time. But read the verb carefully — the question changed in 2022:

• 2016, 2018: “Reduce the number of states… and tabulate the reduced state table.” → reduction only
• 2022, 2023, 2025: “Design a sequential circuit that represents the reduced form of the following state table.” → reduction is only step 1 of 5; you must go on to state assignment, excitation table, K-maps and the circuit
• 2024: “…minimum number of states. For an input sequence 01110010011, compare the output sequences with the given table and the resultant table.” → reduction plus output tracking on both tables

Stopping at the reduced table when the paper says “design” is the single biggest mark-loser in this topic.

Overview In sequential circuit design, initial state diagrams derived from verbal specifications often contain redundant states. State Reduction is a systematic optimization algorithm that eliminates equivalent states without altering the input-output behavior. Reducing the total number of states decreases the required number of flip-flops (N = ⌈log₂ M⌉), significantly reducing hardware complexity and cost.

1. Concept of State Equivalence

Exam Problem (PYQ 2015, 2016, 2018 — 05 marks)

Question (verbatim): Write down the state reduction algorithm.

A short 5-mark bookwork question — give the definition of equivalence below plus the five algorithm steps in §2, and note that the process iterates until a full pass finds no new pairs.

Definition of Equivalent States Two states Si and Sj in a sequential circuit are defined as equivalent (Si ≡ Sj) if and only if for every possible input sequence applied to the circuit:

1. They produce identical output sequences.
2. They transition to identical or equivalent next states.

2. The Row-Elimination State Reduction Algorithm

• Step 1: Inspect State Table for rows with identical Next States and Outputs • Step 2: Identify Equivalent Pair (Si = Sj) • Step 3: Remove Row Sj from State Table • Step 4: Replace all occurrences of Sj with Si throughout the table • Step 5: Final Reduced State Table Complete

3. Master Worked Example: 7-State Table Reduction

3.1 Unreduced Initial State Table

Present State	Next State (x=0)	Next State (x=1)	Output (x=0)	Output (x=1)
a	a	b	0	0
b	c	d	0	0
c	a	d	0	0
d	e	f	0	1
e	a	f	0	1
f	g	f	0	1
g	a	f	0	1

3.2 Step-by-Step Reduction Execution

Reduction is iterative — one pass is never enough

Eliminating a row changes the next-state entries of other rows, which can create new equivalent pairs that did not exist before. You must re-scan the table after every substitution and keep going until a full pass finds nothing. This example needs two passes.

Pass 1 — states e and g

	NS(x=0)	NS(x=1)	Out(x=0)	Out(x=1)
e	a	f	0	1
g	a	f	0	1

All four entries match $⟹\mathbf{e}\equiv \mathbf{g}$. Delete row g and replace every g elsewhere with e.

The only other occurrence of g is in row f, whose $NS(x=0)$ was g. The table now reads:

PS	NS(x=0)	NS(x=1)	Out(x=0)	Out(x=1)
a	a	b	0	0
b	c	d	0	0
c	a	d	0	0
d	e	f	0	1
e	a	f	0	1
f	e	f	0	1

Pass 2 — states d and f (this pair only became equivalent because of Pass 1)

	NS(x=0)	NS(x=1)	Out(x=0)	Out(x=1)
d	e	f	0	1
f	e	f	0	1

All four match $⟹\mathbf{d}\equiv \mathbf{f}$. Delete row f and replace every f with d.

Pass 3 — no further pairs. Checking the survivors: $b$ vs $c$ differ in $NS(x=0)$ ($c$ vs $a$), and $a\not\equiv c$ because $a$‘s $NS(x=1)=b$ outputs $0$ while $c$‘s $NS(x=1)=d$ outputs $1$. Similarly $d\not\equiv e$. The table is minimal.

3.3 Final Reduced State Table

Present State	Next State (x=0)	Next State (x=1)	Output (x=0)	Output (x=1)
a	a	b	0	0
b	c	d	0	0
c	a	d	0	0
d	e	d	0	1
e	a	d	0	1

Hardware Optimization Result

Seven states became five: $\lceil {\log }_{2}7\rceil =3$ flip-flops before, $\lceil {\log }_{2}5\rceil =3$ flip-flops after.

Be honest about the saving — the examiner may probe it

The flip-flop count does not change here. Both 7 and 5 states need 3 flip-flops. What reduction does buy is simpler combinational logic: fewer used states means more unused states, which become don’t cares in the excitation K-maps, producing a smaller gate network. Claiming a flip-flop saving that did not occur is worse than stating the real benefit.

Reduction only cuts flip-flops when it crosses a power-of-two boundary — e.g. 5 states down to 4 would save one.

4. Output Sequence Tracking Analysis

Worked Exam Problem (PYQ 2016 — 15 marks; 2024 — 13 marks)

Question (verbatim, 2016): Reduce the number of states in the following state table and tabulate the reduced state table. Starting from state a of the reduced state table, find the output sequence generated with an input sequence of 01110010011.

(2024 goes further: “compare the output sequences with the given table and the resultant table” — you must trace the sequence through both the original and reduced tables and show they match. That equivalence is the whole point of reduction.)

Trace step by step through the reduced table, starting at a:

Step	Input $x$	Present state	Next state	Output $y$
1	0	a	a	0
2	1	a	b	0
3	1	b	d	0
4	1	d	d	1
5	0	d	e	0
6	0	e	a	0
7	1	a	b	0
8	0	b	c	0
9	0	c	a	0
10	1	a	b	0
11	1	b	d	0

Input: 0 1 1 1 0 0 1 0 0 1 1 States: a a b d d e a b c a b → d Output: 0 0 0 1 0 0 0 0 0 0 0

Reading the output at the right moment

This is a Mealy machine — the output depends on the present state and the current input, so the output for each step is read before the transition, from the row of the present state. Reading it from the next state instead shifts the whole answer by one position, which is the standard way this question goes wrong.

For the 2024 version, repeat the trace on the original 7-state table; you will get the identical output string, which is the proof that the reduction preserved behaviour.

---

4A. Completing the “Design” — Steps 2 to 5

Required by the 2022, 2023 and 2025 wording

Those papers say “Design a sequential circuit that represents the reduced form of the following state table” (13, 12 and 10 marks). The reduced table is only the first of five steps.

Step 2 — State assignment. Assign binary codes to the five surviving states using three flip-flops:

State	$ABC$
a	000
b	001
c	010
d	011
e	100

The three unused codes (101, 110, 111) become don’t cares in every K-map — this is where the real hardware saving comes from.

Step 3 — Excitation table. Expand the reduced state table into binary, then add the flip-flop input columns using the excitation table of your chosen device (see 5.01 Sequential Logic Fundamentals, Latches & Flip-Flops (SR & JK) for the JK and T excitation tables). For JK flip-flops each state bit needs a $J$ and a $K$ column, so a 3-flip-flop design yields six input columns plus the output.

Step 4 — K-maps. Plot one map per flip-flop input over the variables $A,B,C,x$, marking the three unused state codes as don’t cares. Minimise each.

Step 5 — Draw the circuit. Three flip-flops, the minimised input logic, and the output gate.

Marks allocation on the "design" version

Roughly: reduction 4 marks, state assignment 1, excitation table 3, K-maps 3, circuit 2. The reduction alone is under a third of the marks — which is why stopping there is so costly. If time is short, do the reduction, state the assignment, and lay out the excitation table; those three steps bank most of the credit.

5. State Assignment Rules & Methods

Assignment Method	Description	Code for 4 States (S₀…S₃)	Advantage
Binary Assignment	Standard sequential binary numbers.	00, 01, 10, 11	Minimum number of flip-flops used.
Gray Code Assignment	Adjacent states differ in only 1 bit position.	00, 01, 11, 10	Reduces switching noise and glitches.
One-Hot Assignment	Dedicated flip-flop for each state.	0001, 0010, 0100, 1000	Simplifies combinational logic (no decoders).

---

6. Past Year Questions (PYQs)

PYQ Index for this note

Question (as asked)	Years	Marks	Solved in
Write down the state reduction algorithm	2015, 2016, 2018	5	§1, §2
Reduce the number of states in the following state table and tabulate the reduced state table	2018	10	§3
Reduce the states, then from state a find the output sequence for input 01110010011	2016	15	§3, §4
Design a sequential circuit that represents the reduced form of the following state table	2022 (13), 2023 (12), 2025 (10)	10–13	§3, §4A
Design a sequential circuit with the minimum number of states; for input 01110010011 compare the output sequences of the given and resultant tables	2024	13	§3, §4, §4A

Pattern to notice: six appearances in ten years, always the same 7-state table and — when an input sequence is given — always the same string 01110010011. This is among the most predictable questions in the paper.

The wording shift is what matters: up to 2018 the question stopped at the reduced table; from 2022 it says “design a sequential circuit”, which triples the work. Check the verb before you start and budget time for state assignment, excitation table, K-maps and schematic.

---

7. Related Notes

• 5.04 Synchronous Sequential Circuit Analysis & Synthesis — the design procedure (steps 2–5) in full
• 5.01 Sequential Logic Fundamentals, Latches & Flip-Flops (SR & JK) — excitation tables needed for step 3
• 5.06 Chapter 5 Master PYQ Solutions & Synthesis Puzzles — further worked sequential problems