State minimization techniques

3.4.12 · Hardware › Sequential Circuits

WHY minimize karte hain?

WHY matters karta hai: states ki number $N$ decide karti hai flip-flops ki number $⌈ lo g_{2} N ⌉$ . States kam karne se ek flip-flop drop ho sakta hai, next-state/output logic shrink ho sakta hai, power aur area bachta hai.
WHAT exploit karte hain: redundant states — woh states jo kisi doosre state ke equivalent hain.
HOW dhundhen: states ko "abhi-tak-indistinguishable" groups mein partition karo, phir tab tak refine karte raho jab tak koi group split na ho sake. Jo saath bachte hain woh actually equivalent hain.

Hum equivalence relation ko layer by layer build karte hain $k$ -distinguishability ke idea se.

Refinement rule ka derivation. Maano $P_{k}$ woh partition hai jahan do states ek block share karte hain iff woh NOT $k$ -distinguishable hain (length- $k$ inputs tak indistinguishable).

$P_{0}$ (base case): length-0 future ke baare mein kuch nahi batata, isliye hum sirf immediate output par split karte hain. States ko same block mein rakho iff woh same output produce karte hain (Moore: same state output; Mealy: har input ke liye same output row).
Inductive step ( $P_{k} \to P_{k + 1}$ ): $p, q$ $P_{k + 1}$ mein saath rahenge iff woh $P_{k}$ mein saath the AND har input $x$ ke liye, $δ (p, x)$ aur $δ (q, x)$ $P_{k}$ ke same block mein hain. (Kyunki length- $(k + 1)$ string se distinguishable hona = "abhi alag" YA "aisa state jao jo length- $k$ se distinguishable ho".)
Termination: har refinement ya toh ek block split karta hai ya partition ko unchanged chhod deta hai. Blocks ko forever refine nahi kiya ja sakta (finite states). Jab $P_{k + 1} = P_{k}$ ho, hum coarsest stable partition tak pahunch gaye hain — yahi exactly equivalence classes hain. Yeh at most $N - 1$ steps mein converge karta hai.

$P_{0} ⪰ P_{1} ⪰ \dots ⪰ P_{k} = P_{k + 1} = P_{\infty}$

Har final block = minimal machine ka ek state (yeh minimal DFA renaming tak unique hota hai — yeh Myhill–Nerode result hai).

Do practical techniques

Fast, systematic, state table ke roop mein di gayi machines ke liye acha.

2. Implication chart (pairwise) method

States ke har pair ko ek triangular chart mein list karo. Har cell mein:

Agar do states ke alag outputs hain → seedha ✗ mark karo (distinguishable).
Warna implied pairs likho: woh next-state pairs jo BHI equivalent hone chahiye.
Phir sweep karo: agar koi implied pair ✗ ho jaaye, toh is cell ko bhi ✗ mark karo. Stable hone tak repeat karo.
Ant mein unmarked cells = equivalent pairs → unhe merge karo.

Worked Example 1 — Partitioning (Moore machine)

State table (input $x \in {0, 1}$ ), output Moore state output hai:

State	N( $x = 0$ )	N( $x = 1$ )	Output
A	B	C	0
B	A	D	0
C	D	A	0
D	D	A	1

Step P0 — output se split karo. Outputs: A,B,C = 0 ; D = 1. $P_{0} = {A, B, C} {D}$ Yeh step kyun? Length-0 info = current output; D already distinguishable hai (woh akela 1 hai).

Step P1 — next states ko $P_{0}$ blocks ke against check karo. Block1 $= {A, B, C}$ , block2 $= {D}$ mano.

State	on 0	block	on 1	block
A	B	1	C	1
B	A	1	D	2
C	D	2	A	1

Yeh step kyun? Do states same output share kar sakte hain lekin alag blocks mein "leak" ho sakte hain — woh length-2 distinguisher hai. A→(1,1), B→(1,2), C→(2,1): teeno signatures alag hain. $P_{1} = {A} {B} {C} {D}$

Step P2: partition aur refine nahi ho sakta (sab singletons hain). Ruko. Conclusion: koi states merge nahi hote — yeh machine already minimal hai.

Worked Example 2 — states DO merge karte hain

State	N(0)	N(1)	Output
A	B	C	0
B	B	D	0
C	B	C	0
D	B	D	1

