State diagram and state table design — Hinglish notes

3.4.11 · Hardware › Sequential Circuits

WHY — humein states ki zaroorat kyun hai?

WHY yeh matter karta hai: Ek combinational circuit ka output sirf current inputs pe depend karta hai. Ek sequential circuit ka output current inputs plus history pe depend karta hai. Hum "history" ko finite labels (states) ke ek set mein encode karte hain, taaki circuit ko sirf woh state store karni pade jisme woh hai, na ki poora input stream.

Mealy vs Moore — WHAT hai difference?

HOW design karein: recipe

Yeh note steps 1–5 pe focus karta hai ("behaviour capture" wala half). Steps 6+ (K-maps, flip-flop excitation) baad mein aate hain.

Figure — State diagram and state table design

Worked Example 1 — "1011" sequence detector (Mealy, overlapping)

Spec: Output $Z = 1$ ek cycle ke liye jab bhi input serial bit stream $X$ pattern 1011 pe khatam ho. Overlapping allowed hai (ek match ke last bits next ka start kar sakte hain).

Step 1 — WHAT yaad rakhna hai?

Hum sirf yeh care karte hain ki target prefix abhi tak kitna dekha gaya hai. States define karo abhi tak matched longest prefix se:

$S_{0}$ = kuch nahi match hua (ya ek useless prefix)
$S_{1}$ = 1 match hua
$S_{2}$ = 10 match hua
$S_{3}$ = 101 match hua

Yeh step kyun? Yeh char prefixes hi past ke woh akele facts hain jo decide karte hain ki future bit ka kya matlab hai. Koi bhi lambi history irrelevant hai → finite states.

Step 2 — transitions banao (Forecast-then-Verify)

$S_{3}$ par (101 dekha gaya), agar next bit 1 hai → 1011 complete → output $Z = 1$ . Forecast: match ke baad hum kahan jaate hain? Kyunki overlap allowed hai, 1011 ki trailing 1 khud ek fresh 1 prefix hai → $S_{0}$ nahi, $S_{1}$ jao. Verify: input 10111011 — check karo ki do matches detect ho rahe hain. Hote hain. ✅

Har transition ka reason. Input bit $X$ par:

Present	X=0 → Next / Z	X=1 → Next / Z	Kyun?
$S_{0}$	$S_{0}$ / 0	$S_{1}$ / 0	ek `1` ek possible match start karta hai
$S_{1}$ (`1`)	$S_{2}$ / 0	$S_{1}$ / 0	`10` progress karta hai; `11` phir bhi ek `1` pe end karta hai
$S_{2}$ (`10`)	$S_{0}$ / 0	$S_{3}$ / 0	`100` dead → $S_{0}$ ; `101` progress karta hai
$S_{3}$ (`101`)	$S_{2}$ / 0	$S_{1}$ / 1	`1010` → `10` pe end, $S_{2}$ ; `1011` = MATCH, overlap se `1` bachta hai

Step 3 — state assignment

$S_{0} = 00, S_{1} = 01, S_{2} = 10, S_{3} = 11$ lo. Ab har "Next" entry ek 2-bit number ban jaati hai, flip-flop equations ke liye ready.

Worked Example 2 — Same detector ka Moore version

Moore mein, output ek state ka hissa hota hai, toh humein ek extra "accept" state $S_{4}$ chahiye jo 1 output kare.

Present	Output	X=0 → Next	X=1 → Next	Kyun?
$S_{0}$	0	$S_{0}$	$S_{1}$
$S_{1}$	0	$S_{2}$	$S_{1}$
$S_{2}$	0	$S_{0}$	$S_{3}$
$S_{3}$	0	$S_{2}$	$S_{4}$	`1` par hum match state pahunchte hain
$S_{4}$	1	$S_{2}$	$S_{1}$	future input ke liye $S_{1}$ jaise behave karta hai (ek `1` hold karta hai), lekin 1 output karta hai

Common mistakes

Active recall

Recall Ek line mein "state" kya hota hai?

Ek finite label jo exactly woh part summarize karta hai past input ka, jo future outputs aur transitions decide karne ke liye chahiye.

Recall Mealy machines aksar Moore se fewer states kyun use karti hain?

Kyunki Mealy output transitions se attach karta hai, toh use sirf output dikhane ke liye alag state ki zaroorat nahi padti.

Recall

1011 overlap se detect karne ke baad, $S_{1}$ kyun, $S_{0}$ kyun nahi? Trailing 1 ek nayi 1011 ka valid prefix hai; $S_{0}$ par jaane se woh discard ho jaata aur overlapping matches miss ho jaate.

Recall (Feynman) State design ek 12-saal ke bachche ko explain karo.

Soch ek lock hai jo sirf tab khulta hai jab tum 1, 0, 1, 1 order mein press karo. Lock har button jo tune kabhi dabaya yaad nahi rakh sakta — yeh bahut zyada hai. Iski jagah woh ek choti sticky note rakhta hai jisme likha hota hai "secret code mein main kitna aage hoon?" Har note ("abhi kuch nahi", "1 mila", "1-0 mila", "1-0-1 mila") ek state hai. Jab button dabaya jata hai, lock sticky note update karta hai aur, agar code abhi complete hua, toh khul jaata hai. State diagram bas un saari sticky notes ka ek map hai jisme arrows dikhate hain ki kaunsa button kahan le jaata hai.

Connections

Finite State Machines — in diagrams ke peeche ka abstract model
Flip-Flops and Latches — woh physical memory jo state bits store karti hai
State Assignment and Reduction — codes chunna aur equivalent states merge karna
Excitation Tables and Next-State Equations — recipe ke steps 6+
Sequence Detectors — canonical application
Combinational Circuits — contrast: koi memory nahi, koi states nahi

Sequential circuit mein past ko kya summarize karta hai?

Ek state — history ki minimal memory jo future output aur next state decide karne ke liye chahiye.

Moore machine mein output kis par depend karta hai?

Sirf present state par (state bubble ke andar likha hota hai).

Mealy machine mein output kis par depend karta hai?

Present state AUR current input par (transition arrow par input/output ki tarah likha hota hai).

Mealy state diagram mein output kahan likha hota hai?

Transition arrow par, X/Z ki tarah.

Moore state diagram mein output kahan likha hota hai?

State bubble ke andar.

Overlap ke saath '1011' sequence detector mein match ke baad '1' state par kyun wapas jaate hain?

Trailing 1 agali 1011 ka valid prefix hai, toh overlap ke liye uski zaroorat hai (start par jaane se matches miss ho jaate).

State-machine design ke 6 steps list karo.

1) Spec samjho 2) States identify karo 3) State diagram draw karo 4) State table banao 5) State assignment (binary codes) 6) Next-state/output equations derive karo aur flip-flops chuno.

Moore aksar Mealy se ≥ states kyun use karta hai?

Moore ko sirf har output value dikhane ke liye extra states chahiye, kyunki output transitions pe nahi, states se tied hai.

State table 'complete' kab hoti hai?

Jab har (present-state, input) combination ka ek defined next-state (aur output) entry ho.

'1011' Mealy detector ke liye kitni states chahiye?

4 (matched: kuch nahi, 1, 10, 101).