P0 (output se): ${A, B, C} {D}$ . Kyun? D akela output-1 state hai.

P1: blocks: 1 $= {A, B, C}$ , 2 $= {D}$ .

State	on 0 → block	on 1 → block	signature
A	B → 1	C → 1	(1,1)
B	B → 1	D → 2	(1,2)
C	B → 1	C → 1	(1,1)

A aur C ki same signature (1,1) hai; B alag hai. $P_{1} = {A, C} {B} {D}$

P2: naye blocks ke saath re-check karo: $α = {A, C}$ , $β = {B}$ , $γ = {D}$ .

State	on 0	on 1	signature
A	B(β)	C(α)	(β,α)
C	B(β)	C(α)	(β,α)

Same signature → A aur C merged rahenge. Partition stable hai. $P_{\infty} = {A, C} {B} {D}$

Minimized table ( ${A, C} \to S$ rename karo):

State	N(0)	N(1)	Out
S	B	S	0
B	B	D	0
D	B	D	1

Yeh step kyun? 4 states → 3 states. Yahan abhi bhi 2 flip-flops chahiye, lekin logic simplify ho jaata hai aur bade machines mein aksar ek flip-flop drop ho jaata hai. Merge karne se pehle verify karo Forecast se: predict karo "input = 1,1" ka output A se (A→C, out 0; C→C, out 0) vs C se (C→C, out 0; C→C, out 0) — identical, ✓.

Common mistakes (Steel-man + fix)

Active recall

Recall Feynman: ek 12-saal ke bachche ko explain karo

Socho bahut saare toy robots hain. Do robots "same" hain agar chahe tum kaun se bhi buttons dabao, woh same beeps bajaate hain aur same tarah kaam karte hain. Agar tumhe aisa koi "twin" mile, toh ek phenko — tumhe sirf ek chahiye. Twins dhundhne ke liye: pehle un robots ko group karo jo abhi same beep karte hain. Phir dekho har robot kahan jaata hai; agar do "same-beep" robots alag groups mein jaate hain, woh real twins nahi hain — unhe split karo. Tab tak split karte raho jab tak kuch na badle. Jo groups bachte hain woh sache twins hain. Kam robots = sasta toy!

Do states equivalent kab hote hain?

Jab har input sequence ke liye woh identical output sequences dete hain; equivalently same current output AND har input ke liye next states equivalent hoon.

Successive refinement mein base partition P0 kya hai?

States ko sirf unke output ke basis par group karo (Moore: state output; Mealy: sabhi inputs par full output row).

Refinement rule P_k → P_{k+1} batao.

p,q ko saath rakho iff woh P_k mein already saath hain AND har input ke liye unke next states P_k ke same block mein aate hain.

Partition refinement kab rukti hai?

Jab ek full pass mein koi change na ho, yaani P_{k+1}=P_k (coarsest stable partition); ≤ N−1 steps.

k-distinguishable states kya hote hain?

Woh states jo length ≤ k ki kisi input string se alag outputs deke separate ho sakein.

Implication chart mein ek cell mark ✗ ka kya matlab hai?

Do states distinguishable hain (alag outputs, ya ek implied pair distinguishable ho gayi).

Implication chart mein final unmarked cell ka kya matlab hai?

Do states equivalent hain → unhe merge karo.

States merge karna hardware mein kyun help karta hai?

Fewer states → fewer flip-flops (⌈log2 N⌉) aur simpler next-state/output logic → kam area/power.

"Same output" wali common mistake kya hai?

Same output akele (P0) equivalence nahi hai; equivalent next states tak pahunchna bhi zaroori hai.

Kya minimized machine unique hoti hai?

Haan, state renaming tak unique hoti hai (Myhill–Nerode).

Connections

Finite State Machines — woh object jise hum minimize karte hain.
Mealy vs Moore Machines — affect karta hai ki $P_{0}$ kaise define hoti hai.
State Assignment (Encoding) — minimization ke baad hota hai; flip-flop bits set karta hai.
Flip-Flops — state count → count $⌈ lo g_{2} N ⌉$ .
Myhill–Nerode Theorem — unique minimal DFA ka theoretical basis.
Karnaugh Maps — combinational simplification analog (dono redundancy remove karte hain).